凸包生成的一種改進(jìn)算法

呂夢(mèng)樓，劉少華

(長(zhǎng)江大學(xué)地球科學(xué)學(xué)院，湖北荊州 434023)

凸包生成的一種改進(jìn)算法

呂夢(mèng)樓?，劉少華

(長(zhǎng)江大學(xué)地球科學(xué)學(xué)院，湖北荊州 434023)

為提高平面離散點(diǎn)集凸包的求取效率，充分利用原始凸包生成算法的生成特點(diǎn)，提出改進(jìn)的平面離散點(diǎn)集凸包求取算法。主要思想是先將四邊形內(nèi)的點(diǎn)全部刪除，然后對(duì)于每次新生成的三角形區(qū)域，將其內(nèi)部點(diǎn)全部刪除，而無(wú)需每次在查找新的外包點(diǎn)時(shí)，去搜尋整個(gè)原始點(diǎn)集。該算法可用VB實(shí)現(xiàn)，具有較強(qiáng)可靠性、高效性和穩(wěn)定性。

平面離散點(diǎn)集；凸包；時(shí)間復(fù)雜度

1 引 言

在地理信息系統(tǒng)(GIS)中，區(qū)域的裁剪和不規(guī)則三角網(wǎng)(TIN)的生成等都會(huì)用到點(diǎn)集凸包的計(jì)算。但隨著處理數(shù)據(jù)量的急劇增長(zhǎng)，這些算法已不能滿(mǎn)足應(yīng)用要求。當(dāng)二維平面點(diǎn)集的點(diǎn)數(shù)超過(guò)106數(shù)量級(jí)時(shí)，其時(shí)間和空間代價(jià)太大[1]。因此，在進(jìn)行平面點(diǎn)集凸包的生成時(shí)，對(duì)于擁有海量數(shù)據(jù)庫(kù)的GIS，選擇一個(gè)高效率的算法將顯得尤為重要。目前，生成平面點(diǎn)集凸包的算法有多種，經(jīng)典的算法包括卷包裹(Jarris)法和格雷厄姆(Graham)方法等。卷包裹法需要反復(fù)計(jì)算點(diǎn)集元素與旋轉(zhuǎn)線(xiàn)的夾角和比較夾角的大小，才能確定邊界頂點(diǎn)，因此，效率不高。格雷厄姆方法在進(jìn)行構(gòu)建凸包前，需要完成三項(xiàng)準(zhǔn)備工作:①確定基點(diǎn)；②計(jì)算點(diǎn)集所有元素與基點(diǎn)連線(xiàn)的水平夾角和基點(diǎn)到點(diǎn)集元素的距離；③按夾角大小和距離進(jìn)行排序，然后才能進(jìn)行邊界生成[2]。本文依據(jù)先前的凸包生成算法進(jìn)行改進(jìn)，主要是將包圍在三角形或四邊形內(nèi)的點(diǎn)刪除，而無(wú)需每次都去查找整個(gè)原始點(diǎn)集。

2 相關(guān)概念

2.1 平面離散點(diǎn)集

平面散亂點(diǎn)集是指未經(jīng)處理(如排序)，散亂分布的由平面坐標(biāo)組成的點(diǎn)的集合[2]。

2.2 平面點(diǎn)集凸包

平面點(diǎn)集凸包是包含平面點(diǎn)集中所有離散點(diǎn)的最小外接多邊形。由于多邊形的各個(gè)頂點(diǎn)均為凸點(diǎn)，所以稱(chēng)為凸包[2]。凸包有許多優(yōu)良的性質(zhì)，具體請(qǐng)見(jiàn)參考文獻(xiàn)[3]。

2.3 時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是度量算法執(zhí)行的時(shí)間長(zhǎng)短，它是衡量算法復(fù)雜度的標(biāo)準(zhǔn)之一[3]。

3 原始算法基本思想

對(duì)于二維平面的散亂點(diǎn)集[點(diǎn)坐標(biāo)p(x，y)]，先把x＋y最大、x＋y最小、x－y最小、x－y最大的4個(gè)點(diǎn)找出，將這4個(gè)點(diǎn)存放到點(diǎn)數(shù)據(jù)集PntAry1中，然后將其4點(diǎn)連成一個(gè)四邊形，并以四邊形逆時(shí)針為序，規(guī)定每條邊的方向并編號(hào)，將這四條線(xiàn)依次存放到線(xiàn)數(shù)據(jù)集LinAry中。然后，取線(xiàn)數(shù)據(jù)集LinAry的第一條線(xiàn)段作為基準(zhǔn)線(xiàn)，在基準(zhǔn)線(xiàn)的右邊尋找距離最大的點(diǎn)，那么我們就找到了一個(gè)新的凸包點(diǎn)，將其保存在點(diǎn)數(shù)據(jù)集PntAry1中，接著把這個(gè)凸包點(diǎn)作為中繼點(diǎn)，以逆時(shí)針?lè)较蛞来芜B接基準(zhǔn)線(xiàn)的兩端點(diǎn)，將形成的兩條新的線(xiàn)段保存在線(xiàn)數(shù)組中，同時(shí)把線(xiàn)數(shù)據(jù)集LinAry中的本次基準(zhǔn)線(xiàn)做個(gè)標(biāo)記，但如果基準(zhǔn)線(xiàn)右邊沒(méi)有點(diǎn)，就不用標(biāo)記。然后再以數(shù)據(jù)集LinAry第二條線(xiàn)作為基準(zhǔn)線(xiàn)，不斷重復(fù)以上步驟，直到線(xiàn)數(shù)據(jù)集LinAry中的每條線(xiàn)段都被選作過(guò)基準(zhǔn)線(xiàn)。最后，點(diǎn)數(shù)據(jù)集PntAry1中的點(diǎn)就是全部凸包點(diǎn)，線(xiàn)數(shù)據(jù)集LinAry中沒(méi)有被標(biāo)記的線(xiàn)段為凸包的邊。

4 改進(jìn)算法

4.1 算法改進(jìn)方法描述

基于上述方法，在找到4點(diǎn)連成的四邊形后，將上述4點(diǎn)和4條有向線(xiàn)段分別保存在點(diǎn)數(shù)據(jù)集PntAry1和線(xiàn)數(shù)據(jù)集LinAry中，然后將包含在四邊形的點(diǎn)全部刪除，同時(shí)將這些刪除后的點(diǎn)保存在另一個(gè)點(diǎn)數(shù)據(jù)集PntAry2中(便于圖形的顯示)。然后，取線(xiàn)數(shù)據(jù)集LinAry的第一條有向線(xiàn)段作為基準(zhǔn)線(xiàn)，仍采用原始方法，尋找新的凸包點(diǎn)，如果線(xiàn)段右邊沒(méi)有點(diǎn)，基準(zhǔn)線(xiàn)在線(xiàn)數(shù)據(jù)集LinAry中就不用標(biāo)記，如果找到了新的凸包點(diǎn)，標(biāo)記基準(zhǔn)線(xiàn)，然后將落在新的凸包點(diǎn)與基準(zhǔn)線(xiàn)兩端點(diǎn)連接成的三角形區(qū)域內(nèi)的點(diǎn)全部刪除，將刪除點(diǎn)保存在點(diǎn)數(shù)據(jù)集PntAry。然后再以數(shù)據(jù)集LinAry中第二條線(xiàn)作為基準(zhǔn)線(xiàn)，不斷重復(fù)以上步驟，直到線(xiàn)數(shù)據(jù)集LinAry中的每條線(xiàn)段都被選作過(guò)基準(zhǔn)線(xiàn)。最后，點(diǎn)數(shù)組PntAry1中的點(diǎn)就是全部凸包點(diǎn)，點(diǎn)數(shù)據(jù)集PntAry2中的點(diǎn)是被刪除的點(diǎn)，線(xiàn)數(shù)據(jù)集LinAry中沒(méi)有被標(biāo)記的線(xiàn)段為凸包的邊。

4.2 算法具體步驟

步驟1:根據(jù)點(diǎn)的x，y坐標(biāo)值，找出x＋y最大、x＋y最小、x－y最小、x－y最大的4個(gè)點(diǎn)p1、p2、p3、p4，并將它們保存在點(diǎn)數(shù)據(jù)集PntAry1中。

步驟2:將4點(diǎn)圍成一個(gè)簡(jiǎn)單的四邊形，找出落在四邊形區(qū)域內(nèi)的點(diǎn)(只要點(diǎn)在每條線(xiàn)的左邊，則證明點(diǎn)在范圍內(nèi))，將它們保存在點(diǎn)數(shù)據(jù)集PntAry2中，然后再把它們從原始點(diǎn)集中刪除。

步驟3:把四邊形的4條邊以逆時(shí)針為序，規(guī)定每條邊的方向后并編號(hào)，將它們依次存放到線(xiàn)數(shù)據(jù)集LinAry中，然后從線(xiàn)數(shù)據(jù)集LinAry中取第一條有向線(xiàn)段作為基準(zhǔn)線(xiàn)。

步驟4:在基準(zhǔn)線(xiàn)的右邊尋找距離最大的點(diǎn)，如果基準(zhǔn)線(xiàn)的右邊沒(méi)有點(diǎn)，則將線(xiàn)數(shù)據(jù)集LinAry中的下一條線(xiàn)作為基準(zhǔn)線(xiàn)，轉(zhuǎn)到步驟4；如果找到一個(gè)距離最大的點(diǎn)，就把它作為新的凸包點(diǎn)，存入點(diǎn)數(shù)據(jù)集PntAry1中，然后標(biāo)記基準(zhǔn)線(xiàn)。

步驟5:將新的凸包點(diǎn)作為中繼點(diǎn)，與基準(zhǔn)線(xiàn)兩端點(diǎn)以逆時(shí)針?lè)较蛳噙B，將新生成的兩條有向線(xiàn)段保存在線(xiàn)數(shù)據(jù)集LinAry，然后將3條邊圍成的三角形范圍內(nèi)的點(diǎn)全部保存在點(diǎn)數(shù)據(jù)集PntAry2中，之后在原始數(shù)據(jù)集中將它們?nèi)縿h除，最后選取線(xiàn)數(shù)據(jù)集LinAry中的下一條線(xiàn)作為基準(zhǔn)線(xiàn)，轉(zhuǎn)到步驟4。

步驟6:當(dāng)線(xiàn)數(shù)據(jù)集LinAry中的每一條線(xiàn)都被選作過(guò)基準(zhǔn)線(xiàn)時(shí)，凸包點(diǎn)就全部找出，循環(huán)結(jié)束。

步驟7:將點(diǎn)數(shù)據(jù)集PntAry1、PntAry2，線(xiàn)數(shù)據(jù)集LinAry顯示在屏幕上。

4.3 算法的數(shù)據(jù)結(jié)構(gòu)

點(diǎn):X坐標(biāo)，Y坐標(biāo)，ID號(hào)，大小，顏色；

線(xiàn):Point1(線(xiàn)的端點(diǎn)1)，Point2(線(xiàn)的端點(diǎn)2)，ID號(hào)，Lable(標(biāo)記)，大小，顏色；

凸包點(diǎn):采用一個(gè)點(diǎn)數(shù)據(jù)集來(lái)記錄；

刪除點(diǎn):采用一個(gè)點(diǎn)數(shù)據(jù)集來(lái)記錄；

凸包邊:采用一個(gè)線(xiàn)數(shù)據(jù)集來(lái)記錄。

4.4 凸包生成過(guò)程簡(jiǎn)述

先基于平面點(diǎn)集，生成一個(gè)四邊形區(qū)域，如圖1所示，然后將包括在四邊形內(nèi)部的點(diǎn)全部刪除，如圖2所示。取出四邊形第一條邊，在其右側(cè)找到一個(gè)凸包點(diǎn)，生成一個(gè)三角形區(qū)域，然后將其區(qū)域內(nèi)部的點(diǎn)全部刪除，如圖3所示。將每條邊作以上相同操作，直到把所有凸包點(diǎn)找到為止，最后生成凸包，如圖4所示。

圖1 生成四邊形

圖2 刪除內(nèi)部點(diǎn)

圖3 尋找凸包點(diǎn)

圖4 生成凸包

5 時(shí)間復(fù)雜度比較

對(duì)于原始算法，它主要的時(shí)間花費(fèi)在判斷P是否為基準(zhǔn)線(xiàn)右邊的點(diǎn)，在最壞情況下，它需要和原始點(diǎn)集里面的每個(gè)點(diǎn)進(jìn)行比較，就這一過(guò)程所需的時(shí)間復(fù)雜度為O(n)，然后它還要對(duì)每條基準(zhǔn)線(xiàn)進(jìn)行判斷，其最終的時(shí)間復(fù)雜度為O(nlogn)。而改進(jìn)后的算法，它克服了原始算法的缺點(diǎn)，在找到一個(gè)新的范圍的之后，刪除包含在里面的點(diǎn)，從而使原始點(diǎn)集里面的點(diǎn)大大減少，從而大大提高了查找的效率，經(jīng)最終計(jì)算，新算法的時(shí)間復(fù)雜度為O(n)。

6 結(jié) 語(yǔ)

對(duì)于離散點(diǎn)較少的情況下，從節(jié)省時(shí)間方面來(lái)考慮，效果可能不是很明顯，但對(duì)于GIS海量數(shù)據(jù)庫(kù)，選擇一個(gè)高效率的算法，將會(huì)大大提高程序的處理速度。本文提出的是一個(gè)凸包生成的改進(jìn)算法，通過(guò)刪除一定范圍內(nèi)的點(diǎn)來(lái)提高速度，該算法具有較強(qiáng)的可靠性、高效性和穩(wěn)定性。

[1] 程三友，李英杰.一種新的最小凸包算法及其應(yīng)用[J].地理與地理信息科學(xué)，2009(5):43～45

[2] 劉廣忠，黃琳娜.平面散亂點(diǎn)集凸包的快速生成算法[J].工程圖學(xué)學(xué)報(bào)，2008(4):111～114

[3] 葉綠，趙家森.GIS中點(diǎn)集凸包的快速算法[J].測(cè)繪學(xué)報(bào)，2004(4):319～322

An Improvement Algorithm of Convex Hull

Lv MengLou，Liu ShaoHua
(College of Geoscience，Yangtze University，Jingzhou 434023，China)

To improve the generation efficiency of convex hull of planar point set，an improved algorithm on determining convex hull of planar point set is proposed by making full use of the character of the convex hull.The main idea is to first delete all the points within the quadrilateral，Then all the points within the region that is generated by each new triangle deleted without having to find new outsourcing point to search the entire original set of points.The algorithm can be implemented by VB language，with strong reliability，high efficiency and stability.

Planar point set；Convex hull；Time complexity

1672－8262(2011)01－29－03

P208，TP311

A

2010—06—25

呂夢(mèng)樓(1988—)，男，主要從事GIS相關(guān)理論與開(kāi)發(fā)研究。

國(guó)家973項(xiàng)目資助(2009CB219608)；國(guó)家油氣重大專(zhuān)項(xiàng)資助(2009ZX05038)