Delaunay三角网的生成算法研究 应用学专业

Delaunay 三角网的生成算法研究*摘 要 Delaunay 三角网作为一种主要的 DTM 表示法，具有极其广泛的用途。经过二十多年来的研究，它的生成算法已趋于成熟。本文简要介绍了 Delaunay 三角网的定义及其特性，在简单回顾和评价了分割-归并法，逐点插入法，三角网生长法等三类主流算法的基础上，提出了一个融以上算法优点于一体，兼顾空间与时间性能的合成算法。经测试，一般情况下它的运算速度远快于逐点插入法，与分割-归并法相当，较好的情况下快于分割-归并法。关键词 DTM Delaunay 三角网 生成算法 合成算法分类号 TP309A new study of Delaunay triangulation creationAbstract 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.Keywords DTM, Delaunay triangulation, Generation algorithm, Compound algorithm 1 前言 在地学领域，经常需要处理大量分布于地域内的离散数据。由于这些数据分布的不均匀性，就产生了一个如何合理有效地使用这些宝贵数据的问题。1908 年，G.Voronoi 首先在数学上限定了每个离散点数据的有效作用范围，即其有效反映区域信息的范围，并定义了二维平面上的Voronoi 图［1］（以下称为 V-图）。1911 年，A.H.Thiessen 应用 V-图进行了大区域内的平均降水量研究［2］。1934 年，B.Delaunay 由 V-图演化出了更易于分析应用的 Delaunay 三角网［3］（以下称为 D-三角网）。从此，V-图和D-三角网就成了被普遍接受和广泛采用的分析研究区域离散数...