[Poj 2187] 計算幾何之凸包(二) {更高效的演算法}

{

承上一節

繼續介紹點集的凸包

(下文中所有凸包 若不做特殊說明均指點集的凸包)

這一節介紹相比更高效的演算法

}

====================================================================

一.卷包裹演算法(Gift Wrapping Algorithm)的特性

前面提到過卷包裹演算法的複雜度問題

由於卷包裹演算法是兩重循環實現的 因此很好分析它的複雜度

1 while true do 2 begin 3 k:=0; 4 inc(m); ch[m]:=j; 5 for i:=1 to n do 6 if (i<>j)and((k=0)or 7 cmp(p[j],p[k],p[i])) 8 then k:=i; 9 if k=temp then break;10 j:=k;11 end;

內部循環N次 外循環的次數決定於凸包上的點數H

所以卷包裹演算法複雜度為O(HN) 這個複雜度很有特點

考慮一個隨機點集的凸包上的點數往往很少 但是最壞情況下是O(N)級別的

比如所有的點都在一個圓上的時候

這就決定了卷包裹演算法很適合隨機的點集 但是如果是刻意構造的數據或是比較特殊的數據

就會達到O(N^2)的最壞複雜度 這是我們不願意看到的

下面介紹最壞情況下複雜度更好的Graham掃描演算法(Graham Scan Algorithm)

====================================================================

二.Graham掃描演算法(Graham Scan Algorithm)

Graham掃描演算法維護一個凸殼 通過不斷在凸殼中加入新的點和去除影響凸性的點 最後形成凸包

The Graham scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O(n log n). It is named after Ronald Graham, who published the original algorithm in 1972.[1] The algorithm finds all vertices of the convex hull ordered along its boundary.

http://en.wikipedia.org/wiki/Graham_scan

演算法主體由兩部分組成 先是排序 後是掃描 分塊講解一下

----------------------------------------------------------------------------------------------------------

1.點集排序

為了得到加入新點的順序 Graham掃描法的第一步是對點集排序

排序是對雜亂的點集進行了梳理 這也是這種演算法能夠得到更高效率的根本原因

排序的方法也有兩種 極角坐標排序(極角序) 和 直角坐標排序(水平序)

前者好理解一些 但是在實現的時候 後者更方便

先說極角序 為了極角排序 我們先得得到一個參考點

一般的 我們取最左邊(橫坐標最小)的點作為參考點 如果有多個這樣的點就取最下面的(縱坐標最小)

看這樣一個例子 這是一個任意給出的平面點集:

參考點的定義:在橫坐標最小的情況下取縱坐標最小的點

所以所有的點只能在這個黃色的半平面中 而且正上方為閉(可取得) 正下方為開(不可取)

這就決定了參考點的性質:點集中任意兩點和參考點所成的到角為銳角

這樣我們取得參考點 然後再考慮極角排序

極角排序以參考點為極角坐標系原點 各個點的極角為關鍵字

由於上面我們得到的參考點的性質 我們可以設所有點的極角均在(-90,90]之間

排序完成後應該是這樣的:

比較極角我們仍然可以利用向量的叉積

叉積在這裡已經介紹了 http://www.cnblogs.com/Booble/archive/2011/02/28/1967179.html

同樣由於參考點的性質 所有向量之間的到角都是在180度以內 不會產生錯誤

----------------------------------------------------------------------------------------------------------

2.Graham的棧掃描

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

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

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

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

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

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

這樣Graham掃描演算法基本完成

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

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

----------------------------------------------------------------------------------------------------------

3.雙重共線點難題

和卷包裹演算法一樣 我們同樣還要考慮共線點問題

而且Graham掃描演算法的共線問題更複雜 所以需要仔細考慮

i).排序時的共線問題

如果極角相同 我們應該怎麼定先後呢?

我們得加上第二關鍵字距離 比如極角相同 距離參考點近的先

不過不管是近的先還是 遠的先 開始和結束的兩條邊總是矛盾的

我們必須對其中一條特殊處理 除了結束邊外距離近的先 結束邊上距離遠的先

這就是為什麼極角排序不是很好實現的原因了 下面會介紹一下水平序

ii).掃描時的共線問題

這個和卷包裹演算法的處理放法如出一轍

如果需要保留共線的點就在到角相同時取距離最近的

如果僅僅需要凸包極點就取距離最遠的

----------------------------------------------------------------------------------------------------------

4.直角坐標排序(水平序)

直角坐標排序方法沒有了極角排序的不足

以橫坐標為第一關鍵字 縱坐標為第二關鍵字 排序點集

然後從第一個點開始 分別利用Graham掃描生成左鏈和右鏈

需要注意以下兩點:

i).左鏈和右鏈的旋轉方向是相反的

ii).注意生成第二條鏈要忽略第一條鏈上的點

由於水平序的CMP函數比較簡單 代碼也更短

還有一件有意思的事 Graham掃描演算法是1972年提出的 卷包裹演算法是1973年提出的

其實不奇怪 這兩個演算法本來也沒有優劣 所用的思想不同 各自善於處理不同的情況

Graham掃描所用時間在點集隨機時 還不如卷包裹演算法快

正如第一節所說 卷包裹演算法已經可以處理大部分情況 也是一個可取的演算法

實際應用中點集更趨向於均勻 而不是集中在凸包上

----------------------------------------------------------------------------------------------------------

最後給一下比較難實現的極角排序代碼

GrahamScan====================================================================

三.快速凸包演算法(Quickhull Algorithm)

對比Graham掃描演算法和卷包裹演算法

我們發現 Graham掃描演算法在凸包上的點很密集時仍然適用

卷包裹演算法在凸包上點集隨機分布時是很高效的

那麼有沒有兩個優點都具備的演算法呢?

是有的! 快速凸包演算法(Quickhull Algorithm)就是這樣的一個演算法

快速凸包演算法是一個和快速排序(Quicksort Algorithm)神似的演算法

儘管快速排序的最壞複雜度可以達到O(N^2)

但是有著極小的常數 實現方便 思路優美 絕大多數情況特別高效的快速排序 還是贏得了更多人的青睞

快速凸包演算法也是這樣 儘管可以構造一個數據使之達到O(N^2)的複雜度

但這需要刻意針對程序經過分析 才能做到 是實際應用中根本不會碰到的情況

在點集均勻分布時 快速凸包的複雜度更是達到了O(N) 是上面兩種演算法難以企及的

在絕大多數情況下 平均複雜度是O(Nlog2N) 也很高效

快速凸包繼承了快速排序分治的思想 這是一個遞歸的過程

------------------------------------------------------------------------------------

偽代碼如下:

1 void 快速凸包(P:點集 , S:向量 /*S.p,S.q:點)*/ ){ 2 　　/* P 在 S 左側*/ 3 　　選取 P 中距離 S 最遠的 點 Y ; 4 　　向量 A <- { S.p , Y } ; 向量 B <- { Y , S.q } ; 5 　　點集 Q <- 在 P 中 且在 A 左側的點 ; 6 　　點集 R <- 在 P 中 且在 B 左側的點 ; /* 劃分 */ 7 　　快速凸包 ( Q , A ) ; /* 分治 */ 8 　　輸出 (點 Y) ; /* 按中序輸出 保證順序*/ 9 　　快速凸包 ( P , B ) ; /* 分治 */10 }

初始化就選取 最左下和最右上的點 劃分好 然後調用兩次快速凸包函數分別求上下凸包

其中 選取和劃分都需要用到向量的叉乘 注意方向

另外 存儲點集可以用數組裡的連續一段 傳參的時候就傳左右下標

劃分的時候就是給數組交換元素 使新的點集 變成連續的一段

這裡有一個很好的演示

http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/QuickHull.html

還要補充說明一下

快速凸包在所有點都在圓周上的時候還是O(Nlog2N) 不過會比Graham掃描演算法慢一些

可以說 這種數據是Graham掃描法的最好情況 一遍走完就行了

構造快速凸包的最壞情況就是使劃分不均等 和構造快速排序最壞情況一樣

貼以下我很辛苦寫出來的代碼吧 為了好看些 還心血來潮用cpp寫了...

QuickHull

====================================================================

四.凸包演算法複雜度下界

(引自<演算法藝術與信息學競賽>)

====================================================================

五.高效演算法的應用

這裡有一個平面最遠點對的問題 可以利用凸包解決

Poj 2187 http://poj.org/problem?id=2187

由於最遠點對必然在凸包上

我們先求凸包 然後枚舉凸包上的點 不過這個複雜度最壞是O(N^2)的

不過凸包在很多情況下會改善問題的平均複雜度

凸包上的點通常很少 所以這個問題也可以過

篇幅關係 在下一節會介紹降低最壞複雜度的旋轉卡殼演算法

====================================================================

文中部分圖片來源

http://westhoffswelt.de/blog/0040_quickhull_introduction_and_php_implementation.html

http://en.wikipedia.org/wiki/Graham_scan