Trouver le point d'intersection des segments et la liste des segments intersectés pour chaque point d'intersection

Question

J'essaie d'utiliser CGAL pour trouver «tous les points d'intersection» ET «segments intersectés pour chaque point d'intersection» d'une liste de segments en 2D. Je veux utiliser l'algorithme de Bentley-Ottmann pour certaines raisons. La bibliothèque CGAL a une implémentation C++ de cet algorithme appelé Sweepline 2 mais avec cela je ne peux trouver que des points d'intersection. Existe-t-il d'autres implémentations dans CGAL? ou comment puis-je résoudre ce problème?

Answer 1

Edit: La solution vraiment rapide serait juste pour générer tous les points d'intersection en utilisant la ligne de balayage 2, boucle à travers tous les points d'intersection générés, et pour chaque enregistrement de point d'intersection des deux coordonnées est le point et tous les segments de ligne contenant ce pointer dans une structure de votre choix.

---

Une solution rapide (mais pas le plus efficace) est de:

//Probably start off with a struct to store your information 
struct intersection{ 
    //This stores the x and y position of the intersection. 
    int[2] xyCoords; 
    //This stores the segment ids or indexes of the intersection line segments. 
    //For example, if the 1st and 5th line segment intersect, you would store 1 and 5 in here. 
    int[2] segmentIDs; 
} 

Ensuite, il suffit de créer un vecteur de la struct intersection de sorte que vous pouvez stocker toutes vos différentes intersections.

vector<intersection> intersectionVector; 

Ensuite, il suffit boucle à travers tous les segments de ligne que vous avez dans quelque chose de semblable à ce qui suit:

for (int i = 0; i < numSegments; i++){ 
    for (int j = 0; j < numSegments; j++){ 
     //Don't look at the same points.   
     if (i == j) 
      continue; 
     //See below for pseudocode for this part. 
    } 
} 

Maintenant, pour remplir ce bloc, au lieu de réinventer quoi que ce soit simplement se référer à How do you detect where two line segments intersect?. Comme le montre le lien ci-dessus, calculer les valeurs de r × s et (q - p) × r où × est le produit vectoriel croisé. A partir de là, utilisez simplement les blocs if/else pour rendre compte des quatre cas (ctrl f pour "Maintenant il y a quatre cas:") si vous vous souciez des détails. Si vous voulez juste ce que vous avez souligné dans votre question, vérifiez la validité du cas 3. S'il est valide, stockez les index de vos segments de ligne ainsi que les coordonnées x et y dans le vecteur/la structure que vous utilisez .

La seule chose supplémentaire que vous devez faire est d'utiliser le calcul u et l'appliquer à votre deuxième segment de ligne des deux que vous vérifiez, afin de stocker les coordonnées x y de l'intersection.