怎樣判斷平面上兩個扇形是否有重疊？

01-05

@蘇琛的方法是可行的。第一步的實現及優化可看http://www.cnblogs.com/miloyip/archive/2013/04/19/3029852.html。第二步比較麻煩，要實現線段對線段、線段對孤、孤對孤的相交測試。

另一個方法是使用分離軸定理／超平面分離定理（SAT, http://en.wikipedia.org/wiki/Hyperplane_separation_theorem）。對於少於180度的扇形，它們是凸形狀，可直接使用SAT；對於每個大於180度的扇形，要分拆成兩個扇形。

一個扇形由三個特徵組成：1個圓、2個半平面（half-plane）、3個頂點。具體要檢查：

2個圓是否分離；
4個"半平面"是否能分離對方的圓；
2個圓是否能分離對方的3頂點；
4個"半平面"是否能分離對方的3頂點。

若都沒有分離成功，即兩個扇形相交。因為每個測試都只需減法和點積，估計這個方法會較快。

第一步，檢查一個扇形是否包含另外一個扇形三個點（圓心以及弧的兩個端點）中的至少一個，如果是，那麼兩個扇形有重疊；

第二步，把每個扇形都拆成兩條線段和一條弧，分別檢查九對線段-弧線是否有相交，如果有一對有相交，那麼兩個扇形有重疊；

否則兩個扇形沒有重疊。

你也許可以試試MPR （Minkovsky portal refinement）演算法。我猜它可以工作在2維空間里。這個演算法只適用於凸體，如果扇形可能大於180度，那可以考慮砍成倆，然後逐個測試。

注意這個演算法是有一定數值誤差的，只適用於數值運算，不適用於嚴格的理論推導。

也可以用蒙特卡洛方法吧，隨機生成一些在第一個扇形所在的矩形內的點，判斷是否同時在第一個扇形和第二個扇形中。

1、寫出第一個扇形（設為半徑較大的）坐標表達式

$x = x_{0} + r_{0}cos heta \ y = y_{0} + r_{0}sin heta \ heta in ( heta_{0}, heta_{1})$

2、求出第一個扇形圓心過第二個扇形三個邊界點的半徑頂點的極坐標，夾角分別為 $alpha_{1}, alpha_{2},alpha_{3}$ ，設 $alpha_{1} < alpha_{2} < alpha_{3}$ , 所以夾角範圍為 $(alpha_{1}, alpha_{3})$

3、判斷 $( heta_{0}, heta_{1})$ 和 $(alpha_1, alpha_{3})$ 是否有交集，沒有則表示不重疊，return

4、判斷圓心的距離，如果圓心距離大於半徑之和表示不重疊，否則重疊，返回

PS：之前漏掉步驟4，導致答案有問題

已知（x, y, r, a, b）分別是圓心x坐標、圓心y坐標、半徑、起始角度、結束角度

第一步

if (((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) &> ((r1 + r2) * (r1 + r2))) // 不重疊.

第二步

float angle1to2 = Math.atan2(y2 - y1, x2 - x1); if (angle1to2 &< a1 || angle1to2 &> b1) // 不重疊 float angle2to1 = angle1to2 + Math.PI; if (angle2to1 &< a2 || angle2to1 &> b2) // 不重疊

http://stackoverflow.com/questions/10694709/how-to-determine-whether-two-circular-sectors-overlap-with-each-other

這個難道不是 3 * 3的直線和圓的公式計算是否有解的問題嗎