Computational Geometry 計算幾何基礎

幾何算法看起來很學術，但碰撞偵測、地圖邊界計算、機器人路徑規劃，底層都是這些東西。

為什麼需要計算幾何？

給你一堆 GPS 座標，求最小邊界多邊形（凸包）——暴力枚舉所有三角形是 O(n³)，有了凸包演算法是 O(n log n)。

計算幾何的核心工具只有一個：叉積。

叉積：三個點的轉向

cross(O, A, B) = (A.x - O.x) * (B.y - O.y)
               − (A.y - O.y) * (B.x - O.x)

結果 > 0：O→A→B 是左轉（逆時針）
結果 < 0：O→A→B 是右轉（順時針）
結果 = 0：三點共線

這一個公式就能判斷點在線段的哪一側、兩線段是否相交、多邊形的繞行方向。

凸包：三種演算法

凸包是包含所有點的最小凸多邊形——把釘子插進板子，橡皮筋套住縮緊後的形狀。

Monotone Chain（競賽首選）

1. 按 x 座標排序（x 相同按 y）
2. 掃一遍建下凸包（保持右轉）
3. 反向掃建上凸包
4. 合併

關鍵：新點加入時，若棧頂三點不是右轉，彈出棧頂

List<Point> convexHull(Point[] pts) {
    Arrays.sort(pts);   // 先排序
    int n = pts.length, k = 0;
    Point[] hull = new Point[2 * n];
 
    // 下凸包
    for (int i = 0; i < n; i++) {
        while (k >= 2 && cross(hull[k-2], hull[k-1], pts[i]) <= 0) k--;
        hull[k++] = pts[i];
    }
    // 上凸包
    for (int i = n-2, t = k+1; i >= 0; i--) {
        while (k >= t && cross(hull[k-2], hull[k-1], pts[i]) <= 0) k--;
        hull[k++] = pts[i];
    }
    return List.of(Arrays.copyOf(hull, k - 1));
}

Graham Scan vs Jarvis March

演算法	時間	特點
Monotone Chain	O(n log n)	最易實作，競賽標準
Graham Scan	O(n log n)	需極角排序，稍複雜
Jarvis March	O(nh)	h = 凸包頂點數；h 小時快，h 接近 n 時 O(n²)

旋轉卡殼：最遠點對

凸包建好後，要找最遠的兩個點（Diameter），暴力是 O(n²)，旋轉卡殼是 O(n)。

兩個指標從凸包對側出發，同向旋轉：
每次移動讓三角形面積最大化 → 叉積最大的那個點對是最遠點對

核心：凸性保證最遠點對一定在「對蹠點（Antipodal Pairs）」中

常見幾何判斷

問題	方法
點在線段的哪一側	叉積正負
兩線段是否相交	四次叉積判斷
點是否在多邊形內	射線法（ray casting）
最小包圍圓	Welzl 演算法 O(n)

---

計算幾何的精髓是叉積——搞懂它，剩下的都是把叉積用在對的地方。