一种改进的螺旋边三角剖分算法

提出了一种改进的螺旋边三角剖分算法.本算法引用“自然邻近点集”的概念,以螺旋边三角剖分算法的边界环为基础向外生长三角形,以包围盒算法搜索边界点的邻近点集,估计边界点的法向量,将边界点及其邻近点集投影到切平面上并进行局部二维Delaunay三角剖分,从而确定边界点的自然邻近点集,最后将自然邻近点集以适当的方式添加到边界环上.这样,既避免了拼接问题又能搜索到自然邻近点集,三角剖分后的网格基本上接近最优Delaunay网格.实验结果表明,本算法能高效、稳定地重构出散乱数据点的三角网格.

An improved algorithm of spiraling edge triangulation

An improved algorithm of spiraling edge triangulation was put forward.The concept of "neighbor points" was introduced.The new outwards triangles were grown on the basis of the boundary circle of the spiraling edge triangulation arithmetic.Neighbor points of boundary edge by encircling box arithmetic were searched and normal vectors of boundary points estimated.The boundary points and their neighbors were projected onto the tangency plane to get Delaunay triangulation to obtain its natural neighbors.Natural neighbors were properly added onto the boundary edge.The improved arithmetic was able to avoid putting mesh hence finding natural neighbors.The triangulation mesh basically approached the optimum Delaunay meshes.The experimental results showed that this algorithm could effectively and stably reconstruct triangular mesh of scattered data points.