GIS算法的計算幾何基礎(chǔ)3

GIS算法的計算幾何基礎(chǔ)（3）河南大學(xué)環(huán)境與規(guī)劃學(xué)院《地理信息系統(tǒng)算法基礎(chǔ)》第2章2本講內(nèi)容1.判斷點是否在圓內(nèi)2.判斷線段、折線、矩形、多邊形是否在圓內(nèi)3.判斷圓是否在圓內(nèi)4.計算兩條共線的線段的交點5.計算線段或直線與線段的交點6求線段或直線與圓的交點

7.中心點的計算

8.過點作垂線9.作平行線10.過點作平行線

11.線段延長

12.三點畫圓13.線段打斷

14.前方交會

15.距離交會

16.極坐標(biāo)作點

31.判斷點是否在圓內(nèi)

計算圓心到該點的距離，如果小于或等于半徑則該點在圓內(nèi)。偽代碼？42.判斷線段、折線、矩形、多邊形是否在圓內(nèi)

圓是凸集，所以只要判斷是否每個頂點都在圓內(nèi)即可。

偽代碼？53.判斷圓是否在圓內(nèi)

設(shè)兩圓為O1、O2半徑分別為r1、r2，要判斷O2是否在O1內(nèi)。先比較r1、r2的大小如果r1<r2，則O2不可能在O1內(nèi)如果兩圓心的距離大于r1-r2，則O2不在O1內(nèi)反之O2在O1內(nèi)。偽代碼？64.計算兩條共線的線段的交點

設(shè)L1是兩條線段中較長的一條，L2是較短的一條如果L1包含了L2的兩個端點，則是圖(d)的情況，兩線段有無窮交點如果L1只包含L2的一個端點，那么如果L1的某個端點等于被L1包含的L2的那個端點，則是圖(c)的情況，這時兩線段只有一個交點否則就是圖(b)的情況，兩線段也是有無窮的交點；如果L1不包含L2的任何端點，則是圖(a)的情況，這時兩線段沒有交點。偽代碼？75.計算線段或直線與線段的交點

設(shè)一條線段為L0=P1P2，另一條線段或直線為L1=Q1Q2，要計算的就是L0和L1的交點。第一步：判斷L0和L1是否相交，如果不相交則沒有交點，否則L0和L1一定有交點，下面就將L0和L1都看作直線來考慮。第二步：如果P1和P2橫坐標(biāo)相同，即L0平行于y軸。L0L1L0L1L0L1第三步：如果P1和P2橫坐標(biāo)不同，但是Q1和Q2橫坐標(biāo)相同，即L1平行于y軸，則交點橫坐標(biāo)為Q1的橫坐標(biāo)，代入到L0的直線方程中可以計算出交點縱坐標(biāo)。85.計算線段或直線與線段的交點L1L095.計算線段或直線與線段的交點第四步：如果P1和P2縱坐標(biāo)相同，即L0平行于x軸。L0L1L0L1L0L1105.計算線段或直線與線段的交點第五步：如果P1和P2縱坐標(biāo)不同，但是Q1和Q2縱坐標(biāo)相同，即L1平行于x軸，則交點縱坐標(biāo)為Q1的縱坐標(biāo)，代入到L0的直線方程中可以計算出交點橫坐標(biāo)。L1L0115.計算線段或直線與線段的交點第六步：剩下的情況就是L1和L0的斜率均存在且不為零的情況。計算出L0的斜率K0，L1的斜率K1；如果K1=K2，則有兩種情況：第一種情況：如果Q1在L0上，則說明L0和L1共線，假如L1是直線，則有無窮交點，假如L1是線段，可用“計算兩條共線線段的交點”的算法求交點；第二種情況：如果Q1不在L0上，則說明L0和L1平行，則沒有交點。聯(lián)立兩直線的方程組可以解出交點來。125.計算線段或直線與線段的交點這個算法并不復(fù)雜，但是要分情況討論清楚，尤其是當(dāng)兩條線段共線的情況需要單獨考慮，所以在前文將求兩條共線線段的算法單獨寫出來。另外，一開始就先利用矢量叉乘判斷線段與線段(或直線)是否相交，如果結(jié)果是相交，那么在后面就可以將線段全部看作直線來考慮。需要注意的是，我們可以將直線或線段方程改寫為ax+by+c=0的形式，這樣一來上述過程的部分步驟可以合并，縮短了代碼長度，但是由于先要求出參數(shù)，這種算法將花費更多的時間。偽代碼？136.求線段或直線與圓的交點

設(shè)圓心為O，圓半徑為r，直線(或線段)L上的兩點為P1，P2。第一步：如果L是線段且P1、P2都包含在圓O內(nèi)，則沒有交點；否則進行下一步。第二步：如果L平行于y軸。計算圓心到L的距離d；如果d>r,則L和圓沒有交點；利用勾股定理，可以求出兩交點坐標(biāo)，但要注意考慮L和圓的相切情況。146.求線段或直線與圓的交點第三步：如果L平行于x軸，做法與L平行于y軸的情況類似。第四步：如果L既不平行x軸也不平行y軸，可以求出L的斜率K，然后列出L的點斜式方程，和圓方程聯(lián)立即可求解出L和圓的兩個交點。第五步：如果L是線段，對于第二至第四步中求出的交點還要分別判斷是否屬于該線段的范圍內(nèi)。偽代碼？157.中心點的計算

多邊形的中心點(又叫做質(zhì)心或重心）可以通過將多邊形分割成為三角形，求取三角形的中心點，然后將三角形的中心點加權(quán)求和取得。權(quán)重的選取可以依據(jù)每個三角形的面積所占多邊形面積的比例計算。在實際計算中計算方法可以進行簡化，不需要將多邊形分割為一組三角形，但需要利用在計算多邊形面積時，三角形面積的取值為正或負(fù)的特性。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，在所選方向上按照輸入的距離復(fù)制與所選線段一樣的線段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。設(shè)三點為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=2[A(yc+yb)-B(xc-xb)]則圓心P的坐標(biāo)為：xp=(DE-BF)/Gyp=(AF-CE)/G第二步：求取圓半徑R：通過已知三點a、b、c畫圓算法的關(guān)鍵是求取圓心和圓半徑。

2312.三點畫圓其它方法？延伸：橢圓？拋物線？二次曲線的擬合？2413.線段打斷

第一步：計算有向線段AB的長度第二步：根據(jù)輸入距離d計算內(nèi)插點C。

yC=yA+(yB-yA）?d/LxC=xA+(xB-xA)?d/L選取已有線段AB，根據(jù)輸入距離在線段內(nèi)插入一個點C，并將線段分為兩個部分。算法的關(guān)鍵是求取內(nèi)插點的坐標(biāo)。2514.前方交會前方交會：在三角形ABP中，已知點A、B的坐標(biāo)為xA、yA和xB、yB。在A、B兩點設(shè)站，測得∠PAB,∠PBA，解算出未知點P的坐標(biāo)xp、yp,。2614.前方交會如果AP的邊長SAP和坐標(biāo)方位角aAP為巳知，就可以按坐標(biāo)正算公式求得P點的坐標(biāo)，即：從圖可知，aAp=aAB-A，代入上式則得：

或2714.前方交會由于則根據(jù)正弦定理：2814.前方交會則則移項簡化得：余切公式2915.距離交會

思路：由已知邊SAB和觀測邊長Sa、Sb，推出l、g、h，從而算出∠A、∠B，并按余切公式求P點坐標(biāo)。

由圖可知：已知點A、B的坐標(biāo)分別為xA、yA和xB、yB，A與B間的已知長為SAB。測量了邊長Sa、Sb。在△ABP中，AB邊的高為h,而高h將AB邊分成l和g兩段，顯然l+g=SAB3015.距離交會可得：l=SAB-g，將等式兩邊取平方后代人上式得

整理得：因為以及3115.距離交會將上式