基于Voronoi最小邻近点集的Delaunay三角化方法  

A Delaunay Triangulation Algorithm Based on Minimum Voronoi Neighbors

作　　者：孟宪海[1] 成文迪 徐博 杨钦[1] 

机构地区：[1]北京航空航天大学计算机学院,北京100191 [2]中国石油天然气勘探开发公司,北京100034

出　　处：《图学学报》2013年第6期36-41,共6页Journal of Graphics

基　　金：国家自然科学基金资助项目(61003110);国家科技重大专项基金资助项目(2011ZX05008-004-10)

摘　　要：针对局部条件下网格生成的需求,提出一种基于节点的Delaunay三角化生成算法,该算法以Delaunay三角形及其对偶Voronoi图的局部性特征为基础,通过在局部搜索最小Voronoi邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用领域。A node-based algorithm of Delaunay triangulation is proposed, which aims at supplying local triangulation requirements. The algorithm is based on the locality of Delaunay triangulation and its dual Voronoi graph. Local Delaunay meshes are generated by searching Minimum Voronoi Neighbors for each point. The background assistant grid is proposed to improve the efficiency. The theoretical proof, programming implementation and efficiency analysis of the algorithm are given. Finally, several practical applications of the algorithm are introduced.

关 键 词：DELAUNAY三角化 最小Voronoi邻近点集 基于节点模式 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]