En geometría computacional , el polígono de visibilidad o región de visibilidad para un punto p en el plano entre obstáculos es la región poligonal posiblemente ilimitada de todos los puntos del plano visibles desde p . El polígono de visibilidad también se puede definir para la visibilidad desde un segmento o un polígono. Los polígonos de visibilidad son útiles en robótica , videojuegos y para determinar posiciones para ubicar instalaciones , como la mejor ubicación de guardias de seguridad en una galería de arte .
Si el polígono de visibilidad está acotado, entonces es un polígono en forma de estrella . Un polígono de visibilidad está acotado si todos los rayos que disparan desde el punto terminan finalmente en algún obstáculo. Este es el caso, por ejemplo, si los obstáculos son los bordes de un polígono simple y p es el interior del polígono. En el último caso, el polígono de visibilidad se puede encontrar en tiempo lineal. [1] [2] [3] [4]
Definiciones
Formalmente, podemos definir el problema del polígono de visibilidad plana como tal. Dejar ser un conjunto de obstáculos (segmentos o polígonos) en . Dejar ser un punto en eso no está dentro de un obstáculo. Luego, el polígono de visibilidad del punto es el conjunto de puntos en , tal que para cada punto en , el segmento no cruza ningún obstáculo en .
Del mismo modo, el polígono de visibilidad de segmento o el polígono de visibilidad de borde es la parte visible en cualquier punto a lo largo de un segmento de línea .
Aplicaciones
Los polígonos de visibilidad son útiles en robótica . Por ejemplo, en la localización de robots , un robot que usa sensores como un lidar detectará obstáculos que puede ver, lo que es similar a un polígono de visibilidad. [5]
También son útiles en videojuegos , con numerosos tutoriales en línea que explican algoritmos simples para implementarlo. [6] [7] [8]
Algoritmos para polígonos de visibilidad de puntos
Se han propuesto numerosos algoritmos para calcular el polígono de visibilidad de puntos. Para diferentes variantes del problema (por ejemplo, diferentes tipos de obstáculos), los algoritmos varían en la complejidad del tiempo.
Algoritmos ingenuos
Los algoritmos ingenuos son fáciles de entender e implementar, pero no son óptimos , ya que pueden ser mucho más lentos que otros algoritmos.
Algoritmo "físico" de fundición uniforme de rayos
En la vida real, un punto brillante ilumina la región visible porque emite luz en todas direcciones. Esto se puede simular disparando rayos en muchas direcciones. Suponga que el punto es y el conjunto de obstáculos es . Entonces, el pseudocódigo se puede expresar de la siguiente manera:
algoritmo ingenuo_bad_algorithm (, ) es : = por : // dispara un rayo con ángulo : = por cada obstáculo en : : = min ( , distancia desde al obstáculo en esta dirección) agregar vértice a regreso
Ahora bien, si fuera posible probar todos los infinitos ángulos, el resultado sería correcto. Desafortunadamente, es imposible probar todas las direcciones debido a las limitaciones de las computadoras. Se puede crear una aproximación lanzando muchos, digamos, 50 rayos espaciados uniformemente. Sin embargo, esta no es una solución exacta, ya que dos rayos adyacentes pueden pasar por alto pequeños obstáculos por completo. Además, es muy lento, ya que uno puede tener que disparar muchos rayos para obtener una solución aproximadamente similar, y el polígono de visibilidad de salida puede tener muchos más vértices de los necesarios.
Ray casting a cada vértice
El algoritmo descrito anteriormente se puede mejorar significativamente tanto en velocidad como en precisión al hacer la observación de que solo es suficiente disparar rayos a los vértices de cada obstáculo. Esto se debe a que las curvas o esquinas a lo largo del límite de un polígono de visibilidad deben deberse a alguna esquina (es decir, un vértice) en un obstáculo.
algoritmo ingenuo_mejor_algoritmo (, ) es : = por cada obstáculo en : para cada vértice de : // dispara un rayo desde a : = distancia desde a : = ángulo de con respecto a por cada obstáculo en : : = min ( , distancia desde a ) agregar vértice a regreso
Es posible que el algoritmo anterior no sea correcto. Vea la discusión en Hablar.
La complejidad temporal de este algoritmo es . Esto se debe a que el algoritmo dispara un rayo a cada uno de los vértices, y para comprobar dónde termina el rayo, tiene que comprobar la intersección con cada uno de los obstáculos. Esto es suficiente para muchas aplicaciones simples como los videojuegos y, como tal, muchos tutoriales en línea enseñan este método. [8] Sin embargo, como veremos más adelante, hay más algoritmos (o incluso más rápidos si el obstáculo es un polígono simple o si hay un número fijo de huecos poligonales).
Algoritmos óptimos para un punto en un polígono simple
Dado un polígono simple y un punto , un algoritmo de tiempo lineal es óptimo para calcular la región en que es visible desde . Este algoritmo se propuso por primera vez en 1981. [2] Sin embargo, es bastante complicado. En 1983, se propuso un algoritmo conceptualmente más simple, [3] que tenía un error menor que fue corregido en 1987. [4]
El último algoritmo se explicará brevemente aquí. Simplemente camina alrededor del límite del polígono., procesando los vértices en el orden en que aparecen, manteniendo una pila de vértices dónde es la parte superior de la pila. La pila constituye los vértices encontrados hasta ahora que son visibles para. Si, posteriormente durante la ejecución del algoritmo, se encuentran algunos vértices nuevos que oscurecen parte de, luego los vértices oscurecidos en se sacará de la pila. Cuando el algoritmo termina,consistirá en todos los vértices visibles, es decir, el polígono de visibilidad deseado. En 2014 se publicó una implementación eficiente [9].
Algoritmos óptimos para un punto en un polígono con huecos
Para un punto en un polígono con agujeros y vértices en total, se puede demostrar que en el peor de los casos, un el algoritmo es óptimo. Dicho algoritmo se propuso en 1995 junto con su prueba de optimalidad. [10] Sin embargo, se basa en el algoritmo de triangulación de polígonos de tiempo lineal de Chazelle, que es extremadamente complejo.
Algoritmos óptimos para un punto entre segmentos.
Segmentos que no se cruzan excepto en sus extremos
Por un punto entre un conjunto de segmentos que no se cruzan excepto en sus extremos, se puede demostrar que en el peor de los casos, un el algoritmo es óptimo. Esto se debe a que un algoritmo de polígono de visibilidad debe generar los vértices del polígono de visibilidad en orden ordenado, por lo que el problema de la clasificación se puede reducir al cálculo de un polígono de visibilidad. [11]
Observe que cualquier algoritmo que calcule un polígono de visibilidad para un punto entre segmentos se puede usar para calcular un polígono de visibilidad para todos los demás tipos de obstáculos poligonales, ya que cualquier polígono se puede descomponer en segmentos.
Divide y conquistaras
En 1987 se propuso un algoritmo de divide y vencerás para calcular el polígono de visibilidad. [12]
Barrido angular
En 1985 [13] y 1986 se propuso un barrido angular , es decir, un algoritmo de barrido de plano rotacional para calcular el polígono de visibilidad . [11] La idea es ordenar primero todos los puntos finales del segmento por ángulo polar y luego iterar sobre ellos en ese orden. Durante la iteración, la línea de eventos se mantiene como un montón . En 2014 se publicó una implementación eficiente [9].
Segmentos que se cruzan generalmente
Para un punto entre segmentos que generalmente se cruzan, el problema del polígono de visibilidad se puede reducir, en tiempo lineal, al problema de la envolvente inferior . Según el argumento de Davenport-Schinzel , el sobre inferior en el peor de los casos ha número de vértices, donde es la función inversa de Ackermann . Un algoritmo óptimo de divide y vencerás en el peor de los casos que se ejecuta enEl tiempo fue creado por John Hershberger en 1989. [14]
Referencias
- ^ Franco P. Preparata y Michael Ian Shamos (1985). Geometría computacional: una introducción . Springer-Verlag . 1ra edición: ISBN 0-387-96131-3 ; Segunda impresión, corregida y ampliada, 1988: ISBN 3-540-96131-3 ; Traducción rusa, 1989: ISBN 5-03-001041-6 .
- ^ a b El Gindy, Hossam; Avis, David (1981). "Un algoritmo lineal para calcular el polígono de visibilidad desde un punto". Revista de algoritmos . 2 (2): 186-197. doi : 10.1016 / 0196-6774 (81) 90019-5 .
- ^ a b Lee, DT (mayo de 1983). "Visibilidad de un polígono simple". Visión por computadora, gráficos y procesamiento de imágenes . 22 (2): 207–221. doi : 10.1016 / 0734-189X (83) 90065-8 .
- ^ a b Joe, Barry; Simpson, RB (1987). "Correcciones al algoritmo de polígono de visibilidad de Lee". BIT Matemáticas numéricas . 27 (4): 458–473. doi : 10.1007 / BF01937271 .
- ^ Guibas, Leonidas; Motwani, Rajeev; Raghavan, Prabhakar (1992). El problema de la localización del robot en dos dimensiones . Simposio ACM-SIAM sobre algoritmos discretos. Sociedad de Matemáticas Industriales y Aplicadas.
- ^ Liow, Nicklaus. "VISTA Y LUZ cómo crear efectos de visibilidad / sombra 2D para tu juego" . Consultado el 9 de mayo de 2014 .
- ^ Patel, Amit (5 de julio de 2012). "Algoritmo de visibilidad 2d" . Consultado el 9 de mayo de 2014 .
- ^ a b Patel, Amit (5 de julio de 2012). "Blobs en juegos: visibilidad 2d" . Consultado el 9 de mayo de 2014 .
- ^ a b Bungiu, Francisc; Hemmer, Michael; Hershberger, John; Huang, Kan; Kröller, Alexander (2014). "Cálculo eficiente de polígonos de visibilidad". arXiv : 1403,3905 [ cs.CG ].
- ^ Heffernan, Paul; Mitchell, Joseph (1995). "Un algoritmo óptimo para calcular la visibilidad en el avión" (PDF) . Revista SIAM de Computación . 24 (1): 184-201. doi : 10.1137 / S0097539791221505 . hdl : 1813/8838 .
- ^ a b Suri, Subhash; O'Rourke, Joseph (1986). Algoritmos óptimos en el peor de los casos para construir polígonos de visibilidad con agujeros . Simposio de Geometría Computacional. ACM . págs. 14-23. doi : 10.1145 / 10515.10517 .
- ^ Arkin, E .; Mitchell, Joseph (1987). Un algoritmo de visibilidad óptimo para un polígono simple con agujeros en forma de estrella (Informe técnico). Investigación de operaciones e ingeniería industrial de la Universidad de Cornell. 746.
- ^ Asano, Tetsuo (1985). Un algoritmo eficiente para encontrar el polígono de visibilidad de una región poligonal con agujeros . Instituto de Ingenieros en Electrónica, Información y Comunicación. 68 . págs. 557–559.
- ^ Hershberger, John (1989). "Encontrar el sobre superior de segmentos de línea en time ". Information Processing Letters . 33 (4): 169-174. doi : 10.1016 / 0020-0190 (89) 90136-1 .
enlaces externos
- http://web.informatik.uni-bonn.de/I/GeomLab/VisPolygon/index.html.en (visibilidad en polígonos simples - applets)
Software
- VisiLibity : una biblioteca C ++ de código abierto y gratuita para cálculos de visibilidad en entornos poligonales planos.
- visibilidad-polígono-js : una biblioteca de Javascript de dominio público para calcular un polígono de visibilidad para un punto entre segmentos utilizando el método de barrido angular.