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

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

作　　者：刘永和[1] 刘玉芳[1] 王燕平[2] 

机构地区：[1]河南理工大学资环学院,河南焦作454003 [2]河南理工大学图书馆,河南焦作454003

出　　处：《河南理工大学学报（自然科学版）》2007年第3期285-288,共4页Journal of Henan Polytechnic University（Natural Science）

基　　金：河南省自然科学基金资助项目(0124140155)

摘　　要：不规则三角网(TIN)是一种重要的数字高程模型,它一般是基于离散采样点来构建的;构建TIN的算法可归结为由二维平面内的离散点生成Delaunay三角网.目前有很多Delaunay三角网生成算法,但不足之处是已有的算法对三角形之间邻接关系的维护缺乏具体的论述和明确的约定.作者按照凸包切割的思想提出了一种完整的算法,并对三角网的生成和三角形邻接关系维护的具体步骤和约定做了详细论述.编程实验表明:本算法能够正确地将凸包剖分为三角形,且能够保证三角形之间具有正确的邻接关系;当将剩余的非凸包顶点的离散点插入已有的三角形时,仍能保持三角形之间的正确邻接关系.Irregular triangulated networks （TIN） is an built based on spots of discrete samples. The algorithms nay triangles. Now there is many algorithms, but few very important digital elevation model, and it is of TIN generation is dependent on building Delauarticles 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 al- gorithm based on convex hull split idea, and described the steps, contracts of TIN generation and adjacen- cy 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.

关 键 词：不规则三角网 DELAUNAY三角网 凸包 

分 类 号：O189.11[理学—数学]