基于海量數據的二維凸包快速生成算法

馬 駿，藺東杰，凌廣明

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

基于海量數據的二維凸包快速生成算法

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

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

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

凸包；海量；平面點集；預處理；排序；快速

0 引 言

凸包是指包含平面點集內所有點并且頂點屬于平面點集的最小簡單凸多邊形。它作為計算幾何的基本單元之一，廣泛應用于圖像處理、模式識別、地理信息系統、人工智能等領域。對于凸包的研究，一直是計算

幾何領域研究的熱點之一[1]。

自20世紀60年代末,貝爾實驗室要求求解10 000個點的凸包。此后眾多學者提出了大量經典的算法和改良算法[2]。

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

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

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

目前提出的算法中除了卷包囊算法、Gramham法、QuickHull法、Incremental法之外，還有BruteForce算法[9]。這些經典的凸包生成算法，其結構相對簡單，因此在各個領域中應用廣泛。但隨著數據量的不斷增加，這些算法已經不能滿足應用的需求。當平面點集數量達到106時，這些算法付出的時間和空間代價過大[10]。

為解決這一問題，文中提出基于海量數據的二維凸包快速生成算法。該算法在Gramham算法的基礎上通過分區、排序等預處理操作快速去除肯定不在凸包上的點集，同時對邊界點集進行排序等操作，縮小問題規模，快速生成凸包，并與傳統算法進行測試對比。結果表明，該算法理論時間復雜度和空間復雜度相對較低。

1 凸包及其相關概念

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

H(S)=

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

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

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

根據S的正負號來判斷頂點B的凹凸性，如圖1所示。

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

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

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

圖1 點的凹凸性判斷

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

設直線AB的方程是：

將點P代入到上述方程中得：

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

點P與直線AB的位置關系如圖2所示。

(1)F>0時表示點在直線的上方；

(2)F<0時表示點在直線的下方；

(3)F=0時表示點在直線上。

圖2 P與直線AB的位置關系

2 傳統算法思想

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

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

(1)設線段PminPmax上方數據點中距離最遠的點為Pl，連接線段PminPl和線段PlPmax。

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

循環執行步驟(1)和步驟(2)直到各個線段上方均無數據點為止。上凸包求取示意圖如圖3所示。

圖3 凸包求取示意圖

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

3 文中算法思想

3.1 點集預處理

圖4 點集的子集劃分

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

圖5 點集預處理

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

(2)根據點與直線的位置關系函數F，將散亂點集分為五個區域，并將點集V刪除，如圖5(c)所示。

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

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

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

3.2 凸包求取

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

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

(2)利用向量叉積的符號代表向量旋轉方向這一特性，按照逆時針方向對得到的頂點按照極角大小進行排序。

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

該凸包算法對極角進行排序時利用叉積符號代表旋轉方向這一特性可以避免計算小數的誤差。采用棧結構根據叉積進行凹凸性判斷，這樣依次刪除所有凹點，最終保留下來的點為凸包子集。

4 算法分析與測試結果

4.1 效率分析

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

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

(2)凸包求取。利用凸包連續的三個矢量頂點的凹凸性，通過計算叉積來求取平面點集的凸包。

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

4.2 測試結果

這里用產生隨機數的方法生成散亂點集，并將傳統算法與文中算法的運行速度進行多次比較，結果用C#編程獲得，如圖6所示。

圖6 算法運行結果

程序中通過多次比較傳統算法與文中算法的平均運行時間，其結果如表1所示。

表1 運行時間對比

5 結束語

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

[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] 程三友,李英杰.一種新的最小凸包算法及其應用[J].地理與地理信息科學,2009,25(5)：43-45.

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

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

[6] 劉宏兵,鄔長安,周文勇.基于二維凸包的TSP算法[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] 孔德慧,馬春玲.一種平面點集凸包與三角網格綜合生成的算法[J].計算機研究與發展，2000,37(7):891-896.

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

[10] 毛 鵬.快速凸包計算實現及其應用[D].西安:西安電子科技大學,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中散亂點集凸包的快速算法及編程[J].北京聯合大學學報:自然科學版,2009,23(3)：32-34.

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

[15] 劉 波,萬冉冉,阮 見,等.GIS中空間數據最小凸包串行算法的改進[J].測繪科學,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

時間：2017-01-10

國家自然科學基金資助項目(61202098)

馬 駿(1964-)，男，教授，碩士，研究方向為空間信息處理、分布式并行計算及網絡應用；藺東杰(1990-)，男，碩士，通訊作者，研究方向為空間信息處理、分布式并行計算及網絡應用。

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