En la geometría computacional y la planificación del movimiento del robot , un gráfico de visibilidad es un gráfico de ubicaciones intervisibles, generalmente para un conjunto de puntos y obstáculos en el plano euclidiano . Cada nodo del gráfico representa la ubicación de un punto y cada borde representa una conexión visible entre ellos. Es decir, si el segmento de línea que conecta dos ubicaciones no atraviesa ningún obstáculo, se dibuja un borde entre ellos en el gráfico. Cuando el conjunto de ubicaciones se encuentra en una línea, esto puede entenderse como una serie ordenada. Por tanto, los gráficos de visibilidad se han ampliado al ámbito del análisis de series de tiempo .
Aplicaciones
Los gráficos de visibilidad se pueden utilizar para encontrar caminos euclidianos más cortos entre un conjunto de obstáculos poligonales en el plano: el camino más corto entre dos obstáculos sigue segmentos de línea recta excepto en los vértices de los obstáculos, donde puede girar, por lo que el camino más corto euclidiano es el camino más corto en un gráfico de visibilidad que tiene como nodos los puntos de inicio y destino y los vértices de los obstáculos. [1] Por lo tanto, el problema de la ruta más corta euclidiana puede descomponerse en dos subproblemas más simples: construir el gráfico de visibilidad y aplicar un algoritmo de ruta más corta como el algoritmo de Dijkstra al gráfico. Para planificar el movimiento de un robot que tiene un tamaño no despreciable en comparación con los obstáculos, se puede utilizar un enfoque similar después de expandir los obstáculos para compensar el tamaño del robot. [1] Lozano-Pérez y Wesley (1979) atribuyen el método del gráfico de visibilidad para los caminos más cortos euclidianos a la investigación en 1969 de Nils Nilsson sobre la planificación del movimiento para el robot Shakey , y también citan una descripción de 1973 de este método por los matemáticos rusos MB Ignat ' yev, FM Kulakov y AM Pokrovskiy.
Los gráficos de visibilidad también pueden usarse para calcular la ubicación de antenas de radio , o como una herramienta utilizada dentro de la arquitectura y la planificación urbana a través del análisis de gráficos de visibilidad .
El gráfico de visibilidad de un conjunto de ubicaciones que se encuentran en una línea se puede interpretar como una representación gráfica teórica de una serie de tiempo. [2] Este caso particular construye un puente entre series de tiempo , sistemas dinámicos y teoría de grafos .
Caracterización
El gráfico de visibilidad de un polígono simple tiene los vértices del polígono como ubicaciones de puntos y el exterior del polígono como único obstáculo. Los gráficos de visibilidad de polígonos simples deben ser gráficos hamiltonianos : el límite del polígono forma un ciclo hamiltoniano en el gráfico de visibilidad. Se sabe que no todos los gráficos de visibilidad inducen un polígono simple. De hecho, los gráficos de visibilidad de polígonos simples no poseen las características de unas pocas clases especiales de gráficos. [3]
Problemas relacionados
El problema de la galería de arte es el problema de encontrar un pequeño conjunto de puntos de modo que todos los demás puntos que no son obstáculos sean visibles desde este conjunto. Ciertas formas del problema de la galería de arte pueden interpretarse como encontrar un conjunto dominante en un gráfico de visibilidad.
Los bitangentes de un sistema de polígonos o curvas son líneas que tocan dos de ellos sin penetrarlos en sus puntos de contacto. Los bitangentes de un conjunto de polígonos forman un subconjunto del gráfico de visibilidad que tiene los vértices del polígono como sus nodos y los propios polígonos como obstáculos. El enfoque del gráfico de visibilidad para el problema de la ruta más corta euclidiana puede acelerarse formando un gráfico a partir de los bitangentes en lugar de usar todos los bordes de visibilidad, ya que una ruta más corta euclidiana solo puede entrar o salir del límite de un obstáculo a lo largo de un bitangente. [4]
Ver también
Notas
- ^ a b de Berg y col. (2000) , secciones 5.1 y 5.3; Lozano-Pérez y Wesley (1979) .
- ^ Lacasa, Lucas; Luque, Bartolo; Ballesteros, Fernando; Luque, Jordi; Nuño, Juan Carlos (2008). "De series temporales a redes complejas: el gráfico de visibilidad" . Actas de la Academia Nacional de Ciencias . 105 (13): 4972–4975. arXiv : 0810.0920 . doi : 10.1073 / pnas.0709247105 . PMC 2278201 . PMID 18362361 .
- ^ Ghosh, SK (1 de marzo de 1997). "Sobre el reconocimiento y caracterización de gráficos de visibilidad de polígonos simples" . Geometría discreta y computacional . 17 (2): 143-162. doi : 10.1007 / BF02770871 . ISSN 0179-5376 .
- ^ de Berg y col. (2000) , pág. 316.
Referencias
- de Berg, Mark; van Kreveld, Marc; Overmars, Mark ; Schwarzkopf, Otfried (2000), "Capítulo 15: Gráficos de visibilidad", Geometría computacional (2ª ed.), Springer-Verlag , págs. 307–317 , ISBN 978-3-540-65620-3.
- Lozano-Pérez, Tomás; Wesley, Michael A. (1979), "Un algoritmo para planificar caminos sin colisiones entre obstáculos poliédricos", Comunicaciones del ACM , 22 (10): 560–570, doi : 10.1145 / 359156.359164.
enlaces externos
- VisiLibity: una biblioteca C ++ de código abierto libre de algoritmos de visibilidad de punto flotante y tipos de datos de soporte. Este software se puede utilizar para calcular gráficos de visibilidad de entornos poligonales con agujeros poligonales. También se incluye una interfaz Matlab.