gis算法計算幾何基礎

《gis算法計算幾何基礎》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、GIS算法的計算幾何基礎矢量的概念：如果一條線段的端點是有次序之分的，我們把這種線段成為有向線段(directedsegment)。??????如果有向線段p1p2的起點p1在坐標原點，我們可以把它稱為矢量(vector)p2。矢量加減法：設二維矢量P=(x1,y1)，Q=(x2,y2)，??????則矢量加法定義為：P+Q=(x1+x2,y1+y2)，??????矢量減法定義為：P-Q=(x1-x2,y1-y2)。?????顯然有性質(zhì)P+Q=Q+P，P-Q=-(Q-P)。矢量叉積：計算矢量叉積是與直線和線段

2、相關算法的核心部分。設矢量P=(x1,y1)，Q=(x2,y2)，則矢量叉積定義為由(0,0)、p1、p2和p1+p2所組成的平行四邊形的帶符號的面積，即：P×Q=x1*y2-x2*y1，其結(jié)果是一個標量。顯然有性質(zhì)P×Q=-(Q×P)和P×(-Q)=-(P×Q)。兩點的加減法就是矢量相加減，而點的乘法則看作矢量叉積。叉積的一個非常重要性質(zhì)是可以通過它的符號判斷兩矢量相互之間的順逆時針關系：　　若P×Q>0,則P在Q的順時針方向?！　∪鬚×Q<0,則P在Q的逆時針方向?！　∪鬚×Q=0,則P與Q共線，但可能同

3、向也可能反向。折線段的拐向判斷：　　折線段的拐向判斷方法可以直接由矢量叉積的性質(zhì)推出。對于有公共端點的線段p0p1和p1p2，通過計算(p2-p0)×(p1-p0)的符號便可以確定折線段的拐向：　　若(p2-p0)×(p1-p0)>0,則p0p1在p1點拐向右側(cè)后得到p1p2?！　∪?p2-p0)×(p1-p0)<0,則p0p1在p1點拐向左側(cè)后得到p1p2?！　∪?p2-p0)×(p1-p0)=0,則p0、p1、p2三點共線。　　具體情況可參照下圖：　　判斷點是否在線段上：　　設點為Q，線段為P1P2，判斷

4、點Q在該線段上的依據(jù)是：(Q-P1)×(P2-P1)=0且Q在以P1，P2為對角頂點的矩形內(nèi)。前者保證Q點在直線P1P2上，后者是保證Q點不在線段P1P2的延長線或反向延長線上，對于這一步驟的判斷可以用以下過程實現(xiàn)：　　ifmin(Xp1,Xp2)<=Xq<=max(Xp1,Xp2)andmin(Yp1,Yp2)<=Yq<=max(Yp1,Yp2)?????????????????{returntrue};　　else?????????????????{returnfalse;}　　特別要注意的是，由于需要考

5、慮水平線段和垂直線段兩種特殊情況，min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)兩個條件必須同時滿足才能返回真值。　　判斷兩線段是否相交：　　我們分兩步確定兩條線段是否相交：　　(1)快速排斥試驗　　　　設以線段P1P2為對角線的矩形為R，設以線段Q1Q2為對角線的矩形為T，如果R和T不相交，顯然兩線段不會相交?！　?2)跨立試驗　　　　如果兩線段相交，則兩線段必然相互跨立對方。若P1P2跨立Q1Q2，則矢量(P1-Q1)和(P2-Q1)位于矢量(Q

6、2-Q1)的兩側(cè)，即(P1-Q1)×(Q2-Q1)*(P2-Q1)×(Q2-Q1)<0。上式可改寫成(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)>0。當(P1-Q1)×(Q2-Q1)=0時，說明(P1-Q1)和(Q2-Q1)共線，但是因為已經(jīng)通過快速排斥試驗，所以P1一定在線段Q1Q2上；同理，(Q2-Q1)×(P2-Q1)=0說明P2一定在線段Q1Q2上。所以判斷P1P2跨立Q1Q2的依據(jù)是：(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)>=0。同理判斷Q1Q2跨立P1P2

7、的依據(jù)是：(Q1-P1)×(P2-P1)*(P2-P1)×(Q2-P1)>=0?！　∨袛嗑€段和直線是否相交：如果線段P1P2和直線Q1Q2相交，則P1P2跨立Q1Q2，即：(P1-Q1)×(Q2-Q1)*(Q2-Q1)×(P2-Q1)>=0?！　∨袛嗑匦问欠癜c：只要判斷該點的橫坐標和縱坐標是否夾在矩形的左右邊和上下邊之間?！　∨袛嗑€段、折線、多邊形是否在矩形中：因為矩形是個凸集，所以只要判斷所有端點是否都在矩形中就可以了?！　∨袛嗑匦问欠裨诰匦沃校骸　≈灰容^左右邊界和上下邊界就可以了?！　∨袛鄨A是否在矩

8、形中：　　很容易證明，圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩形四邊的距離的最小值?！　∨袛帱c是否在多邊形中：　　判斷點P是否在多邊形中是計算幾何中一個非?；镜鞘种匾乃惴?。以點P為端點，向左方作射線L，由于多邊形是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無窮遠處開始自左向右移動，遇到和多邊形的第一個交點的時候，進入到了多邊形的內(nèi)部，遇到第二個交點的時候，離開