# 計算幾何：凸包 ###### tags: `108 師大附中校隊培訓` ###### wiwiho --- 你有一大堆點 你要找出一個可以圍住這些點 且面積最小的凸多邊形 這個凸多邊形稱為凸包。  --- ## 掃描線 ---- 往固定方向掃描點的方式 稱為掃描線  ---- 把各個點按 $x$ 座標由小到大排序 $x$ 座標相同的話 再按 $y$ 座標由小到大排序 點會有左而右、由上至下排序 &rarr; 可以做由左而右的掃描線 --- ## 凸多邊形 ---- 有一個凸多邊形 它的點已經按逆時針順序排好了 依序是 $p_0p_1p_2...p_{n-1}$ 令 $p_i=p_{i \bmod n}$ ---- 它有什麼性質？ ---- 凸多邊形的邊 應該要是一直往同個方向轉的 逆時針排序後 凸多邊形的邊 斜率應該要是往逆時針方向轉 ---- 而點也會是一直往同個方向轉的 因此： $\overrightarrow{p_ip_{i+1}}\times\overrightarrow{p_ip_{i+2}} > 0$ ----  --- ## 上下凸包 ---- 把凸包分成上下兩部分 以極左點和極右點分割 ---- 那極左點和極右點呢？ ---- 如果極左點有兩個 上面那個屬於上凸包 下面那個屬於下凸包 否則就屬於下凸包 ---- 如果極右點有兩個 上面那個屬於上凸包 下面那個屬於下凸包 否則就屬於上凸包 ---- 上或下凸包中不會有 $x$ 座標相同的頂點 因此在上或下凸包中 每個頂點都能分別出左右的關係 ---- 如果把點按逆時針排序 在下凸包中的點也是由左而右排序的 在上凸包的點也是由右而左排序的 ---- 先用由左而右的掃描線把下凸包做出來 再用由右而左的掃描線把上凸包做出來 就可以得到整個凸包 --- ## Andrew's monotone chain ---- 這整個流程可以用一個 stack 來實作 ---- 在處理一個點的時候 我們嘗試把它加進凸包裡 ---- 時這個點是 $p_{i+2}$ 堆頂的點是 $p_{i+1}$ 堆頂再往下一個點是 $p_{i}$ ---- 代入剛剛的式子： $\overrightarrow{p_ip_{i+1}}\times\overrightarrow{p_ip_{i+2}} > 0$ ---- 符合條件或者 stack 大小小於 $2$ 時就停止 否則就把堆頂 pop 然後繼續重複 結束之後就把目前處理中的點放入堆頂 ---- 在做下凸包的時候 先從最左邊且最下面的點開始做上述動作 最後，堆頂的點是最右邊且最上面的點 把它 pop 掉，因為它應該屬於上凸包 ---- 做上凸包的時候 從最右邊且最上面的點開始 最後堆頂會是最左且最下的點 把它 pop 掉 ---- 最後 這兩個接起來就是完整的凸包 ---- ```cpp #include <bits/stdc++.h> #define mp(a, b) make_pair(a, b) #define pb(a) push_back(a) #define F first #define S second typedef long long ll; using namespace std; template<typename T> pair<T, T> operator-(pair<T, T> a, pair<T, T> b){ return mp(a.F - b.F, a.S - b.S); } template<typename T> ll cross(pair<T, T> a, pair<T, T> b){ return a.F * b.S - a.S * b.F; } template<typename T> vector<pair<T, T>> getConvexHull(vector<pair<T, T>>& pnts){ int n = pnts.size(); sort(pnts.begin(), pnts.end()); vector<pair<T, T>> hull; for(int i = 0; i < 2; i++){ int t = hull.size(); for(pair<T, T> pnt : pnts){ while(hull.size() - t >= 2 && cross(hull.back() - hull[hull.size() - 2], pnt - hull[hull.size() - 2]) <= 0) hull.pop_back(); hull.pb(pnt); } hull.pop_back(); reverse(pnts.begin(), pnts.end()); } return hull; } ```