基于金字塔凸殼算法的初始凸包快速優(yōu)化算法①

張忠武，周 宇，孟祥華，肖 永

(佳木斯大學建筑工程學院，黑龍江 佳木斯154007)

0 引 言

凸包作為計算幾何研究當中重點解決的問題之一，當前許多理論問題與實際問題都需要凸包作為重要的解決工具.如地理信息系統(tǒng)中進行區(qū)裁剪、洪水淹沒區(qū)域范圍確定等應用都將應用到凸包算法.因此凸殼問題特別是平面點集的凸殼更加得到學術界的重視與關注.凸包問題主要是獲取點集的最外圍頂點，但一般情況下凸包頂點只是海量數(shù)據(jù)點集的極小一部分，凸殼內(nèi)部包含了大量對凸殼生成無用的非凸殼頂點.所以可采用盡可能多刪除不包含在凸殼邊界上的非凸殼頂點的方法，減少數(shù)據(jù)點集數(shù)量進而提升凸殼算法的執(zhí)行效率，這種方法被稱為快速凸包技術［1］.Floyd 四邊形法以及余翔宇編寫的八邊形法就是基于快速凸包技術所提出的凸殼算法，兩種算法都是將海量數(shù)點集預先進行處理，剔除不能作為凸殼頂點的凸殼內(nèi)點［2］.從理論上來說快速優(yōu)化技術不能降低凸殼算法的時間復雜度，可是實際當中數(shù)據(jù)大多呈現(xiàn)正態(tài)分布，多數(shù)情況下快速優(yōu)化算法對提升實際的執(zhí)行效率有很大幫助.結合傳統(tǒng)的凸包算法提出了金字塔凸殼算法，其算法步驟與特點適合將快速優(yōu)化技術結合進來.本文將快速優(yōu)化算法改造成適應金字塔算法的初始近似凸殼算法，便于其在金字塔凸殼算法中實現(xiàn)，降低平面點集中非凸殼頂點數(shù)量，提升整體算法實際運行效率.

1 初始近似凸殼算法的工作原理

初始近似凸殼算法是基于傳統(tǒng)快速凸包技術改進而來的，其工作原理同樣是用最少的時間代價事先剔除不能作為頂點的盡可能多的凸殼內(nèi)點，從而達到提升金字塔算法的實際時間效率.初始近似凸殼算法的基本思想是首先在點集S 中查找獲取橫坐標數(shù)值最大、最小與縱坐標數(shù)值最大、最小的4 個方向的極值點，再將4 個極值點連接起來構成最小外接矩形PLPBPRPT.如果橫縱坐標軸方向上的極值點不只4 個，可取各自方向的任意點作為最值點.這對后期使用金字塔凸殼算法無影響，這源自于金字塔凸殼算法的基本思想［3］.至此已將平面離散數(shù)據(jù)點集S 劃分成五部分:Ⅰ，Ⅱ，Ⅲ，Ⅳ，Ⅴ，見圖1.點集Ⅴ所含數(shù)據(jù)點一定是非凸殼頂點，不可能用于生成凸包的凸殼頂點;另外點集Ⅰ，Ⅱ，Ⅲ，Ⅳ它們彼此之間無交叉數(shù)據(jù)點相互獨立，每個點集上的數(shù)據(jù)點能否作為凸殼頂點都由各自點集中點的位置決定，和其他點集中的數(shù)據(jù)點無關聯(lián)，同時各點集中的凸殼頂點必是整個點集的頂點，為此這四個點集的凸殼頂點獲取方法相同，可以采用金字塔算法尋找四個點集的凸殼頂點，最后將這些凸殼頂點順次連接成所求得整個點集的凸包.

2 初始近似凸殼算法的實現(xiàn)

遍歷點集中所有點查找橫縱坐標四個方向相應的極值點，連接四個方向上極值生成4 條有向線段PL→PT、PR→PT、PL→PB、PR→PB將平面數(shù)據(jù)點集S 劃分成五個區(qū)域［4］.然后根據(jù)判斷點線位置關系的行列式值大小判斷平面數(shù)據(jù)點集中所有點歸屬哪個子點集，具體判斷方法如下:逐個選取平面數(shù)據(jù)點集中的點進行判斷，若點位于有向線段PL→PT左側，則該點屬于點集Ⅰ;若點位于有向線段PR→PT右側，則該點屬于點集Ⅱ;若點位于有向線段PL→PB右側，則判定該點歸屬于點集Ⅲ;若點位于有向線段PR→PB左側，則點將作為點集Ⅳ中的點;否則，該點屬于點集Ⅴ.當判定所有點歸屬之后，分別只對Ⅰ、Ⅱ、Ⅲ、Ⅳ點集中的數(shù)據(jù)點采用金字塔算法求出相應各子集的凸殼頂點，之后再將各子集的凸殼頂點順次連接生成整個平面數(shù)據(jù)點集的凸殼.具體步驟如下:

表1 初始近似凸殼算與金字塔算法相結合的測試數(shù)據(jù)

步驟1 查找點集橫縱坐標上四個方向的極值點，當各方向上含有多個極值點時任選一個，再將四個極值點進行有向連接，生成四個各有向線段PL→PT、PR→PT、PL→PB、PR→PB;

步驟2 循環(huán)判定點集中各點與各條有向線段的位置關系，進而確定該點屬于Ⅰ、Ⅱ、Ⅲ、Ⅳ和Ⅴ哪個子集;

步驟3 對Ⅰ、Ⅱ、Ⅲ、Ⅳ每個子集中的點，分別采用金字塔凸殼算法查找出各自子集中的凸包頂點，見圖2，再將其將順次連接生成最終凸包;

圖1 近似的粗凸包對平面點集的劃分

3 算法的加速效率分析

根據(jù)對初始近似凸殼算法實現(xiàn)步驟進行分析可知，步驟1 與步驟2 分別需要進行n 次的循環(huán)，時間復雜度為(n)，所以初始近似凸殼算法加速優(yōu)化效率的好壞主要取決于刪除非凸殼頂點后，平面數(shù)據(jù)點集的規(guī)模與凸殼頂點個數(shù)，其中頂點個數(shù)是不變的，因此主要取決于點集規(guī)模.在步驟3 中各點集都采用金字塔算法，若剔除后點集規(guī)模為m、頂點數(shù)為k，步驟3 的時間復雜度為O(1/4km).為驗證初始近似凸殼算法的加速優(yōu)化效率，筆者進行大量實驗，具體實驗數(shù)據(jù)見表1.對表1 的實驗數(shù)據(jù)分析可知，初始近似凸殼算法提升金字塔凸殼算法的執(zhí)行效率14 ～25 倍，同時凸包內(nèi)點越集中、越密集時，其加速優(yōu)化效率越明顯.

圖2 子集凸殼頂點生成過程

初始近似凸殼算法加速效率取決于點集劃分時，點集V 中含有多少不參與凸殼頂點判斷的點的數(shù)據(jù)量.為提升初始近似凸殼算法的加速優(yōu)化效率筆者還采用余翔宇編寫的八邊形法凸包快速算法，由八個極值點構成的凸八邊形作為點集近似凸包，目的是將更多點集劃分到凸殼內(nèi)點集中提升初始近似凸殼算法的加速優(yōu)化效率.但是實際試驗結果證明整個算法的運行效率沒有明顯提升，實驗數(shù)據(jù)見表2.通過分析得知其原因在于平面點集中多數(shù)呈現(xiàn)正態(tài)分布內(nèi)點多集中在中央，所以采用八邊形和四邊形作為初始粗凸包對提高算法執(zhí)行效率區(qū)別不大.并且在步驟1 和步驟2 當中增加了判斷比較次數(shù)降低了執(zhí)行效率，所以初始近似凸殼算法和金字塔算法相結合時，不是近似凸包的邊數(shù)越多執(zhí)行效率越好，而是由前面論述凸四邊形作為初始近似粗凸包效果最佳.

4 結束語

本文結合金字塔凸殼算法和Floyd 四邊形法快速算法的特點，提出改造一種快速凸殼算法(初始近似凸殼算法).改造之后的初始近似凸殼算法根據(jù)其自身特點，它歸屬于靜態(tài)加速算法，所以該加速優(yōu)化算法只需在初始階段用很少的時間代價刪除平面數(shù)據(jù)點集中的凸殼內(nèi)點，即可大幅提升整個凸殼算法的執(zhí)行效率.通過試驗結果分析得出初始近似凸殼算法在選定初始粗凸包時，并不是粗凸包邊數(shù)越多執(zhí)行效率越佳，恰相反初始粗凸包選擇四邊形執(zhí)行效果最佳.

［1］ 余翔宇，孫洪，余志雄.改進的二維點集凸包快速求取方法［J］.武漢理工大學學報，2005，27(10):81－83.

［2］ 吳克勤，楊冠杰.空間點集卷包裹算法的優(yōu)化實現(xiàn)［J］.青島海洋大學學報，2003，33(4):627－633.

［3］ 張忠武，吳信才.平面海量散亂點集凸殼算法［J］.計算機工程，2009，35(9):43－45，48.

［4］ 金文華，何濤等.基于有序簡單多邊形的平面點集凸包快速求取算法［J］.計算機學報，1998，21(6):533－539.