平面上的凸包計算

陳道蓄

在郊野公園中有一片林地，生長著一些古老的樹木。管理部門希望建圍欄把這些樹木圍起來加以保護。為了便于外圍修建步行道，方便游人觀賞，將保護區(qū)設計成凸多邊形。當然也希望圍欄總長度盡可能小，以降低建設成本。

為簡化計算，我們假設可以用部分樹木作為圍欄的樁柱，換句話說，部分樹木處于保護區(qū)域的邊界上。圖1是這個問題的示意圖，左邊標出樹木的平面位置分布，右邊則顯示完成的圍欄，位于圍欄上的樹木用空心點表示，圍在內(nèi)部的為灰色點。我們能否設計一個算法讓計算機幫我們確定該如何建圍欄呢？

● 問題模型和基本思想

問題可以抽象為：在平面上給定一組點，如何生成一個包含全部點的最小凸包。所謂凸包是滿足如下條件的多邊形：連接多邊形中任意兩點（包括邊界上的點）的直線段完全位于多邊形內(nèi)部（包括邊界）。“最小”是指在保持凸多邊形性質(zhì)不變的前提下，若縮小該圖形，則給定的點中至少有一個位于外部。

圖形處理中大量的問題需要用到這樣的計算，凸包算法是計算幾何領域最早的成果之一。

模型基于平面笛卡爾坐標系。輸入是一組點v1，v2，…，vn，其中vi表示為（xi，yi），即該點在笛卡爾坐標系中的橫坐標值與縱坐標值。我們不妨假設所有坐標值均為整數(shù)，并且約定任何兩點不會“過于靠近”。這個要求并不明確，由于計算過程中可能涉及小數(shù)，如果點過于接近可能導致后面討論的算法產(chǎn)生錯誤結果。我們避免煩瑣的詳細定義，這并不影響讀者理解算法的思想。

算法的輸出是輸入點的一個子集構成的序列。出現(xiàn)在序列中的點即位于凸多邊形邊界上的點。邊界的軌跡即為需要計算的凸包。我們約定其順序是：從某個指定點出發(fā)，按照順時針方向沿凸包排列。如果用畫圖工具將輸出序列中每個相鄰點對之間的連接直線段（包括首尾兩個點之間的）全部畫出，則可顯示計算得到的凸包。

顯然，解題的關鍵是確定哪些點應該在凸包上。當點數(shù)非常多，且隨機分布時，這很難確定，但作為構成凸包的每條線段，其特征倒不難看出來。從圖1右邊的圖很容易看出邊界上的每條線段所在的直線將平面切分為兩個半平面，所有的點一定位于其中一個半平面上（包括分界線），如圖2所示。這就意味著滿足這一條件的線段的兩個端點在邊界上。反之，考慮任意兩點連接的直線段，如果其對應的直線分割成的兩個半平面中都有輸入點，則該線段不可能在凸包上。

● 從思想到算法

利用解析幾何知識，很容易判定相對于特定線段，任給的兩點是否在同一個半平面（是否位于線段的同一側(cè)）。

假設線段uv所在的直線將平面分割為兩個半平面（如圖3），點s和t處在同一個半平面中，折線s-u-v和t-u-v在u點總是向同一方向偏轉(zhuǎn)（這里是右轉(zhuǎn)），而處于另一半平面中的點w決定的折線w-u-v一定是向相反方向偏轉(zhuǎn)（這里是左轉(zhuǎn)）。

以圖3中的折線t-u-v為例，設三個點的坐標值分別為（x1，y1），（x2，y2），（x3，y3），則折轉(zhuǎn)方向完全由下面的行列式值的符號所確定：

當行列式值為正時，則反時針（左）轉(zhuǎn)，當行列式值為負時，則順時針（右）轉(zhuǎn)。行列式值為0當且僅當三點共線。這里的例子該行列式值為負。兩個點相對于線段uv處于兩個不同的半平面當且僅當相應行列式的值符號相反。我們不詳細討論數(shù)學背景，讀者可參考文獻【1】。

利用上述公式，我們很容易實現(xiàn)如下頁圖4所示的line_turn函數(shù)。

利用函數(shù)line_turn，我們先給出一個非常直觀的算法：對輸入的任意兩點連接得到的直線段，判斷其他n-2個點是否全部在其同一側(cè)，如若不然，則這條線段不可能是凸包一部分（如下頁圖5）。簡而言之，采用窮盡法找出凸包上的線段。（注意：這里輸出的是線段集合，而不是模型描述中提到的邊界點序列）

輸入n個點，可生成的直線段數(shù)量為O（n2），對每條線段，最壞情況下要檢查除該線段端點以外的n-2個點是否都在同一個半平面中，因此計算復雜度是O（n3）。

上述窮盡法沒有利用輸入中可能有幫助的隱含信息，一般效率不高。如果能找到一些“竅門”，直接可判定某些線段是否在凸包上，而不用每次都去檢查所有點，就有可能改進算法。

● 一個效率較高的貪心算法

我們再仔細審視一下圖1中右邊那個圖，特別觀察下面標注出的點（如下頁圖6）。

盡管圖6中的凸包在算法未執(zhí)行完成前并不存在，但圖中特別標示出的三個點，即v0（靠坐標值即可確定）、v1和vn-1是可以確定的。后兩個點的確定只需要對除v0外任意點與v0及X軸正方向之間的夾角大小排序。最有啟發(fā)意義的一點在于，我們可以斷定輸入的所有點都位于這三點構成的折線的同一側(cè)。

確定了v0后，首先對除了v0以外所有點相應的夾角從大到小排序（且按此給v0以外的點編號），顯然在最終計算出的凸包上，按照順時針方向，點的序號嚴格遞增。而且沿凸包軌跡，任何正方向上相鄰的三個點構成右轉(zhuǎn)折線。

這為設計效率更高的凸包算法提供了更清晰的思路：首先確定v0，這很容易。接著就按照上述相應的夾角從大到小給其他n-1個點排序，如果夾角相等就按與v0的距離從小到大排（這是為了處理共線的情況）。選擇v0和v1作為開始的兩個邊界點（按照順時針方向）。后面循點序號的增序逐步增加凸包上的點。

按照角度大小排序并不能保證任意連續(xù)三個序號的點一定構成向右的折線。這是算法中最不直觀的部分。每當加入一個新的邊界點，必須檢查當前序列中最后三個點構成的折線是否左轉(zhuǎn)，如果是，就刪除當中的點，再繼續(xù)回溯并做同樣的檢查。下頁圖7是選初始點以及按照夾角大小排序的結果。

下頁圖8顯示從初識點開始，沿順時針方向構造凸包的過程。

下頁圖8（a）為起始狀態(tài)。為了計算方便，選定v0后將其作為坐標系原點（0，0），并根據(jù)解析幾何知識將其他所有點的坐標值做相應修改（這只需要簡單算術運算，總代價是O（n））。

圖8（b）顯示計算過程。每條邊上數(shù)字表示在整個操作序列中相應線段加入以及被刪除的次序（刪除操作次序表示在括號中，邊界上的線段沒有刪除操作）。需要指出的是，算法并不對邊（線段）操作，只處理點。這里是為了讓讀者容易跟蹤算法執(zhí)行過程，畫出線段，其實其加入還是刪除是對點操作的反映。有兩條線段上刪除操作執(zhí)行次序相同，那是因為算法其實刪除的是點，這就同時把與該點關聯(lián)的兩條邊刪除了。

其實并不需要計算出夾角的大小，我們只是用這個數(shù)據(jù)來排序。在0～π范圍內(nèi)正切函數(shù)是在兩個不連續(xù)的區(qū)間（0～π/2，π/2～π）內(nèi)分別嚴格遞增的，所以只要區(qū)分橫坐標的正負，直接比較y/x就可以了（區(qū)分正負區(qū)時必須保證不能讓正負號不同的坐標值放在一起比）。如果想避免浮點計算帶來的不精確，可以利用有關的庫函數(shù)進行分數(shù)值計算與比較，當然也可以自己寫一段程序?qū)崿F(xiàn)精確的分數(shù)計算，這并不難。

從上面的例子可以看出，算法執(zhí)行中是通過回溯檢查是否有不正確的點被當作邊界點，需要不斷糾正前面的誤判。顯然這個過程用堆棧實現(xiàn)最為方便。

定義棧CH，按照點的序號，首先是v0，v1，v2依次進棧，從v3開始，每次按照序號向棧中加一個點，隨即檢查棧頂?shù)倪B續(xù)三個點是否構成左偏轉(zhuǎn)的折線，如果是，則從棧中刪除中間那個點，并繼續(xù)檢查新棧頂位置的連續(xù)三個點，以此類推。折轉(zhuǎn)方向的判定直接調(diào)用函數(shù)line_turn即可。（讀者可以考慮為什么v2進棧時不需要檢查）算法過程描述如下頁圖9所示。

這個算法的最主要代價就是排序（想不到吧?。?，除此之外對每個點的處理代價都是常量，所以總代價為O（n）。整個算法的復雜度是O（nlogn）（也就是排序的代價）。

● 結束語

雖然從漸進復雜度上來說，上述算法已經(jīng)達到“最優(yōu)”了，但仍然可以設法改進。

一個非常簡單的想法：先找出四個“極點”，即橫/縱坐標值最大和最小的點。用這四個點構成一個四邊形，位于該四邊形中（包括內(nèi)部與邊界）的點除了“極點”外，都不可能是邊界點。圖10中標出了上述例子中的四個“極點”，并按照上面的方法進行“預處理”，算法需要考慮的點數(shù)從16個下降到10個。利用解析幾何的基礎知識很容易識別位于四邊形中的點。這是個“啟發(fā)式”算法，對于輸入點集的任意分布，我們無法分析預處理“收益”可能有多大，但經(jīng)驗數(shù)據(jù)表明，當輸入點數(shù)很大，且隨機分布時，計算代價會大大下降。

計算角度（哪怕是利用三角知識間接計算）仍然比較麻煩。文獻【2】中介紹了只需要對點的橫坐標排序的算法。文獻【2】與文獻【1】互補性很好。后者對相關數(shù)學背景以及算法的分析有很好的討論，而前者對算法的實現(xiàn)和比較討論得非常詳細，包括給出了程序代碼。

這里的算法利用了與平面緊密相關的特性，如兩條直線夾角等，所以不能將這樣的思想自然推廣到更高維度。其實凸包問題除了與幾何空間相關，在大數(shù)據(jù)分析等應用中也有很大價值。那里的“維數(shù)”與物理空間無關，往往是允許定義的對象屬性的個數(shù)，所以“高維”是很常見的，但三維或更高維的凸包計算問題超出了本文的范圍。

參考文獻：

[1]Thomas Cormen， etc. Introduction to Algorithms[M].殷建平，等，編譯.北京：機械工業(yè)出版社，2013.

[2]George Heineman， etc.Algorithms-in a Nutshell， 2nd ed. OReilly 2016（算法技術手冊，影印版第2版）[M].南京：東南大學出版社，2017.

注：作者系南京大學軟件學院原院長，計算機系原系主任。