Convex Hull: Andrew’s Monotone Chain
keywords: Andrew’s Monotone Chain, convex hull, cross product
定義
Convex Hull又稱為「凸包」，定義為包覆所有點的外殼當中，外殼為凸且表面積最小的。
所謂凸的意思是指，殼內部任兩點的連線，都不會落在殼外。
Andrew’s Monotone Chain
網路上可以找到很多計算凸包的方式，今天要介紹的則是Andrew’s Monotone Chain。以2D集合為例，整個流程可以分為3個步驟
- 將所有點依 X 座標由左至右，再依 Y 座標由下而上排序
- 從最左下方的點開始尋找下半部的凸殼，直到最右上方 (藍線)
- 從最右上方的點開始尋找上半部的凸殼，直到最左下方 (紅線)
排序後，可知序列第一個點必然為凸包的最左點，序列最後一個點則是凸包的最右點，並以這兩個端點作為lower hull及upper hull的兩端點。
已知序列對x已排序，依序挑出點，確認當前的點加入lower hull stack中，是否可維持lower hull stack的所有點為凸包。這意味著，若新加入一個點，使的lower hull stack的點連線不再是逆時針方向，代表前一個點並不屬於lower hull中，應予以刪除。
如下圖，原本lower_hull = [P(i), P(i+1)]，但P(i+2)的加入會導致P(i+1)至P(i+2)的線段方向，相比前一個線段P(i)至P(i+1)的方向，順時針偏移，代表P(i+1)不應該是lower hull的一份子。
有一種簡單的數學方式可以判斷新加入的線方向是更為偏順時針或是逆時針，就是用外積，假設
- 向量 A=(P(i), P(i+1))
- 向量 B=(P(i), P(i+2))
- A,B的外積=Ax*By - Ay*Bx
若外積為正，代表新的點加入可以保持新的線段朝逆時針轉動，反之則為順時針，此時應該要把stack頂端的點從lower或是upper中剃除，可參考下圖(該圖為順時針方向轉動)。
程式碼
以Leetcode 587. Erect the Fence為例。
兩個while都是不等式，通常我們只需要找到逆時針的組合就好，也就是等於0的時候不考慮，但本題問的是convex hull會經過哪些點，因此剛好在convex hull邊上的點也得納入考量。
- 時間複雜度：O(n*log(n)) 主要花在排序
- 空間複雜度：O(n)
