Delaunay三角剖分算法

点集的三角剖分(Triangulation)，对数值分析(比如有限元分析)以及图形学来说，都是极为重要的一项预处理技术。尤其是Delaunay三角剖分，由于其独特性，关于点集的很多种几何图都和Delaunay三角剖分相关，如Voronoi图，EMST树，Gabriel图等。Delaunay三角剖分有最大化最小角，"最接近于规则化的"的三角网和唯一性(任意四点不能共圆)两个特点。该问题图示如下：