El problema de la ubicación del punto es un tema fundamental de la geometría computacional . Encuentra aplicaciones en áreas que se ocupan del procesamiento de datos geométricos: gráficos por computadora , sistemas de información geográfica (GIS), planificación de movimiento y diseño asistido por computadora (CAD).
En su forma más general, el problema es, dada una partición del espacio en regiones disjuntas, determinar la región donde se encuentra un punto de consulta. Como aplicación de ejemplo, cada vez que uno hace clic con el mouse para seguir un enlace en un navegador web , este problema debe resolverse para determinar qué área de la pantalla de la computadora se encuentra debajo del puntero del mouse. Un caso especial simple es el problema del punto en el polígono . En este caso, necesitamos determinar si el punto está dentro, fuera o en el límite de un solo polígono.
En muchas aplicaciones, necesitamos determinar la ubicación de varios puntos diferentes con respecto a la misma partición del espacio. Para resolver este problema de manera eficiente, es útil construir una estructura de datos que, dado un punto de consulta, determine rápidamente qué región contiene el punto de consulta (por ejemplo, Diagrama de Voronoi ).
Caso plano
En el caso plano, se nos da una subdivisión plana S , formada por múltiples polígonos llamados caras, y necesitamos determinar qué cara contiene un punto de consulta. Es posible realizar una búsqueda de fuerza bruta de cada cara utilizando el algoritmo de punto en polígono , pero generalmente no es factible para subdivisiones de alta complejidad. Varios enfoques diferentes conducen a estructuras de datos óptimos, con O ( n espacio) de almacenamiento y O (log n tiempo de consulta), donde n es el número total de vértices en S . Para simplificar, asumimos que la subdivisión plana está contenida dentro de un cuadro delimitador cuadrado.
Descomposición de la losa
La estructura de datos más simple y más temprana para lograr O (log n tiempo) fue descubierto por Dobkin y Lipton en 1976. Se basa en la subdivisión de S usando líneas verticales que pasan a través de cada vértice en S . La región entre dos líneas verticales consecutivas se llama losa. Observe que cada losa está dividida por segmentos de línea que no se cruzan y que cruzan completamente la losa de izquierda a derecha. La región entre dos segmentos consecutivos dentro de A corresponde losa a una cara única de S . Por lo tanto, reducimos nuestro problema de ubicación de puntos a dos problemas más simples:
- Dada una subdivisión del plano en losas verticales, determine qué losa contiene un punto dado.
- Dada una losa subdividida en regiones por segmentos que no se cruzan y que cruzan completamente la losa de izquierda a derecha, determine qué región contiene un punto dado.
El primer problema se puede resolver mediante una búsqueda binaria en la coordenada x de las líneas verticales en el tiempo O (log n ). El segundo problema también se puede resolver en tiempo O (log n ) mediante búsqueda binaria. Para ver cómo, observe que, como los segmentos no se cruzan y cruzan completamente la losa, los segmentos se pueden clasificar verticalmente dentro de cada losa.
Si bien este algoritmo permite la ubicación de puntos en tiempo logarítmico y es fácil de implementar, el espacio requerido para construir las losas y las regiones contenidas dentro de las losas puede ser tan alto como O ( n ²), ya que cada losa puede atravesar una fracción significativa del segmentos.
Varios autores notaron que los segmentos que cruzan dos losas adyacentes son en su mayoría iguales. Por lo tanto, el tamaño de la estructura de datos se puede reducir significativamente. Más específicamente, Sarnak y Tarjan barren una línea vertical l de izquierda a derecha sobre el plano, mientras mantienen los segmentos que se cruzan l en un árbol rojo-negro persistente . Esto les permite reducir el espacio de almacenamiento a O ( n ), mientras se mantiene el tiempo de consulta O (log n ).
Subdivisiones monótonas
Una cadena monótona (vertical) es una ruta tal que la coordenada y nunca aumenta a lo largo de la ruta. Un polígono simple es monótono (vertical) si está formado por dos cadenas monótonas, con el primer y último vértice en común. Es posible agregar algunas aristas a una subdivisión plana, con el fin de hacer que todas las caras sean monótonas, obteniendo lo que se llama una subdivisión monótona. Este proceso no agrega ningún vértice a la subdivisión (por lo tanto, el tamaño sigue siendo O ( n )), y se puede realizar en tiempo O ( n log n ) mediante barrido plano (también se puede realizar en tiempo lineal, usando triangulación poligonal ). Por tanto, no hay pérdida de generalidad, si restringimos nuestra estructura de datos al caso de subdivisiones monótonas, como hacemos en esta sección.
La debilidad de la descomposición de la losa es que las líneas verticales crean segmentos adicionales en la descomposición, lo que dificulta la obtención de O ( n ) espacio de almacenamiento. Edelsbrunner , Guibas , y Stolfi descubrieron una estructura de datos óptima que sólo utiliza los bordes en una subdivisión monótona. La idea es usar cadenas verticales monótonas, en lugar de usar líneas verticales para dividir la subdivisión.
Convertir esta idea general en una estructura de datos eficaz y real no es una tarea sencilla. Primero, necesitamos poder calcular una cadena monótona que divida la subdivisión en dos mitades de tamaños similares. En segundo lugar, dado que algunos bordes pueden estar contenidos en varias cadenas monótonas, debemos tener cuidado de garantizar que el espacio de almacenamiento sea O (n). En tercer lugar, probar si un punto está en el lado izquierdo o derecho de una subdivisión monótona lleva O ( n ) tiempo si se realiza de manera ingenua.
Los detalles sobre cómo resolver los dos primeros problemas están más allá del alcance de este artículo. Mencionamos brevemente cómo abordar el tercer problema. Usando la búsqueda binaria, podemos probar si un punto está a la izquierda oa la derecha de una cadena monótona en el tiempo O (log n ). Como necesitamos realizar otra búsqueda binaria anidada a través de cadenas O (log n ) para determinar realmente la ubicación del punto, el tiempo de consulta es O (log² n). Para lograr un tiempo de consulta O (log n ), necesitamos usar una cascada fraccionada , manteniendo los punteros entre los bordes de diferentes cadenas monótonas.
Refinamiento de triangulación
Un polígono con m vértices se puede dividir en m –2 triángulos. Lo cual se puede demostrar por inducción a partir de un triángulo. Existen numerosos algoritmos para triangular un polígono de manera eficiente, el más rápido tiene O ( n ) en el peor de los casos. Por lo tanto, podemos descomponer cada polígono de nuestra subdivisión en triángulos y restringir nuestra estructura de datos al caso de subdivisiones formadas exclusivamente por triángulos. Kirkpatrick da una estructura de datos para la ubicación del punto en las subdivisiones triangulados con O ( n espacio) de almacenamiento y O (log n tiempo de consulta).
La idea general es construir una jerarquía de triángulos. Para realizar una consulta, comenzamos por encontrar el triángulo de nivel superior que contiene el punto de consulta. Dado que el número de triángulos de nivel superior está limitado por una constante, esta operación se puede realizar en O (1) tiempo. Cada triángulo tiene punteros a los triángulos que cruza en el siguiente nivel de la jerarquía, y el número de punteros también está limitado por una constante. Procedemos con la consulta encontrando qué triángulo contiene el punto de consulta nivel por nivel.
La estructura de datos se construye en el orden opuesto, es decir, de abajo hacia arriba. Comenzamos con la subdivisión triangulada y elegimos un conjunto independiente de vértices para eliminar. Después de eliminar los vértices, volvemos a triangular la subdivisión. Debido a que la subdivisión está formada por triángulos, un algoritmo codicioso puede encontrar un conjunto independiente que contenga una fracción constante de los vértices. Por lo tanto, el número de pasos de eliminación es O (log n ).
Descomposición trapezoidal
Un enfoque aleatorio de este problema, y probablemente el más práctico, se basa en la descomposición trapezoidal o mapa trapezoidal. Se obtiene una descomposición trapezoidal disparando balas verticales que suben y bajan desde cada vértice en la subdivisión original. Las balas se detienen cuando golpean un borde y forman un nuevo borde en la subdivisión. De esta manera, obtenemos un subconjunto de la descomposición de la losa, con solo O ( n ) aristas y vértices, ya que para cada vértice en la subdivisión original solo agregamos dos nuevos vértices y aumentamos el número de aristas en cuatro.
No es fácil ver cómo usar una descomposición trapezoidal para la ubicación de puntos, ya que ya no se puede realizar una búsqueda binaria similar a la utilizada en la descomposición de la losa. En cambio, necesitamos responder una consulta de la misma manera que el enfoque de refinamiento de triangulación, pero la estructura de datos se construye de arriba hacia abajo. Inicialmente, construimos una descomposición trapezoidal que contiene solo el cuadro delimitador y ningún vértice interno. Luego, agregamos los segmentos de la subdivisión, uno por uno, en orden aleatorio, refinando la descomposición trapezoidal. Usando el análisis hacia atrás , podemos mostrar que el número esperado de trapezoides creados para cada inserción está limitado por una constante.
Construimos un grafo acíclico dirigido , donde los vértices son los trapezoides que existieron en algún punto del refinamiento, y los bordes dirigidos conectan los trapezoides obtenidos por subdivisión. La profundidad esperada de una búsqueda en este dígrafo, comenzando desde el vértice correspondiente al cuadro delimitador, es O (log n ) [ aclaración necesaria ] .
Mayores dimensiones
No se conocen estructuras de datos de ubicación de puntos generales con espacio lineal y tiempo de consulta logarítmico para dimensiones superiores a 2 [ cita requerida ] . Por lo tanto, debemos sacrificar el tiempo de consulta o el espacio de almacenamiento, o restringirnos a algún tipo de subdivisión menos general.
En el espacio tridimensional, es posible responder consultas de ubicación de puntos en O (log² n ) utilizando el espacio O ( n log n ). La idea general es mantener varias estructuras de datos de ubicación de puntos planos, correspondientes a la intersección de la subdivisión con n planos paralelos que contienen cada vértice de subdivisión. Un uso ingenuo de esta idea aumentaría el espacio de almacenamiento a O ( n ²). De la misma manera que en la descomposición de losas, la similitud entre estructuras de datos consecutivas se puede aprovechar para reducir el espacio de almacenamiento a O ( n log n ), pero el tiempo de consulta aumenta a O (log² n ). [ cita requerida ]
En el espacio d -dimensional, la ubicación del punto se puede resolver proyectando recursivamente las caras en un espacio ( d -1) -dimensional. Si bien el tiempo de consulta es O (log n ), el espacio de almacenamiento puede ser tan alto como. La alta complejidad de las estructuras de datos d- dimensionales llevó al estudio de tipos especiales de subdivisión.
Un ejemplo importante es el caso de los arreglos de hiperplanos . Una disposición de n hiperplanos define O ( n d ) células, pero la ubicación de puntos se puede realizar en O (log n ) tiempo con O ( n d ) espacio mediante el uso de esquejes jerárquicos de Chazelle .
Otro tipo especial de subdivisión se llama subdivisión rectilínea (u ortogonal). En una subdivisión rectilínea, todos los bordes son paralelos a uno de los ejes ortogonales d . En este caso, la ubicación del punto se puede responder en O (log d -1 n ) tiempo con O ( n ) espacio.
Referencias
- de Berg, Mark; van Kreveld, Marc; Overmars, Mark ; Schwarzkopf, Otfried (2000). "Capítulo 6: Ubicación del punto". Geometría computacional (2ª ed. Revisada). Springer-Verlag . págs. 121-146 . ISBN 3-540-65620-0.
- Dobkin, David ; Lipton, Richard J. (1976). "Problemas de búsqueda multidimensional". Revista SIAM de Computación . 5 (2): 181–186. doi : 10.1137 / 0205015 .
- Snoeyink, Jack (2004). "Capítulo 34:" Ubicación de puntos ". En Goodman, Jacob E .; O'Rourke, Joseph (eds.). Handbook of Discrete and Computational Geometry (2ª ed.). Chapman & Hall / CRC. ISBN 1-58488-301-4.
- Sarnak, Neil; Tarjan, Robert E. (1986). "Ubicación de puntos planos mediante árboles de búsqueda persistentes". Comunicaciones de la ACM . 29 (7): 669–679. doi : 10.1145 / 6138.6151 .
- Edelsbrunner, Herbert ; Guibas, Leonidas J .; Stolfi, Jorge (1986). "Ubicación óptima del punto en una subdivisión monótona". Revista SIAM de Computación . 15 (2): 317–340. doi : 10.1137 / 0215023 .
- Kirkpatrick, David G. (1983). "Búsqueda óptima en subdivisiones planas". Revista SIAM de Computación . 12 (1): 28–35. CiteSeerX 10.1.1.461.1866 . doi : 10.1137 / 0212002 .
enlaces externos
- Repositorio de fuentes de ubicación puntual en la Universidad de Stony Brook
- Consultas de ubicación de puntos en CGAL , la biblioteca de algoritmos de geometría computacional