陳道蓄

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

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

● 問(wèn)題模型和基本思想

問(wèn)題可以抽象為：在平面上給定一組點(diǎn)，如何生成一個(gè)包含全部點(diǎn)的最小凸包。所謂凸包是滿足如下條件的多邊形：連接多邊形中任意兩點(diǎn)（包括邊界上的點(diǎn)）的直線段完全位于多邊形內(nèi)部（包括邊界）?！白钚　笔侵冈诒３滞苟噙呅涡再|(zhì)不變的前提下，若縮小該圖形，則給定的點(diǎn)中至少有一個(gè)位于外部。

圖形處理中大量的問(wèn)題需要用到這樣的計(jì)算，凸包算法是計(jì)算幾何領(lǐng)域最早的成果之一。

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

算法的輸出是輸入點(diǎn)的一個(gè)子集構(gòu)成的序列。出現(xiàn)在序列中的點(diǎn)即位于凸多邊形邊界上的點(diǎn)。邊界的軌跡即為需要計(jì)算的凸包。我們約定其順序是：從某個(gè)指定點(diǎn)出發(fā)，按照順時(shí)針?lè)较蜓赝拱帕小Ｈ绻卯?huà)圖工具將輸出序列中每個(gè)相鄰點(diǎn)對(duì)之間的連接直線段（包括首尾兩個(gè)點(diǎn)之間的）全部畫(huà)出，則可顯示計(jì)算得到的凸包。

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

● 從思想到算法

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

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

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

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

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

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

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

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

● 一個(gè)效率較高的貪心算法

我們?cè)僮屑?xì)審視一下圖1中右邊那個(gè)圖，特別觀察下面標(biāo)注出的點(diǎn)（如下頁(yè)圖6）。

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

確定了v0后，首先對(duì)除了v0以外所有點(diǎn)相應(yīng)的夾角從大到小排序（且按此給v0以外的點(diǎn)編號(hào)），顯然在最終計(jì)算出的凸包上，按照順時(shí)針?lè)较?，點(diǎn)的序號(hào)嚴(yán)格遞增。而且沿凸包軌跡，任何正方向上相鄰的三個(gè)點(diǎn)構(gòu)成右轉(zhuǎn)折線。

這為設(shè)計(jì)效率更高的凸包算法提供了更清晰的思路：首先確定v0，這很容易。接著就按照上述相應(yīng)的夾角從大到小給其他n-1個(gè)點(diǎn)排序，如果夾角相等就按與v0的距離從小到大排（這是為了處理共線的情況）。選擇v0和v1作為開(kāi)始的兩個(gè)邊界點(diǎn)（按照順時(shí)針?lè)较颍?。后面循點(diǎn)序號(hào)的增序逐步增加凸包上的點(diǎn)。

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

下頁(yè)圖8顯示從初識(shí)點(diǎn)開(kāi)始，沿順時(shí)針?lè)较驑?gòu)造凸包的過(guò)程。

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

圖8（b）顯示計(jì)算過(guò)程。每條邊上數(shù)字表示在整個(gè)操作序列中相應(yīng)線段加入以及被刪除的次序（刪除操作次序表示在括號(hào)中，邊界上的線段沒(méi)有刪除操作）。需要指出的是，算法并不對(duì)邊（線段）操作，只處理點(diǎn)。這里是為了讓讀者容易跟蹤算法執(zhí)行過(guò)程，畫(huà)出線段，其實(shí)其加入還是刪除是對(duì)點(diǎn)操作的反映。有兩條線段上刪除操作執(zhí)行次序相同，那是因?yàn)樗惴ㄆ鋵?shí)刪除的是點(diǎn)，這就同時(shí)把與該點(diǎn)關(guān)聯(lián)的兩條邊刪除了。

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

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

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

這個(gè)算法的最主要代價(jià)就是排序（想不到吧！），除此之外對(duì)每個(gè)點(diǎn)的處理代價(jià)都是常量，所以總代價(jià)為O（n）。整個(gè)算法的復(fù)雜度是O（nlogn）（也就是排序的代價(jià)）。

● 結(jié)束語(yǔ)

雖然從漸進(jìn)復(fù)雜度上來(lái)說(shuō)，上述算法已經(jīng)達(dá)到“最優(yōu)”了，但仍然可以設(shè)法改進(jìn)。

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

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

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

參考文獻(xiàn)：

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

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

注：作者系南京大學(xué)軟件學(xué)院原院長(zhǎng)，計(jì)算機(jī)系原系主任。