Tengo un mapa de Google con un montón de polígonos.
Este es un problema que me interesa: Dado un punto lat,lng, ¿cuál es la mejor manera de determinar todos los polígonos en los que se encuentra este punto?
La forma obvia es ejecutar un algoritmo de "punto en polígono" de forma iterativa para cada polígono, pero me preguntaba si existe un algoritmo eficiente para responder a estas consultas, especialmente si tienes miles de polígonos.
Como con casi todas las preguntas de este tipo, El enfoque óptimo depende de los "casos de uso" y de cómo se representen las características. Los casos de uso suelen distinguirse por (a) si hay muchos o pocos objetos en cada capa y (b) si alguna de las capas (o ambas) permite precomputar algunas estructuras de datos; es decir, si una o ambas son lo suficientemente estáticas e inmutables como para que la inversión en precomputación merezca la pena.
En el caso que nos ocupa, esto da lugar a los siguientes escenarios. Normalmente los puntos son dinámicos: es decir, no se dan de antemano. (Si están disponibles de antemano, o en grupos muy grandes, habrá algunas optimizaciones basadas en la ordenación de los mismos). Sea Q sea el número de puntos de consulta y P sea el número de polígonos vértices.
(1) Pocos puntos, pocos vértices de polígono in toto . Utilice un procedimiento de fuerza bruta, como el clásico algoritmo de apuñalamiento de línea . Para cualquier método decente, el coste es O(P*Q), porque cuesta O(1) tiempo comparar un punto con una arista del polígono y hay que hacer todas esas comparaciones.
(2) Posiblemente muchos vértices de polígonos, pero son dinámicos: Cada vez que se utiliza un punto en la consulta, los polígonos pueden haber cambiado. De nuevo, utilice un algoritmo de fuerza bruta. El coste sigue siendo O(P*Q), que será grande porque P será grande, pero eso no se puede evitar. Si los cambios son pequeños o controlados ( Por ejemplo Si los polígonos cambian ligeramente de forma o simplemente se mueven lentamente) se podría utilizar una versión de la siguiente solución y encontrar una forma eficiente de actualizar las estructuras de datos a medida que los polígonos cambian. Eso sería probablemente una cuestión de investigación original.
(3) Muchos vértices de polígonos y polígonos estáticos (es decir, la capa de polígonos rara vez cambiará). Precalcular una estructura de datos para apoyar la búsqueda (que podría basarse en un barrido de líneas o un quadtree ). El coste de precomputación de estos algoritmos es O(P*log(P)), pero el coste de las consultas pasa a ser O(Q*log(P)), por lo que el coste total es O((P+Q)*log(P)).
Algunas mejoras están disponibles en casos especiales como por ejemplo
(a) Todos los polígonos son convexos ( el preprocesamiento de los polígonos puede hacerse más rápidamente ),
(b) Todos los interiores de los polígonos son disjuntos en cuyo caso se puede considerar que su unión es un único polígono (lo que permite utilizar algoritmos sencillos y eficientes, como los basados en la triangulación, y
(c) La mayoría de los polígonos no son muy tortuosos --es decir, que ocupan grandes porciones de sus cuadros delimitadores-- en cuyo caso se puede hacer una prueba inicial basada sólo en los cuadros delimitadores y luego refinar esa solución. Esta es una optimización muy popular.
(d) El número de puntos es grande. Clasificarlos podría mejorar el tiempo. Por ejemplo, cuando se implementa un algoritmo de barrido de línea de izquierda a derecha punto-en-polígono, se ordenarían los puntos en su primera coordenada, lo que permitiría barrer sobre los puntos al mismo tiempo que se barre sobre los bordes del polígono. No me consta que se haya publicado una optimización de este tipo. Sin embargo, se ha publicado una que consiste en realizar un triangulación restringida de la unión de todos los puntos y vértices del polígono: una vez completada esa triangulación, la identificación de los puntos interiores debería ser rápida. El coste computacional será de O(Q*log(Q) + (P+Q)*log(P+Q)).
Esto es increíblemente fácil: ver la capa de polígonos como un indicador binario raster (1=dentro de un polígono, 0=fuera). (Esto podría requerir una tabla de búsqueda para convertir los valores ráster en indicadores de dentro/fuera). Cada sonda de punto requiere ahora un esfuerzo de O(1) para indexar la celda raster y leer su valor. El esfuerzo total es O(Q).
Un buen solución híbrida en el caso de muchos polígonos vectoriales estáticos (caso vectorial 3 anterior) es inicialmente rasterizar los polígonos, quizás incluso con una resolución gruesa, esta vez distinguiendo cualquier celda que intersecte cualquier parte de un límite de polígono (dándoles un valor de 2, digamos). El uso de una sonda rasterizada (coste O(1)) suele dar una respuesta definitiva (se sabe que el punto está dentro o fuera), pero en ocasiones da una respuesta indefinida (el punto cae en una celda por la que pasa al menos una arista), en cuyo caso se realiza la consulta vectorial, más cara, O(log(P)). Este método conlleva un coste adicional de almacenamiento de la trama, pero en muchos casos incluso una trama pequeña (un MB permitirá una trama de 2000 por 2000 que almacene valores {0,1,2,null}) puede conferir enormes ventajas en el tiempo de cálculo. Asintóticamente, el esfuerzo computacional es el mismo que el de una solución vectorial, pero en la práctica es O(Q + P*log(P)) y posiblemente tan bajo como O(Q+P) (lo que se consigue utilizando una resolución muy fina para la trama y empleando métodos de fuerza bruta para las escasas consultas vectoriales que hay que realizar).
Si tuvieras los recuadros delimitadores de los polígonos almacenados en algo como un árbol de cuadrículas, podrías utilizarlo para determinar rápidamente qué polígonos comprobar. Como mínimo se podría ver si el punto está dentro de cada caja de delimitación del polígono en lugar de hacer un punto completo en el polígono para cada polígono. Personalmente, yo configuraría un servicio web que almacenaría los polígonos en la memoria y utilizaría algo como JTS o NetTopology suite para hacer la consulta de intersección por mí.
En postgis ST_Intersects utiliza los índices para encontrar primero si el punto está dentro de la caja delimitadora del polígono y luego hace una nueva comprobación para ver si realmente está dentro del polígono. Esto es rápido, a menudo muy rápido.
Si ha almacenado sus datos en PostGIS no debería haber ninguna duda de que la base de datos es el lugar adecuado para hacer el cálculo. En otros casos tendrás que enviar tus polígonos a algún programa intermedio o cliente. Eso, en sí mismo tomará mucho más tiempo que hacer los cálculos y simplemente obtener los polígonos relevantes.
/Nicklas
La siguiente url habla sobre el punto en el polígono .. (nunca he utilizado esto).. dar una oportunidad.. puede dar alguna ide.
http://eriestuff.blogspot.com/2008/02/google-maps-point-in-polygon.html
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
