馬 駿，藺東杰，凌廣明

(1.河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開封 475004; 2.河南大學(xué) 軟件學(xué)院，河南 開封 475004)

基于海量數(shù)據(jù)的二維凸包快速生成算法

馬 駿1，藺東杰1，凌廣明2

(1.河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開封 475004; 2.河南大學(xué) 軟件學(xué)院，河南 開封 475004)

凸包算法是計(jì)算機(jī)幾何的基本問題之一，在很多領(lǐng)域應(yīng)用廣泛。傳統(tǒng)的凸包生成算法在處理大容量數(shù)據(jù)時(shí)，表現(xiàn)出的時(shí)間復(fù)雜度相對(duì)較高而且凸包生成速率較低，已經(jīng)不能滿足實(shí)際海量數(shù)據(jù)的需求。為解決這一問題，提出了一種面對(duì)海量數(shù)據(jù)的快速凸包生成算法。該算法通過對(duì)散亂點(diǎn)集分區(qū)、一遍掃描排序，確定散亂點(diǎn)集邊界，快速處理邊界點(diǎn)集中處于共線的點(diǎn)等一系列預(yù)處理操作，快速排除凸包內(nèi)部的點(diǎn)，縮小了問題規(guī)模，避免了對(duì)不在凸包上的點(diǎn)集的掃描處理，明顯地縮短了凸包的求取時(shí)間，可保證最小凸包的快速生成。該算法極其簡單，時(shí)間復(fù)雜度較低，理論上可達(dá)到o(nlogn)，有利于凸包生成速度的提高。與傳統(tǒng)算法進(jìn)行了同步對(duì)比實(shí)驗(yàn)，結(jié)果表明，該算法運(yùn)行有效性較好，且具有較好的應(yīng)用前景。

凸包；海量；平面點(diǎn)集；預(yù)處理；排序；快速

0 引 言

凸包是指包含平面點(diǎn)集內(nèi)所有點(diǎn)并且頂點(diǎn)屬于平面點(diǎn)集的最小簡單凸多邊形。它作為計(jì)算幾何的基本單元之一，廣泛應(yīng)用于圖像處理、模式識(shí)別、地理信息系統(tǒng)、人工智能等領(lǐng)域。對(duì)于凸包的研究，一直是計(jì)算

幾何領(lǐng)域研究的熱點(diǎn)之一[1]。

自20世紀(jì)60年代末,貝爾實(shí)驗(yàn)室要求求解10 000個(gè)點(diǎn)的凸包。此后眾多學(xué)者提出了大量經(jīng)典的算法和改良算法[2]。

1970年,Chand和Kapur提出了任意維空間的gif-wrapping算法。該算法通過不斷查找使相鄰平面內(nèi)角最大的超平面直到平面集合封閉來確定點(diǎn)集的凸包。該算法的時(shí)間復(fù)雜度為o(n2)，其中n為點(diǎn)集中點(diǎn)的數(shù)量[3]。

1972年，Graham提出了時(shí)間復(fù)雜度低于o(n2)的算法，該算法的時(shí)間復(fù)雜度為o(nlogn)；1978年，Anderson重新評(píng)估Graham算法，簡化計(jì)算來確定連續(xù)三個(gè)點(diǎn)中第二個(gè)點(diǎn)是否為凸點(diǎn)。之后Koplowitz和Joup、Atwah、Baker分別在1978年、1995年和2002年在Graham算法的基礎(chǔ)上提出了快速二維平面點(diǎn)集凸包算法[4]。1973年，Jarvis提出了包含點(diǎn)缺失檢測(cè)的凸包算法，并且證明當(dāng)平面上點(diǎn)數(shù)相對(duì)較少時(shí)算法有效[5]。

1972年，Sklansky提出了具有線性時(shí)間復(fù)雜度的簡單多邊形凸包算法，但遺憾的是1978年Bykat發(fā)現(xiàn)該算法有可能產(chǎn)生自交的多邊形并舉出了反例，同年提出了一種新的具有線性時(shí)間復(fù)雜度的簡單多邊形凸包算法，該算法很快也被推翻[6]。1989年，臺(tái)灣大學(xué)的陳誠林在Sklansky算法基礎(chǔ)上提出的算法，較為簡單有效[7]，但浙江大學(xué)的吳中海博士于1997年發(fā)表文章指出了其中的細(xì)節(jié)錯(cuò)誤并提出了改進(jìn)算法[8]。

目前提出的算法中除了卷包囊算法、Gramham法、QuickHull法、Incremental法之外，還有BruteForce算法[9]。這些經(jīng)典的凸包生成算法，其結(jié)構(gòu)相對(duì)簡單，因此在各個(gè)領(lǐng)域中應(yīng)用廣泛。但隨著數(shù)據(jù)量的不斷增加，這些算法已經(jīng)不能滿足應(yīng)用的需求。當(dāng)平面點(diǎn)集數(shù)量達(dá)到106時(shí)，這些算法付出的時(shí)間和空間代價(jià)過大[10]。

為解決這一問題，文中提出基于海量數(shù)據(jù)的二維凸包快速生成算法。該算法在Gramham算法的基礎(chǔ)上通過分區(qū)、排序等預(yù)處理操作快速去除肯定不在凸包上的點(diǎn)集，同時(shí)對(duì)邊界點(diǎn)集進(jìn)行排序等操作，縮小問題規(guī)模，快速生成凸包，并與傳統(tǒng)算法進(jìn)行測(cè)試對(duì)比。結(jié)果表明，該算法理論時(shí)間復(fù)雜度和空間復(fù)雜度相對(duì)較低。

1 凸包及其相關(guān)概念

定義1:設(shè)點(diǎn)集S?Rn，S中任意有限個(gè)點(diǎn)的所有凸組合所構(gòu)成的集合稱為S的凸包，記為H(S),即

H(S)=

點(diǎn)集S的凸包H(S)也可以描述為包含點(diǎn)集S的所有凸集或半空間的公共交集。它是包含點(diǎn)集S的最小凸集[11]。

在Ed空間上的點(diǎn)集S的凸包是由S中至多d+1個(gè)點(diǎn)的所有凸組合的集合。因此，平面點(diǎn)集的凸包是點(diǎn)集中至多3個(gè)點(diǎn)的凸組合的集合，任意3個(gè)點(diǎn)的凸組合的集合構(gòu)成一個(gè)三角形，因而平面點(diǎn)集的凸包可以看成是點(diǎn)集中任意3個(gè)點(diǎn)的凸組合的集合確定的三角形的并集[12]。

S(A,B,C)=(xb-xa)×(yc-yb)-(xc-xb)×(yb-ya)

根據(jù)S的正負(fù)號(hào)來判斷頂點(diǎn)B的凹凸性，如圖1所示。

(1)如果S>0，B為凸點(diǎn)；

(2)如果S<0，B為凹點(diǎn)；

(3)如果S=0，B為平坦點(diǎn)。

圖1 點(diǎn)的凹凸性判斷

定義3:給定平面內(nèi)任意直線AB兩端點(diǎn)坐標(biāo)，A(xA,yA)，B(xB,yB)和一點(diǎn)P(xP,yP)，判斷點(diǎn)P與直線AB的位置關(guān)系。

設(shè)直線AB的方程是：

將點(diǎn)P代入到上述方程中得：

F=xA(yB-yP)-yA(xB-xP)+(xByP-xByB)

點(diǎn)P與直線AB的位置關(guān)系如圖2所示。

(1)F>0時(shí)表示點(diǎn)在直線的上方；

(2)F<0時(shí)表示點(diǎn)在直線的下方；

(3)F=0時(shí)表示點(diǎn)在直線上。

圖2 P與直線AB的位置關(guān)系

2 傳統(tǒng)算法思想

傳統(tǒng)的凸包算法是一種比較常用的算法，其算法思想如下：

以上方點(diǎn)集最小凸包求取為例，根據(jù)上述最小凸包求取的思想可知，線段PminPmax上方點(diǎn)集的最小凸包必包含點(diǎn)段PminPmax的兩端點(diǎn)，因此如果線段PminPmax上方無任何數(shù)據(jù)點(diǎn)，則上方最小凸包由點(diǎn)Pmin和Pmax構(gòu)成。如果線段PminPmax上方數(shù)據(jù)點(diǎn)較多，則上凸包求取步驟如下：

(1)設(shè)線段PminPmax上方數(shù)據(jù)點(diǎn)中距離最遠(yuǎn)的點(diǎn)為Pl，連接線段PminPl和線段PlPmax。

(2)分別找到線段PminPl和PlPmax上方點(diǎn)集中距離最遠(yuǎn)的點(diǎn)，如果PminPl和PlPmax上方均無數(shù)據(jù)點(diǎn)，則上凸包由點(diǎn)Pmin、Pl和Pmax構(gòu)成。

循環(huán)執(zhí)行步驟(1)和步驟(2)直到各個(gè)線段上方均無數(shù)據(jù)點(diǎn)為止。上凸包求取示意圖如圖3所示。

圖3 凸包求取示意圖

根據(jù)算法的基本思想可知，在凸包的求取過程中每確定一個(gè)凸包頂點(diǎn)，就要判斷線段之外是否還有其他數(shù)據(jù)點(diǎn)，這樣就需要遍歷點(diǎn)集中的數(shù)據(jù)點(diǎn)兩次。當(dāng)數(shù)據(jù)點(diǎn)個(gè)數(shù)和頂點(diǎn)個(gè)數(shù)均較大時(shí)，判斷次數(shù)將是數(shù)量級(jí)級(jí)別的增長，如果面對(duì)海量數(shù)據(jù)，其凸包求取速度難以想象，直接影響系統(tǒng)的運(yùn)行效率。因此傳統(tǒng)凸包算法已不能滿足具體現(xiàn)實(shí)需求[15]。

3 文中算法思想

3.1 點(diǎn)集預(yù)處理

圖4 點(diǎn)集的子集劃分

以如圖5(a)所示的點(diǎn)集為例，簡述平面點(diǎn)集的預(yù)處理：

圖5 點(diǎn)集預(yù)處理

(1)從點(diǎn)集中確定極值點(diǎn)，即點(diǎn)A、B、C、D，如圖5(b)所示。

(2)根據(jù)點(diǎn)與直線的位置關(guān)系函數(shù)F，將散亂點(diǎn)集分為五個(gè)區(qū)域，并將點(diǎn)集V刪除，如圖5(c)所示。

(3)將點(diǎn)集V1、V2中的點(diǎn)按照x坐標(biāo)值從小到大排序，當(dāng)x坐標(biāo)值相等時(shí)，選擇y坐標(biāo)值最小的點(diǎn)，將y坐標(biāo)值相對(duì)較大的點(diǎn)刪除；同理將點(diǎn)集V3、V4中的點(diǎn)按照x坐標(biāo)值從小到大進(jìn)行排序，當(dāng)x坐標(biāo)值相等時(shí)，選擇y坐標(biāo)值最小的點(diǎn)，將y坐標(biāo)值相對(duì)較大的點(diǎn)刪除，如圖5(d)所示。

(4)從點(diǎn)A出發(fā)，將點(diǎn)A、子集V1中的點(diǎn)、點(diǎn)D、子集V2中的點(diǎn)、點(diǎn)B、子集V4中的點(diǎn)、點(diǎn)C、子集V3中的點(diǎn)按照逆時(shí)針方向連接，這樣凸包邊界就確定了。分界線以上的點(diǎn)按照x坐標(biāo)從大到小連接，分界線以下的點(diǎn)按照x坐標(biāo)從小到大連接，如圖5(e)所示。

經(jīng)過第二步的處理已經(jīng)刪除的大部分不在凸包上的點(diǎn)，再加上第三步的處理，不僅進(jìn)一步刪除不在凸包上的點(diǎn)，同時(shí)對(duì)凸包邊界上的點(diǎn)進(jìn)行了排序，快速確定凸包邊界，極大地縮短了凸包的求取速度。

3.2 凸包求取

在求取平面散亂點(diǎn)集的凸包算法中，對(duì)于點(diǎn)集的無序性必須進(jìn)行處理。很多算法沒有對(duì)這些散亂點(diǎn)集進(jìn)行預(yù)處理，從而導(dǎo)致算法復(fù)雜且易出錯(cuò)。通過對(duì)上述散亂點(diǎn)集進(jìn)行預(yù)處理排序、刪除多余頂點(diǎn)，得到一個(gè)有序多邊形，下面就以圖5(e)所示的多邊形為例介紹凸包的求取。

(1)選取左下角的頂點(diǎn)為參考點(diǎn)。

(2)利用向量叉積的符號(hào)代表向量旋轉(zhuǎn)方向這一特性，按照逆時(shí)針方向?qū)Φ玫降捻旤c(diǎn)按照極角大小進(jìn)行排序。

(3)通過第二步的處理得到有序頂點(diǎn)序列，利用凸包連續(xù)的三個(gè)矢量頂點(diǎn)的凹凸性，當(dāng)叉積S小于零時(shí)將頂點(diǎn)從棧中刪除，當(dāng)S大于零時(shí)將頂點(diǎn)壓棧。

該凸包算法對(duì)極角進(jìn)行排序時(shí)利用叉積符號(hào)代表旋轉(zhuǎn)方向這一特性可以避免計(jì)算小數(shù)的誤差。采用棧結(jié)構(gòu)根據(jù)叉積進(jìn)行凹凸性判斷，這樣依次刪除所有凹點(diǎn)，最終保留下來的點(diǎn)為凸包子集。

4 算法分析與測(cè)試結(jié)果

4.1 效率分析

根據(jù)上述處理，可知凸包算法求取主要分為：

(1)散亂點(diǎn)集的預(yù)處理。通過尋找極值點(diǎn)刪除一定不再凸包上的點(diǎn)，之后通過一邊掃描排序法，再刪除一些特殊的點(diǎn)同時(shí)實(shí)現(xiàn)剩余點(diǎn)集的有序性，最終對(duì)有序點(diǎn)集按照極角進(jìn)行排序。

(2)凸包求取。利用凸包連續(xù)的三個(gè)矢量頂點(diǎn)的凹凸性，通過計(jì)算叉積來求取平面點(diǎn)集的凸包。

上述過程中對(duì)于點(diǎn)集的預(yù)處理，尋找極值點(diǎn)的時(shí)間復(fù)雜度是o(n)，將點(diǎn)集劃分為子集的時(shí)間復(fù)雜度是o(n)。由目前內(nèi)部排序算法理論可知，對(duì)點(diǎn)集進(jìn)行排序的算法最壞時(shí)間復(fù)雜度為o(nlogn)。對(duì)點(diǎn)集按照極角排序的時(shí)間復(fù)雜度是o(n)。由上述可知，文中提出的平面點(diǎn)集凸包求取算法的時(shí)間復(fù)雜度最壞是o(nlogn)。

4.2 測(cè)試結(jié)果

這里用產(chǎn)生隨機(jī)數(shù)的方法生成散亂點(diǎn)集，并將傳統(tǒng)算法與文中算法的運(yùn)行速度進(jìn)行多次比較，結(jié)果用C#編程獲得，如圖6所示。

圖6 算法運(yùn)行結(jié)果

程序中通過多次比較傳統(tǒng)算法與文中算法的平均運(yùn)行時(shí)間，其結(jié)果如表1所示。

表1 運(yùn)行時(shí)間對(duì)比

5 結(jié)束語

基于海量數(shù)據(jù)的二維凸包快速生成算法通過對(duì)散亂點(diǎn)集分區(qū)、掃描等預(yù)處理，去除肯定不在凸包上的點(diǎn)集，避免了對(duì)不必要點(diǎn)集的處理，快速處理邊界中的共線點(diǎn)集，縮小了問題規(guī)模。在生成邊界的同時(shí)又對(duì)邊界數(shù)據(jù)進(jìn)行排序，使散亂的數(shù)據(jù)變得有序，極大提高了數(shù)據(jù)的處理能力以及凸包的生成速度。通過測(cè)試與對(duì)比，證明了基于海量數(shù)據(jù)的二維凸包快速生成算法在面對(duì)海量數(shù)據(jù)時(shí)，處理效果較好。因此該課題具有一定的理論研究意義和應(yīng)用價(jià)值。

[1] Duncan J S,Ayache N.Medical image analysis:progress over decades and the challenges ahead[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(1):85-106.

[2] Day A M.Planar convex hull algorithms in theory and practice[J].Computer Graphics Forum,1998,7(3):177-193.

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

[4] 吳雪剛.凸包算法和最近子空間分析及其在人臉識(shí)別中的應(yīng)用[D].重慶:重慶大學(xué),2014.

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

[6] 劉宏兵,鄔長安,周文勇.基于二維凸包的TSP算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(8)：1954-1956.

[7] Sklansky J.Measuring concavity on rectangular mosaic[J].IEEE Transactions on Computers,1972,C-21(12):1355-1364.

[8] 孔德慧,馬春玲.一種平面點(diǎn)集凸包與三角網(wǎng)格綜合生成的算法[J].計(jì)算機(jī)研究與發(fā)展，2000,37(7):891-896.

[9] 吳文周,李利番,王結(jié)臣.平面點(diǎn)集凸包Graham算法的改進(jìn)[J].測(cè)繪科學(xué)，2010,35(6):123-125.

[10] 毛 鵬.快速凸包計(jì)算實(shí)現(xiàn)及其應(yīng)用[D].西安:西安電子科技大學(xué),2013.

[11] Chen C L.Computing the convex hull of a simple polygon[J].Pattern Recognition,1989,50(5):561-565.

[12] Preparata P F,Hong S J.Convex hulls of finite sets of points in two and three dimensions[J].Communications of the ACM,1977,20(2):87-93.

[13] 李軍輝,李紫陽.GIS中散亂點(diǎn)集凸包的快速算法及編程[J].北京聯(lián)合大學(xué)學(xué)報(bào):自然科學(xué)版,2009,23(3)：32-34.

[14] 金文華,何 濤,劉曉平,等.基于有序簡單多邊形的平面點(diǎn)集凸包快速求取算法[J].計(jì)算機(jī)學(xué)報(bào),1998,21(6)：533-539.

[15] 劉 波,萬冉冉,阮 見,等.GIS中空間數(shù)據(jù)最小凸包串行算法的改進(jìn)[J].測(cè)繪科學(xué),2015,40(6):81-83.

Fast Algorithm for Generating Two-dimensional Convex Hull Based on Mass Data

MA Jun1，LIN Dong-jie1，LING Guang-ming2

(1.College of Computer and Information Engineering,Henan University,Kaifeng 475004,China; 2.School of Software,Henan University,Kaifeng 475004,China)

The convex hull algorithm is one of the fundamental problems in computer geometry and has been widely used in many fields.Traditional convex hull generation algorithm in dealing with large amounts of data shows high time complexity relatively and the lower rate of convex hull generation,which has been unable to meet the needs of actual data.In order to solve this problem,a fast convex hull algorithm of massive data in the face is proposed.Through a series of pre-processing operations of determining the scattered point set boundary and fast processing of boundary points concentrated in collinear points by partition and over scan sort of scattered point set,the algorithm quickly rules out the points inside the convex hull and reduces the size of the problem,to avoid the processing of assemblies that are not in the convex hull of point scanning,significantly shortening the calculating time of the convex hull,which can ensure the rapid generation of minimum convex hull.The algorithm is extremely simple,with low time complexity,achievingo(nlogn)theoretically.Itisconducivetoimprovethespeedofconvexhull.Comparedwiththetraditionalalgorithm,theexperimentalresultsshowthattheproposedalgorithmiseffectiveandhasgoodapplicationprospects.

convex hull;mass;planar point set;pretreatment;sort;fast

2016-04-13

2016-08-10

時(shí)間：2017-01-10

國家自然科學(xué)基金資助項(xiàng)目(61202098)

馬 駿(1964-)，男，教授，碩士，研究方向?yàn)榭臻g信息處理、分布式并行計(jì)算及網(wǎng)絡(luò)應(yīng)用；藺東杰(1990-)，男，碩士，通訊作者，研究方向?yàn)榭臻g信息處理、分布式并行計(jì)算及網(wǎng)絡(luò)應(yīng)用。

http://www.cnki.net/kcms/detail/61.1450.TP.20170110.1028.068.html

TP

A

1673-629X(2017)02-0042-04

10.3969/j.issn.1673-629X.2017.02.010