先边界后方差的改进的三角网划分算法

Improved algorithm in triangulation with first boundary and second variance

基于Delaunay三角网划分的两个特性:最大最小特性,空外接圆特性,构网过程分3步:生成边界,构造内三角网,对边界与内三角网之间的空洞进行处理。具体实现过程:先通过边界点集构造边界,再在已生成的边界内,利用区域生长法思想,以及方差的方法对非边界点集进行插入,来构造内三角网,最后采用等比例划分方法处理边界与边界内三角网之间的空洞。实验结果表明,改进后,不需要对每次生成的边进行判断是否是边界边,插入的点是否是边界点的处理,也避免了复杂构网的过程,并且快速实现了物体表面Delaunay三角网划分的目的。且上述方法简单,快捷,易于实现,经实验证明是行之有效的。

Based on the two features of the Delaunay triangulation： Maximum and minimum feature, empty circumcircle feature, the procedure of building triangulation network need three steps： Created boundary, built up the interiorTriangulation network, coped with the hole between the boundary and the interiorTriangulation network. The detail process is that build up the boundary through the boundary point set at first, then it can form the inside network by the method of variance and area growth-inserted the non-boundary points, at the last, it was deal with the hole between the boundary and the interior network boundary in the method of equal proportion partition. After the improved. that needn＇t judge the new born edges and the points are weather or not belonged to the boundary, and avoided the complex process. Therefore; the Delannay triangulation surface of the object is acquired as quickly as possible, and the method of what have descripted, demonstrated that it is shortcut, simplify and easy realize, and is very effective in the experiment.