- Algorithme de sweep line
-
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.
Sommaire
Historique
Applications
Recherche d'intersections entre segments
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ï
Références
Mark de Berg, Mark van Kreveld, Mark Overmars, Otfried Cheong, né Schwarzkopf, Computational Geometry : Algorithms and Applications, Springer (ISBN 3-540-65620-0)
- p. 19-42
Catégories :- Wikipédia:ébauche informatique théorique
- Algorithme
Wikimedia Foundation. 2010.