Algorithme de sweep line

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant la géométrie image illustrant l’informatique théorique
Cet article est une ébauche concernant la géométrie et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 | modifier le code]

Applications[modifier | modifier le code]

Recherche d'intersections entre segments[modifier | modifier le code]

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].

Construction de diagrammes de Voronoï[modifier | modifier le code]

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

Références[modifier | modifier le code]

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

  1. p. 19-42