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

图学学报

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

出版日期:2013-12-31 发布日期:2015-06-19

A Delaunay Triangulation Algorithm Based on Minimum Voronoi Neighbors

Online:2013-12-31 Published:2015-06-19

摘要/Abstract

摘要： 针对局部条件下网格生成的需求，提出一种基于节点的Delaunay 三角化
生成算法，该算法以Delaunay 三角形及其对偶Voronoi 图的局部性特征为基础，通过在局部
搜索最小Voronoi 邻近点集，来生成约束点附近的局部网格，通过建立背景索引网格，来提
高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果，并给出了算法的应用
领域。

关键词: Delaunay 三角化, 最小Voronoi 邻近点集, 基于节点模式

Abstract: 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.

Key words: Delaunay triangulation, minimum Voronoi neighbors, node-based model

孟宪海，成文迪，徐博，杨钦. 基于Voronoi 最小邻近点集的Delaunay 三角化方法[J]. 图学学报.

Meng Xianhai, Cheng Wendi, Xu Bo, Yang Qin. A Delaunay Triangulation Algorithm Based on Minimum Voronoi Neighbors[J]. Journal of Graphics.