Algorithme de Bentley-Ottmann

En géométrie algorithmique, l'algorithme de Bentley-Ottmann est un algorithme de sweep line pour trouver les intersections d'un ensemble de segments (en). C'est une généralisation de l'algorithme de Shamos et Hoey qui vérifie si un ensemble de segments possède des intersections ou non. Pour n segments avec k intersections, la complexité en temps de l'algorithme de Bentley-Ottmann est O((n + k) log n). Dans le cas où k = o(n² / log n), c'est une amélioration de l'algorithme naïf qui teste chaque paire de segments en temps O(n²).

L'algorithme a été développé à l'origine par Jon Bentley et Thomas Ottmann (1979). Il est décrit plus en détail dans les articles de Preparata et Shamos (1985), O'Rourke (1998), et de Berg et al. (2000). Bien que des algorithmes asymptotiquement plus rapides sont connus, l'algorithme de Bentley-Ottmann reste un choix pratique en raison de sa simplicité et de faibles besoins en mémoire.

Stratégie générale

L'idée principale de Bentley et Ottmann est d'utiliser une approche sweep line, dans laquelle une ligne verticale L se déplace de gauche à droite dans le plan, intersectant les segments en entrée au fur et à mesure de son déplacement. L'algorithme est décrit sans perte de généralité sous les conditions suivantes :

1. Aucune des deux extrémités du segment ou des intersections n'ont la même abscisse ;
2. Aucune extrémité de segment n'est confondue avec l'extrémité d'un autre segment ;
3. Il n'y a pas plus de deux segments qui se coupent en un même point.

Dans un tel cas, la ligne L coupera toujours les segments en entrée en un ensemble de points dont l'ordonnancement vertical consiste en un ensemble fini d'événements discrets. Ainsi, le mouvement continu de L peut être décomposé en une suite finie d'étapes, et simulé par un algorithme qui s'exécute en un temps fini.

Deux types d'événements peuvent se produire au cours de cette simulation. Lorsque L balaie l'extrémité d'un segment s, l'intersection de L avec s est ajoutée ou supprimée de l'ensemble — ordonné verticalement — de points d'intersection. Ces événements sont faciles à prévoir car les extrémités de segments sont connus dès le début de l'algorithme. Le reste des événements se produit lorsque L balaie un croisement entre deux segments s et t. Ces événements peuvent également être prédits à partir du fait que, juste avant l'événement, les points d'intersection de L avec s et t sont adjacents dans l'ordre vertical des points d'intersection.

L'algorithme de Bentley-maintient lui-même des structures de données représentant les points d'intersection (ordonnés verticalement) de la ligne de balayage avec les segments, et une collection d'événements futurs potentiels formés par des paires adjacentes de points d'intersection. Il traite chaque événement tour à tour en mettant à jour ses structures de données pour stocker l'ensemble des intersections.

Structures de données

Afin de gérer efficacement les points d'intersection de la ligne de balayage L avec les segments et la séquence des événements à venir, l'algorithme de Bentley-Ottmann utilise deux structures de données :

• Un arbre binaire de recherche, contenant l'ensemble des segments qui intersectent L, triés selon l'ordonnée des points d'intersection. Ces points ne sont pas représentés explicitement dans l'arbre binaire. L'algorithme de Bentley-Ottmann insère un nouveau segment s dans cette structure de données lorsque la ligne L atteint l'extrémité gauche p de ce segment. La position correcte de s dans l'arbre binaire de recherche peut être déterminé par une recherche dichotomique : chaque étape de la dichotomie vérifie si p est au-dessus ou en dessous d'un autre segment intersecté par L. Ainsi, l'insertion peut être effectuée en temps logarithmique. L'algorithme de Bentley-Ottmann va également supprimer des segments de l'arbre binaire de recherche et chercher des segments voisins d'autres segments (immédiatement au-dessus ou en dessous). Ces opérations peuvent être effectuées en utilisant uniquement la structure de l'arbre, sans référence à la géométrie sous-jacente des segments.
• Une file de priorité (dite « file d'événements »), utilisée pour stocker une séquence d'événements futurs potentiels dans l'algorithme. Chaque événement est associé à un point p dans le plan : soit une extrémité, soit une intersection. L'événement se produit lorsque la ligne L croise p. Ainsi, les événements peuvent être ordonnés par les abscisses de leurs points associés. Dans l'algorithme de Bentley-Ottmann, les événements potentiels futurs sont des extrémités de segments qui n'ont pas encore été balayées ou bien des points d'intersection de deux segments qui sont chacun immédiatement au-dessus ou au-dessous de l'autre.

L'algorithme n'a pas besoin de garder explicitement une représentation de la ligne L ou de sa position dans le plan. La position de L est plutôt représentée indirectement : c'est la ligne verticale passant par le point traité le plus récemment dans la file d'événements.

L'arbre binaire de recherche peut être implémenté comme n'importe quel arbre équilibré, à l'exemple d'un arbre rouge-noir. L'essentiel est que les insertions, les suppressions et les recherches soient faits en temps logarithmique. De même, la file de priorité peut être un tas binaire ou n'importe quelle autre structure du file en temps logarithmique. Des structures plus évoluées comme le tas de Fibonacci ne sont pas nécessaires.

Algorithme détaillé

L'algorithme de Bentley-Ottmann effectue les étapes suivantes :

1. Initialiser une file de priorité Q d'événements futurs potentiels. Chaque événement est associé à un point du plan et ordonné selon l'abscisse de ce point. Au début de l'algorithme, Q contient un événement pour chaque extrémité des segments.
2. Initialiser un arbre binaire de recherche T des segments qui intersectent la ligne L, triés selon l'ordonnée des intersections. Initialement, T est vide.
3. Tant que Q n'est pas vide, trouver et retirer l'événement de Q associé au point p d'abscisse minimale. Déterminer de quel type d'événement il s'agit afin d'appliquer un des cas suivants :
   • Si p est l'extrémité gauche d'un segment s, insérer s dans T. Trouver les segments r et t qui sont immédiatement en dessous et au-dessus de s dans T (s'ils existent). Si leur intersection forme un événement futur potentiel dans la file d'événements, le supprimer. Si s intersecte r ou t, ajouter les intersections comme des événements futurs potentiels dans la file d'événements.
   • Si p est l'extrémité droite d'un segment s, retirez s de T. Trouver les segments r et t qui ont été (avant le retrait de s) immédiatement au-dessus et en dessous de lui dans T (si ces segments existent). Si r et t s'intersectent, ajouter ce point d'intersection comme un événement futur potentiel dans la file d'événements.
   • Si p est le point d'intersection de deux segments s et t (avec un s au-dessous de t à gauche du point p), échanger la position de s et t dans T. Trouver les segments r et u (s'ils existent) qui sont immédiatement en dessous et au-dessus de t et s respectivement (après l'échange). Supprimer les éventuelles intersections rs et tu de la file d'événements. Si r et t s'intersectent ou si s et u s'intersectent, ajouter les intersections correspondantes dans la file d'événements.

Analyse

Il est possible de montrer par récurrence que l'algorithme traite un événement pour chaque extrémité de segment ou point d'intersection, ordonné selon l'abscisse de ce point. En effet, une fois un événement traité, l'événement suivant (si c'est une intersection) doit être le croisement de deux segments adjacents dans l'ordre des segments représentés par T. Puisque l'algorithme traite toutes les intersections entre segments adjacents comme de futurs événements potentiels, le prochain événement correct sera forcément présent dans la file d'événements. En conséquence, il trouve toutes les intersections des segments en entrée ce qui constitue le problème initial.

L'algorithme de Bentley-Ottmann traite une séquence de 2n + k événements, où n désigne le nombre de segments et k désigne le nombre d'intersections. Chaque cas est traité par un nombre constant d'opérations dans l'arbre binaire de recherche et la file d'événements. Puisque la file d'événements ne contient que des extrémités du segment et les intersections entre les segments adjacents, elle ne contient jamais plus de 3n événements. Ainsi, toutes les opérations se font en temps O(log n) et la durée totale de l'algorithme est O((n + k) log n).

Si les intersections trouvées par l'algorithme n'ont pas besoin d'être stockées une fois qu'elles ont été trouvées, l'espace utilisé par l'algorithme à n'importe quel étape est O(n) : chacun des n segments correspond au plus à un nœud de l'arbre binaire de recherche T et la file d'événements contient au plus 3n éléments. Cette complexité spatiale est due à Brown (1981). La version originale de l'algorithme était légèrement différente : les événements d'intersection de deux segments n'étaient pas retirés de Q lorsque d'autres événements rendaient ces segments non adjacents. Ceci entraîne une utilisation de plus d'espace.

Chen et Chan (2003) ont décrit une version très économe en mémoire de l'algorithme de Bentley-Ottmann. La plupart des informations y sont encodées dans l'ordre des segments de l'entrée de l'algorithme, ce qui requiert seulement O(log²n) blocs mémoire. Cependant, l'algorithme est ralenti d'un facteur logarithmique pour l'accès à l'information encodée.

Cas particuliers et problèmes de précision numérique

La description de l'algorithme ci-dessus suppose que les segments ne sont pas verticaux, que les extrémités de segments ne se chevauchent pas, que les intersections ne sont formées que par deux segments et que deux points d'événement ne peuvent avoir la même abscisse. Cependant, ces hypothèses ne sont pas valides pour la plupart des applications du problème. Bentley et Ottmann (1979) ont suggéré de perturber légèrement les coordonnées des segments en entrée pour éviter ce genre de coïncidences numériques sans préciser comment. De Berg et al. (2000) ont mis au point les procédures suivantes pour gérer les cas particuliers :

• Trier les points d'événement de même abscisse selon leur ordonnée pour pouvoir les traiter. Cette modification gère à la fois le problème des points de même abscisse et le problème des segments verticaux. Les étapes nécessaires pour traiter un segment vertical sont alors essentiellement les mêmes que celles d'un segment quelconque avec une très forte pente.
• Définir un segment comme un fermé contenant ses extrémités. Ainsi, deux segments qui partagent une extrémité ou un segment qui contient l'extrémité d'un autre segment généreront une intersection.
• Lorsque plusieurs segments se coupent en un même point, créer et traiter un événement unique pour cette intersection. Les mises à jour de l'arbre binaire de recherche causées par cet événement peuvent impliquer la suppression de tous les segments dont c'est l'extrémité droite, l'insertion de nouveaux segments dont c'est l'extrémité gauche et l'inversion de l'ordre des autres segments contenant ce point d'événement. La sortie de l'algorithme décrit par de Berg et al. (2000) consiste alors en l'ensemble des points d'intersection de segments, marqués par les segments auxquels ils appartiennent, plutôt que l'ensemble des paires de segments de lignes qui se coupent.

Pour la correction de l'algorithme, il est nécessaire de déterminer (sans approximation) les relations « en dessous » et « au-dessus » entre une extrémité et un segment et de hiérarchiser correctement les points d'événement. Pour cette raison, il est standard d'utiliser des coordonnées entières pour les extrémités des segments et d'utiliser des coordonnées rationnelles exactes pour les intersections à l'aide de l'arithmétique multiprécision. Il est cependant possible d'accélérer les calculs et les comparaisons de coordonnées à l'aide de calculs en virgule flottante et en vérifiant si les valeurs calculées de cette manière sont suffisamment précises pour être utilisées sans aucune possibilité d'erreur. Les calculs arithmétiques exacts requis pour une implémentation naïve de l'algorithme de Bentley-Ottmann peuvent exiger cinq fois le nombre de bits de précision des coordonnées de segments en entrée. Toutefois, Boissonat et al. (2000) ont décrit des modifications de l'algorithme pour réduire la précision requise à deux fois le nombre de bits des entrées.

Algorithmes plus rapides

O(n log n) est un minorant inévitable pour la complexité temporelle de l'algorithme de Bentley-Ottmann. Il équivaut au minorant du problème de la détection d'intersection de segments dans un modèle algébrique de calcul utilisant des arbres de décision. Cependant, la dépendance en k, le nombre d'intersections est améliorable. Clarkson (1988) et Mulmuley (1988) ont fourni des algorithmes probabilistes pour construire un graphe planaire dont les sommets sont les extrémités et les intersections de segments, et dont les arêtes sont des morceaux de segments reliant ces sommets. La complexité en temps de ces algorithmes est en O(n log n + k). Le même problème a été résolu de manière déterministe avec la même borne temporelle O(n log n + k) par Chazelle et Edelsbrunner (1992). Cependant, la construction de cet arrangement comme un ensemble nécessite O(n + k) d'espace mémoire, supérieur à la complexité spatiale en O(n) de l'algorithme de Bentley-Ottmann. Balaban (1995) a décrit un algorithme différent qui répertorie toutes les intersections en temps O(n log n + k) et en espace O(n).

Si les segments et leurs extrémités forment les arêtes et les sommets d'un graphe connexe (éventuellement avec les intersections), la borne temporelle en O(n log n) de l'algorithme de Bentley-Ottmann peut aussi être réduite. Comme Clarkson, Cole et Tarjan (1992) l'ont montré, il existe dans ce cas un algorithme probabiliste pour résoudre ce problème en temps O(n log* n + k) où la fonction log* désigne le logarithme itéré, qui croit beaucoup plus lentement que le logarithme. Un algorithme probabiliste semblable d'Eppstein, Goodrich et Strash (2009) permet de résoudre le même problème en temps O(n + k log⁽ⁱ⁾n) pour toute constante i où log⁽ⁱ⁾ désigne la fonction obtenue par itération de la fonction logarithme i fois. Le premier de ces algorithmes est de complexité temporelle linéaire pour peu que k soit plus grand que n d'un facteur log⁽ⁱ⁾n pour toute constante i. Au contraire, le second algorithme prend un temps linéaire à condition que k soit plus petit que n d'un facteur log(i)n. Ces deux algorithmes consistent à appliquer l'algorithme de Bentley-Ottmann sur de petits échantillons aléatoires de l'entrée.

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bentley–Ottmann algorithm » (voir la liste des auteurs).

Références

• (en) I. J. Balaban, « An optimal algorithm for finding segments intersections », Proc. 11th ACM Symp. Computational Geometry,‎ 1995, p. 211-219 (DOI 10.1145/220279.220302)
• (en) U. Bartuschka, K. Mehlhorn et S. Näher, « A robust and efficient implementation of a sweep line algorithm for the straight line segment intersection problem », Proc. Worksh. Algorithm Engineering,‎ 1997 (lire en ligne)
• (en) J. Bentley et T. Ottmann, « Algorithms for reporting and counting geometric intersections », IEEE Transactions on Computers, vol. C-28,‎ 1979, p. 643-647 (DOI 10.1109/TC.1979.1675432)
• (en) Mark de Berg, Marc van Kreveld, Mark Overmars et Otfried Schwarzkopf, « Chapter 2: Line segment intersection », Computational Geometry,‎ 2000, p. 19-44
• (en) J.-D. Boissonat et F. D. Preparata, « Robust plane sweep for intersecting segments », SIAM Journal on Computing, vol. 29,‎ 2000, p. 1401-1421 (DOI 10.1137/S0097539797329373, lire en ligne)
• (en) K. Q. Brown, « Comments on "Algorithms for Reporting and Counting Geometric Intersections" », IEEE Transactions on Computers, vol. C-30,‎ 1981, p. 147 (DOI 10.1109/tc.1981.6312179)
• (en) Bernard Chazelle et Herbert Edelsbrunner, « An optimal algorithm for intersecting line segments in the plane », Journal of the ACM, vol. 39,‎ 1992, p. 1-54 (DOI 10.1145/147508.147511)
• (en) E. Y. Chen et T. M. Chan, « A space-efficient algorithm for segment intersection », Proc. 15th Canadian Conference on Computational Geometry,‎ 2003 (lire en ligne)
• (en) K. L. Clarkson, « Applications of random sampling in computational geometry, II », Proc. 4th ACM Symp. Computational Geometry,‎ 1998, p. 1-11 (DOI 10.1145/73393.73394)
• (en) K. L. Clarkson, R. Cole et R. E. Tarjan, « Randomized parallel algorithms for trapezoidal diagrams », International Journal of Computational Geometry and Applications, vol. 2,‎ 1992, p. 117-133 (DOI 10.1142/S0218195992000081). Corrigendum, 2 (3) : 341 – 343.
• (en) D. Eppstein, M. Goodrich et D. Strash, « Linear-time algorithms for geometric graphs with sublinearly many crossings », Proc. 20th ACM-SIAM Symp. Discrete Algorithms (SODA 2009),‎ 2009, p. 150-159 (arXiv 0812.0893)
• (en) K. Mulmuley, « A fast planar partition algorithm, I », Proc. 29th IEEE Symp. Foundations of Computer Science (FOCS 1988),‎ 1988, p. 580-589 (DOI 10.1109/SFCS.1988.21974)
• (en) J. O'Rourke, Computational Geometry in C, Cambridge University Press, 1998, 2^e éd., 376 p. (ISBN 978-0-521-64976-6), « Section 7.7 : Intersection of segments », p. 263-265
• (en) F. P. Preparata et M. I. Shamos, Computational Geometry : An Introduction, Springer-Verlag, 1985, « Section 7.2.3 : Intersection of line segments », p. 278-287
• (en) J. Pach et M. Sharir, « On vertical visibility in arrangements of segments and the queue size in the Bentley–Ottmann line sweeping algorithm », SIAM Journal on Computing, vol. 20, n^o 3,‎ 1991, p. 460-470 (DOI 10.1137/0220029, MR 1094525)
• (en) M. I. Shamos et D. Hoey, « Geometric intersection problems », 17th IEEE Conf. Foundations of Computer Science (FOCS 1976),‎ 1976, p. 208-215 (DOI 10.1109/SFCS.1976.16)

Liens externes

• (en) M. Smied, « Computing intersections in a set of line segments: the Bentley–Ottmann algorithm » [PDF], 2003