多边形位置关系判断程序

1、 多边形位置关系判断程序一. 需求说明对软件需求完全理解对于软件开发工作的成功是至关重要的，需求说明的任务是发现、规范的过程，有益于提高软件开发过程中的能见度，便于对软件开发过程中的控制与管理，便于采用工程方法开发软件，提高软件的质量，便于开发人员、维护人员、管理人员之间的交流、协作，并作为工作成果的原始依据，并且在向潜在用户传递软件功能、性能需求，使其能够判断该软件是否与自己的需求相关。我们的程序的功能是可以判断在同一平面内任意两个多边形之间的位置关系，其位置关系分为：相交，相离，包含3种情况。输入条件是两个多边形各自的边数及每个多边形各自顶点的坐标，输入多边形坐标时要注意按逆时针或顺时针的

2、顺序输入，不然程序将无法构成多边形，出现错误。输出是两个多边形的位置关系结果，是相交，相离，包含（能反应哪个多边形包含另外一个多边形）之间的一种情况。六算法说明这个算法的核心为参数法的应用：参数法：已知第一条线段两点：（X0,Y0）,(X1,Y1)参数方程为：X=(X1-X0)*T1+X0;(0<=T1<=1)Y=(Y1-Y0)*T1+Y0;(0<=T1<=1)同理：第二条线段参数方程（ （X2,Y2）,(X3,Y3)）X=(X-X)*T2+X;(0<=T2<=1)Y=(Y-Y)*T2+Y;(0<=T2<=1)联立方程得：X=(X1-X0)*T1

3、+X0=(X-X)*T2+XY=(Y1-Y0)*T1+Y0=(Y-Y)*T2+Y即(X1-X0)*T1+(X0-X)=(X-X)*T2 (Y1-Y0)*T1+(Y0-Y)=(Y-Y)*T2其中0<=T1<=1，0<=T2<=1令X1-X0=E, X0-X2=F, X-X=G Y1-Y0=H, Y0-Y=M, Y-Y=N即E*T1+F=G*T2 H*T2+M=N*T2解得：T1=(M*G-F*N)/(E*N-H*G)T2=(M*E-F*H)/( E*N-H*G)下面进行分类讨论：E*N-H*G!=0时T1和T2均有确定解 这时如果0<=T1,T2<=1则交点落

4、在两线段之间，两线段相交 E*N-H*G=0时，即（X1-X0）*（Y-Y）=(Y1-Y0)*(X3-X2) 1).X1-X0!=0且X3-X2!=0 推得K1=(Y1-Y0)/（X1-X0）=（Y-Y）/(X3-X2)=K2 即两线段平行（两线段均存在斜率） 2). X1-X0=0且X3-X2=0 此时由于两线段两端点不重合，即Y1-Y0!=0且Y-Y!=0 即两线段均不存在斜率，均垂直于X轴，两线段平行 3). X1-X0=E和X0-X2=F中有一个为0，假设X1-X0!=0且X3-X2=0，由于（X1-X0）*（Y-Y）=(Y1-Y0)*(X3-X2)，推得Y3-Y2=0,从而（X2,Y

5、2）,(X3,Y3) 两点重合，舍去。同理，也不可能X1-X0=0且X3-X2!=0 所以由以上可得E*N-H*G=0是两线段平行的充要条件。（1-1） 当E*N-H*G=0时，做近一步讨论：I) M*G-F*N!=0且M*E-F*H!=0时 由T1,T2的表达式可得T1,T2均无解，即由几何关系可得此时两条线段平行且相距一定距离。所以此时两线段无交点。II) M*G-F*N=0时 同理由T1,T2的表达式可得T1有无穷多组解，因为(X1-X0)*T1+(X0-X)=(X-X)*T2 (Y1-Y0)*T1+(Y0-Y)=(Y-Y)*T2 可得T2=(X1-X0)*T1+(X0-X)/(X-X)

6、 T2=(Y1-Y0)*T1+(Y0-Y)/(Y-Y) 因为X-X和Y-Y不可能同时为0，故上式中至少有一个成立，即一个T1对应一个T2,从而T2有无穷多解，即M*E-F*H=0。从几何关系可得此时，两线段所在直线重合。进一步判断两线段相交的条件，同上得，只需在上述无穷多解中，存在0<=T1,T2<=1的解即可。T1和T2之间存在的是线性关系，只需要T1在0,1所对应的T2区间与0,1是否存在交集才可。整个算法分为三部分：1），input多边形的输入。分为两小部分：多边形边数的确定。N>=3,即可。 多边形连续三点是否共线：流程图如下：input： Y测试用例2NNYYNY输

7、入顶点ai的坐标i<m?am=a0am+1=a1利用参数法判断ai-2,ai-1,ai三点是否共线i>=2?i<=m?结束i=i+1输入边数m开始m>=3？i=0测试用例1N2）边的相交：核心为参数法 流程图如下 YNNNYYNY算出参数e,f,g,h,m,n开始en-hg=0?mg-fn=0?0<=t1,t2<=1?算出t1,t2 t1=0,1时对应的t2E0.1?Return 1,即相交Return 0 不相交Return 0 不相交Return 1,即相交结束return 0不相交测试用例3.1测试用例3.2测试用例3.3测试用例3.4测试用例3.53

8、)d,点与多边形关系的判断：（射线法） Count+N测试用例4.5测试用例4.6NYYNYYNYNNYYN开始count=0,i=1,y=c.y ai+1.y-ai.y=0？算出t,及交点x0<=t<=1且x<=c.x?c.y=ai.y? ai-1.y<y|ai+1.y<y? Count+ i=i+1i<=m?Count%2=0？Return 1点在内Return 0点在外测试用例4.1，4.2测试用例4.3测试用例4.4 整个程序的流程图如下：YNYNYNYN开始Input（d1,m）,input(d2,n)i<m且flag=0?i=0,j=0,f

9、lag=0,flag1=0j<n且flag=0?Flag=b(ai,ai+1,bj,bj+1),j+i+flag=1?两多边形相交flag1=d(d1,m,d20)flag1=1?第一个多边形在第二个多边形内flag1=d(d2,n,d10)flag1=1?两多边形相离第二个多边形在第一个多边形内Getchar(),c=getchar()c=Y|c=y?结束七测试用例：1. 针对多边形边数的输入：输入m=2,预期输出：ERROR！多边形的边数应大于等于3！2. 针对多边形连续三顶点不共线：依次输入以上点的坐标预期输出：ERROR！连续三点共线！ 请重新输入第%d点坐标（%d视实际输入情况

10、而定）3.针对相交的判断3.1两边部分重合：依次输入第一个多边形各顶点坐标：（，），（，），（，） 依次输入第一个多边形各顶点坐标：（，），（，），（，） 预期输出结果：两个多边形相交 3.2两边所在直线重合，两边不相交：依次输入第一个多边形各顶点坐标：（，），（，），（，）依次输入第二个多边形各顶点坐标：（，），（，），（，） 预期输出结果：两个多边形相离！ 3.3两边仅相互平行：依次输入第一个多边形各顶点坐标：（，），（，），（，）依次输入第二个多边形各顶点坐标：（1，-1），（3，-1），（2，-2）预期输出结果：两个多边形相离！3.4两边不平行，但t1,t2不均在0,1之内： 依次输入

11、第一个多边形各顶点坐标：（0，0），（2，0），（1，2） 依次输入第二个多边形各顶点坐标：（3，2）,(3,-2),(5，0) 预期输出结果：两个多边形不相交！（3，2）（5，0）（3，-2）（0，2）（0，0）（1，2） 3.5两边不平行，但t1,t2均在0,1之内： 依次输入第一个多边形各顶点坐标：（0，0），（2，0），（1，2） 依次输入第二个多边形各顶点坐标：（2，0）,(2,-2),(4,-1) 预期输出结果：两个多边形相交！(4,-1)(2,-2)(2,0)(0,0)(1,2)4针对包含的判断： 4.1射线法时所做射线过多边形的一边（相离）：依次输入第一个多边形各顶点坐标：（，

12、），（，），（，），（，）依次输入第一个多边形各顶点坐标： （-，），（-，），（-，） 预期输出结果：两个多边形相离！（-10，2）（-8，2）（-9，）（，5）（5，5）（5，）（，）4.2射线法时所做射线过多边形的一边（包含）：依次输入第一个多边形各顶点坐标：（0 ，0），（5，0），（5，3），（3，3），（3，5），（0，5）依次输入第一个多边形各顶点坐标： （1，2），（3，2），（2，3）预期输出结果：第二个多边形在第一个多边形内！（3，2）（1，2）（2，3）（，5）（3，5）（3，3）（5，3）（5，0）（，）4.3射线不和多边形相交 依次输入第一个多边形各顶点坐标：（0 ，

13、0），（6，0），（3，3）依次输入第二个多边形各顶点坐标： （7，1），（11，1），（9，2） 预期输出结果：两个多边形相离!（11，1）（9，2）（7，1）（6 ，0）（0 ，0）（3，3）4.4 所作射线与多边形的相交： 依次输入第一个多边形各顶点坐标：（0 ，0），（6，0），（3，3）依次输入第二个多边形各顶点坐标： （1，1），（5，1），（3，2） 预期输出结果：两个多边形相离!（0，0）（6，0）（1，1）（5，1）（3，2）（3，3）4.5射线过多边形的顶点，两边在射线一侧：依次输入第一个多边形各顶点坐标：（，），（，），（，），（，），（，），（，） 依次输入第二个多边形各顶点坐标：（.，），（.，），（.，） 预期输