幾何常用算法與判斷線段相交

1、代碼角找到。下面這個函數(shù)在我寫的計(jì)算幾何庫函數(shù)里面有，那個庫可以在 HYPERLINK /%e7%9a%84%e8%b5%84%e6%ba%90%e4%b8%ad%e5%bf%83 /的資源中心算法簡單說明：首先判斷以兩條線段為對角線的矩形是否相交，如果不相交兩條線段肯定也不相交。(所謂以a1b2為對角錢的矩形就是以兩邊長為|a1.x - b2.x|和|a1.y - b2.y|以及a1b2為對角線的矩形)。如果相交的話，利用矢量叉乘判斷兩條線段是否相互跨越，如果相互跨越顯然就相交，反之則不相交。算法不難，但是一些特 殊情況需要考慮到，比如兩條相段共線且在斷點(diǎn)處相交。下面的代碼經(jīng)過測試了，應(yīng)該沒

2、有bug，如果你真的發(fā)現(xiàn)了 bug請告 訴我：)返回(P1-P0)*(P2-P0)的叉積。*若結(jié)果為正，則P0,P1在P0,P2的順時針方向；*若為 0 貝OP0,P1P0,P2共線；*若為負(fù)則P0,P1在P0,P2的在逆時針方向；*可以根據(jù)這個函數(shù)確定兩條線段在交點(diǎn)處的轉(zhuǎn)向,*比如確定p0p 1和p1p2在p1處是左轉(zhuǎn)還是右轉(zhuǎn)，只要*求(p2-p0)*(p1-p0)，若0則左轉(zhuǎn)，0則右轉(zhuǎn)，=0則 *共線float multiply(TPoint p1,TPoint p2,TPoint p0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.

3、y);/確定兩條線段是否相交int intersect(TLineSeg u,TLineSeg v)return( (max(u.a.x,u.b.x)=min(v.a.x,v.b.x)&(max(v.a.x,v.b.x)=min(u.a.x,u.b.x)&(max(u.a.y,u.b.y)=min(v.a.y,v.b.y)&(max(v.a.y,v.b.y)=min(u.a.y,u.b.y)& (以兩線段為對角線的矩形是否相交)(multiply(v.a,u.b,u.a)*multiply(u.b,v.b,u.a)=0)&(multiply(u.a,v.b,v.a)*multiply(v.b,

4、u.b,v.a)=0);(是否相互跨立)忘記了說明TPoint和TLineSeg的定義了：)struct TPoint float x,y;struct TLineSeg TPoint a,b;；上面的算法避免了除法運(yùn)算，所以不會出現(xiàn)計(jì)算誤差NOwcan兄的方法雖然簡單，但是求兩條直線的交點(diǎn)需要用到除法，當(dāng)兩條線段相交但是很接近平行的時候，會有精度上的誤 差，所以我的方法不用除法更好一點(diǎn)。這是計(jì)算幾何中的經(jīng)典算法計(jì)算幾何常用算法(一共23個)矢量減法設(shè)二維矢量P=(x1,y1)，Q=(x2,y2)則矢量減法定義為：P - Q = ( x1 - x2 , y1 - y2 )顯然有性質(zhì)P-Q =

5、-( Q-P )如不加說明，下面所有的點(diǎn)都看作矢量，兩點(diǎn)的減法就是矢量相減；矢量叉積設(shè)矢量 P =(x1,y1)，Q=(x2,y2)則矢量叉積定義為：P x Q = x1*y2 - x2*y1 得到的是一個標(biāo)量顯然有性質(zhì) Px Q=-(Q xP )Px(-Q)=-(PxQ)如不加說明，下面所有的點(diǎn)都看作矢量，點(diǎn)的乘法看作矢量叉積；叉乘的重要性質(zhì)：若PxQ 0 ,則P在Q的順時針方向若PxQ若PxQ=0 ,則P與Q共線，但可能同向也可能反向判斷點(diǎn)在線段上設(shè)點(diǎn)為Q，線段為P1P2 ，判斷點(diǎn)Q在該線段上的依據(jù)是：(Q - P1 ) x ( P2 - P1 ) = 0 = 共線且 Q 在以 P1，P2

6、為對角頂點(diǎn)的矩形內(nèi)判斷兩線段是否相交我們分兩步確定兩條線段是否相交：.快速排斥試驗(yàn)設(shè)以線段 P1P2 為對角線的矩形為R，設(shè)以線段 Q1Q2 為對角線的矩形為T，如果R和T不相交，顯然兩線段不會相交；.跨立試驗(yàn)如果兩線段相交，則兩線段必然相互跨立對方，如圖1所示。在圖1中，P1P2跨立Q1Q2 ，則矢量 (P1 - Q1 ) 和( P2- Q1）位于矢量（Q2 -Q1)的兩側(cè)，即( P1- Q1)x(Q2 -Q1)*( P2 - Q1 ) x ( Q2 - Q1 )0當(dāng)（P1 -Q1 ) x( Q2-Q1)=0 時，說明(P1 - Q1 )和(Q2 - Q1 )共線，但是因?yàn)橐呀?jīng)通過快速排斥試

7、驗(yàn)，所以P1 一定在線段Q1Q2上；同理，( Q2- Q1)x( P2-Q1)=0 說明 P2 一定在線段 Q1Q2上。所以判斷P1P2跨立Q1Q2的依據(jù)是:( P1- Q1 ) x ( Q2 -Q1 )*( Q2 -Q1 )x ( P2 -Q1 )0同理判斷Q1Q2跨立P1P2的依據(jù)是：（ Q1 - P1 ） x （ P2 -P1 )*( P2 -P1 )x ( Q2 -P1 )0至此已經(jīng)完全解決判斷線段是否相交的問題。判斷線段和直線是否相交如果線段 P1P2和直線Q1Q2相交，則P1P2跨立Q1Q2，即：Q1 ) x ( P2(P1 - Q1 ) x ( Q2 - Q1 )*( Q2判斷矩

8、形是否包含點(diǎn)只要判斷該點(diǎn)的橫坐標(biāo)和縱坐標(biāo)是否夾在矩形的左右邊和上下邊之間。判斷線段、折線、多邊形是否在矩形中因?yàn)榫匦问莻€凸集，所以只要判斷所有端點(diǎn)是否都在矩形中就可以了。6.判斷矩形是否在矩形中只要比較左右邊界和上下邊界就可以了。（左右邊界相互包含且上下邊界相互包含）判斷圓是否在矩形中圓在矩形中的充要條件是：圓心在矩形中且圓的半徑小于等于圓心到矩形四邊的距離的最小值。判斷點(diǎn)是否在多邊形中以點(diǎn)P為端點(diǎn)，向左方作射線L，由于多邊形是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無窮遠(yuǎn)處開始自左 向右移動，遇到和多邊形的第一個交點(diǎn)的時候，進(jìn)入到了多邊形的內(nèi)部，遇到第二個交點(diǎn)的時候，離開了多邊形

9、，.所以很容 易看出當(dāng)L和多邊形的交點(diǎn)數(shù)目C是奇數(shù)的時候，P在多邊形內(nèi)，是偶數(shù)的話P在多邊形外。但是有些特殊情況要加以考慮。如果L和多邊形的頂點(diǎn)相交，有些情況下交點(diǎn)只能計(jì)算一個，有些情況下交點(diǎn)不應(yīng)被計(jì)算（你 自己畫個圖就明白了）；如果L和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計(jì)。為了統(tǒng)一起見，我們在計(jì)算射線L和多邊形的 交點(diǎn)的時候，1。對于多邊形的水平邊不作考慮；2。對于多邊形的頂點(diǎn)和L相交的情況，如果該頂點(diǎn)是其所屬的邊上縱坐標(biāo)較 大的頂點(diǎn)，則計(jì)數(shù)，否則忽略；3。對于P在多邊形邊上的情形，直接可判斷P屬于多邊行。由此得出算法的偽代碼如下：count 0;2.以P為端點(diǎn)，作從右向左的射線L;3,

10、 for多邊形的每條邊s4.do if P在邊s上5.then return true;6.if s不是水平的7.then if s的一個端點(diǎn)在L上且該端點(diǎn)是s兩端點(diǎn)中縱坐標(biāo)較大的端點(diǎn)9.then count count+110.else if s和L相交11.then count count+1;12.if count mod 2 = 113.then return true14.else return false;其中做射線L的方法是：設(shè)P的縱坐標(biāo)和P相同，橫坐標(biāo)為正無窮大（很大的一個正數(shù)），則P和P就確定了射線L。這個算 法的復(fù)雜度為O（n）。判斷線段是否在多邊形內(nèi)線段在多邊形內(nèi)的一個必

11、要條件是線段的兩個端點(diǎn)都在多邊形內(nèi)；如果線段和多邊形的某條邊內(nèi)交（兩線段內(nèi)交是指兩線段相交且交點(diǎn)不在兩線段的端點(diǎn)）因?yàn)槎噙呅蔚倪叺淖笥覂蓚?cè)分屬多 邊形內(nèi)外不同部分，所以線段一定會有一部分在多邊形外。于是我們得到線段在多邊形內(nèi)的第二個必要條件：線段和多邊形的 所有邊都不內(nèi)交；線段和多邊形交于線段的兩端點(diǎn)并不會影響線段是否在多邊形內(nèi)；但是如果多邊形的某個頂點(diǎn)和線段相交，還必須判斷兩相鄰 交點(diǎn)之間的線段是否包含與多邊形內(nèi)部。因此我們可以先求出所有和線段相交的多邊形的頂點(diǎn)，然后按照X-Y坐標(biāo)排序，這樣 相鄰的兩個點(diǎn)就是在線段上相鄰的兩交點(diǎn)，如果任意相鄰兩點(diǎn)的中點(diǎn)也在多邊形內(nèi)，則該線段一定在多邊形內(nèi)。證

12、明如下：命題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之間至少還有兩個該線段和多邊形的交點(diǎn)，這和P1P2是相鄰兩交點(diǎn)矛盾，故命題成立。證畢由命題1直接可得出推論：推論2：設(shè)多邊形和線段PQ的交點(diǎn)依次為P1,P2,.Pn，其中Pi和Pi+1是相鄰兩交點(diǎn)，線段PQ在多邊形內(nèi)的充要

13、條件是：P，Q在 多邊形內(nèi)且對于i =1, 2,., n-1，Pi ,Pi+1的中點(diǎn)也在多邊形內(nèi)。在實(shí)際編程中，沒有必要計(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多邊形的每條邊sdo if線段的某個端點(diǎn)在s上then 將該端點(diǎn)加入pointSet;else if s的某個端點(diǎn)在線段PQ

14、上then將該端點(diǎn)加入pointSet;else if s和線段PQ相交/ 這時候可以肯定是內(nèi)交then return false;將pointSet中的點(diǎn)按照X-Y坐標(biāo)排序，X坐標(biāo)小的排在前面，對于X坐標(biāo)相同的點(diǎn)，Y坐標(biāo)小的排在前面；forpointSet 中每兩個相鄰點(diǎn)pointSeti , pointSet i+1do if pointSeti , pointSet i+1的中點(diǎn)不在多邊形中then return false;return true;這個算法的復(fù)雜度也是O(n)。其中的排序因?yàn)榻稽c(diǎn)數(shù)目肯定遠(yuǎn)小于多邊形的頂點(diǎn)數(shù)目n，所以最多是常數(shù)級的復(fù)雜度，幾乎 可以忽略不計(jì)。判斷折線在多

15、邊形內(nèi)只要判斷折線的每條線段是否都在多邊形內(nèi)即可。設(shè)折線有m條線段，多邊形有n個頂點(diǎn)，則復(fù)雜度為O(m*n)。判斷多邊形是否在多邊形內(nèi)只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷一個有m個頂點(diǎn)的多邊形是否在一個有n個頂點(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是凸集，所

16、以只要判斷是否每個頂點(diǎn)都在圓內(nèi)即可。判斷圓是否在圓內(nèi)設(shè)兩圓為O1,O2,半徑分別為r1, r2,要判斷O2是否在O1內(nèi)。先比較r1，r2的大小，如果r1r2則O2不可能在O1內(nèi);否則如果兩圓心的距離大于r1r2 ，貝U O2不在O1內(nèi)；否 UO2在O1內(nèi)。計(jì)算點(diǎn)到線段的最近點(diǎn)如果該線段平行于X軸(Y軸)，則過點(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=(kA2 *pt1.x +k* (point.y- pt1.y ) +y=k*( x - pt1.x) + pt1.y;point.x ) / (kA2+1)然后再判斷垂足是否在線段上，如果在線段上則返回垂足；如果不在則計(jì)算兩端點(diǎn)到垂足的距離，選擇距離垂足較近的端點(diǎn)返 回。.計(jì)算點(diǎn)到折線、矩形、多邊形的最近點(diǎn)只要分別計(jì)算點(diǎn)到每條線段的最近點(diǎn)，記錄最近距離，取其中最近距離最小的點(diǎn)即可。.計(jì)算點(diǎn)到