二维限定Voronoi网格剖分细化算法

2D Conforming Voronoi Mesh Generation by Refinement Algorithm

给出了限定点、限定线在Voronoi网格中存在的充要条件,提出了二维限定Voronoi网格细化算法,通过设置初始检测带,然后细分检测带来实现限定Voronoi网格的剖分;同时证明了该算法对于任意平面线段图输入限定条件的收敛性.对于生成的限定Voronoi网格,给出了尺寸控制和质量控制算法,并对其时间复杂度进行了分析.最后通过实例验证了文中算法的有效性.

The conditions that guarantee the existence of constrained points and segments in Voronoi mesh are presented, which puts forward a novel two-dimensional conforming Voronoi mesh refinement algorithm that completes the mesh by setting up initial examining strip set and subdivision of the strip set. The algorithm is guaranteed to terminate on arbitrary input planar straight line graph conditions. The relative size and quality control method is also presented. The analysis of the efficiency is given and solid examples are shown to demonstrate the validation of the algorithm.