凸包算法的線性實(shí)現(xiàn)

易巧玲 劉良方 中山職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系，廣東省中山市 528404

凸包算法的線性實(shí)現(xiàn)

易巧玲 劉良方 中山職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系，廣東省中山市 528404

凸包算法是計(jì)算機(jī)幾何的基本問(wèn)題之一，但傳統(tǒng)的凸包算法在構(gòu)造凸包的過(guò)程中有很大的計(jì)算量，時(shí)間效率非常不理想。本文試圖探討一種新的算法，該算法充分利用點(diǎn)集中兩個(gè)坐標(biāo)值的特性以簡(jiǎn)化運(yùn)算。通過(guò)新的算法，可以極大地降低凸包算法的時(shí)間復(fù)雜度，使該值可降低至O（n）。

凸包；凸包算法；分治法；快包算法凸包是指針對(duì)平面上的一個(gè)點(diǎn)集，將這些所有的點(diǎn)都包含在內(nèi)或在其邊上的最小凸多邊形。而相應(yīng)的凸包算法則是指求取這個(gè)多邊形的方法，這是計(jì)算機(jī)幾何的基本問(wèn)題之一，在計(jì)算機(jī)圖形學(xué)，圖像處理，模式識(shí)別等多個(gè)領(lǐng)域有著廣泛的應(yīng)用。目前比較普及的凸包算法及所謂的快包算法由于要反復(fù)的求取點(diǎn)到直線的距離，在時(shí)間復(fù)雜度上都不能得到較好的結(jié)果，因此，尋求一個(gè)更好的凸包的快速求取方法一直是眾多學(xué)者所熱衷的問(wèn)題之一。

1 凸包算法基本思想

定理1 對(duì)于平面上任意一個(gè)點(diǎn)集S，或者一個(gè)多邊形P，其凸包是指包含S或者P的最小凸多邊形，這里只討論點(diǎn)集S的情況，如果是多邊形，則只需考慮多邊形的各頂點(diǎn)就可以使用同樣的原理來(lái)完成凸包的構(gòu)造。

2 新的凸包算法

2.1 排序

新的算法中依然會(huì)有一步基于分治法的原理。

在構(gòu)造新的凸包之前我們同樣需要先點(diǎn)集進(jìn)行排序處理，但是，在新的算法中，排序不僅在x軸上進(jìn)行，也在y軸上對(duì)點(diǎn)集進(jìn)行另一次的排序。通過(guò)這樣的排序以后，得到同一組點(diǎn)集的兩種不同排列，分別記為Px和Py。

2.2 分割

經(jīng)過(guò)上一步的排序，顯然，Px，Py中的第一個(gè)和最末一個(gè)值，都是凸包的頂點(diǎn)之一。先找出這四個(gè)點(diǎn)。分別記為Px1，Pxn，以及Py1，Pyn。通過(guò)這四個(gè)點(diǎn)，把平面區(qū)域劃分為五塊。分別如下圖所示：

圖1 區(qū)域分割圖

顯然，點(diǎn)集中所有的點(diǎn)都位于圖中標(biāo)注的五個(gè)區(qū)域中，且位于第五部分的點(diǎn)不可能在凸包的邊界上。所以，只需要討論一二三四部分的點(diǎn)的情況。

現(xiàn)在，就區(qū)域一的情況來(lái)對(duì)整個(gè)處理過(guò)程加以討論。

2.3 構(gòu)建凸包

下面以下圖為例，來(lái)解釋如何構(gòu)造一個(gè)區(qū)域中的凸包，假設(shè)第四個(gè)區(qū)域中的點(diǎn)如下圖所示。

圖2 凸包算法示意圖（一）

如上圖，假設(shè)圖中的P1和P5分別為前面圖中的Pxn和Pyn，即該圖中的點(diǎn)為區(qū)域劃分中第四區(qū)域中的點(diǎn)。根據(jù)這一部分點(diǎn)的凸包的構(gòu)造，可以理解如何構(gòu)造整個(gè)點(diǎn)集的凸包。

顯然，P1和P5都是凸包上的點(diǎn)。

現(xiàn)在，有位于該區(qū)域中的新的點(diǎn)集，在這個(gè)點(diǎn)集中，包括P1到P5以及S1至S7共12個(gè)點(diǎn)。構(gòu)造的方法是，現(xiàn)在點(diǎn)集中找到除P1外y值最大的一個(gè)點(diǎn)P2，通過(guò)P2將點(diǎn)集又劃分為兩個(gè)部分，分別為x值大于P2的x值與x值小于P2的x值的兩種情況分別位于兩個(gè)新的點(diǎn)集中。即S1～S4被劃入一個(gè)集，剩下的除P1，P2的點(diǎn)位于另一個(gè)集，顯然，S1～S4不可能位于凸包上，所以，從點(diǎn)集中去除這幾個(gè)點(diǎn)。

圖3 凸包算法示意圖（二）

刪除的點(diǎn)即如圖所示封閉區(qū)域內(nèi)的點(diǎn)

現(xiàn)在，點(diǎn)集中還有P1-P5以及S5-S7這8個(gè)點(diǎn)。繼續(xù)在這些點(diǎn)中查找除了P1，P2兩個(gè)點(diǎn)以外的y值最大的點(diǎn)P3，連接P2，P3，計(jì)算直線P1P2和直線P2P3的斜率，分別記為K12和K23，若后者絕對(duì)值大于前者，則暫時(shí)保留這三個(gè)點(diǎn)，否則，將P2點(diǎn)去除。

繼續(xù)該步驟，如上例中，| K23|〉|K12|，所以保留P1，P2，P3，并在剩下的點(diǎn)集中去除P3以左的點(diǎn)，在余下的點(diǎn)（即P3以右的點(diǎn)中）中繼續(xù)尋找最大y值。

圖4 凸包算法示意圖（三）

現(xiàn)在，找到P4，計(jì)算并比較K34和，有| K34|<| K23|，那么，從點(diǎn)集中去處P3點(diǎn)，連接P2P4，計(jì)算并比較K12和K24，若有| K24|>| K12|，則繼續(xù)在P4點(diǎn)以右尋找新的點(diǎn)，反之，則從點(diǎn)集中去除P2點(diǎn)（即中間點(diǎn)），繼續(xù)向前比較。

圖5 凸包算法示意圖（四）

重復(fù)進(jìn)行如上的步驟，直到選中的點(diǎn)右方只有P5（Pxn）一個(gè)點(diǎn)為止。連接最后一個(gè)點(diǎn)和P5（Pxn），自此，P1（Pyn），P5（Pxn）通過(guò)數(shù)條線段連接了起來(lái)。這些線段和x=xPxn，y=ypyn可構(gòu)成一個(gè)封閉的圖形，該圖形將區(qū)域四內(nèi)的所有點(diǎn)都包含在內(nèi)，且除兩條直角邊以外，其余的所有邊都有如下特點(diǎn)：

一：它們都以點(diǎn)集中的點(diǎn)為端點(diǎn)。

二：從最高點(diǎn)依次向下，每一條線段的斜率的絕對(duì)值依次遞增，或者說(shuō)，在該區(qū)域，線段的斜率都小于0，（因?yàn)楹竺娴狞c(diǎn)總比前一個(gè)點(diǎn)y值小，x值大），且依次遞減。

很顯然，這是一個(gè)凸包。

圖6 ：凸包算法示意圖（五）

在其余三個(gè)區(qū)域中重復(fù)類似的過(guò)程，可得到整個(gè)點(diǎn)集的凸包。

綜上所述，不考慮前面的兩次排序的過(guò)程，在后期的凸包構(gòu)建過(guò)程中，整個(gè)算法的時(shí)間復(fù)雜度為O（n）。

3 分析總結(jié)

在傳統(tǒng)的凸包算法或者快包算法中，由于每進(jìn)行一次分割以后都需要對(duì)依然保留的所有點(diǎn)進(jìn)行一次S值的計(jì)算，將帶來(lái)很大的計(jì)算量，快包算法有著和快速排序相同的時(shí)間復(fù)雜度O（n2）。而在新的算法中，通過(guò)建包前在兩個(gè)方向的排序，這將給算法帶來(lái)一定的復(fù)雜度，但在其后的分治過(guò)程中，不再按照傳統(tǒng)快包算法中的上下包分法，找出兩個(gè)極值點(diǎn)進(jìn)行連線操作，卻幾乎只需要做排出點(diǎn)的操作。而這個(gè)操作只需要將兩種排序的結(jié)果聯(lián)系起來(lái)，同時(shí)符合某種條件的點(diǎn)即可。

通過(guò)這樣的方式，以多一次排序的代價(jià)換來(lái)了后期處理過(guò)程中運(yùn)算量的大幅度降低，從而使總的時(shí)間復(fù)雜度得到降低，最終可以得到一個(gè)O（n）的時(shí)間復(fù)雜度，這個(gè)時(shí)間復(fù)雜度比起原來(lái)的時(shí)間復(fù)雜度，下降了一個(gè)數(shù)量級(jí)，在算法上說(shuō)來(lái)是很大的進(jìn)步。

[1] Anany Levitin 著；潘彥譯.算法設(shè)計(jì)與分析基礎(chǔ),第二版.清華大學(xué)出版社

[2] 金文華,何濤,唐衛(wèi)青,唐榮錫.簡(jiǎn)單快速的平面散亂點(diǎn)集凸包算法.北京航空航天大學(xué)學(xué)報(bào).1999年2月第25卷第一期73-75

[3] 吳中海,葉澄清,潘云鶴.一個(gè)改進(jìn)的簡(jiǎn)單多邊形凸包算法.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào).1997年1月,第1期 第9卷 9-13

10.3969/j.issn.1001-8972.2011.08.069