GIS算法的计算几何基础1

1、1GIS算法的计算几何基础GISGIS算法基础算法基础第二章第二章2本 讲 内 容v1 维数扩展的9交集模型v2 矢量的概念v3 折线段的拐向判断v4 判断点是否在线段上v5 判断两线段是否相交v6 判断矩形是否包含点v7 判断线段、折线、多边形是否在矩形中v8 判断矩形是否在矩形中v9 判断圆是否在矩形中v10 判断点是否在多边形内31、维数扩展的9交集模型v1.1 概述v1.2 模型介绍v1.3 空间关系的判定41.1 概述v关系运算：指的是用于检验两个几何对象的特定的拓扑空间关系的逻辑方法。v几何对象的拓扑空间关系在GIS中是一个重要的研究主题。v最基本的比较方法最基本的比较方法：比较两

2、个几何对象的内部、边界和外部的交集，并基于交集矩阵产生的实体来对两个几何对象空间关系分类。 v普通的拓扑学对内部、外部和边界的概念进行了定义，适用于在二维空间中对二维对象的空间关系的定义。51.1 概述v 普通拓扑学中的概念应用于二维空间中的一维或者零维对象时，需要组合拓扑学的方法。 v 组合拓扑学定义： 几何体的边界由一组较低维数的几何体构成。几何体的边界由一组较低维数的几何体构成。 点(point)或者多点(multipoint)的边界为一个空集。 非闭合曲线的边界由其两个端点组成，闭合曲线的边界为空。 多曲线(multicurve)的边界为它的组成弧段的奇数弧段构成。 多边形的边界是其环

3、的集合。 多多边形(multipolygon)的边界是组成它的多边形环的集合。61.1 概述v几何对象域通常认为是拓扑闭合的，组成几何体内部的点不会因为其外部的点被删除而删除。组成几何体外部的点不在几何体内部或者边界上。v4交集模型：最大维数在一维和二维空间中两个几何体的空间关系研究一般只考虑对比内部和边界的交集，并定义为4交集模型。v9交集模型：4交集模型考虑输入几何体的外部时就扩展为9交集模型。7, 1991)IBE81.1 概述v9-交空间关系模型(9-Intersection Model,9-IM)v对于该矩阵中的每一元素，都有“空”与“非空”两种取值，9个元素总共可产生29=512种

4、情形。B(A)B(B)B(A)I(B)B(A)E(B)I(A)B(B)I(A)I(B)I(A)E(B)E(A)B(B)E(A)I(B)E(A)E(B)9v拓扑关系描述面/面拓扑关系, 1991)DisjointMeetOverlapContainEqualCoveredByInsideCover111100100111110100111111111100100111100010001111011001111001001100110111v面 与面 与面间有面间有效的拓效的拓扑关系扑关系共 有共 有 8个个10v拓扑关系描述线/面拓扑关系, 1991)LR11LR12LR13LR22LR31LR

5、32LR33LR42LR44LR46LR62LR64LR66LR71LR72LR73LR74LR75LR76111100100101110100111110100100111100111101100101111100111111100100110101100100111100110111100111101100101111100111111111101101101111101111111101101101111111101111101111111v线 与线 与面间有面间有效的拓效的拓扑关系扑关系共有共有19个个11v拓扑关系描述线/线拓扑关系, 1991)LL1LL2LL3LL4LL5LL6L

6、L7LL8LL9LL10LL11LL12LL13LL14LL15LL16LL17LL18LL19LL20LL21111100100111100101101100110111100110100100111101100111111100111111001100111001001111001101101001110111001110101001111111001111111101100111101101101101110111101110101101111111101111101010100v线 与线 与线间有线间有效的拓效的拓扑关系扑关系共有共有33个，这个，这里只给里只给出了出了21个个121.

7、2 模型介绍v几何体a，假设I(a)，B(a)和E(a)分别表示为a的内部、边界和外部。I(a)，B(a)和E(a)任意两个的交集就生成一个混合维数的几何体集合x。假设dim(x)返回x中几何体最大最大维数。基于维数扩展的9交集矩阵（DE-9IM，Dimensionally Extended 9 Intersection Model ）为：131.2 模型介绍v如果计算两个闭合的正多边形的交集内部并确定交集的维数，就没有必要分别用几个几何体表示两个多边形内部。v每一单元交集的维数都严格受到两个几何形体类型的限制。线面关系中，内部内部单元的维数只能是-1，1；面面关系中，内部内部单元的维数为-1

8、，2，这些情况下所要做的只是寻找交集。141.2 模型介绍151.2 模型介绍v空间关系的描述可以归纳为空间关系的描述可以归纳为：两个几何体，以表示两个几何体DE-9IM结果合理值集合的模式矩阵形式输入。只要两个只要两个几何体的空间关系符合模式矩阵表示的合理值中的一个，则几何体的空间关系符合模式矩阵表示的合理值中的一个，则返回返回TRUETRUE。161.2 模型介绍v模式矩阵由9种模式值集合构成，一种集合对应矩阵一个单元。可能的模式值p为T，F，*，0，1，2，对于任何单元的所属何种交集含义x如下：vP=T=dim(x)0，1，2，例如，xvP=F=dim(x)=-1，例如，x=vP=*=d

9、im(x)-1，0，1，2，例如，没关系vP=0=dim(x)=0vP=1=dim(x)= 1vP=2=dim(x)=2171.2 模型介绍v模式矩阵可以用一个以行号为顺序的9个元素的数组或者列表表示。如下所示代码用于检测两个区域是否叠置：181.3 空间关系的判定v优点：基于模式矩阵的空间关系的确定可以检测大部分的空优点：基于模式矩阵的空间关系的确定可以检测大部分的空间关系，并且能对特殊的空间关系进行检测。间关系，并且能对特殊的空间关系进行检测。v缺点：语言抽象化，不人性化。缺点：语言抽象化，不人性化。v人性化的语言定义的五种用于人性化的语言定义的五种用于DE-9IMDE-9IM的空间关系命

10、名的空间关系命名 ：相相离、相接、相交、真包含和叠置。离、相接、相交、真包含和叠置。v这些定义中这些定义中P P用于表示零维的几何体（点或者多点），用于表示零维的几何体（点或者多点），L L表示表示一维几何体（线或者多线），而一维几何体（线或者多线），而A A表示二维几何体（面和多表示二维几何体（面和多面）。面）。191.3 空间关系的判定（1）相离（）相离（Disjoint） 假设两个几何体（闭合）a和b： a.Disjoint(b)a b= DE-9IM中表示为：201.3 空间关系的判定（2）相接（）相接（touches） 两个几何体a和b相接关系适用于A/A，L/L，L/A，P/A和P

11、/L，而不适用于P/P。其定义如下：211.3 空间关系的判定221.3 空间关系的判定（3）相交（）相交（Crosses）相交关系适用于P/L，P/A，L/L和L/A的情况。231.3 空间关系的判定（4）真包含（）真包含（Withins）真包含关系定义如下：241.3 空间关系的判定（5）重置（）重置（overlaps）叠置关系定义的情况为A/A，L/L和P/P。定义如下：251.3 空间关系的判定（6）包含（）包含（contains）a.contains(b)b.within(a)(7)相交（Intersects）a.Intersects(b)=!a.Disjoint(b)261.3 空

12、间关系的判定272 矢量的概念v有向线段（directed segment)：端点有次序之分的线段。v如果有向线段p1p2的起点p1在坐标原点，则称为矢量p2。v内容：矢量加减法矢量的叉积283 折线段的拐向判断v方法：根据矢量叉积的性质判断。v对于有公共端点的线段p0p1和p1p2，通过计算(p2-p0)(p1-p0)的符号判断折线的拐向：294 判断点是否在线段上v设点为Q，线段为P1P2，判断点Q在该线段上的依据是(Q-P1)(P2-P1)=0且Q在以P1P2为对角线的矩形内。v判断的实现：305 判断两直线相交v算法1：（1）快速排除：以两条直线为端点的矩形不相交。（方法？）若矩形不相

13、交，则直线不会相交。315 判断两直线相交（2）跨立试验：如果两线段相交，则必然跨立对方。即一直线的两端点必然位于另一直线两侧。v算法算法2： 定义A,B,C,D为二维空间点，则有向线段AB和CD的参数方程为：325 判断两直线相交v如果AB与CD相交，则：解方程得：设P为直线AB和CD的交点，则：335 判断两直线相交v如果 且 ，则有向线段AB与CD相交。v如果(Bx-AX)(Dy-Cy)-(By-Ay)(Dx-CX)=0，则AB与CD平行。v如果(By-Ay)(Dx-Cx)-(Bx-Ax)(Dy-Cy)=0，则AB与CD共线。v如果直线AB和CD相交，而交点不位于线段AB和CD之间，则交

14、点位置可通过如下条件判断：r1，则P位于有向线段AB的延长线上；r1，则P位于有向线段CD的延长线上；s0，则P位于有向线段DC的延长线上；) 10 r（) 10 s（346 矩形是否包含点v只要判断点的横坐标与纵坐标是否夹在矩形的左右只要判断点的横坐标与纵坐标是否夹在矩形的左右边和上下边之间。边和上下边之间。357判断线段、折线、多边形是否在矩形中v矩形是凸集，所以只需判断所有的端点是否在矩形矩形是凸集，所以只需判断所有的端点是否在矩形中。中。368 判断矩形是否在矩形中v比较左右边界和上下边界比较左右边界和上下边界379 判断圆是否在矩形中v圆心在矩形中，且圆的半径小于等于圆心到矩形四圆心

15、在矩形中，且圆的半径小于等于圆心到矩形四边的距离的最小值。边的距离的最小值。38v常用算法：常用算法：射线法（奇偶法）射线法（奇偶法）转角法：环绕数（多边形环绕点的次数）为转角法：环绕数（多边形环绕点的次数）为0，则点在多边形外，否则，点在多边形内。，则点在多边形外，否则，点在多边形内。10 判断点是否在多边形内3910.1 射线法v射线法计算从点射线法计算从点P P开始的射线穿过多边形边界的次数，多边开始的射线穿过多边形边界的次数，多边形的边界将多边形内部与外部分开。如果结果为偶数，则点形的边界将多边形内部与外部分开。如果结果为偶数，则点在多边形外部，否则，若为奇数，则点在多边形内部。在多边

16、形外部，否则，若为奇数，则点在多边形内部。4010.1 射线法v必须决定在多边形边界上的点是在多边形内部还是外部。必须决定在多边形边界上的点是在多边形内部还是外部。一一个标准的约定个标准的约定是是在左边界或者下边界上的点认为是在多边形在左边界或者下边界上的点认为是在多边形内部，在右边界或者上边界的点认为是在多边形外部内部，在右边界或者上边界的点认为是在多边形外部。在这。在这种约定下，如果两个不同的多边形共享一个边，那么在这条种约定下，如果两个不同的多边形共享一个边，那么在这条边上的点会在一个多边形的内部而在另一个多边形的外部。边上的点会在一个多边形的内部而在另一个多边形的外部。 4110.1

17、射线法v一个一个简单的射线法简单的射线法是是选择一条水平的、向点选择一条水平的、向点P P的右侧延伸的、的右侧延伸的、平行于平行于X X轴的射线轴的射线。v为了计算总的交点的数目，算法简单的遍历多边形的所有边，为了计算总的交点的数目，算法简单的遍历多边形的所有边，测试是否穿越边，穿越时增加交点的数目。测试是否穿越边，穿越时增加交点的数目。v穿越测试必须处理好一些特殊的情形。完全穿越测试必须处理好一些特殊的情形。完全规则规则如下：如下：（1 1）方向向上的边）方向向上的边包括其开始点，不包括其终止点包括其开始点，不包括其终止点；（2 2）方向向下的边）方向向下的边不包括其开始点，包括其终止点不包

18、括其开始点，包括其终止点；（3 3）水平边不参加穿越测试水平边不参加穿越测试；（4 4）射线和多边形的边的交点必须严格在点）射线和多边形的边的交点必须严格在点P P的右边的右边。4210.1 射线法4310.1 射线法v射线法的有效性是基于射线法的有效性是基于一个简单的闭合曲线将二维平面分成一个简单的闭合曲线将二维平面分成两个相连接的部分：有边界的内部和无边界的外部两个相连接的部分：有边界的内部和无边界的外部。v曲线必须是简单的（没有自相交），否则平面会被分成两个曲线必须是简单的（没有自相交），否则平面会被分成两个以上的部分，并且不能保证穿越边界时不会改变出入特性以上的部分，并且不能保证穿越边

19、界时不会改变出入特性。v对于一个闭合的曲线，可能将二维平面分成多个部分，但是对于一个闭合的曲线，可能将二维平面分成多个部分，但是其中只有一个没有边界且在曲线外部的部分。其中只有一个没有边界且在曲线外部的部分。v有边界的部分可能在曲线内部也可能在曲线外部。有边界的部分可能在曲线内部也可能在曲线外部。v两个有共同边界的有边界部分可能都在曲线内部，那么穿越两个有共同边界的有边界部分可能都在曲线内部，那么穿越过共享的边界并不会改变出入特性。过共享的边界并不会改变出入特性。4410 判断点是否在多边形内v判断出现错误！判断出现错误！4510.2 转角法v转角法能够很精确的判定一个点是否在多边形内部。需要

20、计转角法能够很精确的判定一个点是否在多边形内部。需要计算多边形绕点多少次，算多边形绕点多少次，环绕数为环绕数为0 0时，点在多边形外部时，点在多边形外部。4610.2 转角法v方法：定义二维平面中某个封闭曲线关于某点的环绕数。令C(u)=(x(u),y(u)，0u1，且C(0)=C(1)，是二维连续曲线。P是不在C(u)上的点。v令Cp(u)= C(u)-P为从点P到C(u)的矢量，并且它的单位方向矢量为W(u)=CP(u)/| CP(u)|。 W(u)坐标形式为： W(u)=(cos(u),sin(u)，v其中(u)是正的逆时针方向的角。环绕的次数(wn)就等于W(u)环绕S1的次数的整数部

21、分。计算公式为：10)(2121duudwn4710.2 转角法v若曲线C是由顶点V0,V1,Vn=V0构成的多边形，那么积分可以简化为计算带符号的角度的总和。这些角PVi与PVi+1的夹角。因此，如果i=angle(PVi,PVi+1),则v这个公式效率不高，原因在于arccos函数很耗时。v改进：在改进：在S1中任取一点中任取一点Q，因为曲线，因为曲线W(u)环绕，则可能多次环绕，则可能多次经过经过Q点。当点。当W(u)按逆时针方向经过按逆时针方向经过Q点时，记为点时，记为+1次，顺次，顺时针经过时针经过Q点时，记为点时，记为-1次，那么总次数和就是次，那么总次数和就是W环绕环绕S1的的次

22、数，刚好等于环绕数（次数，刚好等于环绕数（wn）。）。)|arccos(2121101110niiiiiniiPVPVPVPVwn4810.2 转角法v用一个射线用一个射线R R，R R的起点为的起点为P P并向并向Q Q方向延伸。则方向延伸。则R R穿越曲线穿越曲线C C的的交点和交点和W W经过经过Q Q的点一一对应。在数学上，当的点一一对应。在数学上，当R R从从C C的右边跨到的右边跨到左边时，穿越为正，左边跨到右边是，穿越为负。左边时，穿越为正，左边跨到右边是，穿越为负。v可以通过可以通过C C的一个法线矢量与方向矢量的一个法线矢量与方向矢量Q Q的数量积的符号来判的数量积的符号来判

23、断。断。v当曲线当曲线C C是多边形时，只需要对是多边形时，只需要对C C的每一条边做一次判断。对的每一条边做一次判断。对于射线于射线R R来讲，只要测试边的端点在射线来讲，只要测试边的端点在射线R R的上方还是下方就的上方还是下方就足够了。足够了。v如果边从射线的下方跨到上方，那么穿越如果边从射线的下方跨到上方，那么穿越+1+1，从上方跨到下，从上方跨到下方，是方，是-1.-1.然后只要把所有的穿越值加起来就得到环绕数。然后只要把所有的穿越值加起来就得到环绕数。4910.2 转角法5010.2 转角法v可以不用计算实际的射线和边的交点，但需要判断点可以不用计算实际的射线和边的交点，但需要判断

24、点P P是否是否在边的左边。在边的左边。v对于方向向上的边和向下的边的判断与在右边的规则不同。对于方向向上的边和向下的边的判断与在右边的规则不同。对于方向向上的边，如果穿过射线到达对于方向向上的边，如果穿过射线到达P P的右边，那么的右边，那么P P是在是在边的左边。方向向下的边如果穿越射线的正方向，那么边的左边。方向向下的边如果穿越射线的正方向，那么P P在在边的右边。边的右边。515210 判断点是否在多边形内v两种方法比较：v上图中，重叠区域的点被环绕两次，证明点在多边形内上图中，重叠区域的点被环绕两次，证明点在多边形内部两次，但射线法测试的结果为点在多边形外。环绕法部两次，但射线法测试

25、的结果为点在多边形外。环绕法的结果更加合理。的结果更加合理。53弧长法v弧长法要求多边形是有向多边形，一般规定沿多边弧长法要求多边形是有向多边形，一般规定沿多边形的正向，边的左侧为多边形的内侧域。形的正向，边的左侧为多边形的内侧域。v以被测点为圆心作单位圆，将全部有向边向单位圆以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其中单位圆上弧长的代数和。作径向投影，并计算其中单位圆上弧长的代数和。v若代数和为若代数和为0 0，则点在多边形外部；，则点在多边形外部；v若代数和为若代数和为2,2,则点在多边形内部；则点在多边形内部；v若代数和为若代数和为，则点在多边形上。，则点在多边形上。54弧长法v该算法只需该算法只需O(1)O(1)的附加空间，时间复杂度为的附加空间，时间复杂度为O(n)O(n)，但系数很小；最大的优点是具有很高的精度，只需但系数很小；最大的优点是具有很高的精度，只需做乘法和减法，若针对整数坐标则完全没有精度问做乘法和减法，若针对整数坐标则完全没有精度问题。而且实现起来也非常简单，比转角法和射线法题。