Graphe de visibilité
La mise en forme de cet article est à améliorer ().
La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».
En géométrie algorithmique et en planification de mouvement de robot[1], un graphe de visibilité est un graphe d'emplacements visibles les uns les autres, généralement pour un ensemble de points et d'obstacles dans le plan euclidien. Chaque nœud du graphique représente un emplacement de point et chaque arête représente une connexion visible entre deux points. Autrement dit, pour tout segment reliant deux emplacements ne traversant aucun obstacle, une arête est tracée entre eux dans le graphe.
Applications[modifier | modifier le code]
Les graphes de visibilité peuvent être utilisés pour trouver les plus courts chemins euclidiens parmi un ensemble d'obstacles polygonaux dans le plan : le chemin le plus court entre deux obstacles suit des segments de droite sauf aux sommets des obstacles, où il peut tourner. Un plus court chemin euclidien est donc un plus court chemin dans un graphe de visibilité qui a pour nœuds les points de départ et d'arrivée et les sommets des obstacles . Par conséquent, le problème du plus court chemin euclidien peut être décomposé en deux sous-problèmes plus simples: la construction du graphe de visibilité puis l'application d'un algorithme de recherche du plus court chemin tel que l'algorithme de Dijkstra. Pour planifier le mouvement d'un robot qui a une taille non négligeable par rapport aux obstacles, une approche similaire peut être utilisée après avoir agrandi les obstacles pour compenser la taille du robot[2]. Lozano-Pérez & Wesley (1979) attribuent la méthode du graphe de visibilité pour les plus courts chemins euclidiens à la recherche en 1969 de Nils Nilsson sur la planification de mouvements pour Shakey le robot, et citent également une description de 1973 de cette méthode par les mathématiciens russes MB Ignat'yev, FM Kulakov et AM Pokrovskiy.
Les graphes de visibilité peuvent également être utilisés pour calculer l'emplacement des antennes radio ou comme outil dans l'architecture et l'urbanisme grâce à l'analyse par graphes de visibilité.
Le graphe de visibilité d'un ensemble de points situés sur une ligne peut être interprété comme une représentation graphique théorique d'une série chronologique[3]. Ce cas particulier construit un pont entre les séries temporelles, les systèmes dynamiques et la théorie des graphes.
Caractérisation[modifier | modifier le code]
Le graphe de visibilité d'un polygone simple a les sommets du polygone comme emplacements de points et l'extérieur du polygone comme seul obstacle. Les graphes de visibilité des polygones simples doivent être des graphes hamiltoniens : la frontière du polygone forme un cycle hamiltonien dans le graphe de visibilité. On sait que tous les graphes de visibilité n'induisent pas un simple polygone. Cependant, une caractérisation algorithmique efficace des graphes de visibilité de polygones simples reste inconnue. Ces graphes n'appartiennent pas à de nombreuses familles connues de graphes bien structurés : il se peut qu'il ne s'agisse pas de graphes parfaits, de graphes circulaires ou de graphes cordal [4]. Une exception à ce phénomène est que les graphes de visibilité des polygones simples sont des graphes cop-win [5].
Problèmes connexes[modifier | modifier le code]
Le problème de la galerie d’art consiste à trouver un ensemble de points relativement petit tel que tous les autres points soient visibles depuis cet ensemble en tenant compte d'un certain nombre d'obstacle. Certaines formes du problème des galeries d’art peuvent être interprétées comme la recherche d’un ensemble dominant dans un graphe de visibilité.
Les bitangentes d'un système de polygones ou de courbes sont des droites tangentes à deux polygones à la fois sans en couper un autre, ou à deux points distincts de la courbe. Les bitangentes d'un ensemble de polygones, restreints à une ligne reliant les deux points dont ils sont tangents, forment un sous-ensemble du graphe de visibilité qui a les sommets du polygone comme nœuds et les polygones eux-mêmes comme obstacles. L'approche par graphe de visibilité du problème du chemin le plus court euclidien peut être accélérée en formant un graphique à partir des bitangentes au lieu d'utiliser toutes les arêtes de visibilité, puisqu'un chemin euclidien le plus court ne peut entrer ou sortir de la limite d'un obstacle que le long d'une bitangente.
Voir également[modifier | modifier le code]
- Analyse du graphique de visibilité
- Analyse spatiale architecturale floue
- Syntaxe spatiale
Liens externes[modifier | modifier le code]
- VisiLibity : une bibliothèque C++ open source gratuite d'algorithmes de visibilité à virgule flottante et de types de données pris en charge. Ce logiciel peut être utilisé pour calculer des graphiques de visibilité d'environnements polygonaux comportant des trous polygonaux. Une interface Matlab est également incluse.
Notes et références[modifier | modifier le code]
- Niu, Savvaris, Tsourdos et Ji, « Voronoi-Visibility Roadmap-based Path Planning Algorithm for Unmanned Surface Vehicles », Journal of Navigation, vol. 72, no 04, , p. 850–874 (ISSN 0373-4633, DOI 10.1017/S0373463318001005, lire en ligne)
- de Berg et al. 2000, sections 5.1 et 5.3; Lozano-Pérez et Wesley 1979.
- Lacasa, Luque, Ballesteros et Luque, « From time series to complex networks: The visibility graph », Proceedings of the National Academy of Sciences, vol. 105, no 13, , p. 4972–4975 (PMID 18362361, PMCID 2278201, DOI 10.1073/pnas.0709247105, arXiv 0810.0920)
- Ghosh, « On recognizing and characterizing visibility graphs of simple polygons », Discrete & Computational Geometry, vol. 17, no 2, , p. 143–162 (ISSN 0179-5376, DOI 10.1007/BF02770871)
- Lubiw, Snoeyink et Vosoughpour, « Visibility graphs, dismantlability, and the cops and robbers game », Computational Geometry, vol. 66, , p. 14–27 (DOI 10.1016/j.comgeo.2017.07.001, MR 3693353, arXiv 1601.01298)
