GIS算法的计算几何基础2题库.pptVIP

* 6.判断线段是否在多边形内 线段和多边形交于线段的两端点并不会影响线段是否在多边形内 但是如果多边形的某个顶点和线段相交，还必须判断两相邻交点之间的线段是否包含于多边形内部。 （a) (b) 图2.17线段和多边形关系举例 * 6.判断线段是否在多边形内 判断步骤： 求出所有线段和多边形边的交点; 按照X-Y坐标排序(X坐标小的排在前面，对于X坐标相同的点，Y坐标小的排在前面，这种排序准则也是为了保证水平和垂直情况的判断正确），这样相邻的两个点就是在线段上相邻的两交点; 计算任意相邻两点的中点; 如果任意相邻两点的中点也在多边形内，则该线段一定在多边形内。 * 6.判断线段是否在多边形内 命题1：如果线段和多边形的两相邻交点P1、P2的中点P’也在多边形内，则P1、P2之间的所有点都在多边形内。 证明(反证法）： 假设P1、P2之间含有不在多边形内的点Q 由于多边形是闭合曲线，所以其内外部之间有界，而P1属于多边形内部，Q属于多边形外部，P’属于多边形内部，P1-Q-P‘完全连续，所以P1Q和QP’一定跨越多边形的边界，因此在P1、P’之间至少还有两个该线段和多边形的交点 这和P1、P2是相邻两交点矛盾，故命题成立。证毕。 * 6.判断线段是否在多边形内 由命题1直接可得出推论： 推论2： 设多边形和线段PQ的交点依次为P1,P2,…,Pn，其中Pi和Pi+1是相邻两交点，线段PQ在多边形内的充要条件是：P、Q在多边形内且对于i = 1，2，…，n-1， PiPi+1的中点也在多边形内。 * 6.判断线段是否在多边形内 程序设计思路： 线段的两端点都在多边形内 判断线段和多边形的边是否内交 倘若线段和多边形的某条边内交则线段一定在多边形外 如果线段和多边形的每一条边都不内交，则线段和多边形的交点一定是线段的端点或者多边形的顶点，只要判断点是否在线段上就可以了。 * 6.判断线段是否在多边形内 这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n，所以最多是常数级的复杂度，几乎可以忽略不计。因此算法的时间复杂度也是O(n)。 伪代码 * 思考 如何判断线段与多边形是否相交？ * 7.判断折线是否在多边形内 只要判断折线的每条线段是否都在多边形内。 设折线有m条线段，多边 形有n个顶点，则该算法的时间复杂度为O( m×n)。 伪代码？ * 8.判断多边形是否在多边形内 只要判断多边形的每条边是否都在多边形内即可。 判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m×n)。 伪代码？ * 9.判断矩形是否在多边形内 将矩形转化为多边形，然后再判断是否在多边形内。 * 10.判断圆是否在多边形内 只要计算圆心到多边形的每条边的最短距离，如果该距离大于或等于圆半径则该圆在多边形内。 伪代码？ * 11.判断点是否在圆内 计算圆心到该点的距离，如果小于或等于半径则该点在圆内。 伪代码？ * 12.判断线段、折线、矩形、多边形是否在圆内 圆是凸集，所以只要判断是否每个顶点都在圆内即可。 伪代码？ * 13.判断圆是否在圆内 设两圆为O1、O2半径分别为r1、r2，要判断O2是否在O1内。 先比较r1、r2的大小 如果r1r2，则O2不可能在O1内 如果两圆心的距离大于r1-r2，则 O2不在O1内 反之O2在O1内。 伪代码？ * 14.计算两条共线的线段的交点 设L1是两条线段中较长的一条，L2是较短的一条 如果L1包含了 L2的两个端点，则是图 (d)的情况，两线段有无穷交点 如果L1只包含L2的一个端点，那么如果L1的某个端点等于被L1包含的 L2的那个端点，则是图 (c)的情况，这时两线段只有一个交点 否则就是图 (b)的情况，两线段也是有无穷的交点； 如果L1不包含L2的任何端点，则是图 (a)的情况，这时两线段没有交点。 伪代码？ * 15.计算线段或直线与线段的交点 设一条线段为L0 = P1P2，另一条线段或直线为L1 = Q1Q2，要计算的就是 L0和L1的交点。 第一步：判断L0和L1是否相交，如果不相交则没有交点，否则L0和L1一定有交点，下面就将L0和L1都看作直线来考虑。 第二步：如果P1和P2横坐标相同，即L0平行于y轴。 L0 L1 L0 L1 L0 L1 第三步：如果P1和P2横坐标不同，但是Q1和Q2横坐标相同，即L1平行于y轴，则交点横坐标为Q1的横坐标，代入到L0的直线方程中可以计算出交点纵坐标。 * 15.计算线段或直线与线段的交点 L1 L0 * 15.计算线段或直线与线段的交点 第四步：如果P1和P2纵坐标相同，即L0平行于x轴。 L0 L1 L0 L1 L0 L1 *