Algorithme de balayage de plan: Comment ordonner les segments après le point d'intersection

Question

J'essaye d'implémenter dans le code C++ l'algorithme de balayage de plan pour les intersections de segment basé sur ce livre: http://www.cs.uu.nl/geobook/. Ils suggèrent d'implémenter la structure d'état du balayage plan en utilisant un arbre de recherche binaire équilibré. J'utilise la structure std :: set pour implémenter la structure d'état mais j'ai des problèmes pour réordonner les segments qui contiennent le point "p" et leur extrémité supérieure est le point "p". Ils ont le même point de coordonnées, ce qui signifie que je ne peux pas les insérer dans std :: set parce qu'il ne permet pas de valeurs répétitives ... J'ai essayé de les insérer avec leur extrémité inférieure, mais ils vont perdre l'ordre dans lequel ils se croisent par une ligne de balayage juste en dessous de "p".

Le pseudo-code qui est dans le livre dit ce qui suit:

6. Insérez les segments en U (p) ∪ C (p) dans Tao. L'ordre des segments dans Tao doit correspondre à l'ordre dans lequel ils sont entrecoupés par une ligne de balayage juste en dessous de p. S'il y a un segment horizontal, il vient dernier parmi tous les segments contenant p.
7. (* Suppression et réinsérer les segments de C (p) inverse l'ordre. *)

Je ne sais pas comment ils vont inverser leur ordre .. Comme j'insérer des segments Dans la structure d'état, je les trierai en fonction de leur coordonnée x d'extrémité supérieure. Je ne sais pas comment échanger leur ordre après une intersection.

Une idée?

Mise à jour: Le livre est ici: https://books.google.com/books?id=C8zaAWuOIOcC mais il y a quelques pages qui n'apparaissent pas. Il est sur le chapitre 2, pages 24, 25 et 26. L'espoir qu'il aide à donner un contexte

Best,

Answer 1

Le prédicat de tri pour le std::set utilisé en tant que structure de données d'état de balayage de plan doit fonctionner comme suit:

1. Il faut (dynamiquement) calculer les coordonnées de l'intersection d'un segment donné de la ligne de balayage pour la position actuelle de la ligne de balayage. En cas d'égalité (lorsque deux segments semblent croiser la ligne de balayage à la même coordonnée), il faut également comparer les angles des deux segments - cela permettra de connaître l'ordre des segments dans l'état. pour les futures positions de la ligne de balayage.

Notez que l'exigence 1. ci-dessus signifie que l'objet sous-jacente doit contenir une référence à la variable de position ligne de balayage, de manière à pouvoir comparer les segments correctement les progrès ligne de balayage. La position de ligne de balayage ne peut pas être stockée dans le prédicat lui-même car vous ne pourrez pas le mettre à jour à partir de votre algorithme (std::set ne donne pas accès à son prédicat par référence).

EDIT

Notez que la responsabilité de maintenir l'ordre correct des segments dans l'ensemble (à savoir les échanger au besoin) est toujours avec l'algorithme - un std::set avec un tel prédicat ne sera pas réordonner automatiquement ses éléments.

Answer 2

Exprimer la fonction de comparaison si le genre est mis sur les y, le mineur sur x. Vous pouvez ensuite insérer des segments avec des valeurs y dupliquées, tant que x est différent. (Si vous avez deux segments identiques, vous devez les manipuler spécialement pour les tests d'intersection de toute façon).

Answer 3

Lorsque vous utilisez std::set l'apparition de deux ou plusieurs éléments sur une valeur y commune ne devrait pas être un problème, en supposant utilisez un comparateur approprié pour la std::set. Je suggère, en plus de la valeur y, comparer et trier par pente. (Exemple d'un comparateur pour un std::set)

Je suggère de ne pas utiliser std :: set pour cela, mais quelque chose comme std :: vector. L'utilisation de std :: vector vous permet d'échanger (std :: swap) les références de certains segments de ligne et d'insérer/supprimer en O (log n) temps si un segment commence/finit, où n est le nombre de segments de ligne. L'idée est que vous maintenez le bon ordre de l'état vous-même tout au long du balayage de ligne en inversant les segments de ligne qui correspondent à une intersection, seule la file d'attente d'événements est une file d'attente de priorité. (SUPPRIMÉE suite au commentaire de @Sneftel, merci pour la perspicacité.)

En ce qui concerne votre approche générale sur l'algorithme de ligne de balayage: L'état (sweep line status) ne représente l'ordre des segments de ligne sur un spécifique (courant) temps dans votre balayage de ligne. Pour le statut de la ligne de balayage, à ma connaissance, il faut utiliser un arbre binaire équilibré (comme mentionné par @Sneftel). Ensuite, vous pouvez conserver l'ordre correct de l'état vous-même tout au long du balayage de ligne en inversant les segments de ligne qui correspondent à une intersection, seul le event queue doit être une sorte de file d'attente de priorité.