GIS算法的計算幾何基礎(chǔ)3解析課件

1、GIS算法的計算幾何基礎(chǔ)（3）河南大學(xué)環(huán)境與規(guī)劃學(xué)院地理信息系統(tǒng)算法基礎(chǔ)第2章GIS算法的計算幾何基礎(chǔ)（3）河南大學(xué)環(huán)境與規(guī)劃學(xué)院地理信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)作點 2本講內(nèi)容1.判斷點是否在圓內(nèi) 12.三點畫圓31.判斷點是否在圓內(nèi) 計算圓心到該點的距離，如果小于或等于半徑則該點在圓內(nèi)

2、。偽代碼？31.判斷點是否在圓內(nèi) 計算圓心到該點的距離，如果小于或等于42.判斷線段、折線、矩形、多邊形是否在圓內(nèi) 圓是凸集，所以只要判斷是否每個頂點都在圓內(nèi)即可。 偽代碼？42.判斷線段、折線、矩形、多邊形是否在圓內(nèi) 圓是凸集，所以53.判斷圓是否在圓內(nèi) 設(shè)兩圓為O1、O2半徑分別為r1、r2，要判斷O2是否在O1內(nèi)。先比較r1、r2的大小如果r1r,則L和圓沒有交點；利用勾股定理，可以求出兩交點坐標(biāo)，但要注意考慮L和圓的相切情況。136.求線段或直線與圓的交點 設(shè)圓心為O，圓半徑為r，直線146.求線段或直線與圓的交點第三步：如果L平行于x軸，做法與L平行于y軸的情況類似。第四步：如果L既

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

4、中心點的計算 多邊形的中心點(又叫做質(zhì)心或重心）可以167.中心點的計算167.中心點的計算177.中心點的計算01230(3,1)1(3,2)2(1,2)3(1,1)177.中心點的計算01230(3,1)188.過點作垂線 選取一點C，選擇一條線段AB，求取過點C垂直于AB的垂線段CP，P點位于直線AB上。第一步：求取點C到直線AB的垂點P； 第二步：連接CP，則CP為所求垂線。偽代碼？188.過點作垂線 選取一點C，選擇一條線段AB，求取過點C199.作平行線 選擇一條已有線段AB，選一點C確定方向，輸入距離d，在所選方向上按照輸入的距離復(fù)制與所選線段一樣的線段EF 。第一步：求取點C到

5、直線AB的垂點P；第二步：計算 dx = xc - xp，dy = yc-yp第三步：按照如下公式求取E、F點： xE =xA + dx, yE = yA + dy xF = xA + dx，yF = yA + dy第四步：連接E、F點，則線段EF為所求平行線。錯誤！思考正確的算法？199.作平行線 選擇一條已有線段AB，選一點C確定方向，輸2010.過點作平行線 選擇一條已有線段AB，選擇點P，選一點C，以C點為端點作平行于線段AB的平行線CD，線段CD的長度與線段AB相等。第一步：計算 dx = xB - xA, dy = yB - yA 第二步：判斷點A和點B距P點距離最近點。如果距A點

6、最近，則D點的位置為： xD = xc + dx，yD = yc + dy 如果距B點最近，則D點的位置為： xD = xc - dx，yD = yc dy第三步：連接C、D點，則線段CD為所求平行線。偽代碼？思考：線段CD是否唯一？2010.過點作平行線 選擇一條已有線段AB，選擇點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) d/L yD =yA + (yA -

7、yB) d/L 第三步：連接D點與點A、B中距P點的最近點即為所求延長線。選擇一條已有線段AB，選擇點位為P，輸入延長線距離d (d 0)，求取線段的延長線 思考：算法是否完善？2111.線段延長 第一步：求取線段AB的長度選擇一條已有線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=2A(yc+yb)- B(xc-xb)則圓心P的坐標(biāo)為：xp =(DE - BF)/G yp =(AF - CE)/G第二步：求取圓半徑R：通過已知三

8、點a、b、c畫圓算法的關(guān)鍵是求取圓心和圓半徑。 2212.三點畫圓 第一步：求取圓心P。設(shè)三點為a、b、c，2312.三點畫圓其它方法？延伸：橢圓？拋物線？二次曲線的擬合？2312.三點畫圓其它方法？2413.線段打斷 第一步：計算有向線段AB的長度第二步：根據(jù)輸入距離d計算內(nèi)插點C。 yC =yA + (yB -yA） d/L xC = xA + (xB -xA) d/L選取已有線段AB，根據(jù)輸入距離在線段內(nèi)插入一個點C，并將線段分為兩個部分。算法的關(guān)鍵是求取內(nèi)插點的坐標(biāo)。2413.線段打斷 第一步：計算有向線段AB的長度選取已有線2514.前方交會前方交會：在三角形ABP中，已知點A、B的

9、坐標(biāo)為xA、yA和xB、yB。在A、B兩點設(shè)站，測得PAB, PBA，解算出未知點P的坐標(biāo)xp、yp,。2514.前方交會前方交會：在三角形ABP中，已知點A、B的2614.前方交會如果AP的邊長SAP和坐標(biāo)方位角aAP為巳知，就可以按坐標(biāo)正算公式求得P點的坐標(biāo)，即： 從圖可知，aAp = aAB - A，代入上式則得： 或2614.前方交會如果AP的邊長SAP和坐標(biāo)方位角aAP為巳2714.前方交會由于則根據(jù)正弦定理：2714.前方交會由于2814.前方交會則則移項簡化得：余切公式2814.前方交會則余切公式2915.距離交會 思路：由已知邊SAB和觀測邊長Sa、Sb，推出l、g、h，從而算

10、出A、B，并按余切公式求P點坐標(biāo)。 由圖可知：已知點A、B的坐標(biāo)分別為xA、yA和xB、yB，A與B間的已知長為SAB。測量了邊長Sa、Sb。在ABP中，AB邊的高為h,而高h(yuǎn)將AB邊分成l和g兩段，顯然l+g=SAB2915.距離交會 思路：由已知邊SAB和觀測邊長Sa、Sb3015.距離交會可得：l=SAB-g，將等式兩邊取平方后代人上式得 整理得：因為以及3015.距離交會可得：l=SAB-g，將等式兩邊取平方后代3115.距離交會將上式代入余切公式，可以求得P點的坐標(biāo)：式中3115.距離交會將上式代入余切公式，可以求得P點的坐標(biāo)：3216.極坐標(biāo)作點 第一步：計算有向線段AB的長度L第二步：根據(jù)有向線段AB坐標(biāo)計算 dx = xB XA ，dy = yB yA 第