Delaunay三角划分算法

简介：
Delaunay三角划分算法是一种几何结构构建技术，用于创建点集的唯一三角网，确保网格中无其他点在任意三角形外接圆内。此法广泛应用于计算机图形学、地理信息系统及科学计算等领域。 Delaunay三角剖分算法 1. 三角剖分与Delaunay剖分的定义 如何将一个散点集合分割成不均匀的三角形网格，这就是所谓的散点集的三角剖分问题。对于数值分析和图形学而言，这项预处理技术至关重要。 1.1 三角剖分定义 假设V是一个二维实数域上的有限点集，边e由这个点集中的一些端点构成，并且E为所有这样的边的集合。那么该点集V的一个三角剖分T=(V,E)可以表示成一个平面图G，同时满足以下条件： 1. 除了线段的两个端点外，平面图中的任何一条边都不包含其他散点。 2. 图中没有相交的边。 3. 平面图的所有区域都是由三角形构成，并且这些所有三角形共同构成了该散点集V的凸包。