Graham的掃描是一個很優美的過程 用到的數據結構也很簡單 僅僅是一個棧而已

核心的思想是按照排好的序 依次加入新點得到新的邊

如果和上一條邊成左轉關系就壓棧繼續 如果右轉就彈棧直到和棧頂兩點的邊成左轉關系 壓棧繼續

實現的時候我們不用存邊 只需要含順序在棧里存點 相鄰兩點就是一條邊

由于我們時時刻刻都保證棧內是一個凸殼 所以最后掃描完畢 就得到了一個凸包

下面還是繼續上面的那個樣例 演示一下棧掃描的過程

這樣Graham掃描算法基本完成

復雜度是排序O(Nlog2N) 掃描O(N) {每個點僅僅出入棧一次}

合起來是一個O(Nlog2N)的算法 很優秀