幾何算法看起來很學術，但碰撞偵測、地圖邊界計算、機器人路徑規劃，底層都是這些東西。
為什麼需要計算幾何？
給你一堆 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));
}上面的 Monotone Chain 是「按 x 排序後掃兩趟」，另外兩套的骨架不太一樣，值得各認一下臉：
Graham Scan：先挑一個最低點當基準，把其餘點按「對基準的極角」排序，再用一個棧從頭掃。每加一個新點，就檢查棧頂三點是不是還維持逆時針；一旦出現右轉就把中間那點彈掉——它被新點「包」進去了，不可能在凸包上。跟 Monotone Chain 是同一招（用叉積守住轉向），差別只在它靠極角排序、Monotone Chain 靠座標排序。
Jarvis March（禮物包裝法）：最土但最好懂——從最左邊那點出發，每一步都問「以目前這點為錨，哪個點是最外圈的下一站」（叉積挑出最右轉的那個），像包禮物一樣繞凸包一圈回到起點。它的成本是 O(nh)：每包一個頂點要掃全部 n 個點，包了 h 個頂點。所以凸包頂點少（比如一把散點只圍出三角形）它飛快，但點全落在圓周上、h 逼近 n 時就退化成 O(n²)。
| 演算法 | 時間 | 特點 |
|---|---|---|
| Monotone Chain | O(n log n) | 最易實作，競賽標準 |
| Graham Scan | O(n log n) | 需極角排序，稍複雜 |
| Jarvis March | O(nh) | h = 凸包頂點數；h 小時快，h 接近 n 時 O(n²) |
🎬 互動視覺化：三種凸包演算法並排 — 同一堆散點，看 Monotone Chain 掃兩趟、Graham Scan 繞極角、Jarvis March 一格一格包，直接對照誰彈了哪個點、各自花幾步。
旋轉卡殼：最遠點對
凸包建好後，要找最遠的兩個點（Diameter），暴力是 O(n²)，旋轉卡殼是 O(n)。
兩個指標從凸包對側出發，同向旋轉：
每次移動讓三角形面積最大化 → 叉積最大的那個點對是最遠點對
核心：凸性保證最遠點對一定在「對蹠點（Antipodal Pairs）」中常見幾何判斷
| 問題 | 方法 |
|---|---|
| 點在線段的哪一側 | 叉積正負 |
| 兩線段是否相交 | 四次叉積判斷 |
| 點是否在多邊形內 | 射線法（ray casting） |
| 最小包圍圓 | Welzl 演算法 O(n) |
計算幾何的精髓是叉積——搞懂它，剩下的都是把叉積用在對的地方。
接下來往哪走
- Red-Black Tree 紅黑樹 — 下一篇：回到資料結構，看工業界最常用的自平衡樹
- 掃描線：把二維問題拆成一維問題的連續處理 — 線段交點、最近點對這些幾何問題的系統性解法
- KD-Tree & R-Tree 空間索引：找最近的那個點 — 幾何資料量大了之後，怎麼建索引避免每次掃全部