基于凸包切割的不规则三角网及其邻接关系的生成算法

不规则三角网(TIN)是一种重要的数字高程模型,它一般是基于离散采样点来构建的;构建TIN的算法可归结为由二维平面内的离散点生成Delaunay三角网.目前有很多Delaunay三角网生成算法,但不足之处是已有的算法对三角形之间邻接关系的维护缺乏具体的论述和明确的约定.作者按照凸包切割的思想提出了一种完整的算法,并对三角网的生成和三角形邻接关系维护的具体步骤和约定做了详细论述.编程实验表明:本算法能够正确地将凸包剖分为三角形,且能够保证三角形之间具有正确的邻接关系;当将剩余的非凸包顶点的离散点插入已有的三角形时,仍能保持三角形之间的正确邻接关系.

An algorithm of building TIN and relationship between TIN-triangles based on convex hull split idea

Irregular triangulated networks(TIN) is an very important digital elevation model,and it is built based on spots of discrete samples.The algorithms of TIN generation is dependent on building Delaunay triangles.Now there is many algorithms,but few articles talk of how to manage the adjacency between triangles and we have never seen an explicit contract about it.The paper brought out a complete algorithm based on convex hull split idea,and described the steps,contracts of TIN generation and adjacency maintenance.The programming experiments indicates that this algorithm can correctly split the convex hull of all the points into triangles,guarantee correct adjacency between the triangles,and when the rest points been inserted into the triangles,the adjacency remains correct.