計算幾何常用算法

1、計算幾何常用算法一、引言計算機的出現(xiàn)使得很多原本十分繁瑣的工作得以大幅度簡化，但是也有一些在人們直觀看來很容易的問題卻需要拿出一套并不簡單的通用解決方案，比如幾何問題。作為計算機科學(xué)的一個分支，計算幾何主要研究解決幾何問題的算法。在現(xiàn)代工程和數(shù)學(xué)領(lǐng)域，計算幾何在圖形學(xué)、機器人技術(shù)、超大規(guī)模集成電路設(shè)計和統(tǒng)計等諸多領(lǐng)域有著十分重要的應(yīng)用。在本文中， 我們將對計算幾何常用的基本算法做一個全面的介紹，希望對您了解并應(yīng)用計算幾何的知識解決問題起到幫助。二、目錄本文整理的計算幾何基本概念和常用算法包括如下內(nèi)容：矢量的概念矢量加減法矢量叉積折線段的拐向判斷判斷點是否在線段上判斷兩線段是否相交判斷線段和直線

2、是否相交判斷矩形是否包含點判斷線段、折線、多邊形是否在矩形中判斷矩形是否在矩形中判斷圓是否在矩形中判斷點是否在多邊形中判斷線段是否在多邊形內(nèi)判斷折線是否在多邊形內(nèi)判斷多邊形是否在多邊形內(nèi)判斷矩形是否在多邊形內(nèi)判斷圓是否在多邊形內(nèi)判斷點是否在圓內(nèi)判斷線段、折線、矩形、多邊形是否在圓內(nèi)判斷圓是否在圓內(nèi)計算點到線段的最近點計算點到折線、矩形、多邊形的最近點計算點到圓的最近距離及交點坐標(biāo)計算兩條共線的線段的交點計算線段或直線與線段的交點求線段或直線與折線、矩形、多邊形的交點求線段或直線與圓的交點凸包的概念凸包的求法三、算法介紹矢量的概念：如果一條線段的端點是有次序之分的，我們把這種線段成為有向線段(d

3、irected segment)。如果有向線段p1p2 的起點 p1 在坐標(biāo)原點，我們可以把它稱為矢量(vector)p2。矢量加減法：設(shè)二維矢量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 ) 。矢量叉積：計算矢量叉積是與直線和線段相關(guān)算法的核心部分。設(shè)矢量 p =（x1,y1） ，q = (x2,y2) ，則矢量叉積定義為由(0,0)、p1、p

4、2 和 p1+p2 所組成的平行四邊形的帶符號的面積即： pq = x1*y2 - x2*y1 ，其結(jié)果是一個標(biāo)量。顯然有性質(zhì)pq = - (q p) 和 p ( -q ) = - ( p q)。一般在不加說明的情況下，本文下述算法中所有的點都看作矢量，兩點的加減法就是矢量相加減，而點的乘法則看作矢量叉積。叉積的一個非常重要性質(zhì)是可以通過它的符號判斷兩矢量相互之間的順逆時針關(guān)系：若 p q 0 , 則 p 在 q 的順時針方向。若 p q 0, 則 p0p1 在 p1 點拐向右側(cè)后得到p1p2。若(p2 - p0) (p1 - p0) 0, 則 p0p1 在 p1 點拐向左側(cè)后得到p1p2。若

5、(p2 - p0) (p1 - p0) = 0, 則 p0、p1、p2 三點共線。具體情況可參照下圖：判斷點是否在線段上：設(shè)點為 q，線段為 p1p2 ，判斷點 q 在該線段上的依據(jù)是：( q - p1 ) ( p2 - p1 ) = 0 且 q 在以 p1，p2 為對角頂點的矩形內(nèi)。前者保證q 點在直線p1p2 上，后者是保證q 點不在線段 p1p2 的延長線或反向延長線上，對于這一步驟的判斷可以用以下過程實現(xiàn)：on-segment(pi,pj,pk) if min(xi,xj)=xk=max(xi,xj) and min(yi,yj)=yk=max(yi,yj) then return t

6、rue; else return false; 特 別 要 注 意 的 是 ， 由 于 需 要 考 慮 水 平 線 段 和 垂 直 線 段 兩 種 特 殊 情 況 ，min(xi,xj)=xk=max(xi,xj)和 min(yi,yj)=yk=max(yi,yj)兩個條件必須同時滿足才能返回真值。判斷兩線段是否相交：我們分兩步確定兩條線段是否相交：(1)快速排斥試驗設(shè)以線段p1p2 為對角線的矩形為r， 設(shè)以線段q1q2 為對角線的矩形為t，如果 r 和 t不相交，顯然兩線段不會相交。(2)跨立試驗如果兩線段相交，則兩線段必然相互跨立對方。若p1p2 跨立 q1q2 ，則矢量( p1 - q

7、1 ) 和( p2 - q1 )位于矢量 ( q2 - q1 ) 的兩側(cè)，即( p1 - q1 ) ( q2 - q1 ) * ( p2 - q1 ) ( q2 - q1 ) 0 。當(dāng) ( 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 ) ( p

8、2 - q1 ) = 0 。同理判斷 q1q2 跨立 p1p2 的依據(jù)是： ( q1 - p1 )( p2 - p1 ) * ( p2 - p1 ) ( q2 - p1 ) = 0 。具體情況如下圖所示：在相同的原理下，對此算法的具體的實現(xiàn)細(xì)節(jié)可能會與此有所不同，除了這種過程外，大家也可以參考算法導(dǎo)論上的實現(xiàn)。判斷線段和直線是否相交：有了上面的基礎(chǔ)，這個算法就很容易了。如果線段p1p2 和直線q1q2 相交，則p1p2 跨立q1q2，即： ( p1 - q1 ) ( q2 - q1 ) * ( q2 - q1 ) ( p2 - q1 ) = 0 。判斷矩形是否包含點：只要判斷該點的橫坐標(biāo)和縱坐

9、標(biāo)是否夾在矩形的左右邊和上下邊之間。判斷線段、折線、多邊形是否在矩形中：因為矩形是個凸集，所以只要判斷所有端點是否都在矩形中就可以了。判斷矩形是否在矩形中：只要比較左右邊界和上下邊界就可以了。判斷圓是否在矩形中：很容易證明， 圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩形四邊的距離的最小值。判斷點是否在多邊形中：判斷點 p是否在多邊形中是計算幾何中一個非?；镜鞘种匾乃惴?。以點p 為端點，向左方作射線l，由于多邊形是有界的，所以射線l 的左端一定在多邊形外，考慮沿著l從無窮遠(yuǎn)處開始自左向右移動，遇到和多邊形的第一個交點的時候，進入到了多邊形的內(nèi)部，遇到第二個交點的時候，

10、離開了多邊形，所以很容易看出當(dāng)l 和多邊形的交點數(shù)目c是奇數(shù)的時候，p 在多邊形內(nèi)，是偶數(shù)的話p 在多邊形外。但是有些特殊情況要加以考慮。如圖下圖(a)(b)(c)(d) 所示。在圖 (a)中， l 和多邊形的頂點相交，這時候交點只能計算一個；在圖(b)中， l 和 多邊形頂點的交點不應(yīng)被計算；在圖(c)和(d) 中，l 和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計。如果 l 和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計。為了統(tǒng)一起見，我們在計算射線l 和多邊形的交點的時候，1 對于多邊形的水平邊不作考慮；2 對于多邊形的頂點和l 相交的情況，如果該頂點是其所屬的邊上縱坐標(biāo)較大的頂點，則計數(shù)，否則

11、忽略；3 對于 p在多邊形邊上的情形，直接可判斷p屬于多邊行。由此得出算法的偽代碼如下：count 0; 以 p 為端點，作從右向左的射線l; for 多邊形的每條邊s do if p 在邊 s上 then return true; if s 不是水平的then if s 的一個端點在l 上if 該端點是s 兩端點中縱坐標(biāo)較大的端點then count count+1 else if s 和 l 相交then count count+1; if count mod 2 = 1 then return true; else return false; - 其中做射線l 的方法是： 設(shè) p的縱坐標(biāo)

12、和p 相同，橫坐標(biāo)為正無窮大 （很大的一個正數(shù)） ，則 p 和 p就確定了射線l。判斷點是否在多邊形中的這個算法的時間復(fù)雜度為o(n)。另外還有一種算法是用帶符號的三角形面積之和與多邊形面積進行比較，這種算法由于使用浮點數(shù)運算所以會帶來一定誤差，不推薦大家使用。判斷線段是否在多邊形內(nèi)：線段在多邊形內(nèi)的一個必要條件是線段的兩個端點都在多邊形內(nèi)但由于多邊形可能為凹，所以這不能成為判斷的充分條件。如果線段和多邊形的某條邊內(nèi)交（兩線段內(nèi)交是指兩線段相交且交點不在兩線段的端點），因為多邊形的邊的左右兩側(cè)分屬多邊形內(nèi)外不同部分，所以線段一定會有一部分在多邊形外(見圖 a)。于是我們得到線段在多邊形內(nèi)的第二

13、個必要條件：線段和多邊形的所有邊都不內(nèi)交。線段和多邊形交于線段的兩端點并不會影響線段是否在多邊形內(nèi)；但是如果多邊形的某個頂點和線段相交，還必須判斷兩相鄰交點之間的線段是否包含于多邊形內(nèi)部（反例見圖b)。因此我們可以先求出所有和線段相交的多邊形的頂點，然后按照x-y 坐標(biāo)排序 (x 坐標(biāo)小的排在前面，對于x 坐標(biāo)相同的點，y 坐標(biāo)小的排在前面，這種排序準(zhǔn)則也是為了保證水平和垂直情況的判斷正確)， 這樣相鄰的兩個點就是在線段上相鄰的兩交點，如果任意相鄰兩點的中點也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。證明如下：命題 1：如果線段和多邊形的兩相鄰交點p1,p2 的中點 p 也在多邊形內(nèi)，則p1, p2

14、 之間的所有點都在多邊形內(nèi)。證明：假設(shè) p1,p2 之間含有不在多邊形內(nèi)的點，不妨設(shè)該點為q，在 p1, p之間，因為多邊形是閉合曲線，所以其內(nèi)外部之間有界，而p1 屬于多邊行內(nèi)部，q 屬于多邊性外部，p屬于多邊性內(nèi)部，p1-q-p完全連續(xù) ,所以 p1q 和 qp一定跨越多邊形的邊界，因此在p1,p之間至少還有兩個該線段和多邊形的交點，這和p1p2 是相鄰兩交點矛盾，故命題成立。證畢。由命題 1 直接可得出推論：推論 2：設(shè)多邊形和線段pq 的交點依次為p1,p2, pn，其中 pi 和 pi+1 是相鄰兩交點，線段pq在多邊形內(nèi)的充要條件是：p，q 在多邊形內(nèi)且對于i =1, 2, , n

15、-1，pi ,pi+1 的中點也在多邊形內(nèi) 。在實際編程中， 沒有必要計算所有的交點，首先應(yīng)判斷線段和多邊形的邊是否內(nèi)交，倘若線段和多邊形的某條邊內(nèi)交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)交，則線段和多邊形的交點一定是線段的端點或者多邊形的頂點，只要判斷點是否在線段上就可以了。至此我們得出算法如下：if 線端 pq 的端點不都在多邊形內(nèi)then return false; 點集 pointset 初始化為空 ; for 多邊形的每條邊s do if 線段的某個端點在s 上then 將該端點加入pointset; else if s 的某個端點在線段pq 上then 將該端點加入

16、pointset; else if s 和線段 pq 相交/ 這時候已經(jīng)可以肯定是內(nèi)交了 then return false; 將 pointset 中的點按照x-y 坐標(biāo)排序 ; for pointset 中每兩個相鄰點pointseti , pointset i+1 do if pointseti , pointset i+1 的中點不在多邊形中then return false; return true; 這個過程中的排序因為交點數(shù)目肯定遠(yuǎn)小于多邊形的頂點數(shù)目n，所以最多是常數(shù)級的復(fù)雜度，幾乎可以忽略不計。因此算法的時間復(fù)雜度也是o(n)。判斷折線是否在多邊形內(nèi)：只要判斷折線的每條線段是

17、否都在多邊形內(nèi)即可。設(shè)折線有m 條線段，多邊形有n 個頂點，則該算法的時間復(fù)雜度為o(m*n) 。判斷多邊形是否在多邊形內(nèi)：只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷一個有m 個頂點的多邊形是否在一個有 n 個頂點的多邊形內(nèi)復(fù)雜度為o(m*n) 。判斷矩形是否在多邊形內(nèi)：將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。判斷圓是否在多邊形內(nèi)：只要計算圓心到多邊形的每條邊的最短距離，如果該距離大于等于圓半徑則該圓在多邊形內(nèi)。計算圓心到多邊形每條邊最短距離的算法在后文闡述。判斷點是否在圓內(nèi)：計算圓心到該點的距離，如果小于等于半徑則該點在圓內(nèi)。判斷線段、折線、矩形、多邊形是否在圓內(nèi)：因為圓是凸集，

18、所以只要判斷是否每個頂點都在圓內(nèi)即可。判斷圓是否在圓內(nèi)：設(shè)兩圓為 o1,o2，半徑分別為r1, r2，要判斷 o2 是否在 o1 內(nèi)。先比較r1，r2 的大小，如果r1 r 則 l 和圓沒有交點；c) 利用勾股定理，可以求出兩交點坐標(biāo)，但要注意考慮l 和圓的相切情況。3. 如果 l 平行于 x 軸，做法與l 平行于 y 軸的情況類似；4. 如果 l 既不平行x 軸也不平行y 軸，可以求出l 的斜率 k，然后列出l 的點斜式方程，和圓方程聯(lián)立即可求解出l 和圓的兩個交點；5. 如果 l 是線段，對于2，3，4 中求出的交點還要分別判斷是否屬于該線段的范圍內(nèi)。凸包的概念：點集 q 的凸包 (convex hull) 是指一個最小凸多邊形，滿足 q 中的點或者在多邊形邊上或者在其內(nèi)。下圖中由紅色線段表示的多邊形就是點集q=p0,p1,.p12 的凸包。凸包的求法：現(xiàn)在已經(jīng)證明了凸包算法的時間復(fù)雜度下界是o(n*log