一種基于點(diǎn)集自適應(yīng)分組構(gòu)建Voronoi圖的并行算法

王結(jié)臣， 蒲英霞， 崔 璨， 陳 剛， 馬勁松

（江蘇省地理信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210093；南京大學(xué)地理信息科學(xué)系，江蘇 南京 210093）

Voronoi圖是計(jì)算幾何中的一個(gè)經(jīng)典數(shù)學(xué)問(wèn)題，它在地理信息系統(tǒng)、氣象學(xué)、生態(tài)學(xué)、分子生物學(xué)等學(xué)科有著較成熟的應(yīng)用，自動(dòng)構(gòu)建Voronoi圖也因此得到較多的研究[1-4]。針對(duì)點(diǎn)線面體等多維空間實(shí)體的Voronoi圖生成[5-7]都有著廣泛的研究，其中平面點(diǎn)集的Voronoi圖應(yīng)用最為廣泛，其生成算法主要有增量算法、掃描線算法、分治算法等幾種。

增量算法[8-9]是較早建立的一類Voronoi圖生成算法，它通過(guò)逐個(gè)加入點(diǎn)，并局部修改Voronoi圖結(jié)構(gòu)信息來(lái)構(gòu)造新的Voronoi圖。增量算法設(shè)計(jì)思路簡(jiǎn)單，易于實(shí)現(xiàn)，且Voronoi圖的動(dòng)態(tài)更新較為容易。但其時(shí)間復(fù)雜度為 O(n2)，在數(shù)據(jù)量較大的情況下，難以滿足實(shí)際應(yīng)用。

掃描線算法[10]是Fortune于上世紀(jì)80年代提出，它給定一條垂直掃描線對(duì)平面點(diǎn)集從左至右進(jìn)行掃描，每掃過(guò)一個(gè)點(diǎn)就為該點(diǎn)構(gòu)造一條以掃描線為基線的拋物線（稱之為點(diǎn)事件），離掃描線最近的一些拋物線在相交和連接后可構(gòu)造出一條岸線（Beach Line）。隨著掃描線的推進(jìn)，岸線形狀不斷改變。當(dāng)岸線上某交點(diǎn)到掃描線距離與到該交點(diǎn)對(duì)應(yīng)的兩平面點(diǎn)距離相等時(shí)，獲得Voronoi圖多邊形的頂點(diǎn)（稱之為圓事件）。按此思路，將掃描線推進(jìn)到平面點(diǎn)集最右端，Voronoi圖構(gòu)建完成。

分治算法最早由 Shamos和 Hoey提出[11]，該算法預(yù)先將平面點(diǎn)分為若干組，為每個(gè)組生成各自的Voronoi圖后，再進(jìn)行合并。具體實(shí)施步驟是將所有點(diǎn)按照x值進(jìn)行排序，使用一條垂線將點(diǎn)分為兩組，每組點(diǎn)數(shù)大致相等，分別將兩組點(diǎn)生成 Voronoi圖，最后在垂線處實(shí)現(xiàn) Voronoi圖的合并。該算法一般通過(guò)遞歸方式分組，即在子組內(nèi)構(gòu)造垂直線完成進(jìn)一步分組。垂線兩側(cè)的圖形合并采用構(gòu)造分割鏈的方法實(shí)現(xiàn)，將分割鏈兩側(cè)的完整邊和非完整邊剔除，并把分割鏈補(bǔ)充給新的Voronoi圖，實(shí)現(xiàn)合并。Oishi等在此基礎(chǔ)上將Voronoi圖中元素的拓?fù)浞较蛞胗?jì)算，以提升分治算法速度，取得了一定的效果[12]。

一些學(xué)者從其他角度入手研究Voronoi圖的生成及其重要性質(zhì)，如凸包距離函數(shù)法[13]、遞歸算法[14]、離散Voronoi圖算法等[15-16]，這些研究對(duì)Voronoi圖生成也取得了較好的效果。

隨著計(jì)算機(jī)數(shù)據(jù)處理規(guī)模的不斷增大，現(xiàn)有方法越來(lái)越難以滿足應(yīng)用需求，針對(duì)海量空間數(shù)據(jù)的高效計(jì)算方法成為新的研究重點(diǎn)。當(dāng)代計(jì)算機(jī)在多核、分布式技術(shù)等方面的發(fā)展，使Voronoi生成算法在并行環(huán)境下的實(shí)現(xiàn)成為可能。在將并行計(jì)算技術(shù)引入Voronoi圖的生成方面目前也有一些研究成果，如 Cole等在分治算法的基礎(chǔ)上進(jìn)行并行計(jì)算[17]，Ulrith等采用凸包距離函數(shù)實(shí)現(xiàn)了一種隨機(jī)并行算法[16]。然而，受當(dāng)時(shí)軟硬件條件限制，現(xiàn)有的并行算法多著重于理論分析，算法測(cè)試數(shù)據(jù)量較小，一些研究由于受計(jì)算環(huán)境的限制難以推廣應(yīng)用。此外，已有的并行算法通常以分治法為基礎(chǔ)，此時(shí)分組形狀不易控制，易形成狹長(zhǎng)的條帶，在進(jìn)行分組子網(wǎng)合并時(shí)會(huì)出現(xiàn)大量邊界點(diǎn)，導(dǎo)致子網(wǎng)間出現(xiàn)過(guò)多未封閉多邊形，在一定程度上影響了算法的整體效率。

為此，本文在分析分治算法思想的基礎(chǔ)上，考慮將平面點(diǎn)集進(jìn)行自適應(yīng)網(wǎng)格劃分，使得每個(gè)分組中點(diǎn)的數(shù)量近似相等，且盡量避免每個(gè)矩形分組出現(xiàn)狹長(zhǎng)條帶。同時(shí)，考慮到掃描線算法作為一種較經(jīng)典的Voronoi圖生成算法，其時(shí)間復(fù)雜度為 O(nlgn)，算法性能和穩(wěn)定性都比較好。本文采用其作為各點(diǎn)集分組的子網(wǎng)生成算法，并采用并行計(jì)算方式完成這一過(guò)程。在相鄰網(wǎng)格之間，依據(jù)掃描線算法中的岸線理論提取邊界點(diǎn)，將邊界點(diǎn)集生成Voronoi圖并更新原圖所在的多邊形邊以完成多邊形的合并。

1 平面點(diǎn)集自適應(yīng)分組

1.1 自適應(yīng)分組

為加快平面點(diǎn)集Voronoi圖生成的效率，較有效的策略是對(duì)點(diǎn)集進(jìn)行空間分組，而后進(jìn)行分組間Voronoi圖的合并。這種“各個(gè)擊破”的策略在諸多空間分析算法中有應(yīng)用范例，如分組構(gòu)建凸包、分組生成TIN等。

圖1 基于格網(wǎng)的二維平面點(diǎn)集分組

如圖1所示，點(diǎn)集被分配到6行×9列的空間網(wǎng)格中，若將每個(gè)分組單獨(dú)生成Voronoi圖，則后續(xù)處理只需完成組與組之間的Voronoi子圖合并即可。這種分組策略與常見(jiàn)的分治算法有一定的相似之處，它也體現(xiàn)了一種分而治之的思想。

規(guī)則格網(wǎng)分組在一定程度上可提高原算法的效率，但當(dāng)點(diǎn)的空間分布不均勻時(shí)，會(huì)導(dǎo)致各網(wǎng)格內(nèi)點(diǎn)數(shù)差異太大，影響算法執(zhí)行的整體效率。尤其是進(jìn)行算法并行化實(shí)現(xiàn)時(shí)，這種影響尤為顯著，此時(shí)由于各組耗時(shí)相差太大，導(dǎo)致處理器之間難以均衡而降低計(jì)算效能。

圖2 平面點(diǎn)集自適應(yīng)分組

為避免現(xiàn)有分治算法中采用沿掃描線單方向進(jìn)行分組易形成狹長(zhǎng)條帶等問(wèn)題，同時(shí)借鑒規(guī)則網(wǎng)格分組的思想，本文設(shè)計(jì)了一種基于二叉樹(shù)的點(diǎn)集自適應(yīng)分組方案。如圖2所示，假設(shè)分組后最小點(diǎn)集中點(diǎn)數(shù)不少于20，首先為二叉樹(shù)設(shè)定根結(jié)點(diǎn)（圖2中I(1)），該結(jié)點(diǎn)覆蓋原始點(diǎn)集；然后以一條水平分割線將該初始網(wǎng)格單元一分為二，兩個(gè)子單元中點(diǎn)數(shù)近似相等；再后分別針對(duì)上述每個(gè)子網(wǎng)格單元分別采用一條垂向分割線進(jìn)行劃分，依此類推，直至網(wǎng)格單元中的點(diǎn)數(shù)小于預(yù)設(shè)值2倍時(shí)終止分割，得到最終的葉子結(jié)點(diǎn)。劃分過(guò)程中采用水平還是垂直分割線，主要取決于網(wǎng)格單元的長(zhǎng)寬。該過(guò)程很容易使用遞歸方式實(shí)現(xiàn)，圖3為圖2的二叉樹(shù)分裂示意圖。

圖3 平面點(diǎn)集分組的二叉樹(shù)表達(dá)

1.2 數(shù)據(jù)結(jié)構(gòu)

筆者稱上述方法為“基于二叉樹(shù)的點(diǎn)集自適應(yīng)分組”，在數(shù)據(jù)組織時(shí)，按算法中需要表達(dá)的空間要素從小到大可分為4個(gè)層次：平面點(diǎn)集、Voronoi邊、Voronoi多邊形和二叉樹(shù)矩形網(wǎng)格（限于篇幅，本文省略了Fortune掃描線算法中的幾個(gè)中間過(guò)程結(jié)構(gòu)體），其中二叉樹(shù)網(wǎng)格只有在其葉子結(jié)點(diǎn)上才賦值，其他單元賦值為空。這些結(jié)構(gòu)體用C語(yǔ)言可描述為下述形式（見(jiàn)1.2節(jié)）。

//平面點(diǎn)結(jié)構(gòu)體

//點(diǎn)的平面坐標(biāo)

//該點(diǎn)在網(wǎng)格單元中的編號(hào)

//該點(diǎn)在整個(gè)平面點(diǎn)集中的編號(hào)

//Voronoi邊結(jié)構(gòu)體

//構(gòu)成該邊的直線方程系數(shù)

//Voronoi邊構(gòu)成的線段的兩端點(diǎn)坐標(biāo)

//Voronoi邊兩側(cè)所對(duì)應(yīng)的兩個(gè)原始平面點(diǎn)

//標(biāo)記該邊所在的線段是否與矩形網(wǎng)格單元邊界線相交

//Voronoi多邊形結(jié)構(gòu)體

//構(gòu)成該Voronoi多邊形的邊集合

//Voronoi多邊形對(duì)應(yīng)的平面點(diǎn)

//網(wǎng)格單元結(jié)構(gòu)體

//網(wǎng)格單元內(nèi)平面點(diǎn)的個(gè)數(shù)

//網(wǎng)格單元內(nèi)平面點(diǎn)集合

//網(wǎng)格單元的邊界最下角點(diǎn)和最上角點(diǎn)//網(wǎng)格內(nèi)Voronoi多邊形邊個(gè)數(shù)

//網(wǎng)格內(nèi)Voronoi邊集合

//二叉樹(shù)存儲(chǔ)的網(wǎng)格單元集合

//網(wǎng)格單元

//網(wǎng)格單元的左右(上下)兩側(cè)子網(wǎng)格單元

在算法實(shí)現(xiàn)時(shí)，可以置每個(gè)非葉子結(jié)點(diǎn)中的BlockSite指針為空，因?yàn)閷?shí)際的Voronoi子圖計(jì)算都是在葉子結(jié)點(diǎn)內(nèi)進(jìn)行的，根結(jié)點(diǎn)只是為查詢檢索需要，不必實(shí)例化其BlockSite指針。

2 邊界點(diǎn)提取與子圖合并

2.1 邊界點(diǎn)提取

在完成自適應(yīng)分組后，每個(gè)子集均采用掃描線算法生成子Voronoi圖，如何合并子圖成為該算法的關(guān)鍵環(huán)節(jié)。在實(shí)施子圖合并時(shí)，位于子圖四周的部分點(diǎn)對(duì)應(yīng)的多邊形結(jié)構(gòu)會(huì)發(fā)生局部改變，包括多邊形構(gòu)成邊的更新與多邊形閉合，姑且將這類點(diǎn)稱為邊界點(diǎn)，邊界點(diǎn)的界定與提取方法將直接影響算法的穩(wěn)定性。

在生成各組點(diǎn)集的Voronoi圖時(shí)，無(wú)論網(wǎng)格內(nèi)的點(diǎn)集是按照掃描線從左至右、從右至左、從上至下或從下至上得到，其結(jié)果Voronoi圖是唯一的。設(shè)想將掃描線從無(wú)限遠(yuǎn)處拉回到網(wǎng)格邊界線上（此時(shí)網(wǎng)格邊界線也可看作掃描線），則每個(gè)網(wǎng)格對(duì)應(yīng)著4條掃描線，這些掃描線處于向外推進(jìn)的狀態(tài)。

如圖4所示，圖中的鉛垂線為兩相鄰網(wǎng)格的公共邊界，若將此邊界線看作掃描線，向兩側(cè)網(wǎng)格內(nèi)分別作岸線，左側(cè)岸線由點(diǎn)P1、P2、P3產(chǎn)生的拋物線構(gòu)成，右側(cè)岸線由點(diǎn) Q1、Q2、Q3產(chǎn)生的拋物線構(gòu)成。掃描線兩側(cè)的圖形欲做合并，若固定左側(cè)，將掃描線向右推進(jìn)，左側(cè)岸線的左后方不受影響；同樣地，若固定右側(cè)，將掃描線向左推進(jìn)，右側(cè)岸線的右后方也不受影響。因?yàn)閂oronoi圖中每個(gè)頂點(diǎn)正是共享此頂點(diǎn)的多邊形所在平面點(diǎn)的外接圓的圓心，岸線后方所在多邊形頂點(diǎn)及其對(duì)應(yīng)的各邊都不會(huì)因?yàn)閂oronoi圖的合并發(fā)生改變，其原始平面點(diǎn)也不必再提取作為邊界點(diǎn)。若上述結(jié)論不成立，例如在圖中掃描線左側(cè)插入新的一點(diǎn)P'，其不為邊界點(diǎn)，但是P3、Q3和P'能夠構(gòu)成空外接圓，而按照掃描線算法理論，滿足這一條件的前提是該點(diǎn)P'必須是組成左側(cè)岸線的點(diǎn)，因?yàn)榘毒€一側(cè)的點(diǎn)與掃描線另一側(cè)的點(diǎn)發(fā)生圓事件時(shí)該點(diǎn)必須為構(gòu)成岸線的點(diǎn)，故已經(jīng)排除出構(gòu)造岸線的平面點(diǎn)不能再次發(fā)生圓事件。

圖4 網(wǎng)格邊界掃描線及其兩側(cè)岸線

在圖5中，加粗豎線為兩網(wǎng)格單元的分界線，加粗折線為兩網(wǎng)格單元合并時(shí)新加入的 Voronoi多邊形邊，這些新增加的折線段實(shí)現(xiàn)了原網(wǎng)格單元邊界處Voronoi多邊形的封閉，每條折線段正是邊界線兩側(cè)某兩點(diǎn)之間的垂直平分線。而網(wǎng)格內(nèi)位于邊界附近的一些Voronoi圖頂點(diǎn)將因子圖合并而舍棄，如圖中的頂點(diǎn)O，它是邊界點(diǎn)A、B和C的外接圓圓心，在進(jìn)行子圖合并時(shí)掃描線右側(cè)的某點(diǎn)與A、B、C構(gòu)建新的3條垂直平分線，這3條平分線將A、B、C間的原平分線進(jìn)行了分割，從而頂點(diǎn)O不復(fù)存在（它不再是新垂直平分線的交點(diǎn)）。

圖5 網(wǎng)格邊界Voronoi多邊形合并

在算法實(shí)現(xiàn)時(shí)，針對(duì)每條與邊界線相交的邊，將記錄該邊是與網(wǎng)格單元4條邊界線的哪條邊界線相交，根據(jù)該信息可以較方便地提取各邊界線附近的初始邊界點(diǎn)?；诔跏歼吔琰c(diǎn)，按照岸線理論可建立初始岸線，此岸線并不一定與以邊界線為掃描線的最終岸線重合。在網(wǎng)格單元內(nèi)形成的Voronoi圖中，某些平面點(diǎn)生成的多邊形雖然閉合，但是該點(diǎn)與邊界線構(gòu)成拋物線可能與初始岸線仍然有相交情形出現(xiàn)，通常出現(xiàn)在與初始邊界點(diǎn)共Voronoi邊的點(diǎn)中。在檢索其他邊界點(diǎn)時(shí)，可采用以下步驟進(jìn)行：

1）構(gòu)造一個(gè)隊(duì)列，將初始邊界點(diǎn)逐個(gè)加入隊(duì)列，成為邊界點(diǎn)隊(duì)列，標(biāo)記每個(gè)點(diǎn)已經(jīng)被判定過(guò)；

2）逐個(gè)遍歷隊(duì)列中的邊界點(diǎn)，提取與該邊界點(diǎn)共邊的相鄰點(diǎn)；

3）遍歷這些相鄰點(diǎn)，若該相鄰點(diǎn)已經(jīng)判定過(guò)，則跳過(guò)；否則為該點(diǎn)構(gòu)造拋物線，計(jì)算拋物線與岸線的相交關(guān)系，若相交則更新岸線，并將該點(diǎn)加入隊(duì)列，標(biāo)記該點(diǎn)已被判定過(guò)；

4）當(dāng)隊(duì)列中的邊界點(diǎn)都被遍歷過(guò)，則終止判定，隊(duì)列中的點(diǎn)集就是該條邊界線對(duì)應(yīng)的邊界點(diǎn)。

上述步驟的關(guān)鍵點(diǎn)在第3步，當(dāng)某邊界點(diǎn)相鄰的點(diǎn)都沒(méi)有能夠繼續(xù)更新岸線，則終止尋找這些相鄰點(diǎn)的“二階”相鄰點(diǎn)，即停止對(duì)該邊界點(diǎn)的外延。因?yàn)檫吔琰c(diǎn)所在的未閉合多邊形組合正好是位于邊界點(diǎn)某側(cè)的“第1層”Voronoi多邊形，此時(shí)需要以這些多邊形為基礎(chǔ)進(jìn)行外延，提取后續(xù)滿足能夠更新岸線的新的多邊形。

2.2 Voronoi子圖合并

子網(wǎng)合并是要找到并插入如圖5所示的一條折線，它由兩側(cè)邊界點(diǎn)的垂直平分線所組成，可通過(guò)以下方法實(shí)現(xiàn)：在為網(wǎng)格單元生成 Voronoi圖的同時(shí)，提取每個(gè)網(wǎng)格單元的邊界點(diǎn)，將邊界點(diǎn)作為一組點(diǎn)集并生成Voronoi圖；那么，任一網(wǎng)格單元內(nèi)的邊界點(diǎn)將具有兩個(gè) Voronoi多邊形，一個(gè)是網(wǎng)格單元自身生成的，一個(gè)則是邊界點(diǎn)集生成的。邊界點(diǎn)對(duì)應(yīng)的兩個(gè)多邊形的交集即是該點(diǎn)合并后的Voronoi多邊形。

盡管邊界點(diǎn)在兩種子圖中的多邊形形狀不盡相同，但是網(wǎng)格內(nèi)部邊界點(diǎn)與邊界點(diǎn)之間的Voronoi邊關(guān)系基本保持不變。因此，同一邊界點(diǎn)對(duì)應(yīng)的兩個(gè)Voronoi多邊形必定有幾條邊其構(gòu)成的直線方程相同，或者邊的長(zhǎng)度位置都未曾發(fā)生變化。事實(shí)上，合并后的邊界點(diǎn)對(duì)應(yīng)的Voronoi多邊形正是上述兩個(gè)多邊形區(qū)域的交集。如圖6所示，圖中的水平線為兩個(gè)點(diǎn)集分組的邊界線，兩條連續(xù)的拋物線鏈?zhǔn)窃撨吔缇€對(duì)應(yīng)的兩側(cè)岸線。兩條岸線之間所夾的一條連續(xù)折線正是在進(jìn)行合并時(shí)需要計(jì)算得到的。這條折線在為邊界點(diǎn)集生成的Voronoi圖中可直接得到，如圖6中邊界點(diǎn) O在分組內(nèi)生成的 Voronoi多邊形包含F(xiàn)ABC，其中FA為射線，AB為線段，BC為射線；而點(diǎn)O在邊界點(diǎn)生成的Voronoi圖中多邊形包含BCDEF。針對(duì)這兩個(gè)未封閉的多邊形合并方法較為簡(jiǎn)單，主要是求取多邊形的交集部分并構(gòu)造新的封閉多邊形，對(duì)于已經(jīng)形成的線段可以不用修改，僅僅對(duì)射線間進(jìn)行求交運(yùn)算即可實(shí)現(xiàn)封閉。

圖6 分組間Voronoi多邊形合并

3 分組并行計(jì)算

長(zhǎng)期以來(lái)，并行計(jì)算理論在數(shù)值計(jì)算及非數(shù)值計(jì)算領(lǐng)域有了較快的發(fā)展，先后提出了多種并行計(jì)算模型，如PRAM、BSP、LogP等?；谶@些計(jì)算模型的常用并行算法主要有兩類：一類是SIMD（單指令流多數(shù)據(jù)流），另一類是MIMD（多指令流多數(shù)據(jù)流）。前一類并行算法中，各處理機(jī)同時(shí)處理相同的指令，只是所處理的數(shù)據(jù)不同，這主要體現(xiàn)在數(shù)據(jù)處理上的并行性；后一類并行算法中，各處理機(jī)處理不同的指令，并可以對(duì)不同的數(shù)據(jù)進(jìn)行獨(dú)立操作，處理器之間互不干擾，這是對(duì)算法流程自身的一種并行處理。

前人對(duì)二維歐式空間平面點(diǎn)集Voronoi圖生成的并行算法也進(jìn)行了相關(guān)嘗試，如文獻(xiàn)[17]為平面上有n個(gè)點(diǎn)的點(diǎn)集提供n個(gè)處理器，該算法屬于一種遞歸方法：給定一條垂直分界線每次將平面上的點(diǎn)集分為左右兩組，各組點(diǎn)個(gè)數(shù)大約為n/2，并為每個(gè)組分配n/2個(gè)處理器，然后計(jì)算穿越垂直分界線兩側(cè)的“等值線”。算法在每執(zhí)行一次遞歸時(shí)就計(jì)算分界線兩側(cè)的“等值線”，當(dāng)遞歸結(jié)束時(shí)，合并“等值線”。文獻(xiàn)[18]基于對(duì)稱凸距離函數(shù)，提出一種隨機(jī)并行算法。該方法采用隨機(jī)采樣數(shù)據(jù)構(gòu)建Voronoi圖，在算法中使用固定數(shù)目的處理器。現(xiàn)有基于并行技術(shù)的Voronoi圖構(gòu)建算法主要分為兩類：一類在構(gòu)建分組后為每個(gè)分組分配一個(gè)處理器，另一類為固定處理器個(gè)數(shù)，分組數(shù)量不定。本文采用后一種方式實(shí)現(xiàn)并行運(yùn)算，在現(xiàn)有多核處理器的基礎(chǔ)上，為平面點(diǎn)集構(gòu)建分組。

本文算法中，采用點(diǎn)集自適應(yīng)分組構(gòu)建并行計(jì)算環(huán)境，是一種典型的SIMD算法，每個(gè)處理機(jī)的工作內(nèi)容相同，只是各自處理不同的分組數(shù)據(jù)。由于算法中還涉及到點(diǎn)集分組、邊界點(diǎn)提取構(gòu)建Voronoi圖、子Voronoi圖合并等環(huán)節(jié)，這3個(gè)環(huán)節(jié)是前后相繼處理的。為此，可以在處理機(jī)中確定一臺(tái)主機(jī)，其他處理機(jī)作為從機(jī)，主機(jī)負(fù)責(zé)點(diǎn)集自適應(yīng)分組、分組數(shù)據(jù)向從機(jī)分發(fā)以及接收處理結(jié)果，并在主機(jī)上完成子Voronoi圖合并，從機(jī)只需對(duì)接收到的點(diǎn)集構(gòu)建Voronoi子圖并提取組內(nèi)邊界點(diǎn)。具體處理過(guò)程如下：

1）主機(jī)按照給定的網(wǎng)格參數(shù)對(duì)平面點(diǎn)集進(jìn)行自適應(yīng)分組，假定分為N組；

2）針對(duì)M個(gè)處理機(jī)，主機(jī)逐個(gè)為每個(gè)處理機(jī)分配一個(gè)分組點(diǎn)集，并即時(shí)監(jiān)聽(tīng)各從機(jī)的運(yùn)行結(jié)果；

3）主機(jī)監(jiān)聽(tīng)到某從機(jī)運(yùn)算結(jié)束，從機(jī)將運(yùn)算結(jié)果發(fā)送到主機(jī)，若主機(jī)上還有點(diǎn)集分組未處理完，則繼續(xù)為該從機(jī)分配一個(gè)點(diǎn)集分組；

4）按上述步驟，直到將主機(jī)上的點(diǎn)集分組處理完畢；

5）主機(jī)根據(jù)各個(gè)點(diǎn)集分組生成的 Voronoi子圖和收集到的邊界點(diǎn)，為邊界點(diǎn)集生成Voronoi子圖；

6）針對(duì)上述N+1組Voronoi子圖，完成子圖合并。

4 測(cè)試與分析

本文算法首先對(duì)二維平面點(diǎn)集進(jìn)行自適應(yīng)分組，然后在各分組內(nèi)采用掃描線算法構(gòu)建Voronoi圖，最后進(jìn)行各網(wǎng)格單元子圖的合并。算法耗時(shí)主要由點(diǎn)集自適應(yīng)分組、各組點(diǎn)集的Voronoi圖構(gòu)建、邊界點(diǎn)提取與Voronoi圖構(gòu)建、子Voronoi圖合并4部分構(gòu)成。為評(píng)估各環(huán)節(jié)的耗時(shí)情況，我們進(jìn)行了一些測(cè)試，測(cè)試結(jié)果如表1所示。

測(cè)試結(jié)果表明：

1）算法耗時(shí)主要集中在Voronoi子圖構(gòu)建環(huán)節(jié)，與總耗時(shí)相比，點(diǎn)集分組、子圖合并等所占時(shí)間甚少；

2）由于 Fortune掃描線算法的時(shí)間復(fù)雜度為O(nlogn)，即使不采用并行計(jì)算技術(shù)，在單處理機(jī)環(huán)境下采用分組計(jì)算策略亦能一定程度上提高算法效率；

3）本文算法針對(duì)最耗時(shí)的環(huán)節(jié)（構(gòu)建Voronoi子圖）進(jìn)行并行化處理，可顯著提高算法效率。但需補(bǔ)充說(shuō)明的是，分組數(shù)量并非越多越好，因?yàn)樗鼤?huì)影響到所提取的邊界點(diǎn)數(shù)量，最極端的情形下（例如每個(gè)點(diǎn)作為 1組），原點(diǎn)集中的點(diǎn)均成為邊界點(diǎn)，此時(shí)分組策略將失去意義。

表1 算法效率測(cè)試結(jié)果表

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

基于二維歐式空間平面點(diǎn)集的Voronoi圖是Voronoi圖研究領(lǐng)域里面最為成熟也是應(yīng)用最廣的一類Voronoi圖。前人針對(duì)這類Voronoi圖的生成給出了數(shù)十種算法實(shí)現(xiàn)，主要可以歸納為矢量和柵格方法兩種，柵格方法由于難以保證其數(shù)據(jù)精度，限制了Voronoi圖的應(yīng)用場(chǎng)合，而矢量方法在算法時(shí)間復(fù)雜度上難以突破 nlogn，在遇到數(shù)據(jù)量較大的情況下，其運(yùn)算耗時(shí)較長(zhǎng)，難以滿足實(shí)際應(yīng)用。本文借鑒矢量和柵格方法各自的優(yōu)缺點(diǎn)，提出采用基于二叉樹(shù)的自適應(yīng)分組方法，將平面空間點(diǎn)集預(yù)先進(jìn)行點(diǎn)集分組，并采用并行計(jì)算技術(shù)提升算法效率。本算法以 Fortune的掃描線算法為基礎(chǔ)，引入了網(wǎng)格自適應(yīng)分組方法提升算法運(yùn)算效率，因?yàn)榉纸M間的Voronoi圖生成比較獨(dú)立，它便于在并行計(jì)算環(huán)境下實(shí)現(xiàn)，在數(shù)據(jù)量較大時(shí)，并行環(huán)境能有效降低單機(jī)環(huán)境下算法對(duì)內(nèi)存及磁盤(pán)空間的限制。

[1] Ryu J,Park R,Kim D S. Molecular surfaces on proteins via beta shapes [J]. Computer Aided Design,2007,39(12): 1042-1057.

[2] Okabe A,Boots B,Sugihara K,et al. Spatial tessellations: concepts and applications of Voronoi diagrams [M]. Wiley,Chichester,2000: 1-42.

[3] Qian Bo,Zhang Lichao,Shi Yusheng,et al. Voronoi approach to recursive generation of tool path for SLS [J].Computer Aided Drafting,Design and Manufacturing,2008,18(2): 13-20.

[4] Li Yang,Feng Wei,Zhou Huamin. Un-thorough delaunay approach for tetrahedral mesh generation [J].Computer Aided Drafting,Design and Manufacturing,2007,17(2): 82-90.

[5] Li Jin,Donguk K,Lisen M,et al. A sweepline algorithm for Euclidean Voronoi diagrams of circles [J]. Computer Aided Design,2006,38(3):260-272.

[6] Yap C K. An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments [J]. Discrete& Computational Geometry,1987,(2): 365-393.

[7] Kim D S,Cho Y,Kim D. Euclidean Voronoi diagram of 3D balls and its computation via tracing edges [J].Computer Aided Design,2005,37(13): 1412-1424.

[8] Ohya T. Improvements of the incremental method for the Voronoi diagram with computational comparision of various algorithms [J]. Journal of Operation&Research Sociaty,1984,27(4): 306-336.

[9] Held M,Huber S. Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight line segmengts [J]. Computer Aided Design,2009,41(5): 327-338.

[10] Fortune S. A sweepline algorithm for Voronoi diagrams [J]. Algorithmica,1987,(2): 153-174.

[11] Shamos M I,Hoey D. Closest-point problems[C]//Proceedings of the 16th Annual Symposium on the Fundations of Computer Science,1975: 151-162.

[12] Oishi Y,Sugihara K. Topology-oriented divideand-conquer algorithm for Voronoi diagrams [J].Graphic Models and Image Procedings,1995,57(4):303-314.

[13] Chew L P,Drysedale R L. Voronoi diagrams based on convex distance functions[C]//Proceedings of the Symposium on Computational Geometry,Baltimore,1985: 235-244.

[14] Mark D M. Recursive algorithm for determination of proximal ( thiessen ) polygons in any metric space [J].Geogr. Anal. 1987,19(3): 264-272.

[15] Schwarzkopf O. Parallel computation of discrete Voronoi diagrams[C]// Tech. Rep. Fachbereich Mathematik,Freie Universitat,Berlin,1988: 193-204.

[16] Schueller A. A nearest neighbor sweep circle algorithm for computing discrect voronoi tessellations [J]. Journal of Mathmetical Anaysis and Applications,2007,336(2): 1018-1025.

[17] Cole R,Goodrich M T,et al. A nearly optimal deterministic paranell Voronoi diagram algorithm [J].Algorithmica,1996,16: 569-617.

[18] Ulrich K. A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions [J]. Discrete Applied Mathematics,2001,109(1-2): 177-196.