Get Polygon Intersection Line with CGAL

Question

How can I easily retrieve the intersection line (from the first to the last intersection point) of two intersecting polygons with CGAL. See the image for clarification, the green line is what I want.

Currently I use the following algorithm, where I get the intersection polygon and then find the points which are on both polygon boundaries, these should be the intersection points. Here it is in code:

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;
}

Although this works I don't think it is the correct way to go. Can somebody give me an indication whether this is the correct way to do this or give my pointers how to do it better.

Answer 1

Insert the segments of the two polygons into a 2D Arrangement. Then find the vertices with degree 4. Notice that in the general case there might be more than 2; there might be none, and there might be 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())
  ...
}

You can avoid the construction of the 'segments' list and instead directly insert the segments of the polygons into the arrangement using an iterator adapter. (This is pure generic programming and nothing to do with CGAL.)