intersect.c
上传用户:hhyinxing
上传日期:2013-09-10
资源大小:833k
文件大小:5k
源码类别:

并行计算

开发平台:

Unix_Linux

  1. #include <stdio.h>
  2. #include <mpi.h>
  3. //进程号和处理器数目
  4. int my_rank,group_size;
  5. //第一个多边形的端点
  6. double pointx1[20],pointy1[20];
  7. //第二个多边形的端点
  8. double pointx2[20],pointy2[20];
  9. //多边行的边数
  10. int n_poly,m_poly;
  11. //判断的结果
  12. int result,localresult;
  13. /*
  14.  *函数名:if_not_parallel
  15.  *功能:两条直线不垂直的情况下,判断是否相交
  16.  *输入:(x1,y1),(x2,y2)是线段一的两个端点的坐标
  17.  *     (x3,y3),(x4,y4)是线段二的两个端点的坐标
  18.  *输出:返回整型值判断两条线段是否相交
  19.  */
  20. int if_intersect_np(double x1,double y1,double x2,double y2, double x3,double y3,double x4,double y4)
  21. {
  22. double x;
  23. x=((x1*y2-x2*y1)/(x2-x1)+(x4*y3-x3*y4)/(x4-x3))/((y2-y1)/(x2-x1)-(y4-y3)/(x4-x3));
  24. if(((x1-x)*(x-x2)>=0)&&((x3-x)*(x-x4)>=0))
  25. return 1;
  26. else
  27. return 0;
  28. }
  29. /*
  30.  *函数名:if_intersect_1v
  31.  *功能:线段一是垂直的,判断线段二与一是否相交
  32.  *输入:(x1,y1),(x2,y2)是线段一的两个端点的坐标
  33.  *     (x3,y3),(x4,y4)是线段二的两个端点的坐标
  34.  *输出:返回整型值判断两条线段是否相交
  35.  */
  36. int if_intersect_1v(double x1,double y1,double x2,double y2, double x3,double y3,double x4,double y4)
  37. {
  38. double y;
  39. if(x3==x4)
  40. {
  41. //两线段平行,不在一条直线上
  42. if(x3!=x1)
  43. return 0;
  44. else if((y4<y1)||(y2<y3))
  45. return 0;
  46. else
  47. return 1;
  48. }
  49. //线段一垂直,线段二不垂直
  50. else
  51. {
  52. //线段一所在直线与线段二所在直线的交点纵坐标
  53. y = (y4 - y3)/(x4 - x3)*(x1 - x4)+ y4;
  54. if((y>=y1)&&(y<=y2)&&(y<=y4)&&(y>=y3)&&((x4-x1)*(x3-x1)<=0))
  55. return 1;
  56. else
  57. return 0;
  58. }
  59. }
  60. /*
  61.  *函数名:if_intersect
  62.  *功能:判断线段一(x1,y1),(x2,y2)与线段二(x3,y3),(x4,y4)是否相交
  63.  *输入:(x1,y1),(x2,y2)是线段一的两个端点的坐标
  64.  *     (x3,y3),(x4,y4)是线段二的两个端点的坐标
  65.  *输出:返回整型值判断两条线段是否相交
  66.  */
  67. int if_intersect(double x1,double y1,double x2,double y2, double x3,double y3,double x4,double y4)
  68. {
  69. double temp;
  70. int result;
  71. //将坐标大的换到第二个点
  72. if(y1>y2)
  73. {
  74. temp = x1;
  75. x1 = x2;
  76. x2 = temp;
  77. temp = y1;
  78. y1 = y2;
  79. y2 = temp;
  80. }
  81. if(y3>y4)
  82. {
  83. temp = x3;
  84. x3 = x4;
  85. x4 = temp;
  86. temp = y3;
  87. y3 = y4;
  88. y4 = temp;
  89. }
  90. //线段一为垂直线段
  91. if(x1==x2)
  92. {
  93. result=if_intersect_1v(x1,y1,x2,y2,x3,y3,x4,y4);
  94. }
  95. else
  96. {
  97. /*线段一不垂直,线段二垂直*/
  98. if(x3==x4)
  99. //交换线段一线段二位置,递归调用本函数判断两线段是否相交
  100. result= if_intersect(x3,y3,x4,y4,x1,y1,x2,y2);
  101. //线段一线段二皆不垂直
  102. else
  103. {
  104. //若两线段中存在平行于x轴的
  105. if((y1==y2)||(y3==y4))
  106. //交换线段一线段二中x,y位置,递归调用本函数判断两线段是否相交
  107. result= if_intersect(y1,x1,y2,x2,y3,x3,y4,x4);
  108. //线段一线段二平行
  109. else if((y4-y3)*(x2-x1)==(x4-x3)*(y2-y1))
  110. {
  111. //两线段所在直线在y轴上的截距相同,则两线段在同一直线上
  112. if((x4*y3-x3*y4)*(x2-x1)==(x2*y1-x1*y2)*(x4-x3))
  113. {
  114. //两线段在一条直线上,但不相交
  115. if((y4<y1)||(y2<y3))
  116. result = 0;
  117. //两线段在一条直线上,且相交
  118. else
  119. result = 1;
  120. }
  121. //两线段不在同一直线上
  122. else
  123. result = 0;
  124. }
  125. //两线段不平行
  126. else
  127. {
  128. result=if_intersect_np(x1,y1,x2,y2,x3,y3,x4,y4);
  129. }
  130. }
  131. }
  132. return result;
  133. }
  134. /*
  135.  *函数名:Broadcast
  136.  *功能:将两个多边形的数据传到个处理器
  137.  *输入:无
  138.  *输出:无
  139.  */
  140. void Broadcast()
  141. {
  142. MPI_Barrier(MPI_COMM_WORLD);
  143. MPI_Bcast(&n_poly,1,MPI_INT,0,MPI_COMM_WORLD);
  144. MPI_Bcast(&m_poly,1,MPI_INT,0,MPI_COMM_WORLD);
  145. MPI_Bcast(pointx1,n_poly,MPI_DOUBLE,0,MPI_COMM_WORLD);
  146. MPI_Bcast(pointy1,n_poly,MPI_DOUBLE,0,MPI_COMM_WORLD); 
  147. MPI_Bcast(pointx2,m_poly,MPI_DOUBLE,0,MPI_COMM_WORLD);
  148. MPI_Bcast(pointy2,m_poly,MPI_DOUBLE,0,MPI_COMM_WORLD);
  149. MPI_Barrier(MPI_COMM_WORLD);
  150. }
  151. /*
  152.  *函数名:Judge()
  153.  *功能:判断两个多边形是否相交
  154.  *输入:无
  155.  *输出:无
  156.  */
  157. void Judge()
  158. {
  159. int i,j,k;
  160. /*对第二个多边形的每条边,若还未发现两多
  161. 边形相交, 就判断是否与第一个多边形
  162. 的边集相交, 对应于算法17.4步骤(3)
  163. */
  164. result = 0;
  165. localresult = 0;
  166. for(i=0;(i<m_poly)&&(result==0);i++)
  167. {
  168. /*对处理器分配判断的第一个多边形的
  169. 边集*/
  170. for(j=0;j<n_poly/group_size+1;j++)
  171. {
  172. /*累加第二个多边形当前边与第一
  173. 个多边形边集相交的判断结
  174. 果*/
  175. if(j*group_size+my_rank<n_poly)
  176. {
  177. k=j*group_size+my_rank;
  178. localresult+=if_intersect(pointx1[k],pointy1[k],pointx1[(k+1)%n_poly],pointy1[(k+1)%n_poly],pointx2[i],pointy2[i],pointx2[(i+1)%m_poly],pointy2[(i+1)%m_poly]);
  179. }
  180. }
  181. /*统计第二个多边形与第一个多边形是
  182. 否相交, 对应于算法17.4步骤(4)*/
  183. MPI_Scan(&localresult,&result,1,MPI_INT,MPI_SUM,MPI_COMM_WORLD);
  184. }
  185. }
  186. /*
  187.  *函数名:GetData
  188.  *功能:取得多边形的各种数据
  189.  *输入:无
  190.  *输出:无
  191.  */
  192. void GetData()
  193. {
  194. int i;
  195. //0号处理器
  196. if(my_rank==0)
  197. {
  198. //输入多边形相关数据
  199. printf("please input first polygonn");
  200. printf("please input the count of vertex:");
  201. scanf("%d",&n_poly);
  202. printf("please input the vertexn");
  203. for(i=0;i<n_poly;i++)
  204. {
  205. scanf("%lf",&pointx1[i]);
  206. scanf("%lf",&pointy1[i]);
  207. }
  208. printf("please input second polygonn");
  209. printf("please input the count of vertex:");
  210. scanf("%d",&m_poly);
  211. printf("please input the vertexn");
  212. for(i=0;i<m_poly;i++)
  213. {
  214. scanf("%lf",&pointx2[i]);
  215. scanf("%lf",&pointy2[i]);
  216. }
  217. }
  218. }
  219. /*
  220.  *函数名:main
  221.  *功能:判断两个多边形是否相交
  222.  *输入:argc为命令行参数个数
  223.  *     argv为每个命令行参数组成的字符串数组。
  224.  *输出:返回0代表程序正常结束
  225.  */
  226. int main(int argc,char * argv[])
  227. {
  228.     /*完成任务1:初始化*/   
  229. MPI_Init(&argc,&argv);
  230. MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);
  231. MPI_Comm_size(MPI_COMM_WORLD,&group_size);
  232. /*完成任务2:从输入中获取数据*/
  233.     GetData();
  234. /*完成任务3:将数据广播到每个处理器*/
  235. Broadcast();
  236. /*完成任务4:判断是否相交*/
  237.     Judge();
  238.     /*完成任务5:输出结果*/
  239. MPI_Barrier(MPI_COMM_WORLD);
  240. if(my_rank==0)
  241. {
  242. if(result!=0)
  243. printf("two polygons intersectn");
  244. else
  245. printf("two polygons don't intersectn");
  246. }
  247. MPI_Finalize();
  248. }