來(lái)源:http://www.azure.com.cn/article.asp?id=325
一、引言
計(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。
矢量叉積：計(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。上式可改寫成( 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)處開始自左向右移動(dòng)，遇到和多邊形的第一個(gè)交點(diǎn)的時(shí)候，進(jìn)入到了多邊形的內(nèi)部，遇到第二個(gè)交點(diǎn)的時(shí)候，離開了多邊形，……所以很容易看出當(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)一起見，我們?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ì)有一部分在多邊形外(見圖a)。于是我們得到線段在多邊形內(nèi)的第二個(gè)必要條件：線段和多邊形的所有邊都不內(nèi)交。
線段和多邊形交于線段的兩端點(diǎn)并不會(huì)影響線段是否在多邊形內(nèi)；但是如果多邊形的某個(gè)頂點(diǎn)和線段相交，還必須判斷兩相鄰交點(diǎn)之間的線段是否包含于多邊形內(nèi)部（反例見圖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ú)寫出來(lái)。另外，一開始就先利用矢量叉乘判斷線段與線段（或直線）是否相交，如果結(jié)果是相交，那么在后面就可以將線段全部看作直線來(lái)考慮。需要注意的是，我們可以將直線或線段方程改寫為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è)豐富多彩的世界。