凸包 (Convex Hull)

引言：「橡皮筋」類比

在木板上隨意釘上一堆釘子。現在，拿一條橡皮筋撐開，套住所有的釘子，然後鬆手讓她緊緊崩住。 橡皮筋形成的形狀就是 凸包 (Convex Hull)。她是包圍所有點的最外層邊界。

在機器人技術、圖形學和影像處理中，高效地找到這個邊界至關重要。Graham 掃描法 透過按角度排序點，並進行一次掃描來構建凸包。

演算法要解決什麼問題？

• 輸入： 一組 2D 點。
• 輸出： 構成最外層多邊形的點的子集。
• 承諾： 將成千上萬個點的雲團簡化為一個簡單的多邊形邊界。

核心思想 (直覺版)

1. 從低處開始： 找到最底部的點（她一定是凸包的一部分）。
2. 按角度排序： 根據其他所有點與起始點的夾角進行排序。
3. 行走與轉向： 遍歷排序後的點。
   • 如果我們向 左轉，繼續前進。
   • 如果我們向 右轉（形成了一個凹陷），說明前一個點其實在凸包內部，而不是在邊界上。移除 前一個點。

典型業務場景

• ✅ 碰撞檢測： 在遊戲中，與其檢測與複雜的 10,000 面體角色模型的碰撞，不如先檢測與其簡單的凸包的碰撞。
• ✅ 機器人： 機器人需要知道一組障礙物周圍的「安全區域」以規劃路徑。
• ✅ 影像處理： 手勢識別通常涉及找到手部形狀的凸包來數手指（凸包上的凹陷）。
• ✅ GIS (地圖)： 「找出覆蓋這 50 個送貨地點的區域範圍。」

性能與複雜度總結

• 時間： $O(N \log N)$（主要耗時在排序上）。
• 空間： $O(N)$。

小結：一句話記住它

「凸包是幾何學的『保鮮膜』。她將複雜的數據點雲簡化為乾淨、凸出的邊界，使得碰撞和面積等計算變得極快。」