一种改进的Delaunay三角化算法研究

Delaunay三角化在诸多应用领域具有极其广泛用途,也一直是计算机图形图像学和科学计算可视化技术的重要研究内容。针对二维约束Delaunay三角化问题,提出一种快速生成算法。该算法首先建立环形矩形,分环分治平面散乱点;然后依据Delaunay三角形的性质,从外环到内环分治逐步插入新点,一环插入完毕后,整理有效Delaunay三角形;依次循环快速生成二维约束Delaunay三角网格。本算法计算过程简单,计算效率高,程序编写十分容易无需复杂的递归过程,技巧性地解决了二维约束Delaunay三角化问题。实例证明,该算法具有较好的应用效果。

A research of ameliorating arithmetic about delaunay trangulation

Delaunay triangulation has been widely used in manifold fields and is long researched content in computer Graphics & Image and visualization in scientific computing.This paper introduces a fast algorithm for generating 2D constrained Delaunay triangulation.In this method,a ring-shaped rectangle is applied to separate 2D disheveled points at first,and then,according to the property of Delaunay triangulation,new points are inserted from outside ring to inside ring,step by step.And then the effective Delaunay triangulation is found out by the end of every ring.So that the 2D Delaunay triangular grid is formed quickly.This algorithm is very simple and efficient and there is no recursive computation in it.Moreover,the 2D constrained Delaunay triangulation is solved by a new technique.The algorithm is approved by its applications in engineering.