GIS算法的計算幾何基礎3

1、GIS算法的計算幾何基礎（3）河南大學環(huán)境與規(guī)劃學院地理信息系統(tǒng)算法基礎地理信息系統(tǒng)算法基礎第第2章章2本講內(nèi)容 1.判斷點是否在圓內(nèi)判斷點是否在圓內(nèi) 2.判斷線段、折線、矩形、多邊判斷線段、折線、矩形、多邊形是否在圓內(nèi)形是否在圓內(nèi) 3.判斷圓是否在圓內(nèi)判斷圓是否在圓內(nèi) 4.計算兩條共線的線段的交點計算兩條共線的線段的交點 5.計算線段或直線與線段的交點計算線段或直線與線段的交點 6求線段或直線與圓的交點求線段或直線與圓的交點 7.中心點的計算中心點的計算 8.過點作垂線過點作垂線 9.作平行線作平行線 10.過點作平行線過點作平行線 11.線段延長線段延長 12.三點畫圓三點畫圓 13.線段

2、打斷線段打斷 14.前方交會前方交會 15.距離交會距離交會 16.極坐標作點極坐標作點 31.判斷點是否在圓內(nèi)判斷點是否在圓內(nèi) 計算圓心到該點的距離，如果小于或等于半徑則該點在圓內(nèi)。偽代碼？偽代碼？42.判斷線段、折線、矩形、多邊形是判斷線段、折線、矩形、多邊形是否在圓內(nèi)否在圓內(nèi) 圓是凸集，所以只要判斷是否每個頂點都在圓內(nèi)即可。 偽代碼？偽代碼？53.判斷圓是否在圓內(nèi)判斷圓是否在圓內(nèi) 設兩圓為O1、O2半徑分別為r1、r2，要判斷O2是否在O1內(nèi)。 先比較r1、r2的大小 如果r1r,則L和圓沒有交點；利用勾股定理，可以求出兩交點坐標，但要注意考慮L和圓的相切情況。146.求線段或直線與圓的

3、交點求線段或直線與圓的交點 第三步：如果L平行于x軸，做法與L平行于y軸的情況類似。 第四步：如果L既不平行x軸也不平行y軸，可以求出L的斜率K，然后列出L的點斜式方程，和圓方程聯(lián)立即可求解出L和圓的兩個交點。 第五步：如果L是線段，對于第二至第四步中求出的交點還要分別判斷是否屬于該線段的范圍內(nèi)。偽代碼？偽代碼？157.中心點的計算中心點的計算 多邊形的中心點(又叫做質(zhì)心或重心）可以通過將多邊形分割成為三角形，求取三角形的中心點，然后將三角形的中心點加權求和取得。 權重的選取可以依據(jù)每個三角形的面積所占多邊形面積的比例計算。 在實際計算中計算方法可以進行簡化，不需要將多邊形分割為一組三角形，但

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(xiàn)=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的長度 第二步：根據(jù)輸入距離d計算內(nèi)插點C。 yC =yA + (yB -yA） d/L xC = xA + (xB -xA) d/L選取已有線段AB，根據(jù)輸入距離在線段內(nèi)插入一個點C，并將線段分為兩個部分。算法的關鍵關鍵是求取內(nèi)插點的坐標。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.前方交會前方交會 由于 則 根據(jù)正弦定理：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 第二步：根據(jù)有向線段