《GIS算法的几何基础课件》由会员分享，可在线阅读，更多相关《GIS算法的几何基础课件（41页珍藏版）》请在金锄头文库上搜索。
1、第二章 GIS算法的几何基础2.1 维数扩展的9交集模型2.2 矢量的概念2.3 折线段的拐向判断2.4 判断点是否在线段上2.5 判断两线段是否相交2.6 判断线段和直线是否相交2.7 判断矩形是否包含点2.8 判断线段、折线、多边形是否在矩形中2.9 判断矩形是否在矩形中2.10 判断圆是否在矩形中2.11 判断点是否在多边形内2.12 判断线段是否在多边形内第二章 GIS算法的几何基础2.13 判断折线是否在多边形内2.14 判断多边形是否在多边形内2.15 判断矩形是否在多边形内2.16 判断圆是否在多边形内2.17 判断点是否在圆内2.18 判断线段、折线、矩形、多边形是否在圆内2.
2、19 判断圆是否在圆内2.20 计算两条共线的线段的交点2.21 计算线段或直线与线段的交点2.22 求线段或直线与圆的交点2.1 维数扩展的9交集模型(10-1)模型介绍模型介绍 设有现实世界中的两个简单实体A、B,B(A)、B(B)表示A、B的边界,I(A)、I(B)表示A、B的内部,E(A)、E(B)表示A、B外部。Egenhofer(1993)构造出一个由边界、内部、外部的点集组成的9交空间关系模型(9IM)如下: （1）2.1 维数扩展的9交集模型(10-2) 运用维数扩展法,将9IM进行扩展,利用点、线、面的边界、内部、余之间的交集的维数来作为空间关系描述的框架。对于几何实体的边界
3、,它是比其更低一维的几何实体的集合。为此,点的边界为空集;线的边界为线的两个端点,当线为闭曲线时,线的边界为空;面的边界由构成面的所有线构成。若设P为一个点集,定义点集的求维函数DIM如下: 2.1 维数扩展的9交集模型(10-3)利用维数扩展法,式(1)可扩展为 （2） 根据DE-9IM,对于点集拓扑空间X,当需要进行关系判别时,可对矩阵的9元取值进行分析、比较。令C为各单元交的点集,其取值P可能为T,F,*,0,1,2。各个取值的具体含义为： 1)P=T DIM(C)0,1,2,即交集C包含有点、线、面; 2)P=F DIM(C)=-1,即交集C为空; 2.1 维数扩展的9交集模型(10-
4、4) 3)P=* DIM(C)-1,0,1,2,即两目标交集既有点、线、面,又含有某些部分的交为空的情形,该情况在关系判别时,一般不予以考虑; 4)P=0 DIM(C)=0; 5)P=1 DIM(C)=1; 6)P=2 DIM(C)=2。 2.1 维数扩展的9交集模型(10-5) 式(2)中各元素通过取值T,F,*,0,1,2,可产生的 情形为 =10077696种,关系非常复杂,通过对大量的空间关 系进行归纳和分类,得出5种基本的空间关系:相离关系(Disjoint)、相接关系(Touch)、相交关系(Cross)、真包含关系(Within)、叠置关系(Overlap),并将这5种关系定义为
5、空间关系的最小集,其特征为: 1) 相互之间不能进行转化; 2) 能覆盖所有的空间关系模式; 3) 能应用于同维与不同维的几何目标; 4) 每一种关系对应于唯一的DE-9IM矩阵; 5) 任何其它的DE-9IM关系可以通过用这5种基本关系进行表达。 另外,为了用户的使用方便,还定义几个基本的空间关系即: 相等(Equal)、包含(Contain)、覆盖(Cover)、和被覆 盖(CoverdBy)。2.1 维数扩展的9交集模型(10-6) 在地理信息系统中,空间数据具有属性特征、空间特 征和时间特征,基本数据类型包括属性数据、几何数据和空 间关系数据。作为基本数据类型的空间关系数据主要指点/点
6、、点/线、点/面、线/线、线/面、面/面之间的相互关系。利用DE-9IM方法,识别规则为:（1）相离：A.Disjoint(B) A.Relate(B,“FF*FF*”)（2）相接：A.Touch(B) A.Relate(B,“FT*”) OR A.Relate(B,“F*T*”) OR A.Relate(B,“F*T*”) （如图） （3）相交：A.Cross(B) A.Relate(B,“P*T*”), Case A,BL,P=0,Else P=T （如图） 2.1 维数扩展的9交集模型(10-7) (4)叠置：A.Overlap(B) A.Relate(B,“T*T*T*”), Case
7、 A,BL,P=0,Else P=T （如图）(5)真包含：A.Within(B) A.Relate(B,“TF*F*F*”)（如图）(6)包含：A.Contain(B) B.In(A)(7)相等：A.Equal(B) A.Relate(B,“PF*FP*”),P=0,1,2(8)覆盖：A.Cover(B) (I(A)I(B)=I(A) And (E(A)E(B)(9)被覆盖：A.CoveredBy(B)B.Cover(A) 2.1 维数扩展的9交集模型(10-8)(a)(b)多边形/多边形12(a)(b)12线/线。多边形/点线/点多边形/线相接关系示例多边形/线线/线相交关系示例2.1 维
8、数扩展的9交集模型(10-9)多边形/多边形多边形/线线/线多边形/点真包含关系示意图多边形/多边形s1s2e1e2线/线叠置关系示例空间分析几何对象DE-9IM模版相离（Disjoint） AllFF*FF*相接（Touches）A/AFT*或F*T*或F*T*L/LL/AP/AP/L相交（Crosses）P/LT*T*P/AL/L0*L/AT*T*真包含（Within） AllT*F*F*叠置（Overlaps）A/AT*T*T*L/L1*T*T*P/PT*T*T*2.1 2.1 维数扩展的维数扩展的9 9交集模型交集模型(10-10)(10-10)DE-9IM模版分析2.2 矢量的概念(
9、3-1)一、矢量的概念 如果一条线段的端点是有次序之分的，我们把这种线段 称为有向线段。如果有向线段P1P2的起点P1在坐标原点，我们可以把它成为矢量P2(如图)。P2OP1矢量的概念2.2 矢量的概念(3-2)二、矢量加减法设二维矢量P=（x1,y1），Q=(x2,y2),则：QPP+Q矢量加法QP-QP矢量减法2.2 矢量的概念(3-3)三、矢量叉积 设二维矢量P=（x1,y1），Q=(x2,y2),则矢量叉积定义为：由(0,0) 、P、Q和PQ所组成的平行四边形的带符号的面积，即：PQ=x1y2-x2y1 其结果是一个标量。显然有性质： PQ=-(QP)和P（-Q）=-(PQ)叉积的一个
10、非常重要的性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系： (1)若PQ 0，则P在Q的顺时针方向； (2)若PQ 0,则p0p1在p1点拐向右侧后得到p1p2。(2)若(p2 - p0) (p1 - p0) 0,则p0p1在p1点拐向左侧后得到p1p2。(3)若(p2 - p0) (p1 - p0) = 0,则p0、p1、p2三点共线。具体情况可参考下图： p0p1p2p1p2p0p0p1p2(2)(1)(3)2.4判断点是否在线段上 设点为Q，线段为P1P2，判断点Q在该线段上的依据是：(Q-P1)(P2-P1)=0且Q在以P1，P2为对角顶点的矩形内。前者保证Q点在直线P1P2上
11、，后者是保证Q点不在线段P1P2的延长线或反向延长线上，对于这一步骤的判断可以用以下过程实现：ON-SEGMENT(pi,pj,pk)ifmin(xi,xj)=xk=max(xi,xj)andmin(yi,yj)=yk=max(yi,yj)thenreturntrue;elsereturnfalse;特别要注意的是，由于需要考虑水平线段和垂直线段两种特殊情况，min(xi,xj)=xk=max(xi,xj)和min(yi,yj)=yk=max(yi,yj)两个条件必须同时满足才能返回真值。2.5 判断两线段是否相交 (3-1)我们分两步确定两条线段是否相交：(1)快速排斥试验 设以线段P1P2
12、为对角线的矩形为R，设以线段Q1Q2为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。(2)跨立试验 如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2，则矢量(P1-Q1)和(P2-Q1)位于矢量(Q2-Q1)的两侧，即(P1-Q1)(Q2-Q1)*(P2-Q1)(Q2-Q1)0。！2.5 判断两线段是否相交(3-2)(1)当(P1-Q1)(Q2-Q1)=0时，说明(P1-Q1)和(Q2-Q1)共线，但是因为已经通过快速排斥试验，所以P1一定在线段Q1Q2上； (2)当(Q2-Q1)(P2-Q1)=0时，说明P2一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据
13、是： (P1-Q1)(Q2-Q1)*(Q2-Q1)(P2-Q1)=0(3) 同理判断Q1Q2跨立P1P2的依据是： (Q1-P1)(P2-P1)*(P2-P1)(Q2-P1)=0。 具体情况如下图所示：2.5 判断两线段是否相交(3-3)通过快速排斥试验通过快速排斥试验未通过快速排斥试验未通过快速排斥试验RP1P2Q1Q22.6 判断线段和直线是否相交 有了上面的基础，这个算法就很容易了。如果线段P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即： (P1-Q1)(Q2-Q1)*(Q2-Q1)(P2-Q1)=0。2.7 判断矩形是否包含点判断矩形是否包含点 只要判断该点的横坐标和纵坐标是否
14、夹在矩形的左右边和上下边之间。2.8 判断线段、折线、多边形是否在矩形中判断线段、折线、多边形是否在矩形中 因为矩形是个凸集，所以只要判断所有端点是否 都在矩形中就可以了。2.9 判断矩形是否在矩形中判断矩形是否在矩形中只要比较左右边界和上下边界就可以了。2.10 判断圆是否在矩形中判断圆是否在矩形中 很容易证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。2.11 判断点是否在多边形内 判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外，考虑沿着L从无穷远处
15、开始自左向右移动，遇到和多边形的第一个交点的时候，进入到了多边形的内部，遇到第二个交点的时候，离开了多边形，所以很容易看出当L和多边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。 但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中，L和多边形的顶点相交，这时候交点只能计算一个；在图(b)中， L和多边形顶点的交点不应被计算；在图(c)和(d)中，L和多边形的一条边重合，这条边应该被忽略不计。如果L和多边形的一条边重合，这条边应该被忽略不计。 为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和
16、L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，直接可判断P属于多边行。由此得出算法的伪代码如下：2.11 判断点是否在多边形内P(a)(b)(c)(d)count0;以P为端点，作从右向左的射线L;for多边形的每条边sdoifP在边s上thenreturntrue;ifs不是水平的thenifs的一个端点在L上if该端点是s两端点中纵坐标较大的端点thencountcount+1elseifs和L相交thencountcount+1;ifcountmod2=1thenreturntrue;elsereturnfalse; 其中做射线L
17、的方法是：设P的纵坐标和P相同，横坐标为正 无穷大（很大的一个正数），则P和P就确定了射线L。 判断点是否在多边形中的这个算法的时间复杂度为O(n)。 另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较，这种算法由于使用浮点数运算所以会带来一定误差，不推荐大家使用。 2.11 判断点是否在多边形内2.12 判断线段是否在多边形内判断线段是否在多边形内(5-1)线段在多边形内的一个必要条件是线段的两个端点都在多边形内，但由于多边形可能为凹，所以这不能成为判断的充分条件。如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点），因为多边形的边的左右两侧分属多边形内
18、外不同部分，所以线段一定会有一部分在多边形外(见图a)。于是我们得到线段在多边形内的第二个必要条件：线段和多边形的所有边都不内交。线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含于多边形内部（反例见图b)。 (a)(b)2.12 判断线段是否在多边形内判断线段是否在多边形内(5-2) 因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序(X坐标小的排在前面，对于X坐标相同的点，Y坐标小的排在前面，这种排序准则也是为了保证水平和垂直情况的判断正确)，这样相邻的两个点就是在线段上相邻的两交点，如果
19、任意相邻两点的中点也在多边形内，则该线段一定在多边形内。2.12 判断线段是否在多边形内判断线段是否在多边形内(5-3)证明如下：命题1:如果线段和多边形的两相邻交点P1，P2的中点P也在多边形内，则P1,P2之间的所有点都在多边形内。证明：假设P1,P2之间含有不在多边形内的点，不妨设该点为Q，在P1,P之间，因为多边形是闭合曲线，所以其内外部之间有界，而P1属于多边行内部，Q属于多边性外部，P属于多边性内部，P1-Q-P完全连续，所以P1Q和QP一定跨越多边形的边界，因此在P1,P之间至少还有两个该线段和多边形的交点，这和P1P2 是相邻两交点矛盾，故命题成立。证毕。 2.12 判断线段是
20、否在多边形内判断线段是否在多边形内(5-4)由命题1直接可得出推论：推论2：设多边形和线段PQ的交点依次为P1,P2,Pn，其中Pi和Pi+1是相邻两交点，线段PQ在多边形内的充要条件是：P，Q在多边形内且对于i=1,2,n-1，Pi,Pi+1的中点也在多边形内。在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。(5-5)(5-5)至此我们得出算法如下：if线端PQ的端点不都在多边形内thenretu
21、rnfalse;else 点集pointSet初始化为空;for多边形的每条边sdoif线段的某个端点在s上then将该端点加入pointSet;elseifs的某个端点在线段PQ上then将该端点加入pointSet;elseifs和线段PQ相交/*这时候已经可以肯定是内交了*/ thenreturnfalse; else 将pointSet中的点按照X-Y坐标排序; forpointSet中每两个相邻点pointSeti, pointSeti+1 do ifpointSeti,pointSeti+1的 中点不在多边形中 thenreturnfalse; else returntrue这个过
22、程中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是常数级的复杂度，几乎可以忽略不计。因此算法的时间复杂度也是O(n)。2.13 判断折线是否在多边形内 只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段，多边形有n个顶点，则该算法的时间复杂度为O(mn)。2.14 判断多边形是否在多边形内 只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(mn)。2.15 判断矩形是否在多边形内 将矩形转化为多边形，然后再判断是否在多边形内。2.16 判断圆是否在多边形内 只要计算圆心到多边形的每条边的最短距离，如果该距离大于
23、等于圆半径则该圆在多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。2.17 判断点是否在圆内计算圆心到该点的距离，如果小于等于半径则该点在圆内。2.18 判断线段、折线、矩形、多边形 是否在圆内 因为圆是凸集，所以只要判断是否每个顶点都在 圆内即可。2.19 判断圆是否在圆内 设两圆为O1,O2，半径分别为r1,r2，要判断O2是否在O1内。先比较r1，r2的大小，如果r1r则L和圆没有交点；c)利用勾股定理，可以求出两交点坐标，但要注意考虑L和圆的相切情况。3.如果L平行于X轴，做法与L平行于Y轴的情况类似；4.如果L既不平行X轴也不平行Y轴，可以求出L的斜率K，然后列出L的点斜式方程，和圆方程联立即可求解出L和圆的两个交点；5.如果L是线段，对于2，3，4中求出的交点还要分别判断是否属于该线段的范围内。
