Delaunay三角化补洞C++实现

Delaunay三角化是一种计算几何技术，用于将一组点分割成一系列不相交的三角形，使得任意一点都不在其他三角形的凸包内。如果存在某个点不在生成的三角网内部，这被称为“空洞”（hole）。为了修复这样的补洞，通常会使用一种称为Voronoi Diagram的互补结构，然后通过添加额外的边界边缘来填充这个空洞。

在C++中实现Delaunay三角化并补洞，可以利用如CGAL（Computational Geometry Algorithms Library）等库提供的现成算法，它们提供了高效的算法和数据结构。以下是大致步骤：

1. **构建Delaunay三角图**：首先，你需要创建一个点集，并使用库函数构建Delaunay三角图。

#include <CGAL/Delaunay_triangulation_2.h>
CGAL::Delaunay_triangulation_2<Kernel> dt(points.begin(), points.end());

2. **检测和标记空洞**：检查Voronoi图中的“孤立”顶点，它们对应于三角图的空洞区域。

3. **生长边界**：从空洞边界的顶点开始，逐渐向外扩展，形成新的三角形，直到边界填满。

std::vector<Point> boundary;
CGAL::is_border_point(dt, hole_vertex, boundary);
// 然后对边界点进行遍历，连接它们形成新三角形

4. **合并新三角形**：将新增的三角形加入到原始的Delaunay图中。

5. **输出结果**：最后得到的是一个去除了空洞、完整的三角网格。