Obtenir la ligne d'intersection des polygones avec CGAL

Question

Comment puis-je retrouver facilement la ligne d'intersection (du premier au dernier point d'intersection) de deux polygones qui se croisent avec CGAL. Voir l'image pour la clarification, la ligne verte est ce que je veux.

Actuellement j'utilise l'algorithme suivant, où je reçois le polygone d'intersection et de trouver les points qui sont sur les limites du polygone, ceux-ci devraient être les points d'intersection. Ici, il est dans le 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; 
} 

Bien que cela fonctionne, je ne pense pas que ce soit la bonne façon de procéder. Quelqu'un peut-il me donner une indication si c'est la bonne façon de le faire ou donner à mes pointeurs comment le faire mieux.

Answer 1

Insérez les segments des deux polygones dans un arrangement 2D. Ensuite, trouvez les sommets avec le degré 4. Notez que dans le cas général il pourrait y avoir plus de 2; il pourrait y avoir aucune, et il pourrait y avoir 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()) 
    ... 
} 

Vous pouvez éviter la construction de la liste « segments » et au lieu d'insérer directement les segments des polygones dans l'arrangement à l'aide d'un adaptateur iterator. (Ceci est une pure programmation générique et rien à voir avec le CGAL.)