基于夾角的凸包算法改進(jìn)

劉子堯

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

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

DOI：10.11907/rjdk.173049

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

1 相關(guān)定義

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

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

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

2 算法原理

2.1 夾角法

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

2.2 改進(jìn)后的夾角法

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

算法：

輸入：平面點(diǎn)集D。

輸出：點(diǎn)集D的凸包CH。

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

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

S3：計(jì)算D中每個(gè)點(diǎn)和P1（xmin）的連線(xiàn)與水平線(xiàn)夾角的正弦值，正弦值最大的點(diǎn)即為第2個(gè)凸包點(diǎn)P2。

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

S5：P1代替P2，P2代替P3，在剩余n-3個(gè)點(diǎn)中尋找新的P3。

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

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

3 實(shí)驗(yàn)分析

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

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

4 結(jié)論及展望

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

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

參考文獻(xiàn)：

[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] 呂夢(mèng)樓，劉少華.凸包生成的一種改進(jìn)算法[J].城市勘測(cè)，2011，2011（1）：29-31.

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

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

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

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

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

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

[11] 周之英.平面點(diǎn)集凸殼的實(shí)時(shí)算法[J].計(jì)算機(jī)學(xué)報(bào)，1985（2）：58-65.

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