凸包生成的一種改進算法

呂夢樓，劉少華

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

凸包生成的一種改進算法

呂夢樓?，劉少華

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

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

平面離散點集；凸包；時間復(fù)雜度

1 引 言

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

2 相關(guān)概念

2.1 平面離散點集

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

2.2 平面點集凸包

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

2.3 時間復(fù)雜度

時間復(fù)雜度是度量算法執(zhí)行的時間長短，它是衡量算法復(fù)雜度的標準之一[3]。

3 原始算法基本思想

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

4 改進算法

4.1 算法改進方法描述

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

4.2 算法具體步驟

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

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

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

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

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

步驟6:當線數(shù)據(jù)集LinAry中的每一條線都被選作過基準線時，凸包點就全部找出，循環(huán)結(jié)束。

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

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

點:X坐標，Y坐標，ID號，大小，顏色；

線:Point1(線的端點1)，Point2(線的端點2)，ID號，Lable(標記)，大小，顏色；

凸包點:采用一個點數(shù)據(jù)集來記錄；

刪除點:采用一個點數(shù)據(jù)集來記錄；

凸包邊:采用一個線數(shù)據(jù)集來記錄。

4.4 凸包生成過程簡述

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

圖1 生成四邊形

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

圖3 尋找凸包點

圖4 生成凸包

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

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

6 結(jié) 語

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

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

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

[3] 葉綠，趙家森.GIS中點集凸包的快速算法[J].測繪學(xué)報，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

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

國家973項目資助(2009CB219608)；國家油氣重大專項資助(2009ZX05038)