基于虚拟网格的高效Delaunay三角网生成算法研究  

High efficient algorithm for building Delaunay triangulation based on virtual grid

作　　者：夏少芳[1] 陈立潮[1] 刘佳[2] 

机构地区：[1]太原科技大学计算机科学与技术学院,山西太原030024 [2]石家庄铁路职业技术学院计算机系,河北石家庄050041

出　　处：《计算机工程与设计》2009年第1期238-240,250,共4页Computer Engineering and Design

基　　金：山西省自然基金项目(20051044)

摘　　要：针对传统逐点插入算法存在时间效率比较低的问题,设计了高效的存储结构,通过引入虚拟网格技术,在三角形定位和点的插入顺序方面作了改进和优化,提出了一种改进的D-三角网生成算法,提高了点插入过程中查找相应三角形的速度,有效的减少了重构三角形的数量,大大改进了逐点插入算法的时间效率。实验结果表明,改进后的算法具有较低的时间复杂度,能快速地生成三角网。Focusing on the problem of the low efficiency about the traditional incremental inserting algorithm, a high efficient data struct is designed and an improved algorithm for building delauny triangulation based on it is proposed. The virtual grid is introduced into the improved algorithm and the insertion order of the points and the algorithm for fast location of the triangle that contain the given point are greatly improved. The algorithm can locate the triangle quickly and reduce the num of the triangles which are need to reconstruct improving the efficiency of the incremental inserting algorithm. The result of simulating shows that the efficiency of the improved algorithm is lower than others and it can produce a Delaunay triangulation net quickly.

关 键 词：不规则三角网 DELAUNAY三角网 逐点插入法 虚拟网格 离散点 三角形定位 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术] TP18[自动化与计算机技术—计算机科学与技术]