GIS算法的计算几何基础3.pptVIP

* 15.距离交会 将上式代入余切公式，可以求得P点的坐标： 式中 * 16.极坐标作点 第一步：计算有向线段AB的长度L 第二步：根据有向线段AB坐标计算 dx = xB — XA ，dy = yB — yA 第三步：以A点义为基点旋转有向线段AB，则 第四步：求取P点坐标 选择已有线段AB，以已有线段为极轴，输入角度a和长度d求点P坐标。 16.极坐标作点 绕原点旋转 * 16.极坐标作点 绕指定点旋转 * GIS算法的计算几何基础（3） 河南大学环境与规划学院 《地理信息系统算法基础》第2章 * 本讲内容 1.判断点是否在圆内 2.判断线段、折线、矩形、多边形是否在圆内 3.判断圆是否在圆内 4.计算两条共线的线段的交点 5.计算线段或直线与线段的交点 6求线段或直线与圆的交点 7.中心点的计算 8.过点作垂线 9.作平行线 10.过点作平行线 11.线段延长 12.三点画圆 13.线段打断 14.前方交会 15.距离交会 16.极坐标作点 * 1.判断点是否在圆内 计算圆心到该点的距离，如果小于或等于半径则该点在圆内。 伪代码？ * 2.判断线段、折线、矩形、多边形是否在圆内 圆是凸集，所以只要判断是否每个顶点都在圆内即可。 伪代码？ * 3.判断圆是否在圆内 设两圆为O1、O2半径分别为r1、r2，要判断O2是否在O1内。 先比较r1、r2的大小 如果r1r2，则O2不可能在O1内 如果两圆心的距离大于r1-r2，则 O2不在O1内 反之O2在O1内。 伪代码？ * 4.计算两条共线的线段的交点 设L1是两条线段中较长的一条，L2是较短的一条 如果L1包含了 L2的两个端点，则是图 (d)的情况，两线段有无穷交点 如果L1只包含L2的一个端点，那么如果L1的某个端点等于被L1包含的 L2的那个端点，则是图 (c)的情况，这时两线段只有一个交点 否则就是图 (b)的情况，两线段也是有无穷的交点； 如果L1不包含L2的任何端点，则是图 (a)的情况，这时两线段没有交点。 伪代码？ * 5.计算线段或直线与线段的交点 设一条线段为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的直线方程中可以计算出交点纵坐标。 * 5.计算线段或直线与线段的交点 L1 L0 * 5.计算线段或直线与线段的交点 第四步：如果P1和P2纵坐标相同，即L0平行于x轴。 L0 L1 L0 L1 L0 L1 * 5.计算线段或直线与线段的交点 第五步：如果P1和P2纵坐标不同，但是Q1和Q2纵坐标相同，即L1平行于x轴，则交点纵坐标为Q1的纵坐标，代入到L0的直线方程中可以计算出交点横坐标。 L1 L0 * 5.计算线段或直线与线段的交点 第六步：剩下的情况就是L1和L0的斜率均存在且不为零的情况。 计算出L0的斜率K0，L1的斜率K1； 如果K1=K2，则有两种情况： 第一种情况：如果Q1在L0上，则说明L0和L1共线，假如L1是直线，则有无穷交点，假如L1是线段，可用“计算两条共线线段的交点”的算法求交点； 第二种情况：如果Q1不在 L0上，则说明L0和L1平行，则没有交点。 联立两直线的方程组可以解出交点来。 * 5.计算线段或直线与线段的交点 这个算法并不复杂，但是要分情况讨论清楚，尤其是当两条线段共线的情况需要单独考虑，所以在前文将求两条共线线段的算法单独写出来。 另外，一开始就先利用矢量叉乘判断线段与线段(或直线)是否相交，如果结果是相交，那么在后面就可以将线段全部看作直线来考虑。 需要注意的是，我们可以将直线或线段方程改写为ax + by + c = 0的形式，这样一来上述过程的部分步骤可以合并，缩短了代码长度，但是由于先要求出参数，这种算法将花费更多的时间。 伪代码？ * 6.求线段或直线与圆的交点 设圆心为O，圆半径为r，直线(或线段)L上的两点为P1，P2。 第一步：如果L是线段且P1、P2都包含在圆O内，则没有交点；否则进行下一步。 第二步：如果L平行于y轴。 计算圆心到L的距离d； 如果dr,则L和圆没有交点； 利用勾股定理，可以求出两交点坐标，但要注意考虑L和圆的相切情况。 * 6.求线段或直线与圆的交点 第三步：如果L平行于x轴，做法与L平行于y轴的情况类似。 第四步：如果L既不