Delaunay三角网的生成算法研究

A new study of Delaunay triangulation creation

Ｄｅｌａｕｎａｙ三角网作为一种主要的ＤＴＭ表示法，具有极其广泛的用途。经过二十多年来的研究，它的生成算法已趋于成熟。本文简要介绍了Ｄｅｌａｕｎａｙ三角网的定义及其特性，在简单回顾和评价了分割－归并法，逐点插入法，三角网生长法等三类主流算法的基础上，提出了一个融以上算法优点于一体，兼顾空间与时间性能的合成算法。经测试，一般情况下它的运算速度远快于逐点插入法，与分割－归并法相当，较好的情况下快于分割－归并法。

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 prevalent 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.