計算平面點集凸包的實時插入算法

劉 萍

(甘肅民族師范學院，甘肅 合作 747000)

0 引言

本文討論平面點集的凸包的實時插入算法。假設(shè)平面點集S的點以數(shù)據(jù)流的方式進入系統(tǒng)，如果對于已經(jīng)進入系統(tǒng)的n個點的子集計算出它的凸包H，新的點P進入系統(tǒng)時對H更新，更新的結(jié)果可能刪除P，或?qū)插入H，或?qū)插入H且刪除H的一些點，稱這種更新的算法為實時插入算法。本文提出的實時插入算法分為前向算法和后向算法。對于前向算法和后向算法，用算法所需的檢測次數(shù)為單位計算實時插入算法的復雜度。設(shè)S的點的個數(shù)是N，則計算凸包的實時算法所需的檢測次數(shù)小于3N，這個上界比起漸近復雜度更精確。

1 相關(guān)算法

1.1 凸包算法

S的凸包(或稱凸殼，convex hull)，是指包含S的所有凸集的交，或者說包含S的最小的凸集。凸包的計算起源于純幾何圖形的研究。由于在實際應(yīng)用中與幾何圖形有關(guān)的問題大量出現(xiàn)，如計算機圖形學、計算機輔助設(shè)計CAD、建筑學等，從20世紀70年代起，利用計算機處理幾何圖形，越來越受到計算機科學界的重視。M.L.Shamos的博士論文[1]總結(jié)了上世紀70年代計算機科學家關(guān)于幾何圖形的算法研究，其中關(guān)于凸包的研究占據(jù)重要的位置。

平面有限點集S的凸包計算問題包括兩個方面:找出S的凸包多邊形的所有頂點(稱為S的極點);將凸包多邊形的頂點按序(如逆時針順序)排列。找出極點的最簡單方法如下:

設(shè)P是點，如果存在S的不共線的3個點A、B、C，使得 P在△ABC的內(nèi)部3個角∠APB、∠BPC、∠CPA的和為2π，則P為S的內(nèi)點;否則P是S的極點。因此，檢測的次數(shù)為O(n3)，其中n是S的點的個數(shù)。這樣，要找出S的所有極點的檢測次數(shù)為O(n4)。因為平面有限點集S的極點的平均個數(shù)是O(logn)[2]，O(n4)的近似復雜度實在太大。在文獻[3]中，關(guān)于凸包計算的近似復雜度為O(n2)，這個結(jié)論使得凸包問題的研究向前跨越了很大的一步。實質(zhì)性的研究出現(xiàn)在1972年Graham的論文[4]，給出的復雜度為 O(nlogn)。以后，文獻[5]和文獻[6]，分別給出類似的結(jié)果(復雜度為 O(nlogn)和 O(nm)，m是極點的個數(shù))。

1.2 實時算法

文獻[7]和文獻[8]提出凸包問題的實時算法。在計算平面有限點集S的凸包的過程中，S的點經(jīng)常以數(shù)據(jù)流的方式進入系統(tǒng)，而不是整個出現(xiàn)在系統(tǒng)中。以數(shù)據(jù)流的方式進入系統(tǒng)的算法一般稱為實時算法。凸包問題的實時算法規(guī)定:當S的第i個點p進入系統(tǒng)時，先前進入系統(tǒng)的i－1個點的子集的凸包Hi－1已經(jīng)計算出。實時算法需要計算 Hi－1∪{p}的凸包Hi。有3種可能:(1)p是Hi－1的內(nèi)點，因此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的關(guān)系，都證明了計算時間為O(log m)，其中m是Hi－1的點的個數(shù)。

2 插入算法

2.1 Graham掃描算法

設(shè)S是平面上有n個點的點集，文獻[4]選取S中的3個不共線的點組成的三角形的重心P0作為基點?；cP0的選取可以在O(n)時間完成。Efron在文獻[9]中證明，如果S是絕對連續(xù)分布，則任選三點必以概率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的旋轉(zhuǎn)順序，如果為左旋，則計算 Pi+1、Pi+2、Pi+3，否則丟棄 Pi+1，退回計算 Pi－1、Pi+2、Pi+3。算法結(jié)束時，輸出按逆時針方向排序的凸包頂點。掃描算法的檢測次數(shù)不超過2n，θ(P)的排列時間為 O(nlogn)。

2.2 簡單的結(jié)論

設(shè)A、B、C是平面上的3個點，對A、B、C所作的檢測是指:如果A、B、C按逆時針(順時針)方向排列，則稱 A、B、C為左(右)旋。設(shè) A、B、C的坐標是(xi，yi)(i=1，2，3)，則 A、B、C 左旋(右旋)當且僅當(x2－x1)(y3－y1)－(x3－x1)(y2－y1)＞0(＜0)。設(shè)A、B是直線L上兩點，點C、D稱為在L的同側(cè)，如果A、B、C和A、B、D同時為左旋或者同時為右旋。下面的結(jié)論是顯然的。

引理 設(shè)S是平面點集。(1)設(shè)P∈S。P是S的極點當且僅當存在過P的直線L使得S的點(除去P)都在L的同側(cè)。(2)若P、R是S的極點，則S的點(除去P，R)都在L的同側(cè)。

2.3 插入算法

設(shè)S是平面有限點集，H是按Graham算法計算得到的S的凸包，按逆時針排序，H={P1，…，Pn}，P0是基點。設(shè)Q是插入點，S1=H∪{Q，P0}，H1是S1的凸包。計算H1的插入算法如下。

輸入 凸包H，插入點Q。

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

Step1 在O(logn)時間內(nèi)找到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 插入算法正確性的證明

設(shè)H1是2.3節(jié)插入算法輸出的點集，需要證明H1是S1的凸包。根據(jù)算法，如果PiQPi+1右旋，則Q和P0在直線PiPi+1的同側(cè)，因此Q是S1的內(nèi)點，所以H1=H。否則，如果PiQPi+1左旋，將Q插入H，執(zhí)行前向算法和后向算法。若前向算法在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的兩側(cè)，而P0和H的點在直線PiPi+1的同側(cè)。過Q作直線L平行PiPi+1，則H1的點(除去Q)都在L的同側(cè)，因此Q是極點。

2.5 插入算法的效率

在2.3節(jié)的算法中，關(guān)于左右旋的檢測次數(shù)最好的情形是一次(Q不是極點)，或3次(Q是極點且不刪除其他點)，最壞的情形是n+1次，即Q是極點且刪除所有Pi(i=2，…，n－1)。如果刪除的點越多，剩下的點也就越少，有利于下次插入。因此，提出用插入算法來計算凸包。

3 凸包計算的實時插入算法

設(shè)S是平面上有N個點的集合，S的點順序進入系統(tǒng)。下面的定理給出應(yīng)用實時插入算法所需要的檢測次數(shù)的上界。

定理 計算平面點集S的凸包實時插入算法所需的檢測次數(shù)小于3N(N是S的點的個數(shù))。

證明 首先計算進入系統(tǒng)的t個點(t是較小的數(shù))的子集的凸包H。計算H的時間是和N無關(guān)的常數(shù)C。以后進入系統(tǒng)的點按2.3節(jié)的算法更新H。設(shè)H的點的個數(shù)是n。當?shù)趇個點P進入系統(tǒng)，需要作一次檢測。如果P是內(nèi)點，H的點的個數(shù)不變，轉(zhuǎn)向下一個點。如果P不是內(nèi)點，進入系統(tǒng)后利用前向算法刪除H的h個點，檢測次數(shù)為h+1，利用后向算法刪除H的m個點，檢測次數(shù)為m+1(h，m≥0)，則需要完成的檢測次數(shù)為u=1+h+1+m+1=h+m+3。因為H的點被刪除h+m個，因此H的點的個數(shù)為n－h(huán)－m。當S的k個點進入系統(tǒng)，分別檢測u1，…，uk次，ui=hi+mi+3。則 k個點進入系統(tǒng)的檢測次數(shù)T=u1+…+uk，則H的點被刪除的個數(shù)是T－3k。因此H的個數(shù)為n－T+3k。如果S有N個點，則k=N－n。因為H的點的個數(shù)大于0，因此n－T+3(N－n)＞0，即T＜3N。這就保證，利用實時算法計算有N個點的平面點集S的凸包所需的檢測次數(shù)小于3N。

4 結(jié)束語

凸包計算的研究有著廣泛的應(yīng)用背景。本文在Graham掃描算法的基礎(chǔ)上，提出前向算法和后向算法。一般的凸包計算的復雜度如在第1節(jié)中指出的結(jié)論都是漸近公式，如O(NlogN)和O(mN)(N是集合S的元素個數(shù)，m是凸包的點的個數(shù))。在本文的結(jié)論中，得到精確的上界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].馮博琴，等譯.北京:機械工業(yè)出版社，2005.

[11]鄭宗漢，鄭曉明.算法設(shè)計與分析[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.