GIS算法的计算几何基础3

GIS算法的计算几何基础（3）河南大学环境与规划学院《地理信息系统算法基础》第2章2本讲内容1.判断点是否在圆内2.判断线段、折线、矩形、多边形是否在圆内3.判断圆是否在圆内4.计算两条共线的线段的交点5.计算线段或直线与线段的交点6求线段或直线与圆的交点

7.中心点的计算

8.过点作垂线9.作平行线10.过点作平行线

11.线段延长

12.三点画圆13.线段打断

14.前方交会

15.距离交会

16.极坐标作点

31.判断点是否在圆内

计算圆心到该点的距离，如果小于或等于半径则该点在圆内。伪代码？42.判断线段、折线、矩形、多边形是否在圆内

圆是凸集，所以只要判断是否每个顶点都在圆内即可。

伪代码？53.判断圆是否在圆内

设两圆为O1、O2半径分别为r1、r2，要判断O2是否在O1内。先比较r1、r2的大小如果r1<r2，则O2不可能在O1内如果两圆心的距离大于r1-r2，则O2不在O1内反之O2在O1内。伪代码？64.计算两条共线的线段的交点

设L1是两条线段中较长的一条，L2是较短的一条如果L1包含了L2的两个端点，则是图(d)的情况，两线段有无穷交点如果L1只包含L2的一个端点，那么如果L1的某个端点等于被L1包含的L2的那个端点，则是图(c)的情况，这时两线段只有一个交点否则就是图(b)的情况，两线段也是有无穷的交点；如果L1不包含L2的任何端点，则是图(a)的情况，这时两线段没有交点。伪代码？75.计算线段或直线与线段的交点

设一条线段为L0=P1P2，另一条线段或直线为L1=Q1Q2，要计算的就是L0和L1的交点。第一步：判断L0和L1是否相交，如果不相交则没有交点，否则L0和L1一定有交点，下面就将L0和L1都看作直线来考虑。第二步：如果P1和P2横坐标相同，即L0平行于y轴。L0L1L0L1L0L1第三步：如果P1和P2横坐标不同，但是Q1和Q2横坐标相同，即L1平行于y轴，则交点横坐标为Q1的横坐标，代入到L0的直线方程中可以计算出交点纵坐标。85.计算线段或直线与线段的交点L1L095.计算线段或直线与线段的交点第四步：如果P1和P2纵坐标相同，即L0平行于x轴。L0L1L0L1L0L1105.计算线段或直线与线段的交点第五步：如果P1和P2纵坐标不同，但是Q1和Q2纵坐标相同，即L1平行于x轴，则交点纵坐标为Q1的纵坐标，代入到L0的直线方程中可以计算出交点横坐标。L1L0115.计算线段或直线与线段的交点第六步：剩下的情况就是L1和L0的斜率均存在且不为零的情况。计算出L0的斜率K0，L1的斜率K1；如果K1=K2，则有两种情况：第一种情况：如果Q1在L0上，则说明L0和L1共线，假如L1是直线，则有无穷交点，假如L1是线段，可用“计算两条共线线段的交点”的算法求交点；第二种情况：如果Q1不在L0上，则说明L0和L1平行，则没有交点。联立两直线的方程组可以解出交点来。125.计算线段或直线与线段的交点这个算法并不复杂，但是要分情况讨论清楚，尤其是当两条线段共线的情况需要单独考虑，所以在前文将求两条共线线段的算法单独写出来。另外，一开始就先利用矢量叉乘判断线段与线段(或直线)是否相交，如果结果是相交，那么在后面就可以将线段全部看作直线来考虑。需要注意的是，我们可以将直线或线段方程改写为ax+by+c=0的形式，这样一来上述过程的部分步骤可以合并，缩短了代码长度，但是由于先要求出参数，这种算法将花费更多的时间。伪代码？136.求线段或直线与圆的交点

设圆心为O，圆半径为r，直线(或线段)L上的两点为P1，P2。第一步：如果L是线段且P1、P2都包含在圆O内，则没有交点；否则进行下一步。第二步：如果L平行于y轴。计算圆心到L的距离d；如果d>r,则L和圆没有交点；利用勾股定理，可以求出两交点坐标，但要注意考虑L和圆的相切情况。146.求线段或直线与圆的交点第三步：如果L平行于x轴，做法与L平行于y轴的情况类似。第四步：如果L既不平行x轴也不平行y轴，可以求出L的斜率K，然后列出L的点斜式方程，和圆方程联立即可求解出L和圆的两个交点。第五步：如果L是线段，对于第二至第四步中求出的交点还要分别判断是否属于该线段的范围内。伪代码？157.中心点的计算

多边形的中心点(又叫做质心或重心）可以通过将多边形分割成为三角形，求取三角形的中心点，然后将三角形的中心点加权求和取得。权重的选取可以依据每个三角形的面积所占多边形面积的比例计算。在实际计算中计算方法可以进行简化，不需要将多边形分割为一组三角形，但需要利用在计算多边形面积时，三角形面积的取值为正或负的特性。167.中心点的计算177.中心点的计算01230(3,1)1(3,2)2(1,2)3(1,1)188.过点作垂线

选取一点C，选择一条线段AB，求取过点C垂直于AB的垂线段CP，P点位于直线AB上。第一步：求取点C到直线AB的垂点P；第二步：连接CP，则CP为所求垂线。伪代码？199.作平行线

选择一条已有线段AB，选一点C确定方向，输入距离d，在所选方向上按照输入的距离复制与所选线段一样的线段EF

。第一步：求取点C到直线AB的垂点P；第二步：计算

dx=xc-xp，dy=yc-yp第三步：按照如下公式求取E、F点：

xE=xA+dx,yE=yA+dyxF=xA+dx，yF=yA+dy第四步：连接E、F点，则线段EF为所求平行线。错误！！！思考正确的算法？2010.过点作平行线

选择一条已有线段AB，选择点P，选一点C，以C点为端点作平行于线段AB的平行线CD，线段CD的长度与线段AB相等。第一步：计算

dx=xB-xA,dy=yB-yA

第二步：判断点A和点B距P点距离最近点。如果距A点最近，则D点的位置为：

xD=xc+dx，yD=yc+dy

如果距B点最近，则D点的位置为：

xD=xc-dx，yD=yc—dy第三步：连接C、D点，则线段CD为所求平行线。伪代码？思考：线段CD是否唯一？2111.线段延长

第一步：求取线段AB的长度第二步：判断点A和点B距P点距离最近点。如果距B点最近，则D点的位置为：

xD=xB+(xB—xA)•d/LyD=yB+(yB-yA)•d/L

如果距A点最近，则D点的位置为：

xD=xA+(xA—xB)•d/LyD=yA+(yA-yB)•d/L

第三步：连接D点与点A、B中距P点的最近点即为所求延长线。选择一条已有线段AB，选择点位为P，输入延长线距离d(d>0)，求取线段的延长线思考：算法是否完善？2212.三点画圆

第一步：求取圆心P。设三点为a、b、c，则令：A=xb-xa，B=yb-ya，C=xc-yc，D=yc-ya，E=A(xa+xb)+B(ya+yb)，F=C(xa+xc)+D(ya+yc)G=2[A(yc+yb)-B(xc-xb)]则圆心P的坐标为：xp=(DE-BF)/Gyp=(AF-CE)/G第二步：求取圆半径R：通过已知三点a、b、c画圆算法的关键是求取圆心和圆半径。

2312.三点画圆其它方法？延伸：椭圆？抛物线？二次曲线的拟合？2413.线段打断

第一步：计算有向线段AB的长度第二步：根据输入距离d计算内插点C。

yC=yA+(yB-yA）•d/LxC=xA+(xB-xA)•d/L选取已有线段AB，根据输入距离在线段内插入一个点C，并将线段分为两个部分。算法的关键是求取内插点的坐标。2514.前方交会前方交会：在三角形ABP中，已知点A、B的坐标为xA、yA和xB、yB。在A、B两点设站，测得∠PAB,∠PBA，解算出未知点P的坐标xp、yp,。2614.前方交会如果AP的边长SAP和坐标方位角aAP为巳知，就可以按坐标正算公式求得P点的坐标，即：从图可知，aAp=aAB-A，代入上式则得：

或2714.前方交会由于则根据正弦定理：2814.前方交会则则移项简化得：余切公式2915.距离交会

思路：由已知边SAB和观测边长Sa、Sb，推出l、g、h，从而算出∠A、∠B，并按余切公式求P点坐标。

由图可知：已知点A、B的坐标分别为xA、yA和xB、yB，A与B间的已知长为SAB。测量了边长Sa、Sb。在△ABP中，AB边的高为h,而高h将AB边分成l和g两段，显然l+g=SAB3015.距离交会可得：l=SAB-g，将等式两边取平方后代人上式得

整理得：因为以及3115.距离交会将上式