GIS算法的几何基础

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,其次章 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.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进展扩展,利用点、线、面的边,界、内部、余之间的交集的维数来作为空间关系描述的框架。,对于几何实体的边界,它是比其更低一维的几何实体的集合。为此,点的边界为空集;线的边界为线的两个端点,当线为闭曲线时,线的,边界为空;面的边界由构成面的全部线构成。假设设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),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种关系定义为空间关系的最小集,其特征为:,1)相互之间不能进展转化;,2)能掩盖全部的空间关系模式;,3)能应用于同维与不同维的几何目标;,4)每一种关系对应于唯一的DE-9IM矩阵;,5)任何其它的DE-9IM关系可以通过用这5种根本关系进展表达。,另外,为了用户的使用便利,还定义几个根本的空间关系即:,相等(Equal)、包含(Contain)、掩盖(Cover)、和被覆,盖(CoverdBy)。,2.1,维数扩展的,9,交集模型,(10-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 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),多边形,/,多边形,1,2,(a),(b),1,2,线,/,线,。,多边形,/,点,线,/,点,多边形,/,线,相接关系示例,多边形,/,线,线,/,线,相交关系示例,2.1,维数扩展的,9,交集模型,(10-9),多边形,/,多边形,多边形,/,线,线,/,线,多边形,/,点,真包含关系示意图,多边形,/,多边形,s,1,s,2,e,1,e,2,线,/,线,叠置关系示例,空间分析,几何对象,DE-9IM,模版,相离（,Disjoint,）,All,FF*FF*,相接（,Touches,）,A/A,FT*,或,F*T*,或,F*T*,L/L,L/A,P/A,P/L,相交（,Crosses,）,P/L,T*T*,P/A,L/L,0*,L/A,T*T*,真包含（,Within,）,All,T*F*F*,叠置（,Overlaps,）,A/A,T*T*T*,L/L,1*T*T*,P/P,T*T*T*,2.1,维数扩展的,9,交集模型,(10-10),DE-9IM,模版分析,2.2,矢量的概念,(3-1),一、矢量的概念,假设一条线段的端点是有次序之分的，我们把这种线段,称为有向线段。假设有向线段P1P2的起点P1在坐标原点，我们可以把它成为矢量P2(如图)。,P,2,O,P,1,矢量的概念,2.2,矢量的概念,(3-2),二、矢量加减法,设二维矢量P=x1,y1，Q=(x2,y2),则：,Q,P,P+Q,矢量加法,Q,P-Q,P,矢量减法,2.2,矢量的概念,(3-3),三、矢量叉积,设二维矢量P=x1,y1，Q=(x2,y2),则矢量叉积定义为：,由(0,0)、P、Q和PQ所组成的平行四边形的带符号的面积，即：PQ=x1y2-x2y1 其结果是一个标量。明显有性质：,PQ=-(QP)和P-Q=-(PQ),叉积的一个特殊重要的性质是可以通过它的符号推断两矢量相互之间的顺逆时针关系：,(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三点共线。,具体状况可参考以以下图：,p,0,p,1,p,2,p,1,p,2,p,0,p,0,p,1,p,2,(2),(1),(3),2.4推断点是否在线段上,设点为Q，线段为P1P2，推断点Q在该线段上的依据是：(Q-P1)(P2-P1)=0且Q在以P1，P2为对角,顶点的矩形内。前者保证Q点在直线P1P2上，后者是保证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为对角线的矩形为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),当(P1-Q1)(Q2-Q1)=0时，说明(P1-Q1)和(Q2-Q1)共线，但是由于已经通过快速排斥试验，所以P1确定在线段Q1Q2上；,当(Q2-Q1)(P2-Q1)=0时，说明P2确定在线段 Q1Q2上。所以推断P1P2跨立Q1Q2的依据是：,(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),通,过,快,速,排,斥,试,验,通过快速排斥试验,未通过快速排斥试验,未,通,过,快,速,排,斥,试,验,R,P,1,P,2,Q,1,Q,2,2.6 推断线段和直线是否相交,有了上面的根底，这个算法就很简洁了。假设线段P1P2,和直线Q1Q2相交，则P1P2跨立Q1Q2，即：,(P1-Q1)(Q2-Q1)*(Q2-Q1)(P2-Q1)=0。,2.7 推断矩形是否包含点,只要推断该点的横坐标和纵坐标是否夹在矩形的左右边和上下,边之间。,2.8 推断线段、折线、多边形是否在矩形中,由于矩形是个凸集，所以只要推断全部端点是否,都在矩形中就可以了。,2.9 推断矩形是否在矩形中,只要比较左右边界和上下边界就可以了。,2.10 推断圆是否在矩形中,很简洁证明，圆在矩形中的充要条件是：圆心在矩形中且圆的,半径小于等于圆心到矩形四边的距离的最小值。,2.11 推断点是否在多边形内,推断点P是否在多边形中是计算几何中一个特殊根本但是,特殊重要的算法。以点P为端点，向左方作射线L，由于多边形,是有界的，所以射线L的左端确定在多边形外，考虑沿着L从无穷远,处开头自左向右移动，遇到和多边形的第一个交点的时候，进入到,了多边形的内部，遇到其次个交点的时候，离开了多边形，所,以很简洁看出当L和多边形的交点数目C是奇数的时候，P在多边形,内，是偶数的话P在多边形外。,但是有些特殊状况要加以考虑。如图以以下图(a)(b)(c)(d)所示。,在图(a)中，L和多边形的顶点相交，这时候交点只能计算一个；在,图(b)中，L和多边形顶点的交点不应被计算；在图(c)和(d)中，,L和多边形的一条边重合，这条边应当被无视不计。假设L和多边形,的一条边重合，这条边应当被无视不计。,为了统一起见，我们在计算射线L和多边形的交点的时候，1。对于多边形的水平边不作考虑；2。对于多边形的顶点和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;elsereturn