识别 CGAL 约束 Delaunay 三角剖分中移除的面

Question

我目前正在使用 CGAL 库及其约束 Delaunay 三角剖分 (CDT) 功能。我的目标是确定在将新点 p 插入三角剖分后从 CDT 中删除的三角形。我尝试通过在插入点之前利用

get_conflicts_and_boundary()

函数识别冲突区域面，然后在插入后将它们与当前面进行比较来实现此目的。

这是我的方法的总结：

1. 在插入点之前，我使用

   get_conflicts_and_boundary()

   查找冲突区域中的面
2. 我将点 p 插入到 CDT 中。
3. 我将之前识别的人脸（冲突区域中的人脸）与当前人脸进行比较，以识别已删除的人脸。

但是，我在这种方法上面临着挑战。方法

CDT#is_face()

和

Face_Handle#is_valid()

似乎无法提供有关面部是否已被删除的准确信息，因为它们总是返回

true

。因此，我不确定如何准确检测已删除的面孔。我什至尝试相互比较角坐标。但看起来被移除的面孔仍然以

triangulation.finite_faces_begin()

的形式返回。

下面是我用来比较插入前后面的顶点的代码片段：

std::vector<Edge> conflictZoneEdges;

std::vector<Face_handle> conflictFaces;
triangulation.get_conflicts_and_boundary(
    point,
    std::back_inserter(conflictFaces),
    std::back_inserter(conflictZoneEdges)
);

triangulation.insert(point);

for (const Face_handle conflictFace : conflictFaces) {
    const Point_2 lhVertex1 = conflictFace->vertex(0)->point();
    const Point_2 lhVertex2 = conflictFace->vertex(1)->point();
    const Point_2 lhVertex3 = conflictFace->vertex(2)->point();

    bool anyEqual = false;
    for (auto fit = triangulation.finite_faces_begin(), end = triangulation.finite_faces_end(); fit != end; ++fit) {
        const Point_2 rhVertex1 = fit->vertex(0)->point();
        const Point_2 rhVertex2 = fit->vertex(1)->point();
        const Point_2 rhVertex3 = fit->vertex(2)->point();
        
        if ((lhVertex1 == rhVertex1) && (lhVertex2 == rhVertex2) && (lhVertex3 == rhVertex3)) {
            anyEqual = true;
            break;
        }
    }
    if (!anyEqual) {
        removedFaces.push_back(conflictFace);
    }
}

我正在寻找一种可靠的方法来识别插入点后已从 CDT 中删除的面的指导。如果有替代方法或特定方法可以帮助完成此任务，我将非常感谢您的见解。

感谢您的协助！

Answer 1

参见

Delaunay_triangulation_2::insert_and_give_new_faces