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

1、GIS算法的計(jì)算幾何基礎(chǔ)（3）河南大學(xué)環(huán)境與規(guī)劃學(xué)院地理信息系統(tǒng)算法基礎(chǔ)第2章GIS算法的計(jì)算幾何基礎(chǔ)（3）河南大學(xué)環(huán)境與規(guī)劃學(xué)院地理信2本講內(nèi)容1.判斷點(diǎn)是否在圓內(nèi) 2.判斷線段、折線、矩形、多邊形是否在圓內(nèi) 3.判斷圓是否在圓內(nèi) 4.計(jì)算兩條共線的線段的交點(diǎn)5.計(jì)算線段或直線與線段的交點(diǎn)6求線段或直線與圓的交點(diǎn) 7.中心點(diǎn)的計(jì)算 8.過(guò)點(diǎn)作垂線9.作平行線10.過(guò)點(diǎn)作平行線 11.線段延長(zhǎng) 12.三點(diǎn)畫圓13.線段打斷 14.前方交會(huì) 15.距離交會(huì) 16.極坐標(biāo)作點(diǎn) 2本講內(nèi)容1.判斷點(diǎn)是否在圓內(nèi) 12.三點(diǎn)畫圓31.判斷點(diǎn)是否在圓內(nèi) 計(jì)算圓心到該點(diǎn)的距離，如果小于或等于半徑則該點(diǎn)在圓內(nèi)

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

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

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

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

6、最近，則D點(diǎn)的位置為： xD = xc + dx，yD = yc + dy 如果距B點(diǎn)最近，則D點(diǎn)的位置為： xD = xc - dx，yD = yc dy第三步：連接C、D點(diǎn)，則線段CD為所求平行線。偽代碼？思考：線段CD是否唯一？2010.過(guò)點(diǎn)作平行線 選擇一條已有線段AB，選擇點(diǎn)2111.線段延長(zhǎng) 第一步：求取線段AB的長(zhǎng)度第二步：判斷點(diǎn)A和點(diǎn)B距P點(diǎn)距離最近點(diǎn)。如果距B點(diǎn)最近，則D點(diǎn)的位置為： xD =xB + (xB xA) d/L yD =yB + (yB - yA) d/L 如果距A點(diǎn)最近，則D點(diǎn)的位置為： xD =xA + (xA xB) d/L yD =yA + (yA -

7、yB) d/L 第三步：連接D點(diǎn)與點(diǎn)A、B中距P點(diǎn)的最近點(diǎn)即為所求延長(zhǎng)線。選擇一條已有線段AB，選擇點(diǎn)位為P，輸入延長(zhǎng)線距離d (d 0)，求取線段的延長(zhǎng)線 思考：算法是否完善？2111.線段延長(zhǎng) 第一步：求取線段AB的長(zhǎng)度選擇一條已有線2212.三點(diǎn)畫圓 第一步：求取圓心P。設(shè)三點(diǎn)為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：通過(guò)已知三

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

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

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