多边形位置关系判断程序资料.docx

多边形位置关系判断程序资料.docx

《多边形位置关系判断程序资料.docx》由会员分享，可在线阅读，更多相关《多边形位置关系判断程序资料.docx（13页珍藏版）》请在冰点文库上搜索。

多边形位置关系判断程序资料

多边形位置关系判断程序

一.需求说明

对软件需求完全理解对于软件开发工作的成功是至关重要的，需求说明的任务是发现、规范的过程，有益于提高软件开发过程中的能见度，便于对软件开发过程中的控制与管理，便于采用工程方法开发软件，提高软件的质量，便于开发人员、维护人员、管理人员之间的交流、协作，并作为工作成果的原始依据，并且在向潜在用户传递软件功能、性能需求，使其能够判断该软件是否与自己的需求相关。

我们的程序的功能是可以判断在同一平面内任意两个多边形之间的位置关系，其位置关系分为：

相交，相离，包含3种情况。

输入条件是两个多边形各自的边数及每个多边形各自顶点的坐标，输入多边形坐标时要注意按逆时针或顺时针的顺序输入，不然程序将无法构成多边形，出现错误。

输出是两个多边形的位置关系结果，是相交，相离，包含（能反应哪个多边形包含另外一个多边形）之间的一种情况。

六．算法说明

这个算法的核心为参数法的应用：

参数法：

已知第一条线段两点：

（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+X0=（X３-X２）*T2+X２

Y=（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则交点落在两线段之间，两线段相交

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,Y2）,（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２）

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：

2）边的相交：

核心为参数法流程图如下

3）d,点与多边形关系的判断：

（射线法）

整个程序的流程图如下：

七．测试用例：

1.针对多边形边数的输入：

ｎ＜３

输入m=2,

预期输出：

ERROR！

多边形的边数应大于等于3！

2.针对多边形连续三顶点不共线：

依次输入以上点的坐标

预期输出：

ERROR！

连续三点共线！

请重新输入第%d点坐标（%d视实际输入情况而定）

3.针对相交的判断

3.1两边部分重合：

依次输入第一个多边形各顶点坐标：

（０，０），（２，０），（１，１）

　　　　　　　依次输入第一个多边形各顶点坐标：

（１，０），（３，０），（２，－２）

预期输出结果：

两个多边形相交

3.2两边所在直线重合，两边不相交：

　　依次输入第一个多边形各顶点坐标：

（０，０），（２，０），（１，１）

　　依次输入第二个多边形各顶点坐标：

（３，０），（５，０），（４，１）

预期输出结果：

两个多边形相离！

3.3两边仅相互平行：

依次输入第一个多边形各顶点坐标：

（０，０），（２，０），（１，１）

依次输入第二个多边形各顶点坐标：

（1，-1），（3，-1），（2，-2）

预期输出结果：

两个多边形相离！

3.4两边不平行，但t1,t2不均在[0,1]之内：

依次输入第一个多边形各顶点坐标：

（0，0），（2，0），（1，2）

依次输入第二个多边形各顶点坐标：

（3，2）,（3,-2）,（5，0）

预期输出结果：

两个多边形不相交！

3.5两边不平行，但t1,t2均在[0,1]之内：

依次输入第一个多边形各顶点坐标：

（0，0），（2，0），（1，2）

依次输入第二个多边形各顶点坐标：

（2，0）,（2,-2）,（4,-1）

预期输出结果：

两个多边形相交！

4针对包含的判断：

4.1射线法时所做射线过多边形的一边（相离）：

依次输入第一个多边形各顶点坐标：

（０，０），（０，５），（５，５），（５，０）

依次输入第一个多边形各顶点坐标：

　　　（-９，０），（-８，２），（-１０，２）

预期输出结果：

两个多边形相离！

4.2射线法时所做射线过多边形的一边（包含）：

依次输入第一个多边形各顶点坐标：

（0，0），（5，0），（5，3），（3，3），（3，5），（0，5）

依次输入第一个多边形各顶点坐标：

（1，2），（3，2），（2，3）

预期输出结果：

第二个多边形在第一个多边形内！

4.3射线不和多边形相交

依次输入第一个多边形各顶点坐标：

（0，0），（6，0），（3，3）

依次输入第二个多边形各顶点坐标：

（7，1），（11，1），（9，2）

预期输出结果：

两个多边形相离!

4.4所作射线与多边形的相交：

依次输入第一个多边形各顶点坐标：

（0，0），（6，0），（3，3）

依次输入第二个多边形各顶点坐标：

（1，1），（5，1），（3，2）

预期输出结果：

两个多边形相离!

4.5射线过多边形的顶点，两边在射线一侧：

依次输入第一个多边形各顶点坐标：

（０，０），（５，０），（５，５），（４，２），（３，５），（０，５）

　依次输入第二个多边形各顶点坐标：

（０.５，２），（０.２５，４），（０.７５，４）

预期输出结果：

两个多边形相离！

4.6射线法过多边形的顶点，两边在射线两侧：

依次输入第一个多边形各顶点坐标：

（０，０），（３，０），（４，２），（３，４），（０，４）

　依次输入第二个多边形各顶点坐标：

（２，２），（１，１），（１，３）

预期输出结果：

第二个多边形在第一个多边形内！