在CGAL中插入新点时追踪Delaunay三角剖分的变化

高效实现思路 #

CGAL没有直接提供追踪面变化的内置API，但可以利用Delaunay三角剖分的冲突检测机制高效获取移除和新增的面，无需复制整个三角剖分：

• 插入前，通过locate定位新点所在的初始面，再用find_conflicts获取所有与新点冲突的面（这些面会被删除）。
• 插入点后，遍历新顶点的所有相邻面，这些就是插入操作新增的面。

代码示例 #

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <vector>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_2<K> Delaunay;
typedef Delaunay::Face_handle Face_handle;
typedef Delaunay::Point Point;
typedef Delaunay::Vertex_handle Vertex_handle;

void track_triangulation_changes(Delaunay& dt, const Point& p) {
    // 收集插入前要移除的冲突面
    std::vector<Face_handle> removed_faces;
    Delaunay::Locate_type lt;
    int li, lj;
    Face_handle start_face = dt.locate(p, lt, li, lj);
    
    // 处理点在顶点或边上的边界情况
    if (lt == Delaunay::VERTEX) {
        std::cout << "Point coincides with existing vertex, no changes.\n";
        return;
    } else if (lt == Delaunay::EDGE) {
        // 边上的点会触发两个相邻面的冲突
        removed_faces.push_back(start_face);
        removed_faces.push_back(start_face->neighbor(lj));
    } else {
        // 点在面内部，调用冲突检测获取所有待删除面
        dt.find_conflicts(p, start_face, std::back_inserter(removed_faces));
    }

    // 输出移除的面信息
    std::cout << "Removed " << removed_faces.size() << " faces:\n";
    for (const auto& fh : removed_faces) {
        std::cout << "  Face: " << fh->vertex(0)->point() << ", " 
                  << fh->vertex(1)->point() << ", " 
                  << fh->vertex(2)->point() << "\n";
    }

    // 插入新点
    Vertex_handle vh = dt.insert(p);

    // 收集新增的面（围绕新顶点的所有相邻面）
    std::vector<Face_handle> added_faces;
    Delaunay::Face_circulator fc = dt.incident_faces(vh);
    if (fc != 0) {
        Delaunay::Face_circulator start_fc = fc;
        do {
            added_faces.push_back(fc);
            ++fc;
        } while (fc != start_fc);
    }

    // 输出新增的面信息
    std::cout << "Added " << added_faces.size() << " faces:\n";
    for (const auto& fh : added_faces) {
        std::cout << "  Face: " << fh->vertex(0)->point() << ", " 
                  << fh->vertex(1)->point() << ", " 
                  << fh->vertex(2)->point() << "\n";
    }
}

int main() {
    // 初始化三角剖分
    Delaunay dt;
    std::vector<Point> initial_points = {Point(0,0), Point(0,1), Point(1,0), Point(1,1)};
    dt.insert(initial_points.begin(), initial_points.end());

    // 插入新点并追踪变化
    Point new_point(0.5, 0.5);
    track_triangulation_changes(dt, new_point);

    return 0;
}

关键说明 #

• 冲突面原理：find_conflicts会找出所有外接圆包含新点的面，这些面在插入新点后会被拆分或删除，是三角剖分中需要移除的部分。
• 新增面获取：插入点后，incident_faces可以遍历新顶点的所有相邻面，这些都是插入操作生成的新三角形。
• 性能优势：这种方法复用了Delaunay插入的内部冲突检测逻辑，额外开销极小，完全适配GB级大型数据集的场景，避免了复制整个三角剖分的低效操作。

内容的提问来源于stack exchange，提问作者user13583700