如何从 CGAL 中的段 delaunay 图中提取边？

Question

我需要找到带孔的凹多边形的中轴。我正在使用 CGAL。我目前的做法是：

1. 构建多边形2D segment delaunay graph
2. 提取结果输出段（平分线）
3. 测试每个线段以确定它是否在多边形内
4. 生成的线段集将构成多边形的中轴

我可以构建 SDG，并且测试边缘应该是直截了当的，但我正在努力提取 SDG 的边缘，或者更确切地说是相应的 Voronoi 图。应该有几种类型的边缘：点、线和抛物线。

我该怎么做？我走在正确的轨道上吗？

我也知道我可以使用提供的方法之一遍历图形的边缘，我理解这个 returns 面和相对于边缘的顶点。但是我如何使用它来获取平分线的端点？

Answer 1

您可以使用函数draw_dual() or draw_skeleton()。抛物线弧将被分段近似。如果您需要对输出进行更多控制，可以查看该方法的实现。

您可以使用这样的 class 来收集对象：

struct Collector
{
  std::vector<Ray_2> rays;
  std::vector<Line_2> lines;
  std::vector<Segment_2> segs;

  void operator<<(const Ray_2& p){rays.push_back(p);}
  void operator<<(const Line_2& p){lines.push_back(p);}
  void operator<<(const Segment_2& p){segs.push_back(p);}
};