一、简介
三角剖分是计算几何领域的主要研究课题之一，其在GIS领域、医学可视化、计算机图形图像处理、曲面重构和三维有限元方法的预处理等领域都有着广泛的应用。
对于平面域上的点集，存在且仅存在一种三角划分，使得所有三角形的最小内角之和为最大，称之为Deluanay三角划分（Deluanay Triangulation）。显然DT使得所形成的每个三角形尽可能接近等边三角形避免病态三角形的出现，因此得到了广泛的应用。对点集进行Deluanay三角划分后，就能很容易得到它的Voronoi图了。
二、定义
假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。
如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。
三角剖分是计算几何领域的主要研究课题之一，其在GIS领域、医学可视化、计算机图形图像处理、曲面重构和三维有限元方法的预处理等领域都有着广泛的应用。
对于平面域上的点集，存在且仅存在一种三角划分，使得所有三角形的最小内角之和为最大，称之为Deluanay三角划分（Deluanay Triangulation）。显然DT使得所形成的每个三角形尽可能接近等边三角形避免病态三角形的出现，因此得到了广泛的应用。对点集进行Deluanay三角划分后，就能很容易得到它的Voronoi图了。
二、定义
假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。
如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。