改進的三維點集凸包求取算法

張　飛　謝步瀛　閆星宇　劉　政

摘 要：為提高三維點集凸包的求取效率，提出充分利用凸包極值點和性質(zhì)改進的三維點集凸包求取算法.首先，求出三維點集中的極值點，并由它們形成初步凸包；其次，根據(jù)初步凸包與點的位置關(guān)系，排除其內(nèi)部點；最后，依次考察其外部點，求出符合要求的點集、棱邊集和面集，并對凸包進行擴展，得到凸包的點集、棱邊集和面集.與普通算法進行時間的復(fù)雜度分析比較及實驗表明，該算法效率較高.

關(guān)鍵詞：三維點集；凸包；極值點

中圖分類號：TP212.12；O241.82

文獻標志碼：A

Improved algorithm on determining convex hull of 3D point set

ZHANG Fei，XIE Buying，YAN Xingyu，LIU Zheng

(College of Civil Eng.，Tongji Univ.，Shanghai 200092，China)

Abstract：To improve the computation efficiency of convex hull of 3D point set，an improved algorithm on determining convex hull of 3D point set is proposed by making full use of the extreme points and the character of the convex hull. Firstly，the extreme points in 3D point set are obtained to make up of the initial convex hull. Secondly，the internal points of the convex hull are eliminated according to the position relationship between the initial convex hull and the points. Finally，the external points are examined in turn，the point set，line set and face set that meet the requirements are acquired，and the convex hull is expanded to obtain the final point set，line set and face set of the convex hull. The comparison of time complexity analysis with normal algorithms and the experiments indicate that the algorithm has higher efficiency.

Key words：3D point set；convex hull；extreme point

0 引 言

點集凸包問題是計算幾何學(xué)中基本、常見的問題，通?？梢苑譃槎S凸包和三維凸包.[1]二維凸包被廣泛應(yīng)用于模式識別、圖像處理和設(shè)計自動化等領(lǐng)域[2]；三維凸包被廣泛應(yīng)用于計算機仿真、建筑體建模、衛(wèi)星通信和無線電廣播等領(lǐng)域[3].二維凸包算法相對比較簡單、成熟，已有很多研究成果.隨著計算機軟件和硬件技術(shù)的發(fā)展，處理三維的問題越來越多，有必要進一步研究三維凸包算法.本文在現(xiàn)有二維和三維凸包算法的基礎(chǔ)上，提出1種改進的三維點集凸包求取算法.

自20世紀70年代以來，不少學(xué)者提出有關(guān)點集凸包的算法，較為經(jīng)典的有卷包裹法、格雷厄姆法、分治法、增量法以及周培德在文獻[1]中提出的Z3—1和Z3—2算法.在這些算法中，卷包裹法、分治法、增量法以及Z3—2算法能夠推廣到三維.同樣，也有很多二維算法不能推廣到三維，比如格雷厄姆法和文獻[4]提出的算法.

在絕大多數(shù)情況下，二維凸包和三維凸包由點集中的部分點構(gòu)成，其余點則在凸包內(nèi)部.所以，點集中的點可分為凸包頂點和內(nèi)部點，因而可以考慮利用一些特殊點(如極值點)先構(gòu)成凸包大體形狀，再排除內(nèi)部點中的部分點，以減少點的數(shù)目來提高算法效率，這就是快速凸包技術(shù)[5].這種思想顯然也適用于三維點集凸包算法.

在快速凸包技術(shù)的基礎(chǔ)上，本文給出1種改進的凸包求取算法.與傳統(tǒng)快速凸包算法相比，本文算法考慮采用更多的極值點，更充分地利用極值點性質(zhì)，縮小點的搜索范圍，提高算法效率.

1 定義及性質(zhì)

定義1 凸包.即凸包多面體，把多面體的任何1個面無限延展，其他面都在這個延伸面的同一側(cè).[1，6]文中的點集凸包是指包含點集中所有點的最小凸多面體.凸包的面均由三角形組成，即使真實的面由多邊形組成，這些多邊形也均被分割成三角形.

定義2 一維極值點.在三維點集中，若只考慮點的3個坐標中的1個坐標并求取其最大值或最小值，所求得的這些點稱為一維極值點.如果最大極值點和最小極值點都不止1個，則所有最大極值點在同一平面，所有最小極值點也在同一平面內(nèi).

定義3 二維極值點.在三維點集中，如果把所有點都投影到1個坐標平面上(如xOy平面，yOz平面，zOx平面)，然后在平面上求取極值點，稱這些點為二維極值點.現(xiàn)以投影到xOy平面為例定義二維極值點.在平面點集中，分別稱具有最小和最大x坐標值的點構(gòu)成的子集為X_min子集和X_max子集；分別稱具有最小和最大y坐標值的點構(gòu)成的子集為Y_min子集和Y_max子集.在X_min子集中，稱對應(yīng)y坐標的最小的點為左下點，稱對應(yīng)y坐標最大的點為左上點；在X_max子集中，稱對應(yīng)y坐標的最小的點為右下點，稱對應(yīng)x坐標最大的點為右上點；在Y_min子集中，稱對應(yīng)x坐標最小的點為下左點，稱對應(yīng)x坐標最大的點為下右點；在Y_max子集中，稱對應(yīng)x坐標的最小的點為上左點，稱對應(yīng)x坐標最大的點為上右點.

定義4 極值點.包括一維極值點和二維極值點.在現(xiàn)實情況下，某點可能既是一維極值點也是二維極值點.在算法應(yīng)用的過程中并不嚴格區(qū)分.

性質(zhì)1 空間中給定的若干個點的凸包是唯一的，且凸包的頂點必須是原給定點集中的點.[3]

性質(zhì)2 極值點必為凸包的頂點中的點.

性質(zhì)3 在三維點集中，必存在一維極值點，且至少有1個.如果只有1個一維極值點，則凸包為平面，這種情況將不形成凸包.所以，構(gòu)成凸包的點集中，至少有2個一維極值點.

性質(zhì)4 在三維點集中，必存在二維極值點，且至少有2個.當且僅當為2個極值點時，在投影平面內(nèi)查找離由這2個點構(gòu)成的直線最遠的點作為極值點.如果不存在，則點集不構(gòu)成凸包.這樣，至少有3個極值點，最多8個極值點存在.即三維點集中，二維極值點可以構(gòu)成1個平面或者空間凸環(huán).文獻[4]中給出的在二維情況下的證明，也適用于三維點集中二維極值點的情況.

推論 由性質(zhì)3和性質(zhì)4，在三維點集中，只要存在凸包，即所有點都不在同一平面上，由極值點可以構(gòu)成1個初步凸包.

2 算法思路描述

求取三維點集的凸包，一般要求求出凸包的頂點集、棱邊集以及面集.當然，在3個集合中，頂點集和面集是必需的，棱邊集可以由面集直接推出.

算法的總體思路是：通過依次考察點集中的點，找出極值點，利用極值點快速形成初步凸包.初步凸包把原點集中的點分為初步凸包上點、外部點和內(nèi)部點3個部分.外部點可能在凸包上，而內(nèi)部點一定不在凸包上.算法的第2步則是刪除內(nèi)部點.第3步依次進行考察外部點，不斷擴展初步凸包，最終形成所要得到的凸包.在擴展初步凸包的過程中，將待考察的點依次與上一步擴展凸包中的棱邊構(gòu)成面，并用極值點和上一步擴展凸包中的頂點集中的點判斷該面是否應(yīng)加入新的擴展凸包中，這樣就可以找到所有應(yīng)加入新擴展凸包中的面.再利用該待加入點和極值點驗證原擴展凸包中的面，排除不滿足新擴展凸包的所有的點、棱邊和面.當考察完畢所有外部點時就可以得到最終所要求得凸包的點集、棱邊集和面集.

2.1 算法主體流程

算法主體流程見圖1.

圖 1 算法主體流程

2.2 算法具體步驟

步驟1 求極值點并形成初步凸包，分為4個小步驟進行.

(1)依次考察點集中點的z坐標，分別求出1個最大和1個最小的一維極值點，并把點號保存在極值點集鏈表utdot中.

(2)依次考察點集中點的x坐標和y坐標，按照左下點、下左點、下右點、右下點、右上點、上右點、上左點和左上點的順序依次求出所有存在的二維極值點，并將點號保存到極值點集鏈表utdot中.

(3)按照求取二維極值點的順序，依次連接各點構(gòu)成1個空間環(huán)；然后將z軸方向上的極值點分別與環(huán)中的點連接，構(gòu)成基于三角形初步凸包.

(4)在步驟1的第(3)步中，把依次連接的邊保存到棱邊集鏈表llist中，把依次連接3點構(gòu)成的面保存到面集鏈表alist中.同時，初始化頂點集鏈表endplist后，繼續(xù)下一步.

步驟2 刪除初步凸包內(nèi)部點，又分為2個小步驟進行.

(1)依次考察點集中的點，從該點出發(fā)引1條平行于x軸的射線，如果該射線與初步凸包的面不相交或有2個交點，則該點在初步凸包的外部；如果只有1個交點，則該點在初步凸包的內(nèi)部.如果與初步凸包的棱邊、面或頂點相交，則改平行于y軸或z軸的射線，然后再按照前面的方法判定.如果3個方向的射線均與初步凸包的頂點或棱邊相交，則該點在初步凸包的內(nèi)部.[1]

(2)在步驟2的第(1)步中，把初步凸包外部點的點號保存到點集鏈表plist中.繼續(xù)下一步.

步驟3 從點集鏈表plist中依次取出點pp，如果鏈表plist中點都取完，則執(zhí)行步驟5，否則繼續(xù)下一步.

步驟4 共有10個小步驟.依次從棱邊集鏈表llist中取出棱邊lp，如果鏈表llist中的棱邊都取完，則執(zhí)行步驟4中第(5)步，否則繼續(xù)步驟4中第(1)步.

(1)由步驟3中的點pp和步驟4中的棱邊lp構(gòu)成1個面，依次用極值點集utdot中的點來判斷該面的性質(zhì).如果所有極值點都在該面的同一側(cè)，則繼續(xù)下一步，否則退出本輪循環(huán)，執(zhí)行步驟4.

(2)從頂點集鏈表endplist中依次取出點來判斷該面的性質(zhì)，如果所有點都在該面的同一側(cè)，則繼續(xù)下一步，否則退出本輪循環(huán)，執(zhí)行步驟4.

(3)把步驟4的第(1)和(2)步中滿足要求的面加入到面集鏈表alisttemp中，與該面相應(yīng)的兩條棱邊加入到棱邊集鏈表llisttemp中.

(4)繼續(xù)步驟4.

(5)若alisttemp為空，執(zhí)行步驟4中第(10)步，否則執(zhí)行下一步.

(6)依次從擴展凸包面集alist中取出面a，用點pp和極值點集utdot中不為該面頂點的1點putdot進行判斷，如果點pp和點putdot在面a的異側(cè)，則把該面從alist中刪除，并且加入到待刪除面集鏈表alistdle中，否則不作任何處理，繼續(xù)步驟4中第(6)步.當alist中的面都取完時，把alisttemp添加到alist中，執(zhí)行下一步.

(7)依次考察面集alistdle中的面，如果有3個或者以上的面相交1點，則把該點加入到待處理點集鏈表plistdle中，否則繼續(xù)步驟4中第(7)步.當面集alistdle中所有點面都考察完畢時，執(zhí)行下一步.

(8)依次考察點集plistdle中的點，如果該點在面集alist的頂點中不存在，則從頂點集endplist中刪除該點，否則不作任何處理.當plistdle中所有的點都考察完畢時，把點pp添加到endplist中，執(zhí)行下一步.

(9)依次考察面集alistdle中的面，如果有2個面相交于1條棱邊，則從棱邊集llist中刪除該棱邊.當alistdle中的面全部考察完畢時，把llisttemp添加到llist中，執(zhí)行下一步.

(10)繼續(xù)步驟3.

步驟5 把極值點集鏈表utdot合并到鏈表plist中.最終凸包的點集為鏈表plist，棱邊集為鏈表llist，面集為鏈表alist.算法完成.

2.3 算法改進方法

上述算法利用z軸方向的2個一維極值點和xy平面上最多8個二維極值點形成初步凸包.根據(jù)定義3，x，y和z軸方向的一維極值點均分別在2個平面上.根據(jù)極值點的性質(zhì)，所有一維極值點均為凸包頂點.所以改進的方法是：求出所有一維極值點并由其構(gòu)成1個新初步凸包，這個新初步凸包大于等于上述算法中的初步凸包.新凸包可以排除更多的內(nèi)部點，從而減少步驟3和4中的判斷次數(shù)，提高算法效率.

2.4 時間復(fù)雜度分析

文獻[7]證明凸包算法的時間復(fù)雜度下限為o(n logn)，該結(jié)論也適用于三維凸包算法[1].常見的三維凸包算法中，卷包裹法和文獻[1]中Z3—8算法的時間復(fù)雜度為o(n²)[1，6]；分治法和增量法為o(n log n)[1].經(jīng)典的普通算法是利用定義1的性質(zhì)，通過3點構(gòu)成的面，然后用點集中的點是否都在該面同一側(cè)的方法來判斷該面是否為凸包的面.當考察完畢點集中任意3點所構(gòu)成的面時，就可以得到凸包的所有面，進而求出凸包.其算法的復(fù)雜度為o(n³).

本文算法的時間復(fù)雜度分析如下：步驟1中，查找極值點耗時o(n)；步驟2中，刪除內(nèi)部點的復(fù)雜度為o(n)；步驟3和4構(gòu)成1個用外部點擴展初步凸包的循環(huán).外部點的數(shù)目與點集的數(shù)目相關(guān)，故循環(huán)外部的復(fù)雜度為o(n).循環(huán)內(nèi)部中步驟4的第(1)～(4)步求頂點與棱邊構(gòu)成的面，并用擴展凸包頂點集中的點判斷面的性質(zhì)，其復(fù)雜度與擴展凸包中點的數(shù)目和棱邊的數(shù)目相關(guān).由于擴展凸包中點的數(shù)目相對于點集中點的數(shù)目和棱邊的數(shù)目非常少，也可以認為是常數(shù).所以，一般情況下其計算的復(fù)雜度為o(1).由性質(zhì)和推理知，極值點可以構(gòu)成初步凸包，進而可以排除內(nèi)部點.所以，即使在最壞情況下，其時間復(fù)雜度也不會達到o(n)，可以認為其時間復(fù)雜度接近o(log n).步驟4的第(5)～(10)步的時間復(fù)雜度為o(1)，所以步驟3和4的最壞時間復(fù)雜度接近o(n log n).步驟5耗時可以忽略不計.所以，整個算法的最壞時間復(fù)雜度接近于o(n log n)，即接近于時間復(fù)雜度的下限.

3 實驗分析

實驗所用計算機的CPU為AMD 2500+，內(nèi)存為512 MB.在VC++6.0中的MFC編程環(huán)境中，分別實現(xiàn)普通算法和改進算法.圖2給出點集中點的數(shù)目為500個時的三維凸包計算結(jié)果.分別對普通算法和改進算法求三維點集凸包進行程序?qū)嶒?對不同容量(小于104)的點集分別進行100次實驗，然后求出平均消耗的時間列于表1和圖3.同時，表1對普通算法和改進算法平均消耗時間的比值進行計算.圖3中橫軸表示點集中的數(shù)目，縱軸表示計算點集凸包運行所需要的平均消耗時間.

圖 2 500個點的凸包計算結(jié)果

圖 3 實驗比較

從表1和圖3可見，隨著點集容量的增大，改進算法的優(yōu)勢越發(fā)明顯.普通算法與改進算法的消耗時間比隨著點集容量的增大而增大.在第2.4節(jié)中普通算法和改進算法的時間復(fù)雜度分別為o(n³)和o(n log n)，它們之間的比值為o(n²/log n)，與表1中的比值相符合，從而證明理論分析與實驗分析一致.

4 結(jié) 論

從改進算法與普通算法的比較中可見，對于求102數(shù)量級的三維點集凸包，普通方法也能提供比較滿意的求取時間，但當點集容量達到103時，普通算法就不能滿足要求.改進算法可以快速求取大量三維點集的凸包，不僅在時間上取得較大突破，而且充分利用極值點在凸包上以及凸包的性質(zhì)，為算法優(yōu)化提供新的思路.

另外，改進算法效率高的原因還在于：(1)充分利用極值點，形成最大可能的初步凸包，排除初步凸包內(nèi)部點，減少點的判斷次數(shù)；(2)在判斷面的性質(zhì)中，優(yōu)先用極值點進行判斷，利用極值點的性質(zhì)，可以很快得出該面的性質(zhì)，減少判斷的工作量；(3)在求取過程中，每次向擴展凸包中添加1個點，都構(gòu)成1個新的擴展凸包，充分利用上一步中求取的成果，大大減少后面的計算工作量.

參考文獻：

[1] 周培德. 計算幾何——算法分析與設(shè)計[M]. 2版. 北京：清華大學(xué)出版社，2005：100-135.

[2] ROURKE O J. Computational geometry in C[M]. 2nd ed. Cambridge：Cambridge Univ Press，1998：73-78.

[3] 夏松，朱宜萱，杜志強. 一種新的空間凸多面體的生成算法[J]. 測繪通報，2006(1)：21-23.

[4] 余翔宇，孫洪，余志雄. 改進的二維點集凸包快速求取方法[J]. 武漢理工大學(xué)學(xué)報，2005，27(10)：81-83.

[5] 蔣紅斐. 平面點集凸包快速構(gòu)建算法的研究[J]. 計算機工程與應(yīng)用，2002，38(20)：48-49.

[6] 吳克勤，楊冠杰. 空間點集卷包裹算法的優(yōu)化實現(xiàn)[J]. 青島海洋大學(xué)學(xué)報：自然科學(xué)版，2003，33(4)：627-633.

[7] YAO A C C. A lower bound to finding convex hulls[J]. J ACM，1981，28(4)：780-787.

(編輯 廖粵新)