计算平面点集凸包的实时插入算法

刘 萍

(甘肃民族师范学院，甘肃 合作 747000)

0 引言

本文讨论平面点集的凸包的实时插入算法。假设平面点集S的点以数据流的方式进入系统，如果对于已经进入系统的n个点的子集计算出它的凸包H，新的点P进入系统时对H更新，更新的结果可能删除P，或将P插入H，或将P插入H且删除H的一些点，称这种更新的算法为实时插入算法。本文提出的实时插入算法分为前向算法和后向算法。对于前向算法和后向算法，用算法所需的检测次数为单位计算实时插入算法的复杂度。设S的点的个数是N，则计算凸包的实时算法所需的检测次数小于3N，这个上界比起渐近复杂度更精确。

1 相关算法

1.1 凸包算法

S的凸包(或称凸壳，convex hull)，是指包含S的所有凸集的交，或者说包含S的最小的凸集。凸包的计算起源于纯几何图形的研究。由于在实际应用中与几何图形有关的问题大量出现，如计算机图形学、计算机辅助设计CAD、建筑学等，从20世纪70年代起，利用计算机处理几何图形，越来越受到计算机科学界的重视。M.L.Shamos的博士论文[1]总结了上世纪70年代计算机科学家关于几何图形的算法研究，其中关于凸包的研究占据重要的位置。

平面有限点集S的凸包计算问题包括两个方面:找出S的凸包多边形的所有顶点(称为S的极点);将凸包多边形的顶点按序(如逆时针顺序)排列。找出极点的最简单方法如下:

设P是点，如果存在S的不共线的3个点A、B、C，使得 P在△ABC的内部3个角∠APB、∠BPC、∠CPA的和为2π，则P为S的内点;否则P是S的极点。因此，检测的次数为O(n3)，其中n是S的点的个数。这样，要找出S的所有极点的检测次数为O(n4)。因为平面有限点集S的极点的平均个数是O(logn)[2]，O(n4)的近似复杂度实在太大。在文献[3]中，关于凸包计算的近似复杂度为O(n2)，这个结论使得凸包问题的研究向前跨越了很大的一步。实质性的研究出现在1972年Graham的论文[4]，给出的复杂度为 O(nlogn)。以后，文献[5]和文献[6]，分别给出类似的结果(复杂度为 O(nlogn)和 O(nm)，m是极点的个数)。

1.2 实时算法

文献[7]和文献[8]提出凸包问题的实时算法。在计算平面有限点集S的凸包的过程中，S的点经常以数据流的方式进入系统，而不是整个出现在系统中。以数据流的方式进入系统的算法一般称为实时算法。凸包问题的实时算法规定:当S的第i个点p进入系统时，先前进入系统的i－1个点的子集的凸包Hi－1已经计算出。实时算法需要计算 Hi－1∪{p}的凸包Hi。有3种可能:(1)p是Hi－1的内点，因此Hi=Hi－1;(2)p 是 Hi－1的极点但不删除 Hi－1的其它极点，因此 Hi=Hi－1∪{p};(3)p 是 Hi－1的极点且删除Hi－1的某些极点。文献[7]和文献[8]的算法都是将Hi－1的点排成逆时针的顺序，存储在平衡树(如AVL树)中。在该树中查找p在Hi－1的点的顺序中的位置，通过各自的算法计算p和Hi－1的关系，都证明了计算时间为O(log m)，其中m是Hi－1的点的个数。

2 插入算法

2.1 Graham扫描算法

设S是平面上有n个点的点集，文献[4]选取S中的3个不共线的点组成的三角形的重心P0作为基点。基点P0的选取可以在O(n)时间完成。Efron在文献[9]中证明，如果S是绝对连续分布，则任选三点必以概率1保证三点不共线，因此，上述时间为O(1)。P0与S的点P组成的向量P0P与正X轴的夹角记为θ(P)，将 S的 P按 θ(P)的升序排列为 P1，…，Pn。在文献[10]和文献[11]中基点选取 S中纵坐标最小的点，这样做的好处是上述的夹角不超过π，但对于下文的插入算法，不取这种点。令 P0=Pn+1，Graham扫描算法从 i=0起，计算3个点 Pi、Pi+1、Pi+2的旋转顺序，如果为左旋，则计算 Pi+1、Pi+2、Pi+3，否则丢弃 Pi+1，退回计算 Pi－1、Pi+2、Pi+3。算法结束时，输出按逆时针方向排序的凸包顶点。扫描算法的检测次数不超过2n，θ(P)的排列时间为 O(nlogn)。

2.2 简单的结论

设A、B、C是平面上的3个点，对A、B、C所作的检测是指:如果A、B、C按逆时针(顺时针)方向排列，则称 A、B、C为左(右)旋。设 A、B、C的坐标是(xi，yi)(i=1，2，3)，则 A、B、C 左旋(右旋)当且仅当(x2－x1)(y3－y1)－(x3－x1)(y2－y1)＞0(＜0)。设A、B是直线L上两点，点C、D称为在L的同侧，如果A、B、C和A、B、D同时为左旋或者同时为右旋。下面的结论是显然的。

引理 设S是平面点集。(1)设P∈S。P是S的极点当且仅当存在过P的直线L使得S的点(除去P)都在L的同侧。(2)若P、R是S的极点，则S的点(除去P，R)都在L的同侧。

2.3 插入算法

设S是平面有限点集，H是按Graham算法计算得到的S的凸包，按逆时针排序，H={P1，…，Pn}，P0是基点。设Q是插入点，S1=H∪{Q，P0}，H1是S1的凸包。计算H1的插入算法如下。

输入 凸包H，插入点Q。

输出 S1=H∪{Q，P0}的凸包H1。

Step1 在O(logn)时间内找到i使得θ(Pi)≤θ(Q)＜θ(Pi+1)。

Step2 如果PiQPi+1右旋，H1=H，算法中止。

Step3 如果PiQPi+1左旋，H1←H∪{Q}，

Step3.1 前向算法:

(1)k=i;

(2)若Pk－1PkQ左旋，前向算法终止;

(3)若 Pk－1PkQ 右旋，H1←H1－{Pk}，k －－ ，返回Step2。

Step3.2 后向算法:

(1)k=i+1;

(2)若QPkPk+1左旋，后向算法终止;

(3)若 QPkPk+1右旋，H1←H1－{Pk}，k++，返回Step2。

Step4 输出H1。

2.4 插入算法正确性的证明

设H1是2.3节插入算法输出的点集，需要证明H1是S1的凸包。根据算法，如果PiQPi+1右旋，则Q和P0在直线PiPi+1的同侧，因此Q是S1的内点，所以H1=H。否则，如果PiQPi+1左旋，将Q插入H，执行前向算法和后向算法。若前向算法在k=h终止，后向算法在k=m中止，则Ph+1，…，Pi以及Pi+1，…，Pm－1都不是极点，从 H1中删除，H1={P1…PhQPm…Pn}。因为H是凸包，因此所有PsPs+1Ps+2(s=0，…，h－2，m，…，n－1)都是左旋，因此，所有 Pj(j=1，…，h，m，…，n)都是极点。剩下只需证明Q是极点。因为PiQPi+1左旋，因此Q和P0在直线PiPi+1的两侧，而P0和H的点在直线PiPi+1的同侧。过Q作直线L平行PiPi+1，则H1的点(除去Q)都在L的同侧，因此Q是极点。

2.5 插入算法的效率

在2.3节的算法中，关于左右旋的检测次数最好的情形是一次(Q不是极点)，或3次(Q是极点且不删除其他点)，最坏的情形是n+1次，即Q是极点且删除所有Pi(i=2，…，n－1)。如果删除的点越多，剩下的点也就越少，有利于下次插入。因此，提出用插入算法来计算凸包。

3 凸包计算的实时插入算法

设S是平面上有N个点的集合，S的点顺序进入系统。下面的定理给出应用实时插入算法所需要的检测次数的上界。

定理 计算平面点集S的凸包实时插入算法所需的检测次数小于3N(N是S的点的个数)。

证明 首先计算进入系统的t个点(t是较小的数)的子集的凸包H。计算H的时间是和N无关的常数C。以后进入系统的点按2.3节的算法更新H。设H的点的个数是n。当第i个点P进入系统，需要作一次检测。如果P是内点，H的点的个数不变，转向下一个点。如果P不是内点，进入系统后利用前向算法删除H的h个点，检测次数为h+1，利用后向算法删除H的m个点，检测次数为m+1(h，m≥0)，则需要完成的检测次数为u=1+h+1+m+1=h+m+3。因为H的点被删除h+m个，因此H的点的个数为n－h－m。当S的k个点进入系统，分别检测u1，…，uk次，ui=hi+mi+3。则 k个点进入系统的检测次数T=u1+…+uk，则H的点被删除的个数是T－3k。因此H的个数为n－T+3k。如果S有N个点，则k=N－n。因为H的点的个数大于0，因此n－T+3(N－n)＞0，即T＜3N。这就保证，利用实时算法计算有N个点的平面点集S的凸包所需的检测次数小于3N。

4 结束语

凸包计算的研究有着广泛的应用背景。本文在Graham扫描算法的基础上，提出前向算法和后向算法。一般的凸包计算的复杂度如在第1节中指出的结论都是渐近公式，如O(NlogN)和O(mN)(N是集合S的元素个数，m是凸包的点的个数)。在本文的结论中，得到精确的上界3N。此外，在本文的算法中，不需要Graham扫描算法中必须的排序工作(时间O(NlogN))。因为在算法的第1步中，为了找到i的位置所需的时间只是O(logm)。

[1]Shamos M I.Computational Geometry[D].Department of Computer Science，Yale University，1978.

[2]Bentley J L，Kung H T，Schkolnick M，et al.On the average number of maxima in a set of vertors and applications[J].Journal of the Association for Computing Machinery，1978，25(4):536-543.

[3]Chand D R，Kapur S S.An algorithm for convex polytopes[J].Journal of the ACM，1970，17(1):78-86.

[4]Graham R L.An efficient algorithm for determining the convex hull of a finite planar set[J].Information Processing Letter，1972，1(4):132-133.

[5]Javis R A.On the identification of the convex hull of a finite set of points in the plane[J].Information Processing Letter，1973，2(1):18-21.

[6]Shamos M I.Germetric complexity[C]//Proceedings of the 7th Annual ACM Symposium on Theory of Computing.1975:224-233.

[7]Preparata F T.An optimal real-time algorithm for planar convex hulls[J].Communication of ACM，1979，22(7):402-405.

[8]周之英.平面点集凸壳的实时算法[J].计算机学报，1985，8(2):136-142.

[9]Efron B.The convex hull of a randon set of points[J].Blometrika，1965，52(3):331-343.

[10]霍罗威茨.计算机算法[M].冯博琴，等译.北京:机械工业出版社，2005.

[11]郑宗汉，郑晓明.算法设计与分析[M].北京:清华大学出版社，2005.

[12]Bronnimann H，Iacono J，et al.Space-efficient planar convex hull algorithms[J].Theoretical Computer Science，2004，321(1):25-40.

[13]周培德，付梦印.寻求简单多变形凸壳的线性时间算法[J].计算机工程与科学，2002，24(3):1-2，44.

[14]金文华，何涛，等.基于有序简单多边形的平面点集凸包快速求取算法[J].计算机学报，1998，21(6):533-539.