Algorithme de sweep line

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 ou un sommet d'un segment, ou 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