c++ - 使用 CGAL 获取多边形相交线

Question

如何使用 CGAL 轻松检索两个相交多边形的交线(从第一个交点到最后一个交点)。请参阅图片进行说明，绿线是我想要的。

目前我使用以下算法，我在其中获取交点多边形，然后找到位于两个多边形边界上的点，这些点应该是交点。这是代码:

Polygon_2 P,Q;
Pwh_list_2                  intR;
Pwh_list_2::const_iterator  it;
CGAL::intersection(P, Q, std::back_inserter(intR));

//Loop through intersection polygons
for (it = intR.begin(); it != intR.end(); ++it) {
    boost::numeric::ublas::vector<double> firstIntersectPoint(3), lastIntersectPoint(3);
    Polygon_2 Overlap = it->outer_boundary();
    typename CGAL::Polygon_2<Kernel>::Vertex_iterator vit;
    int pointNr = 1;

    //Loop through points of intersection polygon to find first and last intersection point.
    for (vit = Overlap.vertices_begin(); vit != Overlap.vertices_end(); ++vit) {
        CGAL::Bounded_side bsideThis = P.bounded_side(*vit);
        CGAL::Bounded_side bsideArg = Q.bounded_side(*vit);
        if (bsideThis == CGAL::ON_BOUNDARY && bsideArg == CGAL::ON_BOUNDARY && pointNr == 1) {
            firstIntersectPoint <<= 0, CGAL::to_double(vit->x()), CGAL::to_double(vit->y());
            pointNr = 2;
        }
        else if (bsideThis == CGAL::ON_BOUNDARY && bsideArg == CGAL::ON_BOUNDARY && pointNr == 2) {
            lastIntersectPoint <<= 0, CGAL::to_double(vit->x()), CGAL::to_double(vit->y());
            pointNr = 2;
        }
    }

    //RESULT
    std::cout << firstIntersectPoint << std::endl;
    std::cout << lastIntersectPoint << std::endl;
}

虽然这可行，但我认为这不是正确的方法。有人可以告诉我这是否是执行此操作的正确方法，或者指导我如何做得更好。

Answer 1

将两个多边形的线段插入二维排列。然后找到度数为 4 的顶点。请注意，在一般情况下，可能会多于 2 个；可能没有，也可能有 1 个。

std::list<X_monotone_curve_2> segments;
for (const auto& pgn : polygons) {
  for (auto it = pgn.curves_begin(); it != pgn.curves_end(); ++it)
    segments.push_back(*it);
}
Arrangement_2 arr;
insert(arr, segments.begin(), segments.end());
for (auto it = arr.begin_vertices(); it != arr.end_vertices(); ++it) {
  if (4 == it->degree())
  ...
}

您可以避免构建“段”列表，而是使用迭代器适配器直接将多边形的段插入到排列中。 (这是纯泛型编程，与 CGAL 无关。)