GIS算法的计算几何基础3

1、GIS算法的计算几何基础（3）河南大学环境与规划学院地理信息系统算法基础地理信息系统算法基础第第2章章2本讲内容 1.判断点是否在圆内判断点是否在圆内 2.判断线段、折线、矩形、多边判断线段、折线、矩形、多边形是否在圆内形是否在圆内 3.判断圆是否在圆内判断圆是否在圆内 4.计算两条共线的线段的交点计算两条共线的线段的交点 5.计算线段或直线与线段的交点计算线段或直线与线段的交点 6求线段或直线与圆的交点求线段或直线与圆的交点 7.中心点的计算中心点的计算 8.过点作垂线过点作垂线 9.作平行线作平行线 10.过点作平行线过点作平行线 11.线段延长线段延长 12.三点画圆三点画圆 13.线段

2、打断线段打断 14.前方交会前方交会 15.距离交会距离交会 16.极坐标作点极坐标作点 31.判断点是否在圆内判断点是否在圆内 计算圆心到该点的距离，如果小于或等于半径则该点在圆内。伪代码？伪代码？42.判断线段、折线、矩形、多边形是判断线段、折线、矩形、多边形是否在圆内否在圆内 圆是凸集，所以只要判断是否每个顶点都在圆内即可。 伪代码？伪代码？53.判断圆是否在圆内判断圆是否在圆内 设两圆为O1、O2半径分别为r1、r2，要判断O2是否在O1内。 先比较r1、r2的大小 如果r1r,则L和圆没有交点；利用勾股定理，可以求出两交点坐标，但要注意考虑L和圆的相切情况。146.求线段或直线与圆的

3、交点求线段或直线与圆的交点 第三步：如果L平行于x轴，做法与L平行于y轴的情况类似。 第四步：如果L既不平行x轴也不平行y轴，可以求出L的斜率K，然后列出L的点斜式方程，和圆方程联立即可求解出L和圆的两个交点。 第五步：如果L是线段，对于第二至第四步中求出的交点还要分别判断是否属于该线段的范围内。伪代码？伪代码？157.中心点的计算中心点的计算 多边形的中心点(又叫做质心或重心）可以通过将多边形分割成为三角形，求取三角形的中心点，然后将三角形的中心点加权求和取得。 权重的选取可以依据每个三角形的面积所占多边形面积的比例计算。 在实际计算中计算方法可以进行简化，不需要将多边形分割为一组三角形，但

4、需要利用在计算多边形面积时，三角形面积的取值为正或负的特性。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

5、，dy = yc-yp 第三步：按照如下公式求取E、F点： x xE E =x =xA A + dx, y + dx, yE E = y = yA A + dy + dy x xF F = x= xA A + dx+ dx，y yF F = y = yA A + dy + dy 第四步：连接E、F点，则线段EF为所求平行线。错误！错误！思考正确的算法？思考正确的算法？2010.过点作平行线过点作平行线 选择一条已有线段AB，选择点选择点P P，选一点C，以C点为端点作平行于线段AB的平行线CD，线段CD的长度与线段AB相等。 第一步：计算 dx = xB - xA, dy = yB - yA

6、第二步：判断点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/L yD =yB + (yB - yA) d/L 如果距A点最近，则D点的位置为： xD =xA + (xA xB)

7、d/L yD =yA + (yA - yB) d/L 第三步：连接D点与点A、B中距P点的最近点即为所求延长线。选择一条已有线段AB，选择点位为P，输入延长线距离d (d 0)，求取线段的延长线 22)()(ABAByyxxL思考：算法是否完善？思考：算法是否完善？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=2A(yc+yb)- B(xc-xb) 则圆心P的坐标为：xp =(DE - BF)/G yp =(AF - CE

8、)/G 第二步：求取圆半径R：通过已知三点a、b、c画圆算法的关键是求取圆心和圆半径。 22)()(papayyxxR2312.三点画圆三点画圆 其它方法？ 延伸：椭圆？抛物线？二次曲线的拟合？2413.线段打断线段打断 第一步：计算有向线段AB的长度 第二步：根据输入距离d计算内插点C。 yC =yA + (yB -yA） d/L xC = xA + (xB -xA) d/L选取已有线段AB，根据输入距离在线段内插入一个点C，并将线段分为两个部分。算法的关键关键是求取内插点的坐标。22)()(ABAByyxxL2514.前方交会前方交会 前方交会：在三角形ABP中，已知点A、B的坐标为xA、

9、yA和xB、yB。在A、B两点设站，测得PAB, PBA，解算出未知点P的坐标xp、yp,。2614.前方交会前方交会 如果AP的边长SAP和坐标方位角aAP为巳知，就可以按坐标正算公式求得P点的坐标，即： 从图可知，aAp = aAB - A，代入上式则得： APAPApAPAPApaSyyaSxxsincos或APAPApAPAPApaSyyaSxxsincos)sincoscos(sin)sin()sinsincos(cos)cos(AaAaSAaSyyAaAaSAaSxxABABAPABAPApABABAPABAPAp2714.前方交会前方交会 由于 则 根据正弦定理：ABABABAB

10、ABABSyyaSxxasincos)(cos)(sin)(cos)(sinABABABAPApABABABAPApxxAyySASyyyyAxxSASxx)sin(sinsinsinBABPBSSABAP2814.前方交会前方交会 则 则 移项简化得：BABABASASABAPcoscot1)sin(sinsinsinBAxxAyyyyBAyyAxxxxABABApABABApcotcot)(cot)(cotcot)(cot)(BAxxAyAyxBAyyAxAxxBABApBABApcotcot)cotcotcotcot)cotcot余切公式余切公式2915.距离交会距离交会 思路：由已知边

11、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=SABABabSglSghSlh2222223015.距离交会距离交会 可得：l=SAB-g，将等式两边取平方后代人上式得 整理得： 因为 以及22222ABbABSSgSghABbABaSSSSg2222ABaABbSSSSl22222222gSlShabhA1cothgB cotABABSgBABSBAAcotcotcot1cotcotcot3115.距离交会距离交会 将上式代入余切公式，可以求得P点的坐标： 式中)()()()(ABABApABABApxxHyyLyyyyHxxLxx22222222222222221ABbABaABABaABbABABaABbABSSSSSgGGSSLSSShHSSSSSL3216.极坐标作点极坐标作点 第一步：计算有向线段AB的长度L 第二步：根据有向线段