Delaunay三角剖分算法

Delaunay三角剖分算法1.三角剖分与Delaunay剖分的定义如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。1.1.三角剖分定义三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段,E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：1.除了端点，平面图中的边不包含点集中的任何点。2.没有相交边。3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。