Delaunay 三角剖分算法

Delaunay 三角剖分算法是一种用于将点集转化为三角网格的算法，它保证了所有的三角形的外接圆不包含其他点。该算法的基本思想是：对于给定的点集，找到一个三角形网格，使得每个三角形的外接圆内部不包含任何其他的点。

具体实现过程如下：

1. 在点集的外围添加一个超级三角形，其中包含所有点。

2. 将点按照任意顺序插入到三角形网格中。

3. 对于每个新加入的点，找到其所在的三角形，将该三角形删除，并将其周围的三角形加入到一个待处理的列表中。

4. 对于待处理的每个三角形，检查是否存在其他点在其外接圆内部，若存在，则将该三角形删除，并将其周围的三角形加入到待处理列表中。

5. 将新的三角形加入到三角形网格中。

6. 重复步骤3-5，直到所有点都被插入到三角形网格中。

7. 将超级三角形和与之相邻的所有三角形删除，得到最终的三角形网格。

Delaunay 三角剖分算法具有许多优秀的性质，例如最小角度性质和最大化最小角度性质，使得它在计算机图形学、计算机辅助设计和有限元分析等领域得到广泛应用。