CGAL折线简化是否非确定性？处理带洞多边形遇结果不一致问题

我尝试简化多个带有共享边界的Polygon_with_holes_2，运行以下C++代码片段时发现，相同几何结构在多次运行后得到的简化结果不同（即简化后的点数存在差异）：

CGAL::Constrained_triangulation_plus_2<CDT> ct;

// 假设此向量已填充多个`Polygon_with_holes_2`
std::vector<CGAL::Polygon_with_holes_2<Scd>> pwh_vector; 

for (const auto &pwh : pwh_vector) {
  ct.insert_constraint(pwh.outer_boundary());
  for (const auto &h : pwh.holes()) {
    ct.insert_constraint(h);
  }
}

CGAL::Polyline_simplification_2::simplify(ct, Cost(), Stop(0.5));

因此我想确认：CGAL的折线简化是否具有非确定性？我在用户手册中未找到相关说明。

我推测可能的原因有两点：一是Constrained_triangulation_plus_2<CDT>的遍历顺序未定义；二是节点优先级判定存在平局，这也能解释为何部分几何频繁出现该现象，部分则从未出现。

这种非确定性给程序调试带来了极大困难，若这是CGAL折线简化的默认特性，请问是否有办法将其关闭？

问题解答 #

1. 非确定性确认
   CGAL的Polyline_simplification_2模块默认确实存在非确定性行为，你的推测完全正确：

• Constrained_triangulation_plus_2内部对约束边的遍历顺序没有明确的定义，不同运行过程中遍历顺序可能不同
• 当多个节点的简化成本（优先级）完全相等时，算法选择简化节点的顺序是随机的，这会直接导致最终简化结果的差异

2. 关闭非确定性的方案
   针对上述原因，可以通过以下方式强制算法输出确定性结果：

• 固定约束插入顺序：在将Polygon_with_holes_2的边界插入三角剖分前，对所有边界点按坐标的字典序（比如先比较x坐标，再比较y坐标）进行排序，确保每次运行时插入点的顺序完全一致
• 自定义成本函数打破平局：在原有成本计算逻辑基础上，加入一个基于节点唯一标识（如点坐标哈希值）的微小偏移量，确保不会出现完全相同的成本值，强制算法按固定顺序处理节点。示例代码如下：

  struct DeterministicCost : public CGAL::Polyline_simplification_2::Squared_distance_cost {
    template <typename CDT>
    boost::optional<typename CDT::Geom_traits::FT>
    operator()(const typename CDT::Vertex_handle& v, const CDT& cdt) const {
      auto cost = Squared_distance_cost::operator()(v, cdt);
      if (!cost) return cost;
      // 基于点坐标生成哈希值，添加微小偏移打破成本平局
      const auto& p = v->point();
      std::size_t hash = std::hash<double>()(p.x()) ^ (std::hash<double>()(p.y()) << 1);
      typename CDT::Geom_traits::FT offset = static_cast<typename CDT::Geom_traits::FT>(hash) * 1e-12;
      return *cost + offset;
    }
  };
  

  调用时替换原成本函数：

  CGAL::Polyline_simplification_2::simplify(ct, DeterministicCost(), Stop(0.5));
  

• 使用确定性优先级队列：如果默认的优先级队列实现不保证平局时的顺序，可以自定义一个严格按成本（含平局打破规则）排序的队列，替换算法默认使用的队列类型，确保每次处理节点的顺序一致

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