Utilisez un algorithme de ligne de balayage, en utilisant le fait qu'un polygone rectiligne est défini par ses sommets.
Représentez les sommets avec le rectangle auquel ils appartiennent, par exemple (x, y, #rect). À cet ensemble de points, ajoutez les points qui résultent des intersections de tous les bords. Ces nouveaux points sont de la forme (x, y, final), puisque nous savons déjà qu'ils appartiennent à l'ensemble des points qui en résulte.
maintenant:
- trier tous les points de leur valeur x
- utilisent une ligne de balayage, à partir de la première coordonnée x; pour chaque nouveau point:
- s'il s'agit d'un "point de départ", ajoutez-le à un ensemble temporaire
T. Marquez-le "final" s'il s'agit d'un point du rectangle A et entre les coordonnées y et les points du rectangle B dans T (ou vice versa).
- si elle est un « point d'extrémité », le retirer et son point de départ correspondant de T.
Après cela, tous les points qui sont marqués « final » désignent les sommets du polygone résultant.
Soit N le nombre total de points. En supposant en outre que le fait de tester si nous devons marquer un point comme étant "final" prend du temps O (log (n)) en recherchant T, cet algorithme entier est dans O (N * log (N)).
Notez que la tâche de trouver toutes les intersections peut être incorporée dans l'algorithme ci-dessus, puisque trouver toutes les intersections efficacement est lui-même un algorithme de ligne de balayage habituellement. Notez également que l'ensemble de points qui en résulte peut contenir plus d'un polygone, ce qui rend la reconstruction des polygones de solution hors des sommets "finaux" légèrement plus difficile.
sont les bords du polygone rectiligne et les rectangles parallèles aux axes? –
@Andre - oui - toutes les lignes sont parallèles – jedierikb
Comme première idée, stocker le polygone rectiligne dans un [arbre de segments] (pour deux dimensions) mon esprit. En supposant que les polygones rectilignes sont ceux qui ne changent pas et les rectangles varient. –