標籤：

如何判斷一條線段和一個矩形或者圓相交？

12-30

如何判斷一條線段和一個矩形或者圓相交？

有沒有什麼比較快速的方法？

用四條線段（矩形），半徑（圓）是不是比較慢？

線段與多邊形關係的演算法

判斷一條線段與任何多邊形的關係，包括 相交，包含，相切，無任何關係。

--------------更新-------------------------

上面是在手機上寫的答案，只能給出連接。下面是詳細的過程：

介紹

最近項目中要用到有關幾何（Geometry）方面的知識，程序需要判斷給定的一條線段（Segment）與指定多邊形（Polygon）的位置關係。這種關係分為三種：多邊形包含線段、多邊形與線段相交以及多邊形與線段無關聯。

起初我以為.NET類庫中已經包含此種判定功能的API，比如類似System.Drawing.Region這些類型，後來等到實際要用的時候才發現根本就沒這種「高級」演算法。

沒辦法，只能自己去寫代碼實現。後來在stackoverflow（鏈接）上找到了一個解決方案，不過都是源代碼，並沒有詳細的說明。本文參照原作者提供的源碼，進行詳細的說明。如果你只需要最終答案，可以不用閱讀本文所有內容，文章最後會給出判斷源代碼，很簡答使用，就一個方法，代入參數直接調用即可，但如果你想搞清楚怎麼回事，那麼可以靜下心來看看本文全部內容，雖然比較複雜，但是相信一定會有所收穫的。

解決思路

線段與多邊形的關係只有三種：無關聯、相交以及包含。我們可以分以下兩步來進行分析：

  • 判斷線段與多邊形的各條邊是否相交，若是，則線段與多邊形屬於「相交」關係；
  • 如果線段與多邊形的任何邊都不相交，那麼我們接著判斷線段的任意一個端點是否在多邊形內部，若是，則整條線段肯定在多邊形內（即「包含」關係）；若不是，則整條線段肯定都在多邊形外部（即「無關聯」關係）。

上面兩步看似簡單，實質相當複雜。判斷線段與多邊形各條邊的關係涉及到了「線段與線段關係的判斷」、判斷線段任意一個端點是否在多邊形內部涉及到了「點與線段關係的判斷」，總之，要解決大問題必須先解決一些小問題：

  • 點與線段的關係
  • 線段與線段的關係
  • 點與多邊形的關係

下面依次介紹以上三個小問題和整個大問題的解決方法。

問題一：點與線段的關係

點與線段只有兩種關係：

  • 點在線段上
  • 點與線段無關聯

這種判斷方法很簡單，只要我們能確保給定點P的Y坐標在線段AB兩個端點的Y坐標之間（或者點P的X坐標在兩個端點的X坐標之間也行），並且點P與線段AB任意端點間的斜率與AB線段斜率相等即可說明點P在線段AB上。

如上圖，如果Y2&

問題二：線段與線段的關係

線段與線段也只有兩種關係：

  • 兩線段相交
  • 兩線段無關聯

這種判斷稍微複雜一些，為了更方便計算，涉及到了「平移」、「旋轉」等操作。給定線段AB和CD，先將兩線段整體平移（注意是整體），讓線段AB的A端點與原點（0,0）重合，接著將兩線段整體旋轉（注意是整體），讓線段AB與X軸的正方向重合。

如上圖，將任意兩線段AB和CD按照「先整體平移，再整體旋轉」的順序操作一遍，最終讓線段AB的A端點與原點（0,0）重合，並讓線段AB與X軸正方向重合。很顯然，任意線段均可以進行以上操作。接下來，再在此基礎上進行判斷就比較簡單了，如果線段CD的兩個端點C和D的Y坐標均大於零（分布在第一、二象限）或者均小於零（分布在第三、四象限），那麼AB與CD肯定不相交，換句話說，CD的兩個端點必須一個在X軸上方另一個在X軸下方時，兩條線段才有可能相交。如果線段CD的端點確實是一個在X軸上方一個在X軸下方，接下來再計算直線AB和直線CD（注意這裡說的是直線）的交點（這時候兩條直線一定有交點，並且交點在X軸上），這裡暫定交點為P，如果P在X軸的負方向上（P.X&<0），那麼說明線段AB和CD不相交，如果P在X軸正方向但是P的X坐標大於線段AB的長度，那麼說明線段AB和CD也不相交，其他情況下，線段AB和CD才屬於「相交」關係。

問題三：點與多邊形的關係

點與多邊形有三種關係：

  • 點與多邊形無關聯
  • 點在多邊形上（某條邊上）
  • 點在多邊形內部

判斷點是否在多邊形上需要用到解決問題一的方法，即判斷點與線段的關係。如果點不在多邊形上，那麼需要判斷它在多邊形內部還是外部，這個判斷方法說難也不難，說不難也挺難的。事實上，只需要判斷點在多邊形每條邊的左邊還是右邊（注意這裡的左邊和右邊定義，見下圖）

如上圖，多邊形ABCDE在右側光源的照射下，它的每條邊（如AB、BC等）都會與Y軸上各自的投影（如A`B`、B`C`等）之間形成一個梯形區域，如ABB`A`、BCC`B`等。我們只需要統計給定點P在這些梯形區域中的次數，若點P在某條邊對應的梯形區域內，那麼計數N加1，最後看N是否為偶數，如果N為偶數（包括0），那麼說明點P不在多邊形內部；否則，點P在多邊形內部。上圖中P1的計數N==1（只在ABB`A`內部），所以點P1在多邊形ABCDE內部，而點P2的計數N==2（同時在AEE`A`和BCC`B`內部），所以點P2不在多邊形ABCDE內部，同理，點P3的計數N==0，所以它也不在多邊形內部。

由上可以看出，解決問題三需要依賴問題一的解決方法。以上三個小問題都已經有解決方案了，那麼我們再來看看最開始那個問題「線段與多邊形關係」怎麼解決。

問題四：線段與多邊形關係

前三個問題解決了，這個問題其實已經很簡單了。再看一遍【解決思路】中的兩個步驟：

  • 判斷線段與多邊形的各條邊是否相交，若是，則線段與多邊形屬於「相交」關係；
  • 如果線段與多邊形的任何邊都不相交，那麼我們接著判斷線段的任意一個端點是否在多邊形內部，若是，則整條線段肯定在多邊形內（即「包含」關係）；若不是，則整條線段肯定都在多邊形外部（即「無關聯」關係）。

我們可以使用問題二的解決方法去判斷線段是否與多邊形的各條邊相交，如果都不相交，那麼我們可以使用問題三的解決方法去判斷線段的某個端點是否在多邊形內部，如果在，那麼整個線段必然在多邊形內部；否則，整個線段必然在多邊形外部。

是的，問題四就是這麼簡單！只要我們弄懂了前三個問題的解決思路。

先說線段與圓形（circle）的相交檢測。（這裡的圓形是指圓形的曲線，不包含面積。包含面積的稱作圓盤，稍後更新。）

設線段為參數方程

mathbf{x}(t) = mathbf{o} + tmathbf{d}, t in [0, 1]

設圓為隱含方程

left | mathbf{x} - mathbf{c} ight |^2 = r ^2

聯合兩個方程，得 t 的二次方程：

egin{align*} left | mathbf{o} + tmathbf{d} - mathbf{c} ight |^2 = r^2\ left |tmathbf{d} + (mathbf{o} - mathbf{c}) ight |^2 = r^2\ left | mathbf{d} ight|^2 t^2 + 2 mathbf{d}cdot(mathbf{o} - mathbf{c})t + left | mathbf{o} - mathbf{c} ight |^2 - r^2 = 0\ end{align*}

求二次方程的判別式。

若 Delta < 0 則無實根，即兩形狀不相交；

若 Delta ge 0 則求實根t_0, t_1，若其中一個實根滿足 t_i in [0, 1]則兩形狀相交。

此方法可擴展至三維球面（或更高維），也可用於光線（ray）和直線（line）。光線使用t in [0, infty]，而直線則只需判斷判別式。

----

待續

第一次答題，好緊張，感覺編輯器太不好用，排版太難看了。對這兩個問題的詳細介紹參見[6],[8]提供的博客，會有詳細的偽碼解釋。

一. 線性對象與矩形對象的裁剪

問題描述：求矩形(R:X({t_0},{t_1}) = C + {t_0} cdot {vec e_0} + {t_1} cdot {vec e_1}, - {u_0} le {t_0} le {u_0}, - {u_1} le {t_1} le {u_1})對線段({P_0}{P_1})的裁剪。

圖1. 線段的端點坐標沿著矩形的兩條軸的投影

Cyrus-Beck演算法解決了凸多邊形或者凸多面體對象對線性對象的裁剪，矩形也是一個凸多邊形，同樣適用。在圖形學中，有一個經典的問題，就是矩形窗口對線段的裁剪，即二維平面上軸對齊的矩形對線段的裁剪問題。對於非軸對齊的矩形的裁剪，可以把線段坐標按矩形的兩條互相垂直的軸作投影，把矩形轉化為軸對齊的情況。如圖1所示，把線段的兩個端點({P_0})和({P_1})投影到({vec e_0})和({vec e_1})上，得到新的坐標P0"和P1"，投影等式為[{P_0}

問題就轉化為求軸對齊的矩形對線段P0"P1"的裁剪問題。求出裁剪後的線段Q0"Q1"後，再變換成原矩形的坐標，設({Q_0}，則變換等式是

[{Q_0} = {x_0}{vec e_0} + {y_0}{vec e_1} + C,{Q_1} = {x_1}{vec e_0} + {y_1}{vec e_1} + C]

下面將重點討論軸對齊的矩形對線段的裁剪演算法，大致有五種演算法，可以解決軸對齊的矩形對線段的裁剪演算法。最早由Danny CohenIvan Sutherland提出的一種演算法，稱為Cohen-Sutherlad裁剪演算法（簡稱CS演算法），該演算法把平面分成9個區域，根據點的位置確定與矩形的相交邊。後來，CyrusBeck[1](1978)提出了Cyrus-Beck裁剪演算法（簡稱CB演算法），線段用參數方程來表示，計算與矩形的每條邊所在的直線的交點，但是該演算法的效率相對較低。LiangBarsky[2](1984)嘗試對CS演算法進行改進，提出了該演算法的一種變種，稱為Liang-Barsky裁剪演算法（簡稱為LB演算法），Liang和Barsky[3](1992)進一步對LB演算法進行了改進。SobkowPospisilYang[4](1987)描述了另外一種線段的裁剪演算法，稱為快速裁剪演算法（簡稱為SPY演算法）。Nicholl,LeeNicholl[5]對前面四種線段裁剪演算法進行了較為深入地分析和比較，並且描述了一種更加高效的演算法，稱為Nicholl-Lee-Nicholl演算法（簡稱為NLN演算法）。對比五種演算法的性能，它們並不是在數量級上的差別，只是演算法中運算個數的差別，比如NLN演算法擁有最少的除法次數。CS、LB和SPY在不同機器、不同的數據集上，會顯示出不同的演算法性能。在演算法實現上，NLN和SPY演算法較為複雜，CS和LB相對簡單。如果不會特別苛求演算法的性能，建議選擇CS或者LB演算法。

1.1. Cohen-Sutherland裁剪演算法

設矩形的左側邊為(x = {x_{min }})，右側邊為(x = {x_{max }})，下側邊為 (y = {y_{min }})，上側邊為 (y = {y_{max }})。矩形的四條邊所在的直線，把平面分成9個區域，可以用4位的編碼來指定點所在的區域，我們可以作如下所規定：

  • 0000 點在矩形區域內；
  • 0001 點在左側邊的左側；
  • 0010 點在右側邊的右側；
  • 0100 點在下側邊的下方；
  • 1000 點在上側邊的上方；

圖2. 區域的編碼表示

對於左上側的區域的編碼，就可以用0001 | 1000 = 1001得到，同理可以得到左下區域，右上區域和右下區域的編碼，如圖2所示。給定一個坐標，判斷它所在區域的編碼的偽碼實現，如下所示：

int computeCode( Real x, Real y)
1. 令INSIDE = 0000, LEFT = 0001 , RIGHT = 0010 , BOTTOM = 0100 , TOP = 1000;
2. code = INSIDE;
3. if x &< xmin, then 4. code |= LEFT; 5. else if x &> xmax, then
6. code |= RIGHT;
7. end if;
8. if y &< ymin, then 9. code |= BOTTOM; 10. else y &> ymax, then
11. code |= TOP;
12. end if;
13. return code;

設當前線段的兩個端點 [{Q_0}]和 [{Q_1}]的編碼分別是 [{c_0}] 和 [{c_1}]，若 [{c_0} = 0000]且 [{c_1} = 0000]，說明線段在矩形區域內；若[({c_0} {c_1}) e 0]，說明線段一定不與矩形區域相交；否則，說明線段與矩形相交，求出線段與矩形邊界的交點，線段上一部分可能在矩形內，另一部分一定在矩形外，將在矩形外的部分丟棄。對於保留下的線段，重複這個過程，直至線段的兩個端點都在矩形內為止，演算法最多循環四次。

圖3. 沿著矩形邊界裁剪線段

如何計算直線對線段的截斷呢？如圖3所示，顯示了線段與矩形的右邊界的相交情況，由相似三角形，可得

[frac{{y - {y_0}}}{{{y_1} - {y_0}}} = frac{{{x_{max }} - {x_0}}}{{{x_1} - {x_0}}} ag{1}]

則有

[left{ egin{array}{l}x = {x_{max }}\y = {y_0} + frac{{{x_{max }} - {x_0}}}{{{x_1} - {x_0}}}({y_1} - {y_0})end{array} ight. ag{2}]

同理，可以計算出另外三條邊界的相交情況，使用等式（2）計算交點時，可以保證兩個端點不在同一個區域，因此分母一定不為零。

Cohen-Sutherlad線段裁剪演算法的偽碼如下所示：

求矩形[R:X({t_0},{t_1}) = C + {t_0} cdot {vec e_0} + {t_1} cdot {vec e_1}, - {u_0} le {t_0} le {u_0}, - {u_1} le {t_1} le {u_1}]對線段[{P_0}{P_1}]的裁剪。

1. 令INSIDE = 0000, LEFT = 0001, RIGHT = 0010, BOTTOM = 0100, TOP = 1000;
2. x0=(P0?C)?e? 0,y0=(P0?C)?e? 1 ;
3. x1=(P1?C)?e? 0,y1=(P1?C)?e? 1 ;
4. xmin=?u0,ymin=?u1,xmax=u0,ymax=u1 ;
5. code0 = computeCode(x0 , y0);
6. code1 = computeCode(x1 , y1);
7. accept = true;
8. while( true )
9. if !(code0 | code1), then
10. break;
11. else if (code0 code1), then
12. accept = false;
13. break;
14. end if;
15. code = code0≠0 ? code0 : code1;
16. if (code TOP), then
17. x=x0+(x1?x0)?(ymax?y0)/(y1?y0) ;
18. y=ymax ;
19. else if (code BOTTOM), then
20. x=x0+(x1?x0)?(ymin?y0)/(y1?y0) ;
21. y=ymin ;
22. else if (code LEFT), then
23. x=xmin ;
24. y=y0+(y1?y0)?(xmin?x0)/(x1?x0) ;
25. else if (code RIGHT), then
26. x=xmax ;
27. y=y0+(y1?y0)?(xmax?x0)/(x1?x0) ;
28. end if;
29. if code0 == code, then
30. x0=x,y0=y ;
31. code0 = computeCode(x0,y0);
32. else
33. x1=x,y1=y ;
34. code1 = computeCode(x1,y1);
35. end if;
36. end while;
37. if accept == true, then
38. Q0=x0e? 0+y0e? 1+C ;
39. Q1=x1e? 0+y1e? 1+C ;
40. return true; //裁剪線段是 Q0Q1 ;
41. else
42. return false; //捨棄線段
43. end if;

2. Liang-Barsky裁剪演算法

設矩形的左側邊為[x = {x_{min }}]，右側邊為[x = {x_{max }}]，下側邊為 [y = {y_{min }}]，上側邊為 [y = {y_{max }}]。。如果一個點(x,y)在矩形區域內，則它滿足下面的不等式：

[left{ egin{array}{l}{x_{min }} le x le {x_{max }}\{y_{min }} le y le {y_{max }}end{array} ight. ag{3}]

設線段的兩個端點分別是[{P_0}({x_0},{y_0})]和 [{P_1}({x_1},{y_1})]，線段可以用參數方程的形式來表示

[left{ egin{array}{l}x = {x_0} + Delta x cdot t\y = {y_0} + Delta y cdot tend{array} ight. ag{4}]

其中， [Delta x = {x_1} - {x_0},Delta y = {y_1} - {y_0}]。

把等式（4）代入等式（3）中，可得

[left{ egin{array}{l} - Delta x cdot t le {x_0} - {x_{min }}\Delta x cdot t le {x_{max }} - {x_0}\ - Delta y cdot t le {y_0} - {y_{min }}\Delta y cdot t le {y_{max }} - {y_0}end{array} ight. ag{5}]

等式（5）可以用一個統一的不等式形式來表示

[{p_i}t le {q_i},i = 1,2,3,4 ag{6}]

其中，

[egin{array}{*{20}{l}}{{p_1} = - Delta x,}{{q_1} = {x_0} - {x_{min }}}\{{p_2} = Delta x,}{{q_2} = {x_{max }} - {x_0}}\{{p_3} = - Delta y,}{{q_3} = {y_0} - {y_{min }}}\{{p_4} = Delta y,}{{q_4} = {y_{max }} - {y_0}}end{array}]

現在考慮從幾何意義上理解 [{q_i}]和 [{p_i}]。矩形的邊界所在的直線把平面分成兩半，稱矩形所在的一側半平面為可視半面，另一側半平面為不可視半面。線段與邊界線的交點處的參數值 [t = {q_i}/{p_i}]，把它代入等式（6）就是交點。對於不等式中的 [{q_i}] ，若[{q_i} ge 0] ，說明點[{P_0}]在可視可半面；若[{q_i} prec 0] ，說明點[{P_1}]在不可視半面。對於不等式中的 [{p_i}]，若[{p_i} prec 0] ，則不等式是 [t ge {q_i}/{p_i}] ，說明線段[{P_0}{P_1}]可能由不可視半面進入可視半面，此時[{q_i} ge 0]，則有 [{t_0} prec 0]，那麼不再需要計算交點；若[{p_i} succ 0] ，不等式是 [t le {q_i}/{p_i}]，說明線段 [{P_0}{P_1}]可能由可視半面進入不可視半面，此時[{q_i} ge {p_i}]，則有 [{t_1} succ 1]，那麼不再需要計算交點；若 [{p_i} = 0] ，不等式是 [0 le {q_i}] ，線段與邊界線平行，如果 [{q_i} prec 0] ，捨棄線段，因它它在邊界之外，否則，完整的保留線段。 [{q_i}]和 [{p_i}]的幾何解釋的流程圖，如圖3所示。

圖3. [{q_i}]和 [{p_i}]的幾何解釋的流程圖

對於給定其個裁剪邊界的 q 和 p值，當 p?0,q?0 時， r=q/p ，若 r?t1 ，捨棄線段，否則更新 t0=r ；當 p?0,q?p 時， r=q/p ，若 r?t0 ，捨棄線段，否則，更新 t1=r ；若 p=0 時，若 q?0 ，捨棄線段，否則，保留線段， t0 和 t1 值不變。邊界裁剪線段的實現偽碼，如下所示：

bool clip(Real p,Real q,Real t0,Real t1) //Real是單精度或雙精度
1. if p&<0 q&<0, then 2. r = q / p; 3. if r &> t1, then
4. return false;
5. else if r &> t0 , then
6. t0 = r;
7. end if;
8. else if p&>0 q&

初始化t0=0和t1=1，計算出矩形的四條裁剪邊的p值和q值，重複調用clip()方法四次，來判斷是捨棄線段還是改變參數t。

舉個例子來解釋Liang-Barsky線段裁剪演算法，設線段 P0P1 的兩個端點分別是 P0(?1,?2) 和 P1(2,4) ，矩形的邊界分別是 xmin=0 , xmax=1 , ymin=0 和 ymax=1 ，則有 Δx=3 和 Δy=6 。等式式（5），得到

[egin{array}{*{20}{l}}{{p_1} = - Delta x = - 3,}{{q_1} = {x_0} - {x_{min }} = - 1,}{{q_1}/{p_1} = 1/3;}\{{p_2} = Delta x = 3,}{{q_2} = {x_{max }} - {x_0} = 2,}{{q_2}/{p_2} = 2/3;}\{{p_3} = - Delta y = - 6,}{{q_3} = {y_0} - {y_{min }} = - 2,}{{q_3}/{p_3} = 1/3;}\{{p_4} = Delta y = 6,}{{q_4} = {y_{max }} - {y_0} = 3,}{{q_3}/{p_3} = 1/2;}end{array}]

根據這些數值，可以計算出t0和t1的值，即

[left{ egin{array}{l}{t_0} = max ({ {q_i}/{p_i}|{p_i} prec 0,i = 1,2,3,4} cup { 0} ) = max (1/3,1/3,0) = 1/3\{t_1} = min ({ {q_i}/{p_i}|{p_i} prec 0,i = 1,2,3,4} cup { 1} ) = max (2/3,1/2,1) = 1/2end{array} ight.]

在實現中特別注意，當 pi?0,qi≥0 或者 pi?0,qi≥pi 時，可以忽略 qi/pi 的計算。

Liang-Barsky線段裁剪演算法的偽碼如下所示：

求矩形[R:X({t_0},{t_1}) = C + {t_0} cdot {vec e_0} + {t_1} cdot {vec e_1}, - {u_0} le {t_0} le {u_0}, - {u_1} le {t_1} le {u_1}]對線段[{P_0}{P_1}]的裁剪。

1. x0=(P0?C)?e? 0,y0=(P0?C)?e? 1 ;
2. x1=(P1?C)?e? 0,y1=(P1?C)?e? 1 ;
3. xmin=?u0,ymin=?u1,xmax=u0,ymax=u1 ;
4. t0 = 0, t1 = 1;
5. Δx = x1 – x0;
6. if clip(- Δx , x0-xmin, t0, t1) == true clip( Δx , xmax-x0, t0, t1) == true, then
7. Δy = y1 – y0;
8. if clip(- Δy , y0-ymin, t0, t1) == true clip( Δy , ymax-y0, t0, t1) == true, then
9. if t0 ≥ 0, then
10. x=x0+t0?Δx,y=y0+t0?Δy ;
11. end if;
12. Q0=xe? 0+ye? 1+C ;
13. if t1 ≤ 1, then
14. x=x0+t1?Δx,y=y0+t1?Δy ;
15. end if;
16. Q1=xe? 0+ye? 1+C ;
17. return true; //裁剪線段是 Q0Q1
18. end if;
19. end if;
20. return false; //捨棄線段

二. 射線與球的相交測試

三維空間上射線與球的相交測試演算法，也可以用於解決二維空間上射線與圓的相交測試問題，線段與圓的相交測試是其中的一個特例。

至少有兩種演算法，解決三維空間上射線與球的相交測試問題。一種是參數方程法，通過求解參數方程的方法來求解；另外一種演算法，就稱為優化演算法，在Akenine-M?ller等[7]書中有介紹。

圖4. 射線與球體相交測試的優化方法

設射線的參數方程為 (L(t) = P + t cdot vec d)，其中 (vec d)是單位長度。如圖4（a）所示，計算出從射線原點出發到球體中心的向量 (vec a = C - P)，計算出該向量的長度({a^2} = vec a cdot vec a)，若 ({a^2} prec {R^2}) ，那麼說明射線的原點在球體內部，一定與球體相交，如圖4（c）所示，若只是想判斷它們是否相交，演算法至此就可以結束了。否則，計算向量 (vec a)沿著 (vec d)方向的投影： (l = vec d cdot vec a) ，若(l prec 0)，說明球體在射線原點的後面，且射線的原點在球體外，因此可以判定射線與球體一定不相交，完成第一次排除測試，如圖1（b）所示。否則，利用勾股定理，計算出球心與投影之間距離的平方：({m^2} = {a^2} - {l^2}) ，若 ({m^2} succ {R^2}) ，則可以判定射線與球體一定不相交，完成第二次排除測試。如果射線和球體經過兩次排除測試，則就可以判定它們一定相交。如果只希望判定它們是否相交，演算法至此就可以結束了。

接下來，計算射線與球體的交點，計算出距離的平方，({q^2} = {R^2} - {m^2})，因為 ({m^2} le {R^2})，所以計算出 (q)的值。相交點與射線原點之間的距離為(t = l pm q) ，求第一個相交點，若({l^2} succ {R^2})，說明射線原點在球體外，取(t = l - q)，否則取 (t = l + q)，最後把 t 值代入射線的參數方程中，就求出第一個相交點。

偽代碼就不貼了，排版起來太難看，參見博客[8].

參考

[1] Mike Cyrus, and Jay Beck. "Generalized two-and three-dimensional clipping."Computers Graphics, vol.3, no.1, pp.23-28, 1978.

[2] You-Dong Liang, and Brian A. Barsky. "A new concept and method for line clipping." ACM Transactions on Graphics (TOG), vol.3, no.1, pp.1-22, 1984.

[3] Brian A. Barsky, You Liang, and Mel Slater. "Some Improvements to a Parametric Line Clipping Algorithm." 1992.

[4] Mark S. Sobkow, Paul Pospisil, and Yee-Hong Yang. "A fast two-dimensional line clipping algorithm via line encoding." Computers graphics, vol.11, no.4, pp.459-467, 1987.

[5] Tina M. Nicholl, D. T. Lee, Robin A. Nicholl. "An efficient new algorithm for 2-D line clipping: Its development and analysis". SIGGRAPH "87, pp.253–262, 1987.

[6] twinklingstar. "矩形". website&.

[7] Tomas Akenine-M?ller, Eric Haines, and Naty Hoffman. Real-time rendering, second edition. AK, 2002.

[8] twinklingstar. "包圍體." website&<11. 包圍體 | TwinklingStar&>.

PNPOLY - Point Inclusion in Polygon Test

（1）與矩形：四個點分別代入到直線方程，如果結果符號相同則不相交；否則，直線與矩形相交。

（2）與圓：算下圓心到直線距離，大於圓半徑不相交；否則，相交。

還有比這更快的么？

-----------edit------------

上面不對。題主問的是線段。

線段有三個volonoi域。如果你圓心的在線段上的投影在線段的外側，那就計算圓心到頂點之間的距離；否則計算圓心到線段的距離。

假設你的線段由A和B兩個頂點坐標表示。那麼線段方向向量AB = B - A。然後，圓心O點乘AB，除以AB長度，就是它在線段上的投影。如果這個數小於零，就計算OA長度；如果大於AB長度，就計算OB長度；否則就計算sqrt(OA方-投影長度方)，得到O與線段的距離。

線段與矩形的判斷，可以看線段的兩個頂點處於矩形的九個volonoi域中的哪幾個。 @張建龍的答案給出了細節。

有本叫《實時碰撞檢測演算法技術》的書，講了很多這方面的東西。你可以看看。

相關的代碼很多圖形引擎中都會有的.

[1]矩形與圓

這是最簡單的,將矩形放大到圓,將圓縮小到點.

inline bool YcRect::IsIntersectsCircle(const YsVector2 vCenter,
float fRadius) const
{
return ( vCenter.x &>= left - fRadius vCenter.x &<= right + fRadius vCenter.y &>= top - fRadius vCenter.y &<= bottom + fRadius); }

[2]矩形與線段

先判斷線段的兩個頂點是否在矩形內,再判斷線段是否與矩形的對角線是否相交.

inline bool YcRect::IsIntersectsSegment(const YsVector2 vStart,
const YsVector2 vEnd) const
{
if (IsContainsPoint(vStart) || IsContainsPoint(vEnd))
{
return true;
}

YsVector2 vRect[4];
vRect[0].x = left; vRect[0].y = top;
vRect[1].x = right; vRect[1].y = top;
vRect[2].x = right; vRect[2].y = bottom;
vRect[3].x = left; vRect[3].y = bottom;

return (YfVector2SegmentIntersects(vStart, vEnd, vRect[0], vRect[2]) ||
YfVector2SegmentIntersects(vStart, vEnd, vRect[1], vRect[3]));
}

補充下兩線段是否相交的代碼:

inline float YfVector2IsLeft
(
const YsVector2 v,
const YsVector2 vStart,
const YsVector2 vEnd
)
{
return (vStart.x-v.x)*(vEnd.y-v.y) - (vEnd.x-v.x)*(vStart.y-v.y);
}

inline bool YfVector2SegmentIntersects
(
const YsVector2 vStart1,
const YsVector2 vEnd1,
const YsVector2 vStart2,
const YsVector2 vEnd2
)
{
float leftS, leftE;
leftS = YfVector2IsLeft(vStart1, vStart2, vEnd2);
leftE = YfVector2IsLeft(vEnd1, vStart2, vEnd2);
if ( leftS * leftE &> YD_EPS_REAL32 )
{
return false; // vStart1, vEnd1在另一條直線的同側
}

leftS = YfVector2IsLeft(vStart2, vStart1, vEnd1);
leftE = YfVector2IsLeft(vEnd2, vStart1, vEnd1);
if ( leftS * leftE &> YD_EPS_REAL32 )
{
return false; // vStart2, vEnd2在另一條直線的同側
}

return true;
}

[3]圓與線段

先求線段上到圓心最近的點,然後計算該點與圓心的距離

inline bool YcCircle::IsIntersectsSegment(const YsVector2 vStart,
const YsVector2 vEnd) const
{
YsVector2 vNearest; // 線段上到圓心最近的點
{
YsVector2 vDis = vEnd - vStart;
if (vDis.IsZero())
{
vNearest = vStart;
}
else
{
// 求圓心在直線上的投影點
YsVector2 upright;
{
#if 1
// 直線的長度與方向
float length = YfVector2Distance(vStart, vEnd);
YsVector2 dir = vDis / length;

// 直線法向
YsVector2 normal = YsVector2(-dir.y, dir.x);
float distance = -(vStart.x*normal.x + vStart.y*normal.y);

// 圓心到直線的距離
float disToCenter = normal.x*x + normal.y*y + distance;
if (disToCenter &> radius)
{
return false;
}

upright = normal * (-disToCenter);
upright.x += x;
upright.y += y;

#else
float a, b, c;
YfVector2CalculateLine(vStart, vEnd, a, b, c);
YfVector2ProjectOnLine(upright, YsVector2(x, y), a, b, c);
#endif
}

float radio;
if (YD_IS_ZERO(vDis.x)) // 是否為0
{
radio = (upright.x - vStart.x) / vDis.x;
}
else
{
radio = (upright.y - vStart.y) / vDis.y;
}

if (radio &< 0) { vNearest = vStart; } else if (radio &> 1)
{
vNearest = vEnd;
}
else
{
vNearest.x = upright.x;
vNearest.y = upright.y;
}
}
}

return ( YfVector2DistanceSquared( vNearest, YsVector2(x, y) ) &< radius * radius ); }

這個我寫的有點複雜.

樓上的答案已經非常科學和充分了，既然題主只要求判斷。那麼我就貢獻個簡單點的思路。。

1. 判斷圓和線段是否相交。分兩種情況：

1.1 有至少一個線段的端點落在圓內，這個只要判斷點在圓內就好了，端點到圓心的距離小於等於半徑 ;

1.2 兩個端點都不在圓內，那麼看圓心到線段所在直線的垂足是否小於半徑 且 垂足在線段上;

2. 判斷長方形和線段是否相交。同樣分兩種情況：

2.1 有至少一個線段的端點落在長方形內，如果點到長方形兩平行邊的距離和等於兩平行邊的距離，那麼點夾在兩平行線之間。

2.2 如果兩個線段的端點都不落在長方形內，那麼如果線段於長方形有交點，必然線段與長方形的邊有交點。長方形的邊也是線段，我們作長方形的邊所在直線和線段所在直線的交點（只要兩條直線不平行，必然有交點） 判斷這個交點是否同時落在線段上和長方形邊上即可。

都只考慮了二維？三維呢？

關於圓(球)與線段是否相交, 有一種簡單方法, 就是解析法求線段與圓(球)心的最短距離, 判斷此距離是否大於圓(球)半徑即可判斷是否相交.

設線段端點為A和B, 圓心為C. 在 AB 上的任意點 D = A + (B - A) * t (其中 0 &<= t &<= 1). 那麼 |DC| = | A + (B - A) * t - C |, 然後求一階導的零點, 注意結果 t 要限制在 [0, 1] (因為距離函數是 2 次的所以零點兩邊是單調的, 所以可以直接將結果截斷到 [0, 1]).

下面是 3D 代碼實現. 這是一段以前寫的代碼, 用於計算線段上距離某個定點最近的點(因為是解析法所以代碼是無法直接理解的, 你可以自己推導看看):

public static Vector3 ClosestPoint(Vector3 start, Vector3 end, Vector3 point)
{
Vector3 direction = end - start;

float t = direction.sqrMagnitude;
if (t &< 0.000001f) return start; t = Mathf.Clamp01(Vector3.Dot(point - start, direction) / t); return start + direction * t; }

其中, direction.sqrMagnitude 是向量長度的平方, Mathf.Clamp01 是截斷數值到 [0, 1] 區間, Vector3.Dot 是點乘.

獲得這個點就可以計算最短距離了. 下面是完整的判斷圓與線段是否相交方法:

public static bool IsIntersect(Vector3 start, Vector3 end, Vector3 center, Vector3 radius)
{
float sqrDistance = (ClosestPoint(start, end, center) - center).sqrMagnitude;
return sqrDistance &< radius * radius; }

計算線段兩端點與圓心距離d1,d2以及圓心到線段距離d3，和圓半徑r比較

if (d1≤r≤d2) 線段與圓相交;

else if (r＜min{d1,d2}

且r≥d3

且圓心到線段的垂線垂足落在線段上)

線段與圓相交;

else

圓與線段無交點;

//對球同樣適用

看到以上回答都是基於平面二維坐標系，這裡補充一下在三維坐標系下相交問題（二維坐標也適用）。

由於實驗需要分析一個線段和一個平面區域是否相交，在網上搜索了一下也基本都是在二維坐標系了。後來通過查閱計算機圖形學相關知識才算搞明白，這裡簡要說明下，作為一個補充：

首先 假設我們已知線段兩端點C，E坐標，平面上三點A，F，G（不在一條直線上）的坐標。

那麼我們可以用向量方程來表示線段 和 平面。（以下字母表示的都是向量）

直線上點的坐標可表示為 P(t)=C+(E-C)t，其中對於線段t屬於[0,1]，簡化為P(t)=C+Dt

平面上的點坐標表示為 Q(u,w)=A+(D-C)u+(E-C)w，簡化為 Q(u,w)=A+Bu+Cw

那麼直線和平面的交點就可以通過聯立兩方程求解。為了

D+Et = A+Bu+Cw

兩邊同時點乘BXC....(這裡X指向量的叉乘)

(BXC).(D+Et)=(BXC).(A+B+Cw)=(BXC).A (BXC 平行平面)

所以求得

進一步可求得

求出t之後 就可以通過直線方程求出交點的坐標。

如果是判斷線段和平面區域相交問題，那就是判斷t在[0,1]之間且也在平面有效區域內。

圓的話，首先需要判斷到線段的距離，距離小於等於半徑後需要進一步看兩個端點到圓心的距離，若有某一個端點到圓心的距離小於等於半徑則顯然相交，若沒有則考察圓心在線段上的投影點C分別到線段兩端點A,B的向量CA,CB的內積，若內積小於零則相交

題主強調快，那就用人體神經系統判斷吧！

——目測

大概是個圖形學問題？不如加個標籤

線段和矩形：先看線段兩個端點在不在矩形區域內，只要有一個端點在矩形內的話相交；要是都不在，在判斷線段和矩形的兩條對角線是否相交，是就相交，不是就不相交。

線段和圓：計算下線段到圓心距離是否小於半徑。也就是找出經過圓心並且垂直於線段所在直線的垂線，圓心到垂線與線段相交點的距離就是圓心到線段的距離，這距離小於圓半徑：相交。否則不相交。

理解題設是在平面坐標系下。先判斷端點，圓直接根據到圓心距離判斷，矩形需轉換坐標系之後根據不等式判斷。之後再根據兩端的判斷結果是否一致判斷是否相交

推薦閱讀：

※對大整數N開平方，求其整數部分，有什麼好的演算法嗎？
※有沒有一種加密演算法可以識別不同密鑰加密的同一明文？
※有什麼理論複雜但是實現簡單的演算法？
※如何更好的理解和掌握 KMP 演算法?
※編程語言是怎麼設計出來的？

TAG:演算法 | 編程 | 計算幾何 |