GIS算法基础

GIS算法的几何基础1维数扩展的9交集模型2矢量的概念3折线段的拐向判断4判断点是否在线段上5判断两线段是否相交6判断线段和直线是否相交7判断矩形是否包含点8判断线段、折线、多边形是否在矩形中9判断矩形是否在矩形中10判断圆是否在矩形中11判断点是否在多边形内12判断线段是否在多边形内第二章GIS算法的几何基础13判断折线是否在多边形内14判断多边形是否在多边形内15判断矩形是否在多边形内16判断圆是否在多边形内17判断点是否在圆内18判断线段、折线、矩形、多边形是否在圆内19判断圆是否在圆内20计算两条共线的线段的交点21计算线段或直线与线段的交点22求线段或直线与圆的交点1维数扩展的9交集模型(a)(b)多边形/多边形12(a)(b)12线/线。多边形/点·线/点多边形/线相接关系示例多边形/线线/线相交关系示例1维数扩展的9交集模型多边形/多边形多边形/线线/线·多边形/点真包含关系示意图多边形/多边形s1s2e1e2线/线叠置关系示例2矢量的概念(3-1)一、矢量的概念如果一条线段的端点是有次序之分的，我们把这种线段称为有向线段。如果有向线段P1P2的起点P1在坐标原点，我们可以把它成为矢量P2(如图)。P2OP1矢量的概念2矢量的概念(3-2)二、矢量加减法设二维矢量P=（x1,y1），Q=(x2,y2),则：QPP+Q矢量加法QP-QP矢量减法2矢量的概念(3-3)三、矢量叉积设二维矢量P=（x1,y1），Q=(x2,y2),则矢量叉积定义为：由(0,0)、P、Q和PQ所组成的平行四边形的带符号的面积，即：P×Q=x1·y2-x2·y1其结果是一个标量。显然有性质：P×Q=-(Q×P)和P×（-Q）=-(P×Q)叉积的一个非常重要的性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：(1)若P×Q0，则P在Q的顺时针方向；(2)若P×Q0，则P在Q的逆时针方向；(3)若P×Q=0，则P与Q共线，但可能同向也可能反向。3折线段的拐向判断折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2-p0)×(p1-p0)的符号便可以确定折线段的拐向：(1)若(p2-p0)×(p1-p0)0,则p0p1在p1点拐向右侧后得到p1p2。(2)若(p2-p0)×(p1-p0)0,则p0p1在p1点拐向左侧后得到p1p2。(3)若(p2-p0)×(p1-p0)=0,则p0、p1、p2三点共线。具体情况可参考下图：p0p1p2p1p2p0·p0p1p2(2)(1)(3)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)两个条件必须同时满足才能返回真值。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。上式可改写成(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)0。！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的依据是：(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)=0(3)同理判断Q1Q2跨立P1P2的依据是：(Q1-P1)×(P2-P1)*(P2-P1)×(Q2-P1)=0。具体情况如下图所示：5判断两线段是否相交(3-3)通过快速排斥试验通过快速排斥试验未通过快速排斥试验未通过快速排斥试验RP1P2Q1Q26判断线段和直线是否相交有了上面的基础，这个算法就很容易了。如果线段P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即：(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)=0。2.7判断矩形是否包含点只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。2.8判断线段、折线、多边形是否在矩形中因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。9判断矩形是否在矩形中只要比较左右边界和上下边界就可以了。10判断圆是否在矩形中很容易证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。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属于多边行。由此得出算法的伪代码如下：11判断点是否在多边形内P(a)(b)(c)(d)count←0;以P为端点，作从右向左的射线L;for多边形的每条边sdoifP在边s上thenreturntrue;ifs不是水平的thenifs的一个端点在L上if该端点所属的两边在射线L异侧thencount←count+1elseifs和L相交thencount←count+1;ifcountmod2=1thenreturntrue;elsereturnfalse;其中做射线L的方法是：设P‘的纵坐标和P相同，横坐标为正无穷大（很大的一个正数），则P和P'就确定了射线L。判断点是否在多边形中的这个算法的时间复杂度为O(n)。另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较，这种算法由于使用浮点数运算所以会带来一定误差，不推荐大家使用。11判断点是否在多边形内12判断线段是否在多边形内(5-1)线段在多边形内的一个必要条件是线段的两个端点都在多边形内，但由于多边形可能为凹，所以这不能成为判断的充分条件。如果线段和多边形的某条边内交（两线段内交是指两线段相交且交点不在两线段的端点），因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有一部分在多边形外(见图a)。于是我们得到线段在多边形内的第二个必要条件：线段和多边形的所有边都不内交。线段和多边形交于线段的两端点并不会影响线段是否在多边形内；但是如果多边形的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含于多边形内部（反例见图b)。(a)(b)12判断线段是否在多边形内(5-2)因此我们可以先求出所有和线段相交的多边形的顶点，然后按照X-Y坐标排序(X坐标小的排在前面，对于X坐标相同的点，Y坐标小的排在前面，这种排序准则也是为了保证水平和垂直情况的判断正确)，这样相邻的两个点就是在线段上相邻的两交点，如果任意相邻两点的中点也在多边形内，则该线段一定在多边形内。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是相邻两交点矛盾，故命题成立。证毕。12判断线段是否在多边形内(5-4)由命题1直接可得出推论：推论2：设多边形和线段PQ的交点依次为P1,P2,……Pn，其中Pi和Pi+1是相邻两交点，线段PQ在多边形内的充要条件是：P，Q在多边形内且对于i=1,2,……,n-1，Pi,Pi+1的中点也在多边形内。在实际编程中，没有必要计算所有的交点，首先应判断线段和多边形的边是否内交，倘若线段和多边形的某条边内交则线段一定在多边形外；如果线段和多边形的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。(5-5)至此我们得出算法如下：if线端PQ的端点不都在多边形内thenreturnfalse;else点集pointSet初始化为空;for多边形的每条边sdoif线段的某个端点在s上then将该端点加入pointSet;elseifs的某个端点在线段PQ上then将该端点加入pointSet;elseifs和线段PQ相交/*这时候已经可以肯定是内交了*/thenreturnfalse;else将pointSet中的点按照X-Y坐标排序;forpointSet中每两个相邻点pointSet[i],pointSet[i+1]doifpointSet[i],pointSet[i+1]的中点不在多边形中thenreturnfalse;elsereturntrue这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是常数级的复杂度，几乎可以忽略不计。因此算法的时间复杂度也是O(n)。13判断折线是否在多边形内只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段，多边形有n个顶点，则该算法的时间复杂度为O(m×n)。14判断多边形是否在多边形内只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m×n)。15判断矩形是否在多边形内将矩形转化为多边形，然后再判断是否在多边形内。16判断圆是否在多边形内只要计算圆心到多边形的每条边的最短距离，如果该距离大于等于圆半径则该圆在多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。17判断点是否在圆内计算圆心到该点的距离，如果小于等于半径则该点在圆内。18判断线段、折线、矩形、多边形是否在圆内因为圆是凸集，所以只要判断是否每个顶点都在圆内即可。19判断圆是否在圆内设两圆为O1,O2，半径分别为r1,r2，要判断O2是否在O1内。先比较r1，r2的大小，如果r1r2则O2不可能在O1内；否则如果两圆心的距离大于r1-r2，则O2不在O1内；否则O2在O1内。20计算两条共线的线段的交点(2-1)对于两条共线的线段，它们之间的位置关系有下图所示的几种情况。图(a)中两条线段没有交点；图(b)和(d)中两条线段有无穷焦点；图(c)中两条线段有一个交点。设line1是两条线段中较长的一