（轉(zhuǎn)自http://dev.gameres.com/Program/Abstract/Geometry.htm）

一、引言

　　計(jì)算機(jī)的出現(xiàn)使得很多原本十分繁瑣的工作得以大幅度簡(jiǎn)化，但是也有一些在人們直觀看來(lái)很容易的問(wèn)題卻需要拿出一套并不簡(jiǎn)單的通用解決方案，比如幾何問(wèn)題。作為計(jì)算機(jī)科學(xué)的一個(gè)分支，計(jì)算幾何主要研究解決幾何問(wèn)題的算法。在現(xiàn)代工程和數(shù)學(xué)領(lǐng)域，計(jì)算幾何在圖形學(xué)、機(jī)器人技術(shù)、超大規(guī)模集成電路設(shè)計(jì)和統(tǒng)計(jì)等諸多領(lǐng)域有著十分重要的應(yīng)用。在本文中，我們將對(duì)計(jì)算幾何常用的基本算法做一個(gè)全面的介紹，希望對(duì)您了解并應(yīng)用計(jì)算幾何的知識(shí)解決問(wèn)題起到幫助。

二、目錄

　　本文整理的計(jì)算幾何基本概念和常用算法包括如下內(nèi)容：

　　矢量的概念

　　矢量加減法

　　矢量叉積

　　折線段的拐向判斷

　　判斷點(diǎn)是否在線段上

　　判斷兩線段是否相交

　　判斷線段和直線是否相交

　　判斷矩形是否包含點(diǎn)

　　判斷線段、折線、多邊形是否在矩形中

　　判斷矩形是否在矩形中

　　判斷圓是否在矩形中

　　判斷點(diǎn)是否在多邊形中

　　判斷線段是否在多邊形內(nèi)

　　判斷折線是否在多邊形內(nèi)

　　判斷多邊形是否在多邊形內(nèi)

　　判斷矩形是否在多邊形內(nèi)

　　判斷圓是否在多邊形內(nèi)

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

　　判斷線段、折線、矩形、多邊形是否在圓內(nèi)

　　判斷圓是否在圓內(nèi)

　　計(jì)算點(diǎn)到線段的最近點(diǎn)

　　計(jì)算點(diǎn)到折線、矩形、多邊形的最近點(diǎn)

　　計(jì)算點(diǎn)到圓的最近距離及交點(diǎn)坐標(biāo)

　　計(jì)算兩條共線的線段的交點(diǎn)

　　計(jì)算線段或直線與線段的交點(diǎn)

　　求線段或直線與折線、矩形、多邊形的交點(diǎn)

　　求線段或直線與圓的交點(diǎn)

　　凸包的概念

　　凸包的求法

三、算法介紹

　　矢量的概念：

　　如果一條線段的端點(diǎn)是有次序之分的，我們把這種線段成為有向線段(directed segment)。如果有向線段p1p2的起點(diǎn)p1在坐標(biāo)原點(diǎn)，我們可以把它稱為矢量(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 )。

　　矢量叉積：

　　計(jì)算矢量叉積是與直線和線段相關(guān)算法的核心部分。設(shè)矢量P = ( x1, y1 )，Q = ( x2, y2 )，則矢量叉積定義為由(0,0)、p1、p2和p1+p2所組成的平行四邊形的帶符號(hào)的面積，即：P × Q = x1*y2 - x2*y1，其結(jié)果是一個(gè)標(biāo)量。顯然有性質(zhì) P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加說(shuō)明的情況下，本文下述算法中所有的點(diǎn)都看作矢量，兩點(diǎn)的加減法就是矢量相加減，而點(diǎn)的乘法則看作矢量叉積。

　　叉積的一個(gè)非常重要性質(zhì)是可以通過(guò)它的符號(hào)判斷兩矢量相互之間的順逆時(shí)針關(guān)系：

　　若 P × Q > 0 , 則P在Q的順時(shí)針?lè)较颉?br />　　若 P × Q < 0 , 則P在Q的逆時(shí)針?lè)较颉?br />　　若 P × Q = 0 , 則P與Q共線，但可能同向也可能反向。

　　折線段的拐向判斷：

　　折線段的拐向判斷方法可以直接由矢量叉積的性質(zhì)推出。對(duì)于有公共端點(diǎn)的線段p0p1和p1p2，通過(guò)計(jì)算(p2 - p0) × (p1 - p0)的符號(hào)便可以確定折線段的拐向：

　　若(p2 - p0) × (p1 - p0) > 0,則p0p1在p1點(diǎn)拐向右側(cè)后得到p1p2。

　　若(p2 - p0) × (p1 - p0) < 0,則p0p1在p1點(diǎn)拐向左側(cè)后得到p1p2。

　　若(p2 - p0) × (p1 - p0) = 0,則p0、p1、p2三點(diǎn)共線。

　　具體情況可參照下圖：

???

　　判斷點(diǎn)是否在線段上：

　　設(shè)點(diǎn)為Q，線段為P1P2 ，判斷點(diǎn)Q在該線段上的依據(jù)是：( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2為對(duì)角頂點(diǎn)的矩形內(nèi)。前者保證Q點(diǎn)在直線P1P2上，后者是保證Q點(diǎn)不在線段P1P2的延長(zhǎng)線或反向延長(zhǎng)線上，對(duì)于這一步驟的判斷可以用以下過(guò)程實(shí)現(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 true;

　　else return false;

　　特別要注意的是，由于需要考慮水平線段和垂直線段兩種特殊情況，min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)兩個(gè)條件必須同時(shí)滿足才能返回真值。

　　判斷兩線段是否相交：

　　我們分兩步確定兩條線段是否相交：

　　(1)快速排斥試驗(yàn)

　　　　設(shè)以線段 P1P2 為對(duì)角線的矩形為R， 設(shè)以線段 Q1Q2 為對(duì)角線的矩形為T，如果R和T不相交，顯然兩線段不會(huì)相交。

　　(2)跨立試驗(yàn)

　　　　如果兩線段相交，則兩線段必然相互跨立對(duì)方。若P1P2跨立Q1Q2 ，則矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的兩側(cè)，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改寫(xiě)成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。當(dāng) ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 時(shí)，說(shuō)明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共線，但是因?yàn)橐呀?jīng)通過(guò)快速排斥試驗(yàn)，所以 P1 一定在線段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 說(shuō)明 P2 一定在線段 Q1Q2上。所以判斷P1P2跨立Q1Q2的依據(jù)是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判斷Q1Q2跨立P1P2的依據(jù)是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具體情況如下圖所示：

???

　　在相同的原理下，對(duì)此算法的具體的實(shí)現(xiàn)細(xì)節(jié)可能會(huì)與此有所不同，除了這種過(guò)程外，大家也可以參考《算法導(dǎo)論》上的實(shí)現(xiàn)。

　　判斷線段和直線是否相交：

　　有了上面的基礎(chǔ)，這個(gè)算法就很容易了。如果線段P1P2和直線Q1Q2相交，則P1P2跨立Q1Q2，即：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。

　　判斷矩形是否包含點(diǎn)：

　　只要判斷該點(diǎn)的橫坐標(biāo)和縱坐標(biāo)是否夾在矩形的左右邊和上下邊之間。

????
　　判斷線段、折線、多邊形是否在矩形中：

　　因?yàn)榫匦问莻€(gè)凸集，所以只要判斷所有端點(diǎn)是否都在矩形中就可以了。

　　判斷矩形是否在矩形中：

　　只要比較左右邊界和上下邊界就可以了。

　　判斷圓是否在矩形中：

　　很容易證明，圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩形四邊的距離的最小值。

　　判斷點(diǎn)是否在多邊形中：

　　判斷點(diǎn)P是否在多邊形中是計(jì)算幾何中一個(gè)非常基本但是十分重要的算法。以點(diǎn)P為端點(diǎn)，向左方作射線L，由于多邊形是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無(wú)窮遠(yuǎn)處開(kāi)始自左向右移動(dòng)，遇到和多邊形的第一個(gè)交點(diǎn)的時(shí)候，進(jìn)入到了多邊形的內(nèi)部，遇到第二個(gè)交點(diǎn)的時(shí)候，離開(kāi)了多邊形，……所以很容易看出當(dāng)L和多邊形的交點(diǎn)數(shù)目C是奇數(shù)的時(shí)候，P在多邊形內(nèi)，是偶數(shù)的話P在多邊形外。

　　但是有些特殊情況要加以考慮。如圖下圖(a)(b)(c)(d)所示。在圖(a)中，L和多邊形的頂點(diǎn)相交，這時(shí)候交點(diǎn)只能計(jì)算一個(gè)；在圖(b)中，L和多邊形頂點(diǎn)的交點(diǎn)不應(yīng)被計(jì)算；在圖(c)和(d) 中，L和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計(jì)。如果L和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計(jì)。

????

　　為了統(tǒng)一起見(jiàn)，我們?cè)谟?jì)算射線L和多邊形的交點(diǎn)的時(shí)候，1。對(duì)于多邊形的水平邊不作考慮；2。對(duì)于多邊形的頂點(diǎn)和L相交的情況，如果該頂點(diǎn)是其所屬的邊上縱坐標(biāo)較大的頂點(diǎn)，則計(jì)數(shù)，否則忽略；3。對(duì)于P在多邊形邊上的情形，直接可判斷P屬于多邊行。由此得出算法的偽代碼如下：

??? count ← 0;
??? 以P為端點(diǎn)，作從右向左的射線L;?
??? for 多邊形的每條邊s
???? do if P在邊s上?
????????? then return true;
??????? if s不是水平的
????????? then if s的一個(gè)端點(diǎn)在L上
???????????????? if 該端點(diǎn)是s兩端點(diǎn)中縱坐標(biāo)較大的端點(diǎn)
?????????????????? 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)和P相同，橫坐標(biāo)為正無(wú)窮大（很大的一個(gè)正數(shù)），則P和P'就確定了射線L。

　　判斷點(diǎn)是否在多邊形中的這個(gè)算法的時(shí)間復(fù)雜度為O(n)。

　　另外還有一種算法是用帶符號(hào)的三角形面積之和與多邊形面積進(jìn)行比較，這種算法由于使用浮點(diǎn)數(shù)運(yùn)算所以會(huì)帶來(lái)一定誤差，不推薦大家使用。

　　判斷線段是否在多邊形內(nèi)：

　　線段在多邊形內(nèi)的一個(gè)必要條件是線段的兩個(gè)端點(diǎn)都在多邊形內(nèi)，但由于多邊形可能為凹，所以這不能成為判斷的充分條件。如果線段和多邊形的某條邊內(nèi)交（兩線段內(nèi)交是指兩線段相交且交點(diǎn)不在兩線段的端點(diǎn)），因?yàn)槎噙呅蔚倪叺淖笥覂蓚?cè)分屬多邊形內(nèi)外不同部分，所以線段一定會(huì)有一部分在多邊形外(見(jiàn)圖a)。于是我們得到線段在多邊形內(nèi)的第二個(gè)必要條件：線段和多邊形的所有邊都不內(nèi)交。

　　線段和多邊形交于線段的兩端點(diǎn)并不會(huì)影響線段是否在多邊形內(nèi)；但是如果多邊形的某個(gè)頂點(diǎn)和線段相交，還必須判斷兩相鄰交點(diǎn)之間的線段是否包含于多邊形內(nèi)部（反例見(jiàn)圖b)。

???

　　因此我們可以先求出所有和線段相交的多邊形的頂點(diǎn)，然后按照X-Y坐標(biāo)排序(X坐標(biāo)小的排在前面，對(duì)于X坐標(biāo)相同的點(diǎn)，Y坐標(biāo)小的排在前面，這種排序準(zhǔn)則也是為了保證水平和垂直情況的判斷正確)，這樣相鄰的兩個(gè)點(diǎn)就是在線段上相鄰的兩交點(diǎn)，如果任意相鄰兩點(diǎn)的中點(diǎn)也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。

　　證明如下：
　

　　命題1：
　　　　如果線段和多邊形的兩相鄰交點(diǎn)P1 ，P2的中點(diǎn)P' 也在多邊形內(nèi)，則P1, P2之間的所有點(diǎn)都在多邊形內(nèi)。
????

　　證明：
　　　　假設(shè)P1,P2之間含有不在多邊形內(nèi)的點(diǎn)，不妨設(shè)該點(diǎn)為Q，在P1, P'之間，因?yàn)槎噙呅问情]合曲線，所以其內(nèi)外部之間有界，而P1屬于多邊行內(nèi)部，Q屬于多邊性外部，P'屬于多邊性內(nèi)部，P1-Q-P'完全連續(xù)，所以P1Q和QP'一定跨越多邊形的邊界，因此在P1,P'之間至少還有兩個(gè)該線段和多邊形的交點(diǎn)，這和P1P2是相鄰兩交點(diǎn)矛盾，故命題成立。證畢。

　　由命題1直接可得出推論：
　　推論2：
　　　　設(shè)多邊形和線段PQ的交點(diǎn)依次為P1,P2,……Pn，其中Pi和Pi+1是相鄰兩交點(diǎn)，線段PQ在多邊形內(nèi)的充要條件是：P，Q在多邊形內(nèi)且對(duì)于i =1, 2,……, n-1，Pi ,Pi+1的中點(diǎn)也在多邊形內(nèi)。

　　在實(shí)際編程中，沒(méi)有必要計(jì)算所有的交點(diǎn)，首先應(yīng)判斷線段和多邊形的邊是否內(nèi)交，倘若線段和多邊形的某條邊內(nèi)交則線段一定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)交，則線段和多邊形的交點(diǎn)一定是線段的端點(diǎn)或者多邊形的頂點(diǎn)，只要判斷點(diǎn)是否在線段上就可以了。

　　至此我們得出算法如下：

??? if 線端PQ的端點(diǎn)不都在多邊形內(nèi)?
????? then return false;
??? 點(diǎn)集pointSet初始化為空;
??? for 多邊形的每條邊s
????? do if 線段的某個(gè)端點(diǎn)在s上
?????????? then 將該端點(diǎn)加入pointSet;
???????? else if s的某個(gè)端點(diǎn)在線段PQ上
?????????? then 將該端點(diǎn)加入pointSet;
???????? else if s和線段PQ相交 // 這時(shí)候已經(jīng)可以肯定是內(nèi)交了
?????????? then return false;
??? 將pointSet中的點(diǎn)按照X-Y坐標(biāo)排序;
??? for pointSet中每?jī)蓚€(gè)相鄰點(diǎn) pointSet[i] , pointSet[ i+1]
????? do if pointSet[i] , pointSet[ i+1] 的中點(diǎn)不在多邊形中
?????????? then return false;
??? return true;

　　這個(gè)過(guò)程中的排序因?yàn)榻稽c(diǎn)數(shù)目肯定遠(yuǎn)小于多邊形的頂點(diǎn)數(shù)目n，所以最多是常數(shù)級(jí)的復(fù)雜度，幾乎可以忽略不計(jì)。因此算法的時(shí)間復(fù)雜度也是O(n)。

　　判斷折線是否在多邊形內(nèi)：

　　只要判斷折線的每條線段是否都在多邊形內(nèi)即可。設(shè)折線有m條線段，多邊形有n個(gè)頂點(diǎn)，則該算法的時(shí)間復(fù)雜度為O(m*n)。

　　判斷多邊形是否在多邊形內(nèi)：

　　只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷一個(gè)有m個(gè)頂點(diǎn)的多邊形是否在一個(gè)有n個(gè)頂點(diǎn)的多邊形內(nèi)復(fù)雜度為O(m*n)。

　　判斷矩形是否在多邊形內(nèi)：

　　將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。

　　判斷圓是否在多邊形內(nèi)：

　　只要計(jì)算圓心到多邊形的每條邊的最短距離，如果該距離大于等于圓半徑則該圓在多邊形內(nèi)。計(jì)算圓心到多邊形每條邊最短距離的算法在后文闡述。

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

　　計(jì)算圓心到該點(diǎn)的距離，如果小于等于半徑則該點(diǎn)在圓內(nèi)。

　　判斷線段、折線、矩形、多邊形是否在圓內(nèi)：

　　因?yàn)閳A是凸集，所以只要判斷是否每個(gè)頂點(diǎn)都在圓內(nèi)即可。

　　判斷圓是否在圓內(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)。

　　計(jì)算點(diǎn)到線段的最近點(diǎn)：

　　如果該線段平行于X軸（Y軸），則過(guò)點(diǎn)point作該線段所在直線的垂線，垂足很容易求得，然后計(jì)算出垂足，如果垂足在線段上則返回垂足，否則返回離垂足近的端點(diǎn)；如果該線段不平行于X軸也不平行于Y軸，則斜率存在且不為0。設(shè)線段的兩端點(diǎn)為pt1和pt2，斜率為：k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );該直線方程為：y = k* ( x - pt1.x) + pt1.y。其垂線的斜率為 - 1 / k，垂線方程為：y = (-1/k) * (x - point.x) + point.y 。

　　聯(lián)立兩直線方程解得：x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1) ，y = k * ( x - pt1.x) + pt1.y;然后再判斷垂足是否在線段上，如果在線段上則返回垂足；如果不在則計(jì)算兩端點(diǎn)到垂足的距離，選擇距離垂足較近的端點(diǎn)返回。

　　計(jì)算點(diǎn)到折線、矩形、多邊形的最近點(diǎn)：

　　只要分別計(jì)算點(diǎn)到每條線段的最近點(diǎn)，記錄最近距離，取其中最近距離最小的點(diǎn)即可。

　　計(jì)算點(diǎn)到圓的最近距離及交點(diǎn)坐標(biāo)：

　　如果該點(diǎn)在圓心，因?yàn)閳A心到圓周任一點(diǎn)的距離相等，返回UNDEFINED。

　　連接點(diǎn)P和圓心O，如果PO平行于X軸，則根據(jù)P在O的左邊還是右邊計(jì)算出最近點(diǎn)的橫坐標(biāo)為centerPoint.x - radius 或 centerPoint.x + radius。如果PO平行于Y軸，則根據(jù)P在O的上邊還是下邊計(jì)算出最近點(diǎn)的縱坐標(biāo)為 centerPoint.y -+radius或 centerPoint.y - radius。如果PO不平行于X軸和Y軸，則PO的斜率存在且不為0，這時(shí)直線PO斜率為k = （ P.y - O.y ）/ ( P.x - O.x )。直線PO的方程為：y = k * ( x - P.x) + P.y。設(shè)圓方程為:(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2，聯(lián)立兩方程組可以解出直線PO和圓的交點(diǎn)，取其中離P點(diǎn)較近的交點(diǎn)即可。

　　計(jì)算兩條共線的線段的交點(diǎn)：

　　對(duì)于兩條共線的線段，它們之間的位置關(guān)系有下圖所示的幾種情況。圖(a)中兩條線段沒(méi)有交點(diǎn)；圖 (b) 和 (d) 中兩條線段有無(wú)窮焦點(diǎn)；圖 (c) 中兩條線段有一個(gè)交點(diǎn)。設(shè)line1是兩條線段中較長(zhǎng)的一條，line2是較短的一條，如果line1包含了line2的兩個(gè)端點(diǎn)，則是圖(d)的情況，兩線段有無(wú)窮交點(diǎn)；如果line1只包含line2的一個(gè)端點(diǎn)，那么如果line1的某個(gè)端點(diǎn)等于被line1包含的line2的那個(gè)端點(diǎn)，則是圖(c)的情況，這時(shí)兩線段只有一個(gè)交點(diǎn)，否則就是圖(b)的情況，兩線段也是有無(wú)窮的交點(diǎn)；如果line1不包含line2的任何端點(diǎn)，則是圖(a)的情況，這時(shí)兩線段沒(méi)有交點(diǎn)。

　　計(jì)算線段或直線與線段的交點(diǎn):

　　設(shè)一條線段為L(zhǎng)0 = P1P2，另一條線段或直線為L(zhǎng)1 = Q1Q2 ，要計(jì)算的就是L0和L1的交點(diǎn)。

　1． 首先判斷L0和L1是否相交（方法已在前文討論過(guò)），如果不相交則沒(méi)有交點(diǎn)，否則說(shuō)明L0和L1一定有交點(diǎn)，下面就將L0和L1都看作直線來(lái)考慮。

　2． 如果P1和P2橫坐標(biāo)相同，即L0平行于Y軸

　　a) 若L1也平行于Y軸，

　　　　i. 若P1的縱坐標(biāo)和Q1的縱坐標(biāo)相同，說(shuō)明L0和L1共線，假如L1是直線的話他們有無(wú)窮的交點(diǎn)，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前文已討論過(guò)）；
　　　　ii. 否則說(shuō)明L0和L1平行，他們沒(méi)有交點(diǎn)；

　　b) 若L1不平行于Y軸，則交點(diǎn)橫坐標(biāo)為P1的橫坐標(biāo)，代入到L1的直線方程中可以計(jì)算出交點(diǎn)縱坐標(biāo)；

　3． 如果P1和P2橫坐標(biāo)不同，但是Q1和Q2橫坐標(biāo)相同，即L1平行于Y軸，則交點(diǎn)橫坐標(biāo)為Q1的橫坐標(biāo)，代入到L0的直線方程中可以計(jì)算出交點(diǎn)縱坐標(biāo)；

　4． 如果P1和P2縱坐標(biāo)相同，即L0平行于X軸

　　a) 若L1也平行于X軸，

　　　　i. 若P1的橫坐標(biāo)和Q1的橫坐標(biāo)相同，說(shuō)明L0和L1共線，假如L1是直線的話他們有無(wú)窮的交點(diǎn)，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前文已討論過(guò)）；
　　　　ii. 否則說(shuō)明L0和L1平行，他們沒(méi)有交點(diǎn)；

　　b) 若L1不平行于X軸，則交點(diǎn)縱坐標(biāo)為P1的縱坐標(biāo)，代入到L1的直線方程中可以計(jì)算出交點(diǎn)橫坐標(biāo)；

　5． 如果P1和P2縱坐標(biāo)不同，但是Q1和Q2縱坐標(biāo)相同，即L1平行于X軸，則交點(diǎn)縱坐標(biāo)為Q1的縱坐標(biāo)，代入到L0的直線方程中可以計(jì)算出交點(diǎn)橫坐標(biāo)；

　6． 剩下的情況就是L1和L0的斜率均存在且不為0的情況

　　a) 計(jì)算出L0的斜率K0，L1的斜率K1 ；

　　b) 如果K1 = K2?

　　　　i. 如果Q1在L0上，則說(shuō)明L0和L1共線，假如L1是直線的話有無(wú)窮交點(diǎn)，假如L1是線段的話可用"計(jì)算兩條共線線段的交點(diǎn)"的算法求他們的交點(diǎn)（該方法在前文已討論過(guò)）；
　　　　ii. 如果Q1不在L0上，則說(shuō)明L0和L1平行，他們沒(méi)有交點(diǎn)。

　　c) 聯(lián)立兩直線的方程組可以解出交點(diǎn)來(lái)

　　這個(gè)算法并不復(fù)雜，但是要分情況討論清楚，尤其是當(dāng)兩條線段共線的情況需要單獨(dú)考慮，所以在前文將求兩條共線線段的算法單獨(dú)寫(xiě)出來(lái)。另外，一開(kāi)始就先利用矢量叉乘判斷線段與線段（或直線）是否相交，如果結(jié)果是相交，那么在后面就可以將線段全部看作直線來(lái)考慮。需要注意的是，我們可以將直線或線段方程改寫(xiě)為ax+by+c=0的形式，這樣一來(lái)上述過(guò)程的部分步驟可以合并，縮短了代碼長(zhǎng)度，但是由于先要求出參數(shù)，這種算法將花費(fèi)更多的時(shí)間。

　　求線段或直線與折線、矩形、多邊形的交點(diǎn)：

　　分別求與每條邊的交點(diǎn)即可。

　　求線段或直線與圓的交點(diǎn):

　　設(shè)圓心為O，圓半徑為r，直線（或線段）L上的兩點(diǎn)為P1,P2。

　　1. 如果L是線段且P1，P2都包含在圓O內(nèi)，則沒(méi)有交點(diǎn)；否則進(jìn)行下一步。

　　2. 如果L平行于Y軸，

　　　a) 計(jì)算圓心到L的距離dis；
　　　b) 如果dis > r 則L和圓沒(méi)有交點(diǎn)；
　　　c) 利用勾股定理，可以求出兩交點(diǎn)坐標(biāo)，但要注意考慮L和圓的相切情況。

　　3. 如果L平行于X軸，做法與L平行于Y軸的情況類似；

　　4. 如果L既不平行X軸也不平行Y軸，可以求出L的斜率K，然后列出L的點(diǎn)斜式方程，和圓方程聯(lián)立即可求解出L和圓的兩個(gè)交點(diǎn)；

　　5. 如果L是線段，對(duì)于2，3，4中求出的交點(diǎn)還要分別判斷是否屬于該線段的范圍內(nèi)。

　　凸包的概念：

　　點(diǎn)集Q的凸包(convex hull)是指一個(gè)最小凸多邊形，滿足Q中的點(diǎn)或者在多邊形邊上或者在其內(nèi)。下圖中由紅色線段表示的多邊形就是點(diǎn)集Q={p0,p1,...p12}的凸包。?
???
　

　　

?????凸包的求法：

　　現(xiàn)在已經(jīng)證明了凸包算法的時(shí)間復(fù)雜度下界是O(n*logn),但是當(dāng)凸包的頂點(diǎn)數(shù)h也被考慮進(jìn)去的話，Krikpatrick和Seidel的剪枝搜索算法可以達(dá)到O(n*logh)，在漸進(jìn)意義下達(dá)到最優(yōu)。最常用的凸包算法是Graham掃描法和Jarvis步進(jìn)法。本文只簡(jiǎn)單介紹一下Graham掃描法，其正確性的證明和Jarvis步進(jìn)法的過(guò)程大家可以參考《算法導(dǎo)論》。

　　對(duì)于一個(gè)有三個(gè)或以上點(diǎn)的點(diǎn)集Q，Graham掃描法的過(guò)程如下：

　　令p0為Q中Y-X坐標(biāo)排序下最小的點(diǎn)?
　　設(shè)<p1,p2,...pm>為對(duì)其余點(diǎn)按以p0為中心的極角逆時(shí)針排序所得的點(diǎn)集（如果有多個(gè)點(diǎn)有相同的極角，除了距p0最遠(yuǎn)的點(diǎn)外全部移除
　　壓p0進(jìn)棧S
　　壓p1進(jìn)棧S
　　壓p2進(jìn)棧S
??? for i ← 3 to m
????? do while 由S的棧頂元素的下一個(gè)元素、S的棧頂元素以及pi構(gòu)成的折線段不拐向左側(cè)
??????? 對(duì)S彈棧
??????壓pi進(jìn)棧S
??? return S;
　

　　此過(guò)程執(zhí)行后，棧S由底至頂?shù)脑鼐褪荙的凸包頂點(diǎn)按逆時(shí)針排列的點(diǎn)序列。需要注意的是，我們對(duì)點(diǎn)按極角逆時(shí)針排序時(shí)，并不需要真正求出極角，只需要求出任意兩點(diǎn)的次序就可以了。而這個(gè)步驟可以用前述的矢量叉積性質(zhì)實(shí)現(xiàn)。

四、結(jié)語(yǔ)

　　盡管人類對(duì)幾何學(xué)的研究從古代起便沒(méi)有中斷過(guò)，但是具體到借助計(jì)算機(jī)來(lái)解決幾何問(wèn)題的研究，還只是停留在一個(gè)初級(jí)階段，無(wú)論從應(yīng)用領(lǐng)域還是發(fā)展前景來(lái)看，計(jì)算幾何學(xué)都值得我們認(rèn)真學(xué)習(xí)、加以運(yùn)用，希望這篇文章能帶你走進(jìn)這個(gè)豐富多彩的世界。

轉(zhuǎn)載于:https://www.cnblogs.com/Geometry/archive/2009/03/02/1401310.html

總結(jié)

以上是生活随笔為你收集整理的计算几何常用算法的理论基础【转】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。