Delaunay三角网的生成算法研究分析 计算机专业VIP免费

Delaunay三角网的生成算法研究*摘要Delaunay三角网作为一种主要的DTM表示法，具有极其广泛的用途。经过二十多年来的研究，它的生成算法已趋于成熟。本文简要介绍了Delaunay三角网的定义及其特性，在简单回顾和评价了分割-归并法，逐点插入法，三角网生长法等三类主流算法的基础上，提出了一个融以上算法优点于一体，兼顾空间与时间性能的合成算法。经测试，一般情况下它的运算速度远快于逐点插入法，与分割-归并法相当，较好的情况下快于分割-归并法。关键词DTMDelaunay三角网生成算法合成算法分类号TP309AnewstudyofDelaunaytriangulationcreationAbstractAsoneofthemostimportantDTMmodel,Delaunaytriangulationiswidelyappliedinmanifoldfields.Thispaperintroducesbrieflyitsdefinitionandsignificantproperties.Afterreviewedandassessedsimplytoitsprevalentgenerationalgorithms—divide-conquer,incrementalinsertion,triangulationgrowth,thisarticleprovidesanewupgradealgorithm—compoundalgorithm.Thenewalgorithmtakesadvantagesofdivide-conquerandincrementalinsertionalgorithm.Itusescomputerresourcesoftimeandspacemorereasonably.ThroughtestwithrealDEMdata,itsrunningspeedprovesfarfasterthanthatofincrementalinsertionandmatchestodivide-conquerinaveragecase.Inbettercase,fasterthandivide-conquer.KeywordsDTM,Delaunaytriangulation,Generationalgorithm,Compoundalgorithm1前言在地学领域，经常需要处理大量分布于地域内的离散数据。由于这些数据分布的不均匀性，就产生了一个如何合理有效地使用这些宝贵数据的问题。1908年，G.Voronoi首先在数学上限定了每个离散点数据的有效作用范围，即其有效反映区域信息的范围，并定义了二维平面上的Voronoi图［1］（以下称为V-图）。1911年，A.H.Thiessen应用V-图进行了大区域内的平均降水量研究［2］。1934年，B.Delaunay由V-图演化出了更易于分析应用的Delaunay三角网［3］（以下称为D-三角网）。从此，V-图和D-三角网就成了被普遍接受和广泛采用的分析研究区域离散数据的有力工具。当然，它的应用不仅适用于地学，而且活跃于所有与2.5维分析有关的领域。在GIS中，2.5维的分析处理由DTM（数字地形模型）模型进行。DTM主要由栅格与TIN（不规则三角网）两种数据格式来表示［4，5］，而以后者更为重要。前者的优点是，充分表现了高程的细节变化，拓扑关系简单，算法实现容易，某些空间操纵及存储方便；它的不足之处是，占用巨大的存储空间，不规则的地面特征与规则的数据表示之间的不协调。后者的优点是，高效率的存储，数据结构简单，与不规则的地面特征和谐一致，可以表示线性特征和迭加任意形状的区域边界，易于更新，可适应各种分布密度的数据等；它的局限性是，算法实现比较复杂和困难。在现今的GIS系统中，基本上均支持以上两种数据格式，以TIN为主，栅格为辅，并提供相互转换功能。历经二十余年的不懈努力，TIN的许多算法难关已被攻克。TIN的生成算法中，最终有三种为普遍接受和采用，它们是分割-归并法、逐点插入法和逐步生长法，而又以前二者更为流行。分割-归并法时间效率高，但占用内存空间较多。逐点插入法时间效率较差，占用内存空间较少。本文在此二者基础上，提出了一种综合性能的算法——合成算法。它的时性能优于以上两种算法。2Delaunay三角网的定义及其特性Delaunay三角网是V-图（也称为Thiessen图，Dirichlet图，Vigner-Seithz图）的伴生图形。对它的研究是从对V-图的研究开始的。V-图定义是：假设V={v1,v2,...,vN},N≥3是欧几里德平面上的一个点集，并且这些点不共线，四点不共圆。用d(vi,vj)表示点vi,vj间的欧几里德距离。设x为平面上的点，则区域V(i)={x∈E2|d(x,vi)≤d(x,vj),j=1,2,...,N,j≠I}称为Voronoi多边形（V-多边形）。各点的V-多边形共同组成V-图。平面上的V-图可以看作是点集V中的每个点作为生长核，以相同的速率向外扩张，直到彼此相遇为止而在平面上形成的图形。除最外层的点形成开放的区域外，其余每个点都形成一个凸多边形。D-三角网的定义是：有公共边的V-多边形称为...