Algorithme de sweep line

algorithme utilisant une "ligne de balayage" virtuelle pour résoudre des problèmes dans l'espace euclidien

En géométrie algorithmique, un algorithme de sweep line (ligne de balayage) est un type d'algorithme utilisant une "ligne de balayage" virtuelle pour résoudre des problèmes dans l'espace euclidien.

Historique

modifier

Applications

modifier

Recherche d'intersections entre segments

modifier

Une sweep line est utilisée dans l'algorithme de recherche d'intersections entre segments présenté par de Berg, van Kreveld, Overmars et Schwazkopf. Dans celui-ci, chaque point d'évènement est soit un sommet d'un segment, soit une intersection entre deux segments; à chaque point, il est testé si deux segments voisins et traversés par la ligne se croisent[CG 1]. Ce principe est aussi celui de l'algorithme de Bentley-Ottmann dont la complexité temporelle est linéarithmique.

Construction de diagrammes de Voronoï

modifier
Animation représentant l'exécution de l'algorithme de Fortune, qui permet la construction de diagrammes de Voronoï

L'algorithme de Fortune est un algorithme sweep line.

Références

modifier

(en) Mark de Berg, Mark van Kreveld, Mark Overmars, Otfried Cheong, né Schwarzkopf, Computational Geometry : Algorithms and Applications, Springer, 367 p. (ISBN 978-3-540-65620-3)

  1. p. 19-42