CGAL修改三角剖分后如何跟踪面？Chew细化算法相关疑问

在CGAL的Delaunay三角剖分中，修改剖分后原有Face_handle会失效，Chew细化算法中每次插入点后重建待优化面列表成本较高，针对你遇到的索引问题及相关疑问，解答如下：

问题1：添加新面后，face range中的面索引是否保持不变？ #

不会保持不变。Face_range底层依赖CGAL的Compact_container实现，该容器在插入新元素时，会重用已删除元素的内存槽位，或在扩容时重新排布内存结构，导致原有面的索引发生变化。此外，旧面因剖分修改被销毁后，对应的索引会被回收复用，因此靠索引跟踪面完全不可靠。

问题2：能否获取Face_handle（迭代器）在face range中的索引？ #

直接通过std::distance或index()方法不可行，原因如下：

• 调用std::distance(face_range.begin(), face_handle)触发断言错误，是因为CGAL的Face_handle并非随机访问迭代器，不满足std::distance对随机访问迭代器的要求，底层容器的断言会拦截这种非法操作。
• face_range.index(face_handle)返回异常大值，是因为该方法仅对当前容器中存在的有效面有效，若面已因剖分修改失效（被销毁），调用该方法会返回未定义的数值。

问题3：是否存在其他可在修改三角剖分后跟踪面的方法？ #

有三种可行的替代方案：

• 给面附加自定义标记：使用CGAL::Triangulation_face_base_with_info_2作为三角剖分的面基类，给每个面添加自定义字段（比如批次标记、有效性标识）。插入点后，仅处理新生成的面，并通过标记过滤掉已失效的旧面。
• 利用插入操作的返回值：Delaunay_triangulation_2::insert()会返回插入顶点的Vertex_handle，通过该顶点遍历其相邻的所有面（从vertex->face()开始遍历邻接面），这些就是插入点后新生成的面，直接将这些面加入待优化列表即可，无需重建整个列表。
• 延迟失效检查：无需提前存储所有面的handle或索引，每次处理待优化列表前，先遍历列表中的每个Face_handle，调用is_valid()判断其有效性，移除无效面后，再加入新生成的面。这种方法的遍历成本远低于重建整个列表。

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