Delaunay三角網的并行構建和更新

崔水軍 尹文亭

摘 要：文章提出一種Delaunay三角網并行構建和更新算法。該算法中先將點數據進行格網劃分，然后將每塊區域作為一個工作單元進行構網，當相鄰區域的三角網構建完畢，就將相鄰區域進行合并，最終生成一個完整的三角網。

關鍵詞：Delaunay三角網；并行；動態更新；加速比

引言

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

并行算法采用數據分塊[8]的思想，首先將點數據按給定閾值（實驗中發現閾值選擇受實驗環境影響）進行格網劃分，每一個數據塊形成一個獨立的工作單元。每一個工作單元只負責所屬區域內三角網的構建更新。利用計算機單機多核的優勢，可以同時將多個工作單元分配給計算機進行處理。最后將相鄰的區域進行合并，最終完成三角網的構建。每一個工作單元所負責的工作主要有三方面：初始三角網的構建、點的插入和刪除，下面將分別闡述。

1 初始三角網構建

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

2 點的插入或刪除

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

3 內存管理

在多線程程序中，多個線程同時對內存進行訪問，在創建（刪除）三角形或點時，每一個線程都需要調用內核進行內存的分配（釋放）。這時會因為存在大量的鎖競爭而花費很高比例的時間，這對于追求高效率的并行目的是不符的。為了避免這種情況的發生，可以為每一個線程分配獨立的內存空間，線程在其中創建數據塊，如果數據被刪除，則把它還給自己的內存池。當內存池中空間不足時，線程才會調用內核申請新的內存塊。

4 實驗和分析

由于點集中數據點的分布狀態對一個算法的速度和精度都有很大的影響，所以我們采用三種典型的數據分布對算法進行測試，分別為：線性分布、標準分布和均勻分布。

實驗環境為6核12線程Intel Core i7 4930k CUP（3.4GHz）、16G內存。分別將15M不同分布狀態的點數據在多個線程上運行，測試結果如表1所示。用加速比來衡量并行程序的性能和效果。

表1 不同情況下運行時間（秒）

結果表明并行算法能很大的提高構網的速度，且并行數越多，速度越快。分布狀態不同的數據對于串行算法執行時間影響更大，而對于并行算法，隨著并行數增加，這種影響就越小。這也說明并行算法對于復雜地形的數據有很好的適應性。

5 結束語

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

參考文獻

[1]芮一康，王結臣.Delaunay三角網構網的分治掃描線算法[J].測繪學報，2007，36（3）：358-362.

[2]袁正午，侯林，彭軍還.點集收集分配的Delaunay三角網快速生成算法及實現[J].測繪科學，2011，36（5）：223-225.

[3]譚仁春，杜清運，楊品福，等.地形建模中不規則三角網構建的優化算法研究[J].武漢大學學報·信息科學版，2006，31（5）：436-439.

[4]陳楚江，王德峰.海量數據CDT快速建立及其實時更新[J].測繪學報，2002，31（3）：262-265.

[5]陳少勤，張駿驍，陳捷，等.地形特征約束的不規則三角網動態更新方法[J].地理信息世界，2014，21（4）：71-75.

[6]李堅，李德仁，邵振峰.一種并行計算的流數據Delaunay構網算法[J].武漢大學學報·信息科學版，2013，38（7）：794-798.

[7]張真.海量數據Delaunay三角網的并行構建算法[J].計算機工程與科學，2013，35（4）：1-7.

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

作者簡介：崔水軍（1987-），男，碩士研究生，主要從事地理信息系統應用開發等方面研究。