金字塔凸殼算法的并行化處理①

張忠武， 王文仲， 桂 丹， 周 宇

(1.佳木斯大學(xué)建筑工程學(xué)院，黑龍江佳木斯 154007;2.佳木斯腫瘤結(jié)核醫(yī)院，黑龍江佳木斯 15007))

0 引言

凸殼問(wèn)題是目前實(shí)際應(yīng)用中經(jīng)常要遇到并且需要加以解決的問(wèn)題之一，而且更為重的是，凸殼問(wèn)題是求解當(dāng)前很多實(shí)際問(wèn)題與理論問(wèn)題極為重要的工具.所以凸殼問(wèn)題尤其是平面點(diǎn)集的凸殼計(jì)算更加受到學(xué)術(shù)界的關(guān)注.由于平面凸殼所擁有的問(wèn)題復(fù)雜性和實(shí)際應(yīng)用的重要性，平面凸殼算法受到國(guó)內(nèi)外眾多專家學(xué)的關(guān)注，為此做了許多研究工作來(lái)研究、改進(jìn)平面點(diǎn)集的凸殼算法，目的在于提升凸殼算法的執(zhí)行效率.目前算法比較成熟并廣泛被認(rèn)可的串行凸殼算法有格雷厄姆算法、卷包裹算法，為提高凸殼問(wèn)題的解決速度，又有一些并行的凸殼算法被提出，其中比較突出的是快速凸殼算法、折半分治算法.筆者多年從事計(jì)算幾何方面的研究，在總結(jié)格雷厄姆算法的基礎(chǔ)上，提出了格雷厄姆算法的逆算法，即金字塔凸殼算法.本算法是一種串行算法，因此總體上這種凸殼算法效率還不夠高，時(shí)間復(fù)雜度為O(hn)有進(jìn)一步提升必要.由于金字塔凸殼算法的自身特點(diǎn)，可以將并行思想引進(jìn)來(lái)改進(jìn)本算法.為此，本文提出了執(zhí)行效率更高的基于工作站機(jī)群的金字塔凸殼的并行處理方法.

1 平面點(diǎn)的凸殼定義

為論述和書寫方便平面離散點(diǎn)集以下用S表示，平面點(diǎn)集S的凸殼由CH(S)表示，平面點(diǎn)集S的凸殼邊界將表示為BCH(S).

定義1 在平面坐標(biāo)系下，將點(diǎn)集S當(dāng)中x軸值最小的點(diǎn)即為S的最左點(diǎn)，用PL表示.當(dāng)S中x軸值最小點(diǎn)由多個(gè)時(shí)取y軸坐標(biāo)值最小點(diǎn)作為PL;同理，將點(diǎn)集S當(dāng)中x軸值最大點(diǎn)即為S的最右點(diǎn)，用PR表示.當(dāng)S中x軸值最大點(diǎn)擁有不只一個(gè)取y軸坐標(biāo)最大的點(diǎn)作為P[1]R

定義2 平面點(diǎn)集S的凸殼表示為CH(S)，若將凸殼CH(S)上結(jié)點(diǎn)度數(shù)為2的點(diǎn)剔除后，余下的點(diǎn)所構(gòu)成凸多邊形被稱之為點(diǎn)集S的子凸殼，用SCH(S)表示[2].

定義3 子凸殼SCH(S)外面的點(diǎn)被稱之為子凸殼SCH(S)外點(diǎn);子凸殼SCH(S)內(nèi)部的點(diǎn)被稱之稱為子凸殼SCH(S)內(nèi)點(diǎn)[2].

定理1 平面點(diǎn)集S中的任意取三點(diǎn)p，q，r，三點(diǎn)坐標(biāo)分別是(px，py)，(qx，qy)，(rx，ry)，則[3]

則存在下面點(diǎn)線位置關(guān)系

(1)當(dāng)Det＞0時(shí)，點(diǎn)r將位于有向線段p→q的左側(cè).

(2)當(dāng)Det＜0時(shí)，點(diǎn)r將位于有向線段p→q的右側(cè).

(3)當(dāng) Det=0 時(shí)，點(diǎn) r，p，q共線.

2 金字塔算法的描述與并行算法概述

金字塔凸殼算法是以點(diǎn)集S中最左點(diǎn)PL和最右點(diǎn)PR的有向線段PL→PR為界，把點(diǎn)集S劃分為上下兩個(gè)子集，分別構(gòu)成相應(yīng)的子凸殼，再將兩者子凸殼合并生成凸殼.具體實(shí)施步驟:首先尋找點(diǎn)集 S中的最頂左點(diǎn)PL和最右頂點(diǎn)PR，之后在分別沿著順時(shí)針找出斜率最大點(diǎn)和按逆時(shí)針找出斜率最小點(diǎn)，查詢確定的這兩點(diǎn)必是凸殼頂點(diǎn)，然后再以重復(fù)上述步驟逐級(jí)尋找其他凸殼頂點(diǎn)，就像搭建金字塔一樣一層層構(gòu)建點(diǎn)集S的二維凸殼邊界BCH(S).

圖1 COW系統(tǒng)示意圖

并行算法程序?qū)崿F(xiàn)方法有別于串行算法程序?qū)崿F(xiàn)方法，并行程序與串行程序的主要區(qū)別是串行算法程序?qū)崿F(xiàn)是通過(guò)單線程的方式完成事務(wù)變化發(fā)展，由于在任何事務(wù)之間總存在著某種因果聯(lián)系，為此應(yīng)將相關(guān)的事務(wù)當(dāng)成一個(gè)不可分割的整體.在實(shí)際事務(wù)的理解和認(rèn)識(shí)上，以往結(jié)構(gòu)化程序?qū)崿F(xiàn)方法，將一個(gè)完整系統(tǒng)視為由眾多彼此相互關(guān)聯(lián)的實(shí)體構(gòu)建而成.可是在實(shí)現(xiàn)方法僅看到復(fù)雜事務(wù)表層行為和靜態(tài)結(jié)構(gòu)關(guān)系，不能從事務(wù)的深層行為與動(dòng)態(tài)結(jié)構(gòu)關(guān)系分解和認(rèn)識(shí)事務(wù).所以從事務(wù)實(shí)現(xiàn)方式的根本上看，各實(shí)體相互之間無(wú)法實(shí)現(xiàn)并發(fā)操作可能，因此也就不存在同時(shí)發(fā)生相互影響相互作用的并發(fā)行為.并行算法程序?qū)崿F(xiàn)方法的則是將一個(gè)紛繁復(fù)雜事務(wù)行為是由許多個(gè)子事務(wù)相互作用的結(jié)果，子事務(wù)之間相互獨(dú)立可同時(shí)運(yùn)行實(shí)現(xiàn).這造成程序設(shè)計(jì)實(shí)現(xiàn)觀念的轉(zhuǎn)變，這種程序設(shè)計(jì)思想指導(dǎo)的并行算法程序?qū)崿F(xiàn)方法，核心部分的內(nèi)容是將復(fù)雜事務(wù)進(jìn)行并行劃分和算法映射，并行計(jì)算模型是其的理論基礎(chǔ).由于并行計(jì)算模型決定了程序設(shè)計(jì)將要采用并行語(yǔ)義，而并行語(yǔ)義將進(jìn)一步?jīng)Q定程序并行執(zhí)行的準(zhǔn)則，進(jìn)而確定了并行劃分的原則和并行算法程序設(shè)計(jì).

3 系統(tǒng)硬件環(huán)境

算法實(shí)現(xiàn)所用實(shí)驗(yàn)的并行計(jì)算機(jī)是機(jī)群系統(tǒng)(COW系統(tǒng)).COW系統(tǒng)擁有編程方便、投資風(fēng)險(xiǎn)小、性價(jià)比高、系統(tǒng)結(jié)構(gòu)靈活、能充分將分散在各處的計(jì)算機(jī)資源，更重要是其具有良好的可擴(kuò)展性等優(yōu)點(diǎn)，并且同時(shí)COW系統(tǒng)從實(shí)際工作條件出發(fā)利用當(dāng)前擁有的網(wǎng)絡(luò)資源與PC機(jī).COW系統(tǒng)是由客戶端與網(wǎng)絡(luò)構(gòu)成，從程序?qū)崿F(xiàn)的角度來(lái)說(shuō)，COW系統(tǒng)是利用面向消息傳遞程序設(shè)計(jì)方式，也就是不同的客戶端都執(zhí)行同一個(gè)計(jì)算機(jī)程序，但不同的客戶端加載數(shù)據(jù)有所不同，這樣實(shí)現(xiàn)程序執(zhí)行的并行計(jì)算.并行計(jì)算系統(tǒng)的運(yùn)行過(guò)程示意圖見(jiàn)圖1，客戶端就是實(shí)際工作中性能各異的PC機(jī)，相互連接的網(wǎng)絡(luò)是使用以太網(wǎng)技術(shù)，其網(wǎng)路數(shù)據(jù)傳輸速率為100M/s;實(shí)際連接的網(wǎng)絡(luò)拓?fù)潢P(guān)系一般使用星型結(jié)構(gòu)，其網(wǎng)絡(luò)中心是交換機(jī)，COW系統(tǒng)的最簡(jiǎn)配置可由HUB與兩臺(tái)PC機(jī)來(lái)構(gòu)成.

圖2 點(diǎn)集區(qū)域劃分

4 金字塔凸殼算法的并行凸殼新算法

并行算法程序設(shè)計(jì)的前提條件是將要實(shí)現(xiàn)的任務(wù)可以在空間與時(shí)間上進(jìn)行分割，達(dá)到將不同的計(jì)算任務(wù)加載到不同終端計(jì)算節(jié)點(diǎn)上.根據(jù)上述對(duì)金字塔算法的描述可對(duì)平面點(diǎn)集進(jìn)行劃分生成不同的子集，其中子集V所含的點(diǎn)集必定不在凸殼邊界上，可先將其中的點(diǎn)刪除出去，這樣可極大提升算法的執(zhí)行效率.在圖2所示的點(diǎn)集中，子集Ⅰ，Ⅱ，Ⅲ，Ⅳ，Ⅴ都是在自己范圍內(nèi)尋找最左和最右點(diǎn)，可是在這個(gè)執(zhí)行過(guò)程中每個(gè)子集間沒(méi)有產(chǎn)生數(shù)據(jù)交叉，各子集間可同時(shí)在不同的終端上運(yùn)行.因此可將所有點(diǎn)集先在主機(jī)中進(jìn)行分割，劃分成不同點(diǎn)子集，不同子集分別使用同步設(shè)置通過(guò)網(wǎng)絡(luò)消息傳遞在同一時(shí)間步上發(fā)送數(shù)據(jù)到并行的各個(gè)終端計(jì)算節(jié)點(diǎn)，各終端節(jié)點(diǎn)獨(dú)立查詢最左和最右凸殼頂點(diǎn)，各節(jié)點(diǎn)定點(diǎn)查詢完畢后再各自發(fā)送給主機(jī)進(jìn)行匯總處理.通過(guò)采用數(shù)據(jù)劃分進(jìn)行并行計(jì)算極好的解決海量數(shù)據(jù)在串行計(jì)算實(shí)現(xiàn)中時(shí)間效率差的難題.下面是在COW系統(tǒng)上實(shí)現(xiàn)金字塔凸殼算法的并行算法步驟:

步驟1:在主機(jī)上預(yù)先用初始近似凸殼算法對(duì)平面點(diǎn)集進(jìn)行區(qū)域劃分處理，尋找點(diǎn)集中上下左右四個(gè)方向的極值點(diǎn)，將點(diǎn)集劃分為五個(gè)子點(diǎn)集，剔除明顯不能構(gòu)成凸殼邊界的子集V所含點(diǎn)，組件4個(gè)并行處理機(jī)群.

步驟2:通過(guò)并行化處理分別在子機(jī)群COWi(1＜i＜4)上對(duì)各子集域Si中點(diǎn)進(jìn)行查詢構(gòu)建各自子凸殼邊界頂點(diǎn).

步驟2－1:在子集Si上用子機(jī)群COWi尋找斜率極值點(diǎn)，確定子凸殼邊界頂點(diǎn)Qi的并行處理.

步驟2－2:刪除左新頂點(diǎn)Qi，L，和右新頂點(diǎn)Qi，r所連成的直線下方的所有點(diǎn)的并行處理.

步驟2－3:對(duì)尋找到的子凸殼Qi的所有頂點(diǎn)進(jìn)行標(biāo)記處理.

步驟3:凸殼邊界的生成.依次將劃分的各子集所查詢確定的頂點(diǎn)，相互連接構(gòu)建生成二維點(diǎn)集的凸殼Q.

5 結(jié)束語(yǔ)

本文提出的金字塔凸殼算法的并行處理方法，在時(shí)間和空間復(fù)雜度上不但好于傳統(tǒng)的串行算法(格雷厄姆凸殼算法、卷包裹凸殼算法)和并行算法(折半分治凸殼算法)，同時(shí)擁有較好的擴(kuò)展性，可推廣到更多機(jī)群上實(shí)現(xiàn)凸殼并行處理.在當(dāng)下信息化的背景下，GIS系統(tǒng)得到廣泛應(yīng)用，GIS所處理的數(shù)據(jù)多為海量數(shù)據(jù)點(diǎn)，如何快速處理海量數(shù)據(jù)倍受關(guān)注.本文提出的金字塔算法的并行處理正是對(duì)這方的一種嘗試，取得了很好的執(zhí)行效果.

[1]金文華，何濤，唐衛(wèi)清等.簡(jiǎn)單快速的平面散亂點(diǎn)集凸殼算法[J].北京航天航空大學(xué)學(xué)報(bào)，1999，25(1):73－76.

[2]王杰臣.2維空間數(shù)據(jù)最小凸包生成算法優(yōu)化[J].測(cè)繪學(xué)報(bào)，2002，31(1):82－86.

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