刘子尧

摘 要：针对基于夹角的二维凸包算法提出一种利用四边形初始凸包方法进行优化的思路。其基本思想是利用平面点集中4个极值点构成的四边形，摒弃掉平面点集中位于四边内部的内点，再利用夹角凸包算法对剩余點集进行凸包计算。实验结果表明，该凸包算法有效提升了原有算法的运行效率，但两个算法同样存在着无法应用于数量庞大的数据中的问题。

关键词：夹角凸包算法；初始凸包；离散点；地理信息系统

DOI：10.11907/rjdk.173049

中图分类号：TP312

文献标识码：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）。

凸包是计算几何中的重要单元之一，在图像处理、地理信息系统、空间分析等领域有着广泛应用。国内外专家学者针对凸包算法进行了深入研究，例如1972年RL Graham[1]提出的一种基于极角排序的凸包算法，FP Preparata等[2]于1977年提出的将凸包问题利用分治（Divide and Conquer）思想处理的算法，C Bradford等[3]基于Delaunay三角网等思想提出的快速凸包（Quickhull）算法。此外，经典的凸包算法还包括Jarvis步进法、卷包裹（Gift-Wrapping）法等。在这些经典算法基础上，国内学者也提出了许多改进算法，例如吕梦楼等[4]提出的一种寻找平面点集中x+y最大、x+y最小、x-y最大、x-y最小坐标点的四边形初始凸包思想，类似找寻初始凸包的算法还有刘人午等[5]提出的寻找4个坐标极值点的最小凸包生成算法；邬长安等[6]提出了一种基于夹角的二维凸包改进算法，以下称为夹角法，该算法的基本思想是利用平面点集中点与凸包起点构成的夹角以及与下一个顺时针查询点构成的角度大小判断查询点是否是凸包点。

平面点集中有相当一部分点位于凸包内部，凸包点只是平面点集中的很小一部分。因此，如果将平面点集中肯定位于凸包内部的点去除，可以在很大程度上加速凸包构建，这也是初始凸包的思想。本文基于该思想改进了夹角法，将原本需要查询整个平面点集的凸包算法改进为只需查询部分点集的夹角凸包算法。初始凸包由快速凸包经过众多学者研究演变成四边形初始凸包和八边形初始凸包，而八边形初始凸包在去除多余凸包内部点上效率并未达到预期，所以本文采用的是四边形初始凸包[7]。

1 相关定义

定义1：对于一个平面点集D={P1，P2，P3，…，Pn}，点集CH是点集D的凸包，将删除点集CH内的若干个点后形成的多边形称为点集D的初始凸包OCH。

定义2：将包含在点集OCH形成多边形内的点称为OCH的内点，将落在点集OCH形成多边形外的点称为点集OCH的外点。

定义3：初始凸包OCH内的点称为点集D的初始凸包点，所连接形成的边称为点集D的初始凸包边。

2 算法原理

2.1 夹角法

夹角法求凸包的基本思想是首先确定横坐标最小的点P1；其次遍历点集中各点与P1的连线与水平线的夹角，找到夹角最大的点作为第2个凸包点P2。判断角度大小采用角度的正弦值，因为P1是横坐标最小的点，则连线与水平线构成的夹角范围在[-90°，90°]内，正弦函数在该范围内是一个单增函数，所以利用夹角正弦值判断夹角大小，P1与P2则构成一条凸包上的边，如图2所示；然后寻找第3个凸包点，利用P1和P2的连线作为一个三角形的一边，遍历点集中其它点，找到第3个点P3使∠P1P2P3的余弦值最小，即∠P1P2P3最大，因为余弦函数在[0°，180°]范围内是一个减函数，所以当α的余弦值最小时，对应的角度也最大，则P3为第3个凸包点，如图3所示；最后，将P2视为新的起点（P1），P3视为P2重复上述过程，直至P3与横坐标最小的点重合，如图4、图5所示。

2.2 改进后的夹角法

在针对凸包的计算中，夹角法有其独特优势，即可以不用单独处理点的共线问题。但夹角法对很多凸包内部的点进行了不必要的访问，而初始凸包的提出正好可解決该问题，利用初始凸包去掉许多内部的点，能有效减少多余查询，提高算法效率。算法基本思想是：首先针对拥有100个随机离散点的平面点集D，找出点集中横坐标最大、最小，纵坐标最大、最小的点，这4个点必然是凸包上的点，如果出现多个相同的最小横坐标，则取纵坐标最小的一个，多个相同的最大横坐标取纵坐标最大的，纵坐标相同时类似横坐标，如图6所示；其次，连接4个坐标极值点形成初始凸包，去掉其内部点，剩余点集拥有51个数据，如图7所示；然后利用夹角凸包算法对数量减少后的点集进行凸包计算，最终计算结果如图8所示。

算法：

输入：平面点集D。

输出：点集D的凸包CH。

S1：根据点集D内的数据找到四边形初始凸包的4个极值顶点Pminx、Pmaxx、Pminy、Pmaxy。

S2：将初始凸包的内点从点集D中删除。

S3：计算D中每个点和P1（xmin）的连线与水平线夹角的正弦值，正弦值最大的点即为第2个凸包点P2。

S4：以P1和P2的连线P1P2作为三角形的一条边，依次将点集内剩余的n-2个点与P1P2构成三角形，并比较∠P1P2P3的余弦值，最小余弦值对应的点P3即为第3个凸包点。

S5：P1代替P2，P2代替P3，在剩余n-3个点中寻找新的P3。

S6：重复步骤S5，当P3与Pminx重合时，算法结束。

算法的基本思想是在基于夹角的凸包算法中，利用初始凸包的思路尽量减少夹角法中需要访问和计算的数量。

3 实验分析

一个算法的运行效率及处理数据的能力不能单纯依靠时间复杂度判断，必须经过多次实验才能判断算法优劣。针对上文提到的夹角凸包法和改进后算法，首先使用Matlab随机生成的100个（10，10）范围内离散点加以实现，运行配置为8G内存，处理器为Intel Core（TM） 2.50GHz。实现过程中发现，两个算法在各个步骤都有执行时间的差别，如表1所示。

对于两种算法，使用不同规模的平面点集对凸包生成效率进行对比，点集内离散点数量分别为102、103、104、105和106。针对不同数量规模的点集，两种算法运行时间如表2所示。表中数据均是10次试验结果的平均值，与表1中存在的时间差距是由于两种实现方法不同，表1中的算法实现是分步骤进行的，而表2中的执行时间是算法的整体执行时间。

4 结论及展望

分析试验结果可以得到：①利用初始凸包思想优化过的夹角凸包算法可以提高算法运行效率；②两种算法同样存在的问题是在点的数量超过104后运算效率下降，无法与四边形、八边形和快凸包等方法相比[5，7]。

本文算法在算法执行效率上进行了改进，可以实现最小凸包的生成，并应用到地理信息系统或图像处理中，但对于点集中离散点数量庞大时并不适用。对于本文算法的进一步改进可以简化顺时针卷包裹下一个凸包点的方式，也可以考虑在改进算法中形成三角形时摒弃掉三角形内点，以减少运行时间。

参考文献：

[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].大地测量与地球动力学，2011，31（3）：130-133.

[6] 邬长安，王志平.基于夹角的二维凸包改进算法[J].信阳师范学院学报：自然科学版，2007，20（4）：508-510.

[7] 陈明晶，方源敏，陈杰.初始凸包对改进快速凸包算法效率的影响[J].测绘科学，2016，41（7）：23-27.

[8] 樊广佺，马丽平，杨炳儒.平面点集凸壳的一种快速算法[J].地理与地理信息科学，2006，22（6）：38-41.

[9] 魏向辉，夏春林，鲁庆伟.一种基于凸包的Delaunay三角网算法设计[J].测绘科学，2010，35（5）：152-153.

[10] 程三友，李英杰.一种新的最小凸包算法及其应用[J].地理与地理信息科学，2009，25（5）：43-45.

[11] 周之英.平面点集凸壳的实时算法[J].计算机学报，1985（2）：58-65.

（责任编辑：黄 健）