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

GIS算法的計(jì)算幾何基礎(chǔ)（3）河南大學(xué)環(huán)境與規(guī)劃學(xué)院《地理信息系統(tǒng)算法基礎(chǔ)》第2章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)

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

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

圓是凸集，所以只要判斷是否每個(gè)頂點(diǎn)都在圓內(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.計(jì)算兩條共線的線段的交點(diǎn)

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

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

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

選擇一條已有線段AB，選一點(diǎn)C確定方向，輸入距離d，在所選方向上按照輸入的距離復(fù)制與所選線段一樣的線段EF

。第一步：求取點(diǎn)C到直線AB的垂點(diǎn)P；第二步：計(jì)算

dx=xc-xp，dy=yc-yp第三步：按照如下公式求取E、F點(diǎn)：

xE=xA+dx,yE=yA+dyxF=xA+dx，yF=yA+dy第四步：連接E、F點(diǎn)，則線段EF為所求平行線。錯(cuò)誤！??！思考正確的算法？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)最近，則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是否唯一？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/LyD=yB+(yB-yA)?d/L

如果距A點(diǎn)最近，則D點(diǎn)的位置為：

xD=xA+(xA—xB)?d/LyD=yA+(yA-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)線思考：算法是否完善？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=2[A(yc+yb)-B(xc-xb)]則圓心P的坐標(biāo)為：xp=(DE-BF)/Gyp=(AF-CE)/G第二步：求取圓半徑R：通過(guò)已知三點(diǎn)a、b、c畫圓算法的關(guān)鍵是求取圓心和圓半徑。

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

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

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

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

思路：由已知邊SAB和觀測(cè)邊長(zhǎng)Sa、Sb，推出l、g、h，從而算出∠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=SAB3015.距離交會(huì)可得：l=SAB-g，將等式兩邊取平方后代人上式得

整理得：因?yàn)橐约?115.距離交會(huì)將上式