劉子堯

摘 要：針對基于夾角的二維凸包算法提出一種利用四邊形初始凸包方法進行優(yōu)化的思路。其基本思想是利用平面點集中4個極值點構(gòu)成的四邊形，摒棄掉平面點集中位于四邊內(nèi)部的內(nèi)點，再利用夾角凸包算法對剩余點集進行凸包計算。實驗結(jié)果表明，該凸包算法有效提升了原有算法的運行效率，但兩個算法同樣存在著無法應(yīng)用于數(shù)量龐大的數(shù)據(jù)中的問題。

關(guān)鍵詞：夾角凸包算法；初始凸包；離散點；地理信息系統(tǒng)

DOI：10.11907/rjdk.173049

中圖分類號：TP312

文獻標(biāo)識碼：A 文章編號：1672-7800（2018）004-0094-03

Abstract：Aiming at the two-dimensional convex hull algorithm based on the included angle， a method for optimizing the initial hull is proposed. The basic idea is to use the 4 extreme points in the points set to remove the points within the four sides. Then， the algorithm is run based on included angle to calculate the convex hull in the remainder points set. The result shows that the new algorithm has improved the efficiency of the previous one， but these two algorithms can not calculate the convex hull of the points set with the points beyond 104bear the same disadvantage that they can not be applied to large data.

Key Words：convex hull algorithm based on included angle； initial convex hull； discrete point； geographic information system

0 引言

針對一個平面上的點集D={P1，P2，P3，…，Pn}，總能找到一個點集CH（CHD），CH中的點連接所成的凸多邊形可以包含點集D中的所有點，這樣的點集CH稱為點集D的凸包（Convex Hull）。

凸包是計算幾何中的重要單元之一，在圖像處理、地理信息系統(tǒng)、空間分析等領(lǐng)域有著廣泛應(yīng)用。國內(nèi)外專家學(xué)者針對凸包算法進行了深入研究，例如1972年RL Graham[1]提出的一種基于極角排序的凸包算法，F(xiàn)P Preparata等[2]于1977年提出的將凸包問題利用分治（Divide and Conquer）思想處理的算法，C Bradford等[3]基于Delaunay三角網(wǎng)等思想提出的快速凸包（Quickhull）算法。此外，經(jīng)典的凸包算法還包括Jarvis步進法、卷包裹（Gift-Wrapping）法等。在這些經(jīng)典算法基礎(chǔ)上，國內(nèi)學(xué)者也提出了許多改進算法，例如呂夢樓等[4]提出的一種尋找平面點集中x+y最大、x+y最小、x-y最大、x-y最小坐標(biāo)點的四邊形初始凸包思想，類似找尋初始凸包的算法還有劉人午等[5]提出的尋找4個坐標(biāo)極值點的最小凸包生成算法；鄔長安等[6]提出了一種基于夾角的二維凸包改進算法，以下稱為夾角法，該算法的基本思想是利用平面點集中點與凸包起點構(gòu)成的夾角以及與下一個順時針查詢點構(gòu)成的角度大小判斷查詢點是否是凸包點。

平面點集中有相當(dāng)一部分點位于凸包內(nèi)部，凸包點只是平面點集中的很小一部分。因此，如果將平面點集中肯定位于凸包內(nèi)部的點去除，可以在很大程度上加速凸包構(gòu)建，這也是初始凸包的思想。本文基于該思想改進了夾角法，將原本需要查詢整個平面點集的凸包算法改進為只需查詢部分點集的夾角凸包算法。初始凸包由快速凸包經(jīng)過眾多學(xué)者研究演變成四邊形初始凸包和八邊形初始凸包，而八邊形初始凸包在去除多余凸包內(nèi)部點上效率并未達(dá)到預(yù)期，所以本文采用的是四邊形初始凸包[7]。

1 相關(guān)定義

定義1：對于一個平面點集D={P1，P2，P3，…，Pn}，點集CH是點集D的凸包，將刪除點集CH內(nèi)的若干個點后形成的多邊形稱為點集D的初始凸包OCH。

定義2：將包含在點集OCH形成多邊形內(nèi)的點稱為OCH的內(nèi)點，將落在點集OCH形成多邊形外的點稱為點集OCH的外點。

定義3：初始凸包OCH內(nèi)的點稱為點集D的初始凸包點，所連接形成的邊稱為點集D的初始凸包邊。

2 算法原理

2.1 夾角法

夾角法求凸包的基本思想是首先確定橫坐標(biāo)最小的點P1；其次遍歷點集中各點與P1的連線與水平線的夾角，找到夾角最大的點作為第2個凸包點P2。判斷角度大小采用角度的正弦值，因為P1是橫坐標(biāo)最小的點，則連線與水平線構(gòu)成的夾角范圍在[-90°，90°]內(nèi)，正弦函數(shù)在該范圍內(nèi)是一個單增函數(shù)，所以利用夾角正弦值判斷夾角大小，P1與P2則構(gòu)成一條凸包上的邊，如圖2所示；然后尋找第3個凸包點，利用P1和P2的連線作為一個三角形的一邊，遍歷點集中其它點，找到第3個點P3使∠P1P2P3的余弦值最小，即∠P1P2P3最大，因為余弦函數(shù)在[0°，180°]范圍內(nèi)是一個減函數(shù)，所以當(dāng)α的余弦值最小時，對應(yīng)的角度也最大，則P3為第3個凸包點，如圖3所示；最后，將P2視為新的起點（P1），P3視為P2重復(fù)上述過程，直至P3與橫坐標(biāo)最小的點重合，如圖4、圖5所示。

2.2 改進后的夾角法

在針對凸包的計算中，夾角法有其獨特優(yōu)勢，即可以不用單獨處理點的共線問題。但夾角法對很多凸包內(nèi)部的點進行了不必要的訪問，而初始凸包的提出正好可解決該問題，利用初始凸包去掉許多內(nèi)部的點，能有效減少多余查詢，提高算法效率。算法基本思想是：首先針對擁有100個隨機離散點的平面點集D，找出點集中橫坐標(biāo)最大、最小，縱坐標(biāo)最大、最小的點，這4個點必然是凸包上的點，如果出現(xiàn)多個相同的最小橫坐標(biāo)，則取縱坐標(biāo)最小的一個，多個相同的最大橫坐標(biāo)取縱坐標(biāo)最大的，縱坐標(biāo)相同時類似橫坐標(biāo)，如圖6所示；其次，連接4個坐標(biāo)極值點形成初始凸包，去掉其內(nèi)部點，剩余點集擁有51個數(shù)據(jù)，如圖7所示；然后利用夾角凸包算法對數(shù)量減少后的點集進行凸包計算，最終計算結(jié)果如圖8所示。

算法：

輸入：平面點集D。

輸出：點集D的凸包CH。

S1：根據(jù)點集D內(nèi)的數(shù)據(jù)找到四邊形初始凸包的4個極值頂點Pminx、Pmaxx、Pminy、Pmaxy。

S2：將初始凸包的內(nèi)點從點集D中刪除。

S3：計算D中每個點和P1（xmin）的連線與水平線夾角的正弦值，正弦值最大的點即為第2個凸包點P2。

S4：以P1和P2的連線P1P2作為三角形的一條邊，依次將點集內(nèi)剩余的n-2個點與P1P2構(gòu)成三角形，并比較∠P1P2P3的余弦值，最小余弦值對應(yīng)的點P3即為第3個凸包點。

S5：P1代替P2，P2代替P3，在剩余n-3個點中尋找新的P3。

S6：重復(fù)步驟S5，當(dāng)P3與Pminx重合時，算法結(jié)束。

算法的基本思想是在基于夾角的凸包算法中，利用初始凸包的思路盡量減少夾角法中需要訪問和計算的數(shù)量。

3 實驗分析

一個算法的運行效率及處理數(shù)據(jù)的能力不能單純依靠時間復(fù)雜度判斷，必須經(jīng)過多次實驗才能判斷算法優(yōu)劣。針對上文提到的夾角凸包法和改進后算法，首先使用Matlab隨機生成的100個（10，10）范圍內(nèi)離散點加以實現(xiàn)，運行配置為8G內(nèi)存，處理器為Intel Core（TM） 2.50GHz。實現(xiàn)過程中發(fā)現(xiàn)，兩個算法在各個步驟都有執(zhí)行時間的差別，如表1所示。

對于兩種算法，使用不同規(guī)模的平面點集對凸包生成效率進行對比，點集內(nèi)離散點數(shù)量分別為102、103、104、105和106。針對不同數(shù)量規(guī)模的點集，兩種算法運行時間如表2所示。表中數(shù)據(jù)均是10次試驗結(jié)果的平均值，與表1中存在的時間差距是由于兩種實現(xiàn)方法不同，表1中的算法實現(xiàn)是分步驟進行的，而表2中的執(zhí)行時間是算法的整體執(zhí)行時間。

4 結(jié)論及展望

分析試驗結(jié)果可以得到：①利用初始凸包思想優(yōu)化過的夾角凸包算法可以提高算法運行效率；②兩種算法同樣存在的問題是在點的數(shù)量超過104后運算效率下降，無法與四邊形、八邊形和快凸包等方法相比[5，7]。

本文算法在算法執(zhí)行效率上進行了改進，可以實現(xiàn)最小凸包的生成，并應(yīng)用到地理信息系統(tǒng)或圖像處理中，但對于點集中離散點數(shù)量龐大時并不適用。對于本文算法的進一步改進可以簡化順時針卷包裹下一個凸包點的方式，也可以考慮在改進算法中形成三角形時摒棄掉三角形內(nèi)點，以減少運行時間。

參考文獻：

[1] GRAHAM R L. An efficient algorith for determining the convex hull of a finite planar set[J]. Information Processing Letters，1972（4）：132-133.

[2] PREPARATA F P， HONG S J. Convex hull of a finite set of points in two and three dimensions[J].1977，20（2）：87-93.

[3] BRADFORD B C， DOBKIN D P，et al. The quickhull algorithm for convex hulls[J]. Acm Transactions on Mathematical Software，1996，22（4）：469-483.

[4] 呂夢樓，劉少華.凸包生成的一種改進算法[J].城市勘測，2011，2011（1）：29-31.

[5] 劉人午，楊德宏，李燕，等.一種改進的最小凸包生成算法[J].大地測量與地球動力學(xué)，2011，31（3）：130-133.

[6] 鄔長安，王志平.基于夾角的二維凸包改進算法[J].信陽師范學(xué)院學(xué)報：自然科學(xué)版，2007，20（4）：508-510.

[7] 陳明晶，方源敏，陳杰.初始凸包對改進快速凸包算法效率的影響[J].測繪科學(xué)，2016，41（7）：23-27.

[8] 樊廣佺，馬麗平，楊炳儒.平面點集凸殼的一種快速算法[J].地理與地理信息科學(xué)，2006，22（6）：38-41.

[9] 魏向輝，夏春林，魯慶偉.一種基于凸包的Delaunay三角網(wǎng)算法設(shè)計[J].測繪科學(xué)，2010，35（5）：152-153.

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

[11] 周之英.平面點集凸殼的實時算法[J].計算機學(xué)報，1985（2）：58-65.

（責(zé)任編輯：黃 ?。?/p>