凸包生成的一种改进算法

吕梦楼，刘少华

(长江大学地球科学学院，湖北荆州 434023)

凸包生成的一种改进算法

吕梦楼∗，刘少华

(长江大学地球科学学院，湖北荆州 434023)

为提高平面离散点集凸包的求取效率，充分利用原始凸包生成算法的生成特点，提出改进的平面离散点集凸包求取算法。主要思想是先将四边形内的点全部删除，然后对于每次新生成的三角形区域，将其内部点全部删除，而无需每次在查找新的外包点时，去搜寻整个原始点集。该算法可用VB实现，具有较强可靠性、高效性和稳定性。

平面离散点集；凸包；时间复杂度

1 引 言

在地理信息系统(GIS)中，区域的裁剪和不规则三角网(TIN)的生成等都会用到点集凸包的计算。但随着处理数据量的急剧增长，这些算法已不能满足应用要求。当二维平面点集的点数超过106数量级时，其时间和空间代价太大[1]。因此，在进行平面点集凸包的生成时，对于拥有海量数据库的GIS，选择一个高效率的算法将显得尤为重要。目前，生成平面点集凸包的算法有多种，经典的算法包括卷包裹(Jarris)法和格雷厄姆(Graham)方法等。卷包裹法需要反复计算点集元素与旋转线的夹角和比较夹角的大小，才能确定边界顶点，因此，效率不高。格雷厄姆方法在进行构建凸包前，需要完成三项准备工作:①确定基点；②计算点集所有元素与基点连线的水平夹角和基点到点集元素的距离；③按夹角大小和距离进行排序，然后才能进行边界生成[2]。本文依据先前的凸包生成算法进行改进，主要是将包围在三角形或四边形内的点删除，而无需每次都去查找整个原始点集。

2 相关概念

2.1 平面离散点集

平面散乱点集是指未经处理(如排序)，散乱分布的由平面坐标组成的点的集合[2]。

2.2 平面点集凸包

平面点集凸包是包含平面点集中所有离散点的最小外接多边形。由于多边形的各个顶点均为凸点，所以称为凸包[2]。凸包有许多优良的性质，具体请见参考文献[3]。

2.3 时间复杂度

时间复杂度是度量算法执行的时间长短，它是衡量算法复杂度的标准之一[3]。

3 原始算法基本思想

对于二维平面的散乱点集[点坐标p(x，y)]，先把x＋y最大、x＋y最小、x－y最小、x－y最大的4个点找出，将这4个点存放到点数据集PntAry1中，然后将其4点连成一个四边形，并以四边形逆时针为序，规定每条边的方向并编号，将这四条线依次存放到线数据集LinAry中。然后，取线数据集LinAry的第一条线段作为基准线，在基准线的右边寻找距离最大的点，那么我们就找到了一个新的凸包点，将其保存在点数据集PntAry1中，接着把这个凸包点作为中继点，以逆时针方向依次连接基准线的两端点，将形成的两条新的线段保存在线数组中，同时把线数据集LinAry中的本次基准线做个标记，但如果基准线右边没有点，就不用标记。然后再以数据集LinAry第二条线作为基准线，不断重复以上步骤，直到线数据集LinAry中的每条线段都被选作过基准线。最后，点数据集PntAry1中的点就是全部凸包点，线数据集LinAry中没有被标记的线段为凸包的边。

4 改进算法

4.1 算法改进方法描述

基于上述方法，在找到4点连成的四边形后，将上述4点和4条有向线段分别保存在点数据集PntAry1和线数据集LinAry中，然后将包含在四边形的点全部删除，同时将这些删除后的点保存在另一个点数据集PntAry2中(便于图形的显示)。然后，取线数据集LinAry的第一条有向线段作为基准线，仍采用原始方法，寻找新的凸包点，如果线段右边没有点，基准线在线数据集LinAry中就不用标记，如果找到了新的凸包点，标记基准线，然后将落在新的凸包点与基准线两端点连接成的三角形区域内的点全部删除，将删除点保存在点数据集PntAry。然后再以数据集LinAry中第二条线作为基准线，不断重复以上步骤，直到线数据集LinAry中的每条线段都被选作过基准线。最后，点数组PntAry1中的点就是全部凸包点，点数据集PntAry2中的点是被删除的点，线数据集LinAry中没有被标记的线段为凸包的边。

4.2 算法具体步骤

步骤1:根据点的x，y坐标值，找出x＋y最大、x＋y最小、x－y最小、x－y最大的4个点p1、p2、p3、p4，并将它们保存在点数据集PntAry1中。

步骤2:将4点围成一个简单的四边形，找出落在四边形区域内的点(只要点在每条线的左边，则证明点在范围内)，将它们保存在点数据集PntAry2中，然后再把它们从原始点集中删除。

步骤3:把四边形的4条边以逆时针为序，规定每条边的方向后并编号，将它们依次存放到线数据集LinAry中，然后从线数据集LinAry中取第一条有向线段作为基准线。

步骤4:在基准线的右边寻找距离最大的点，如果基准线的右边没有点，则将线数据集LinAry中的下一条线作为基准线，转到步骤4；如果找到一个距离最大的点，就把它作为新的凸包点，存入点数据集PntAry1中，然后标记基准线。

步骤5:将新的凸包点作为中继点，与基准线两端点以逆时针方向相连，将新生成的两条有向线段保存在线数据集LinAry，然后将3条边围成的三角形范围内的点全部保存在点数据集PntAry2中，之后在原始数据集中将它们全部删除，最后选取线数据集LinAry中的下一条线作为基准线，转到步骤4。

步骤6:当线数据集LinAry中的每一条线都被选作过基准线时，凸包点就全部找出，循环结束。

步骤7:将点数据集PntAry1、PntAry2，线数据集LinAry显示在屏幕上。

4.3 算法的数据结构

点:X坐标，Y坐标，ID号，大小，颜色；

线:Point1(线的端点1)，Point2(线的端点2)，ID号，Lable(标记)，大小，颜色；

凸包点:采用一个点数据集来记录；

删除点:采用一个点数据集来记录；

凸包边:采用一个线数据集来记录。

4.4 凸包生成过程简述

先基于平面点集，生成一个四边形区域，如图1所示，然后将包括在四边形内部的点全部删除，如图2所示。取出四边形第一条边，在其右侧找到一个凸包点，生成一个三角形区域，然后将其区域内部的点全部删除，如图3所示。将每条边作以上相同操作，直到把所有凸包点找到为止，最后生成凸包，如图4所示。

图1 生成四边形

图2 删除内部点

图3 寻找凸包点

图4 生成凸包

5 时间复杂度比较

对于原始算法，它主要的时间花费在判断P是否为基准线右边的点，在最坏情况下，它需要和原始点集里面的每个点进行比较，就这一过程所需的时间复杂度为O(n)，然后它还要对每条基准线进行判断，其最终的时间复杂度为O(nlogn)。而改进后的算法，它克服了原始算法的缺点，在找到一个新的范围的之后，删除包含在里面的点，从而使原始点集里面的点大大减少，从而大大提高了查找的效率，经最终计算，新算法的时间复杂度为O(n)。

6 结 语

对于离散点较少的情况下，从节省时间方面来考虑，效果可能不是很明显，但对于GIS海量数据库，选择一个高效率的算法，将会大大提高程序的处理速度。本文提出的是一个凸包生成的改进算法，通过删除一定范围内的点来提高速度，该算法具有较强的可靠性、高效性和稳定性。

[1] 程三友，李英杰.一种新的最小凸包算法及其应用[J].地理与地理信息科学，2009(5):43～45

[2] 刘广忠，黄琳娜.平面散乱点集凸包的快速生成算法[J].工程图学学报，2008(4):111～114

[3] 叶绿，赵家森.GIS中点集凸包的快速算法[J].测绘学报，2004(4):319～322

An Improvement Algorithm of Convex Hull

Lv MengLou，Liu ShaoHua
(College of Geoscience，Yangtze University，Jingzhou 434023，China)

To improve the generation efficiency of convex hull of planar point set，an improved algorithm on determining convex hull of planar point set is proposed by making full use of the character of the convex hull.The main idea is to first delete all the points within the quadrilateral，Then all the points within the region that is generated by each new triangle deleted without having to find new outsourcing point to search the entire original set of points.The algorithm can be implemented by VB language，with strong reliability，high efficiency and stability.

Planar point set；Convex hull；Time complexity

1672－8262(2011)01－29－03

P208，TP311

A

2010—06—25

吕梦楼(1988—)，男，主要从事GIS相关理论与开发研究。

国家973项目资助(2009CB219608)；国家油气重大专项资助(2009ZX05038)