Delaunay三角網(wǎng)的生成算法研究

摘　要　Delaunay三角網(wǎng)作為一種主要的DTM表示法，具有極其廣泛的用途。經(jīng)過二十多年來的研究，它的生成算法已趨于成熟。本文簡要介紹了Delaunay三角網(wǎng)的定義及其特性，在簡單回顧和評價(jià)了分割-歸并法，逐點(diǎn)插入法，三角網(wǎng)生長法等三類主流算法的基礎(chǔ)上，提出了一個(gè)融以上算法優(yōu)點(diǎn)于一體，兼顧空間與時(shí)間性能的合成算法。經(jīng)測試，一般情況下它的運(yùn)算速度遠(yuǎn)快于逐點(diǎn)插入法，與分割-歸并法相當(dāng)，較好的情況下快于分割-歸并法。
關(guān)鍵詞　DTM　Delaunay三角網(wǎng)　生成算法　合成算法
分類號(hào)　TP309
A new study of Delaunay triangulation creation
Abstract　As one of the most important DTM model, Delaunay triangulation is widely applied in manifold fields. This paper introduces briefly its definition and significant properties. After reviewed and assessed simply to its preva lent generation algorithms—divide-conquer, incremental insertion, triangulation growth, this article provides a new upgrade algorithm—compound algorithm. The new algorithm takes advantages of divide-conquer and incremental insertion algorithm. It uses computer resources of time and space more reasonably. Through test with real DEM data, its running speed proves far faster than that of incremental insertion and matches to divide-conquer in average case. In better case, faster than divide-conquer.
Keywords　DTM, Delaunay triangulation, Generation algorithm, Compound algorithm