Delaunay三角網(wǎng)的并行構(gòu)建和更新

崔水軍 尹文亭

摘 要：文章提出一種Delaunay三角網(wǎng)并行構(gòu)建和更新算法。該算法中先將點(diǎn)數(shù)據(jù)進(jìn)行格網(wǎng)劃分，然后將每塊區(qū)域作為一個(gè)工作單元進(jìn)行構(gòu)網(wǎng)，當(dāng)相鄰區(qū)域的三角網(wǎng)構(gòu)建完畢，就將相鄰區(qū)域進(jìn)行合并，最終生成一個(gè)完整的三角網(wǎng)。

關(guān)鍵詞：Delaunay三角網(wǎng)；并行；動(dòng)態(tài)更新；加速比

引言

隨著測(cè)量技術(shù)的發(fā)展和新型測(cè)量設(shè)備的出現(xiàn)，空間數(shù)據(jù)的獲取變得更加容易和快捷，與此同時(shí)，數(shù)據(jù)量也呈爆炸性的增長(zhǎng)。如何利用這些海量的空間數(shù)據(jù)實(shí)現(xiàn)數(shù)字地面模型DTM的高效構(gòu)建是當(dāng)前空間分析及應(yīng)用領(lǐng)域亟需解決的問題之一。Delaunay三角網(wǎng)以其唯一性、空?qǐng)A性、能以不同分辨率表達(dá)地形、適合各種分布的數(shù)據(jù)等諸多優(yōu)點(diǎn)而被廣泛地應(yīng)用于DTM建模中。長(zhǎng)久以來(lái)，國(guó)內(nèi)外學(xué)者對(duì)Delaunay三角網(wǎng)的構(gòu)建提出了多種算法[1-3]。這些算法按實(shí)現(xiàn)過程大致可以分為三類：逐點(diǎn)插入法、分治法和掃描線法。陳楚江等[4]提出了實(shí)現(xiàn)三角網(wǎng)局部更新的方法。陳少勤等[5]提出利用多源數(shù)據(jù)實(shí)現(xiàn)不規(guī)則三角網(wǎng)的動(dòng)態(tài)更新。但這些算法都是基于串行程序?qū)崿F(xiàn)，不支持點(diǎn)并行的插入和刪除。隨著多核計(jì)算機(jī)的普及，并行為解決大數(shù)據(jù)量的不規(guī)則三角網(wǎng)（TIN）構(gòu)建和更新提供了新的思路。不少學(xué)者也對(duì)此做了研究，李堅(jiān)等[6]提出將分治算法與流數(shù)據(jù)處理方法相結(jié)合，利用多核處理器平臺(tái)進(jìn)行并行運(yùn)算。張真[7]提出一種適用于并行計(jì)算的歸并構(gòu)網(wǎng)方法。這些算法滿足于Delaunay三角網(wǎng)的并行構(gòu)建，但不適用于三角網(wǎng)的并行動(dòng)態(tài)更新。因?yàn)樵谶@些算法在開始之前，點(diǎn)集必須是確定的，而三角網(wǎng)更新時(shí)，被插入（刪除）點(diǎn)是不確定的。文章提出一種單機(jī)多核環(huán)境下Delaunay三角網(wǎng)并行構(gòu)建算法，該算法將數(shù)據(jù)進(jìn)行格網(wǎng)劃分，每一個(gè)數(shù)據(jù)塊作為一個(gè)工作單元。同時(shí)為解決內(nèi)存共享帶來(lái)的問題，可以為各工作單元分配獨(dú)立的內(nèi)存空間，工作單元之間相對(duì)獨(dú)立，因此可以很好的實(shí)現(xiàn)三角網(wǎng)的并行構(gòu)建和更新。

并行算法采用數(shù)據(jù)分塊[8]的思想，首先將點(diǎn)數(shù)據(jù)按給定閾值（實(shí)驗(yàn)中發(fā)現(xiàn)閾值選擇受實(shí)驗(yàn)環(huán)境影響）進(jìn)行格網(wǎng)劃分，每一個(gè)數(shù)據(jù)塊形成一個(gè)獨(dú)立的工作單元。每一個(gè)工作單元只負(fù)責(zé)所屬區(qū)域內(nèi)三角網(wǎng)的構(gòu)建更新。利用計(jì)算機(jī)單機(jī)多核的優(yōu)勢(shì)，可以同時(shí)將多個(gè)工作單元分配給計(jì)算機(jī)進(jìn)行處理。最后將相鄰的區(qū)域進(jìn)行合并，最終完成三角網(wǎng)的構(gòu)建。每一個(gè)工作單元所負(fù)責(zé)的工作主要有三方面：初始三角網(wǎng)的構(gòu)建、點(diǎn)的插入和刪除，下面將分別闡述。

1 初始三角網(wǎng)構(gòu)建

主線程對(duì)隊(duì)列中的所用點(diǎn)進(jìn)行掃描，如果點(diǎn)位于某一個(gè)工作單元負(fù)責(zé)的區(qū)域，則將點(diǎn)移動(dòng)到該工作單元的私有隊(duì)列中。工作單元根據(jù)負(fù)責(zé)區(qū)域的四個(gè)角點(diǎn)坐標(biāo)形成兩個(gè)初始三角形，然后從自己的私有隊(duì)列中取點(diǎn)進(jìn)行插入構(gòu)網(wǎng)。主要步驟如下：（1）先找到包含點(diǎn)集中所有點(diǎn)的初始三角形，即將數(shù)據(jù)塊的邊界線向外擴(kuò)大某個(gè)值d，然后連接任意一條對(duì)角線，形成兩個(gè)超三角形，并對(duì)其進(jìn)行標(biāo)號(hào)；（2）取點(diǎn)集中的任意一點(diǎn)v，查找v點(diǎn)所在的三角形，如果v在三角形內(nèi)則連接v和三角形的三個(gè)頂點(diǎn)，如果點(diǎn)v在三角形邊上，則連接該邊相對(duì)的一個(gè)或兩個(gè)頂點(diǎn)，如果該點(diǎn)與三角形頂點(diǎn)重合則放棄該點(diǎn)；（3）調(diào)用Lop優(yōu)化算法，判斷點(diǎn)的影響區(qū)域，對(duì)局部三角網(wǎng)進(jìn)行更新；（4）重復(fù)（2）到（3）步，直到所有點(diǎn)插入三角網(wǎng)；（5）刪除包含超三角形頂點(diǎn)的所有三角形，算法結(jié)束。

2 點(diǎn)的插入或刪除

對(duì)生成的初始三角網(wǎng)進(jìn)行更新，主要是通過插入和刪除點(diǎn)來(lái)完成。對(duì)于需要插入的點(diǎn)集P，主線程首先對(duì)其進(jìn)行掃描，將點(diǎn)分配到所屬區(qū)域的私有隊(duì)列P1、P2、P3…中。然后將工作單元分配到各個(gè)處理器上進(jìn)行執(zhí)行。單點(diǎn)插入過程主要步驟如下：（1）找到包含插入點(diǎn)v的三角形t；（2）檢索所有與t關(guān)聯(lián)的三角形，找到外接圓中包含點(diǎn)v的三角形集D （v）；（3）D （v）的外邊界相連形成一個(gè)多邊形P（v）；（4）將P（v）內(nèi)的三角形邊刪除；（5）連接P（v）的頂點(diǎn)和v形成新的Delaunay三角網(wǎng)D （v）；（6）用D （v）取代D （v）形成新的Delaunay三角網(wǎng)，完成一點(diǎn)插入。刪除點(diǎn)時(shí)只需要找到對(duì)應(yīng)的點(diǎn)，然后將與之關(guān)聯(lián)的點(diǎn)重新構(gòu)造三角網(wǎng)即可。

3 內(nèi)存管理

在多線程程序中，多個(gè)線程同時(shí)對(duì)內(nèi)存進(jìn)行訪問，在創(chuàng)建（刪除）三角形或點(diǎn)時(shí)，每一個(gè)線程都需要調(diào)用內(nèi)核進(jìn)行內(nèi)存的分配（釋放）。這時(shí)會(huì)因?yàn)榇嬖诖罅康逆i競(jìng)爭(zhēng)而花費(fèi)很高比例的時(shí)間，這對(duì)于追求高效率的并行目的是不符的。為了避免這種情況的發(fā)生，可以為每一個(gè)線程分配獨(dú)立的內(nèi)存空間，線程在其中創(chuàng)建數(shù)據(jù)塊，如果數(shù)據(jù)被刪除，則把它還給自己的內(nèi)存池。當(dāng)內(nèi)存池中空間不足時(shí)，線程才會(huì)調(diào)用內(nèi)核申請(qǐng)新的內(nèi)存塊。

4 實(shí)驗(yàn)和分析

由于點(diǎn)集中數(shù)據(jù)點(diǎn)的分布狀態(tài)對(duì)一個(gè)算法的速度和精度都有很大的影響，所以我們采用三種典型的數(shù)據(jù)分布對(duì)算法進(jìn)行測(cè)試，分別為：線性分布、標(biāo)準(zhǔn)分布和均勻分布。

實(shí)驗(yàn)環(huán)境為6核12線程Intel Core i7 4930k CUP（3.4GHz）、16G內(nèi)存。分別將15M不同分布狀態(tài)的點(diǎn)數(shù)據(jù)在多個(gè)線程上運(yùn)行，測(cè)試結(jié)果如表1所示。用加速比來(lái)衡量并行程序的性能和效果。

表1 不同情況下運(yùn)行時(shí)間（秒）

結(jié)果表明并行算法能很大的提高構(gòu)網(wǎng)的速度，且并行數(shù)越多，速度越快。分布狀態(tài)不同的數(shù)據(jù)對(duì)于串行算法執(zhí)行時(shí)間影響更大，而對(duì)于并行算法，隨著并行數(shù)增加，這種影響就越小。這也說明并行算法對(duì)于復(fù)雜地形的數(shù)據(jù)有很好的適應(yīng)性。

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

Delaunay三角網(wǎng)對(duì)DTM模型建立和分析的一種重要手段。文章針對(duì)海量數(shù)據(jù)并行構(gòu)建三角網(wǎng)的要求，提出一種基于數(shù)據(jù)分塊的并行構(gòu)網(wǎng)方法。該方法構(gòu)網(wǎng)前不需要對(duì)元數(shù)據(jù)進(jìn)行刪重、排序等預(yù)處理，實(shí)現(xiàn)點(diǎn)的并行插入和刪除，而且對(duì)不同分布狀態(tài)的數(shù)據(jù)有很好的適應(yīng)性。由于算法可以動(dòng)態(tài)的對(duì)三角網(wǎng)進(jìn)行更新，因此可以方便的對(duì)模型進(jìn)行實(shí)時(shí)編輯，并用于工程計(jì)算和分析，如土石方量計(jì)算、建立DTM模型、等高線繪制等。

參考文獻(xiàn)

[1]芮一康，王結(jié)臣.Delaunay三角網(wǎng)構(gòu)網(wǎng)的分治掃描線算法[J].測(cè)繪學(xué)報(bào)，2007，36（3）：358-362.

[2]袁正午，侯林，彭軍還.點(diǎn)集收集分配的Delaunay三角網(wǎng)快速生成算法及實(shí)現(xiàn)[J].測(cè)繪科學(xué)，2011，36（5）：223-225.

[3]譚仁春，杜清運(yùn)，楊品福，等.地形建模中不規(guī)則三角網(wǎng)構(gòu)建的優(yōu)化算法研究[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，2006，31（5）：436-439.

[4]陳楚江，王德峰.海量數(shù)據(jù)CDT快速建立及其實(shí)時(shí)更新[J].測(cè)繪學(xué)報(bào)，2002，31（3）：262-265.

[5]陳少勤，張駿驍，陳捷，等.地形特征約束的不規(guī)則三角網(wǎng)動(dòng)態(tài)更新方法[J].地理信息世界，2014，21（4）：71-75.

[6]李堅(jiān)，李德仁，邵振峰.一種并行計(jì)算的流數(shù)據(jù)Delaunay構(gòu)網(wǎng)算法[J].武漢大學(xué)學(xué)報(bào)·信息科學(xué)版，2013，38（7）：794-798.

[7]張真.海量數(shù)據(jù)Delaunay三角網(wǎng)的并行構(gòu)建算法[J].計(jì)算機(jī)工程與科學(xué)，2013，35（4）：1-7.

[8]李小麗，陳花竹.基于格網(wǎng)劃分的Delaunay三角剖分算法研究[J].計(jì)算機(jī)與數(shù)字工程，2011（7）：57-59.

作者簡(jiǎn)介：崔水軍（1987-），男，碩士研究生，主要從事地理信息系統(tǒng)應(yīng)用開發(fā)等方面研究。