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

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

0 引 言

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

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

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

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

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

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

步驟1 查找點(diǎn)集橫縱坐標(biāo)上四個(gè)方向的極值點(diǎn)，當(dāng)各方向上含有多個(gè)極值點(diǎn)時(shí)任選一個(gè)，再將四個(gè)極值點(diǎn)進(jìn)行有向連接，生成四個(gè)各有向線段PL→PT、PR→PT、PL→PB、PR→PB;

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

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

圖1 近似的粗凸包對(duì)平面點(diǎn)集的劃分

3 算法的加速效率分析

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

圖2 子集凸殼頂點(diǎn)生成過程

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

4 結(jié)束語

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

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

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

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

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