GIS算法的计算几何基础2.ppt

1、1,GIS算法的计算几何基础(2),GIS算法基础第二章,2,本 讲 内 容,1 判断矩形是否包含点 2 判断线段、折线、多边形是否在矩形中 3 判断矩形是否在矩形中 4 判断圆是否在矩形中 5 判断点是否在多边形内 6 判断线段是否在多边形内 7 判断折线是否在多边形内 8 判断多边形是否在多边形内 9 判断矩形是否在多边形内 10 判断圆是否在多边形内,3,本 讲 内 容,11 判断点是否在圆内 12 判断线段、折线、矩形、多边形是否在圆内 13 判断圆是否在圆内 14 计算两条共线的线段的交点 15 计算线段或直线与线段的交点,4,1 矩形是否包含点,只要判断点的横坐标与纵坐标是否夹在矩

2、形的左右边和上下边之间。,5,2判断线段、折线、多边形是否在矩形中,矩形是凸集，所以只需判断所有的端点是否在矩形中。,6,3 判断矩形是否在矩形中,比较左右边界和上下边界,7,4 判断圆是否在矩形中,圆心在矩形中，且圆的半径小于等于圆心到矩形四边的距离的最小值。,8,常用算法： 射线法（奇偶法） 转角法：环绕数（多边形环绕点的次数）为0，则点在多边形外，否则，点在多边形内。,5 判断点是否在多边形内,9,5.1 射线法,射线法计算从点P开始的射线穿过多边形边界的次数，多边形的边界将多边形内部与外部分开。如果结果为偶数，则点在多边形外部，否则，若为奇数，则点在多边形内部。,10,5.1 射线法,

3、必须决定在多边形边界上的点是在多边形内部还是外部。一个标准的约定是在左边界或者下边界上的点认为是在多边形内部，在右边界或者上边界的点认为是在多边形外部。在这种约定下，如果两个不同的多边形共享一个边，那么在这条边上的点会在一个多边形的内部而在另一个多边形的外部。,11,5.1 射线法,一个简单的射线法是选择一条水平的、向点P的右侧延伸的、平行于X轴的射线。 为了计算总的交点的数目，算法简单的遍历多边形的所有边，测试是否穿越边，穿越时增加交点的数目。 穿越测试必须处理好一些特殊的情形。完全规则如下： （1）方向向上的边包括其开始点，不包括其终止点； （2）方向向下的边不包括其开始点，包括其终止点；

4、 （3）水平边不参加穿越测试； （4）射线和多边形的边的交点必须严格在点P的右边。,12,5.1 射线法,13,5.1 射线法,射线法的有效性是基于一个简单的闭合曲线将二维平面分成两个相连接的部分：有边界的内部和无边界的外部。 曲线必须是简单的（没有自相交），否则平面会被分成两个以上的部分，并且不能保证穿越边界时不会改变出入特性。 对于一个闭合的曲线，可能将二维平面分成多个部分，但是其中只有一个没有边界且在曲线外部的部分。 有边界的部分可能在曲线内部也可能在曲线外部。 两个有共同边界的有边界部分可能都在曲线内部，那么穿越过共享的边界并不会改变出入特性。,14,5 判断点是否在多边形内,判断出现

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

6、7,5.2 转角法,若曲线C是由顶点V0,V1,Vn=V0构成的多边形，那么积分可以简化为计算带符号的角度的总和。这些角PVi与PVi+1的夹角。因此，如果i=angle(PVi,PVi+1),则 这个公式效率不高，原因在于arccos函数很耗时。 改进：在S1中任取一点Q，因为曲线W(u)环绕，则可能多次经过Q点。当W(u)按逆时针方向经过Q点时，记为+1次，顺时针经过Q点时，记为-1次，那么总次数和就是W环绕S1的次数，刚好等于环绕数（wn）。,18,5.2 转角法,用一个射线R，R的起点为P并向Q方向延伸。则R穿越曲线C的交点和W经过Q的点一一对应。在数学上，当R从C的右边跨到左边时，穿

7、越为正，左边跨到右边是，穿越为负。 可以通过C的一个法线矢量与方向矢量Q的数量积的符号来判断。 当曲线C是多边形时，只需要对C的每一条边做一次判断。对于射线R来讲，只要测试边的端点在射线R的上方还是下方就足够了。 如果边从射线的下方跨到上方，那么穿越+1，从上方跨到下方，是-1.然后只要把所有的穿越值加起来就得到环绕数。,19,5.2 转角法,20,5.2 转角法,可以不用计算实际的射线和边的交点，但需要判断点P是否在边的左边。 对于方向向上的边和向下的边的判断与在右边的规则不同。对于方向向上的边，如果穿过射线到达P的右边，那么P是在边的左边。方向向下的边如果穿越射线的正方向，那么P在边的右边

8、。,21,22,5 判断点是否在多边形内,两种方法比较：,上图中，重叠区域的点被环绕两次，证明点在多边形内部两次，但射线法测试的结果为点在多边形外。环绕法的结果更加合理。,23,弧长法,弧长法要求多边形是有向多边形，一般规定沿多边形的正向，边的左侧为多边形的内侧域。 以被测点为圆心作单位圆，将全部有向边向单位圆作径向投影，并计算其中单位圆上弧长的代数和。 若代数和为0，则点在多边形外部； 若代数和为2,则点在多边形内部； 若代数和为，则点在多边形上。,24,弧长法,该算法只需O(1)的附加空间，时间复杂度为O(n)，但系数很小；最大的优点是具有很高的精度，只需做乘法和减法，若针对整数坐标则完全

9、没有精度问题。而且实现起来也非常简单，比转角法和射线法都要好写且不易出错。,25,弧长法,将坐标原点平移到被测点P，这个新坐标系将平面划分为4个象限，对每个多边形顶点P ，只考虑其所在的象限，然后按邻接顺序访问多边形的各个顶点Pi，分析Pi和Pi+1，有下列三种情况： （1）Pi+1在Pi的下一象限。此时弧长和加/2；（2）Pi+1在Pi的上一象限。此时弧长和减/2；（3）Pi+1在Pi的相对象限。 首先计算f=yi+1*x-xi+1*y（叉积）， 若f=0，则点在多边形上； 若f0，弧长和加。最后对算出的代数和和上述的情况一样判断即可。,26,射线法流程图,27,射线法流程图解释,1.已知点

10、point(x,y)和多边形Polygon(x1,y1;x2,y2;.xn,yn;)； 2.以point为起点，以无穷远为终点作平行于X轴的直线line(x,y; -,y)； 3.循环取得(for(i=0;in;i+)多边形的每一条边side(xi,yi; xi+1,yi+1)，且判断是否平行于X轴，如果不平行continue，否则，i+； 4.同时判断point(x,y)是否在side上，如果是，则返回1(点在多边形上)，否则继续下面的判断； 5. 判断线side与line是否有交点，如果有则count+，否则，i+。 6. 判断交点的总数，如果为奇数则返回0（点在多边形内），偶数则返回2（

11、点在多边形外）。,28,铅垂线法,29,6.判断线段是否在多边形内,线段在多边形内 线段的两个端点在多边形内 两种情况： 多边形为凸多边形：充要条件 多边形为凹多边形：必要条件 定义： 线段内交：两线段相交且交点不在两线段的端点。 线段和多边形的某条边内交，因为多边形的边的左右两侧分属多边形内外不同部分，所以线段一定会有一部分在多边形外。 线段和多边形所有边都不内交。,必要条件1,必要条件2,30,6.判断线段是否在多边形内,线段和多边形交于线段的两端点并不会影响线段是否在多边形内 但是如果多边形的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含于多边形内部。,（a) (b) 图2.

12、17线段和多边形关系举例,31,6.判断线段是否在多边形内,判断步骤： 求出所有线段和多边形边的交点; 按照X-Y坐标排序(X坐标小的排在前面，对于X坐标相同的点，Y坐标小的排在前面，这种排序准则也是为了保证水平和垂直情况的判断正确），这样相邻的两个点就是在线段上相邻的两交点; 计算任意相邻两点的中点; 如果任意相邻两点的中点也在多边形内，则该线段一定在多边形内。,32,6.判断线段是否在多边形内,命题1：如果线段和多边形的两相邻交点P1、P2的中点P也在多边形内，则P1、P2之间的所有点都在多边形内。 证明(反证法）： 假设P1、P2之间含有不在多边形内的点Q 由于多边形是闭合曲线，所以其内

13、外部之间有界，而P1属于多边形内部，Q属于多边形外部，P属于多边形内部，P1-Q-P完全连续，所以P1Q和QP一定跨越多边形的边界，因此在P1、P之间至少还有两个该线段和多边形的交点 这和P1、P2是相邻两交点矛盾，故命题成立。证毕。,33,6.判断线段是否在多边形内,由命题1直接可得出推论： 推论2： 设多边形和线段PQ的交点依次为P1,P2,Pn，其中Pi和Pi+1是相邻两交点，线段PQ在多边形内的充要条件是：P、Q在多边形内且对于i = 1，2，n-1， PiPi+1的中点也在多边形内。,34,6.判断线段是否在多边形内,程序设计思路： 线段的两端点都在多边形内 判断线段和多边形的边是否

14、内交 倘若线段和多边形的某条边内交则线段一定在多边形外 如果线段和多边形的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。,35,6.判断线段是否在多边形内,这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是常数级的复杂度，几乎可以忽略不计。因此算法的时间复杂度也是O(n)。,伪代码,36,思考,如何判断线段与多边形是否相交？,37,7.判断折线是否在多边形内,只要判断折线的每条线段是否都在多边形内。 设折线有m条线段，多边 形有n个顶点，则该算法的时间复杂度为O( mn)。,伪代码？,38,8.判断多边形是否在多边形内

15、,只要判断多边形的每条边是否都在多边形内即可。 判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(mn)。,伪代码？,39,9.判断矩形是否在多边形内,将矩形转化为多边形，然后再判断是否在多边形内。,40,10.判断圆是否在多边形内,只要计算圆心到多边形的每条边的最短距离，如果该距离大于或等于圆半径则该圆在多边形内。,伪代码？,41,11.判断点是否在圆内,计算圆心到该点的距离，如果小于或等于半径则该点在圆内。,伪代码？,42,12.判断线段、折线、矩形、多边形是否在圆内,圆是凸集，所以只要判断是否每个顶点都在圆内即可。,伪代码？,43,13.判断圆是否在圆内,设两圆为O1、

16、O2半径分别为r1、r2，要判断O2是否在O1内。 先比较r1、r2的大小 如果r1r2，则O2不可能在O1内 如果两圆心的距离大于r1-r2，则 O2不在O1内 反之O2在O1内。,伪代码？,44,14.计算两条共线的线段的交点,设L1是两条线段中较长的一条，L2是较短的一条 如果L1包含了 L2的两个端点，则是图 (d)的情况，两线段有无穷交点 如果L1只包含L2的一个端点，那么如果L1的某个端点等于被L1包含的 L2的那个端点，则是图 (c)的情况，这时两线段只有一个交点 否则就是图 (b)的情况，两线段也是有无穷的交点； 如果L1不包含L2的任何端点，则是图 (a)的情况，这时两线段没

17、有交点。,伪代码？,45,15.计算线段或直线与线段的交点,设一条线段为L0 = P1P2，另一条线段或直线为L1 = Q1Q2，要计算的就是 L0和L1的交点。 第一步：判断L0和L1是否相交，如果不相交则没有交点，否则L0和L1一定有交点，下面就将L0和L1都看作直线来考虑。 第二步：如果P1和P2横坐标相同，即L0平行于y轴。,第三步：如果P1和P2横坐标不同，但是Q1和Q2横坐标相同，即L1平行于y轴，则交点横坐标为Q1的横坐标，代入到L0的直线方程中可以计算出交点纵坐标。,46,15.计算线段或直线与线段的交点,L1,L0,47,15.计算线段或直线与线段的交点,第四步：如果P1和P

18、2纵坐标相同，即L0平行于x轴。,L0,L1,L0,L1,L0,L1,48,15.计算线段或直线与线段的交点,第五步：如果P1和P2纵坐标不同，但是Q1和Q2纵坐标相同，即L1平行于x轴，则交点纵坐标为Q1的纵坐标，代入到L0的直线方程中可以计算出交点横坐标。,L1,L0,49,15.计算线段或直线与线段的交点,第六步：剩下的情况就是L1和L0的斜率均存在且不为零的情况。 计算出L0的斜率K0，L1的斜率K1； 如果K1=K2，则有两种情况： 第一种情况：如果Q1在L0上，则说明L0和L1共线，假如L1是直线，则有无穷交点，假如L1是线段，可用“计算两条共线线段的交点”的算法求交点； 第二种情况：如果Q1