Estoy tratando de encontrar todos los polígonos cruzados por una sola línea (una pista GPS). Estoy usando la biblioteca OGR (de python) para calcular esto, pero actualmente es un poco 'fuerza bruta' (y lenta). Para cada punto de mi pista, llamo al método de intersección con todos los polígonos. La optimización obvia es verificar solo con polígonos adyacentes. Pero supongo que este es un problema clásico, con una solución ya conocida (que no puedo encontrar ...).
Me gustaría evitar el uso de una base de datos dedicada ya que estoy tratando de escribir un software independiente (spaceialite es una opción si el DB es el camino a seguir).
(Para su información, el código fuente actual está disponible aquí: https://github.com/dkm/airspace-checker )
fuente
En lugar de una intersección expansiva , puede realizar una preselección de polígonos según la comparación de los cuadros delimitadores. En otras palabras, encuentre todos los polígonos superpuestos / adyacentes a MBR de segmentos de su pista. Luego realice una prueba detallada en el subconjunto de polígonos.
fuente
Las propuestas de mloskot y Nicklas para comparar los cuadros delimitadores son realmente correctas.
Si está utilizando shapefiles, también podría considerar llamar a este módulo de saga: http://www.saga-gis.org/saga_modules_doc/shapes_transect/index.html
fuente
Lo que hace una base de datos como PostGIS para acelerar esto es hacer primero un índice, comparar el cuadro delimitador. Primero encuentra todos los polígonos que tienen cuadros delimitadores que se cruzan con el cuadro delimitador de la línea. El problema en su caso podría ser que la cadena lineal es larga y tendrá un cuadro delimitador muy grande que intersecta muchos polígonos que no tiene ningún interés.
Si las líneas son muy largas, probablemente también tendrá que trabajar con funciones geodésicas que son mucho más complejas y lentas que las funciones planas.
Puede ser bastante complejo hacer que las cosas funcionen sin problemas.
¿Por qué no quieres confiar en una base de datos? Eso no resolverá todos sus problemas, pero hay muchas optimizaciones integradas en PostGIS, por ejemplo. Allí también tiene los cálculos geodésicos de intersección si lo necesita.
Actualización: volví a leer su pregunta y me di cuenta de que no está utilizando la cadena de líneas de las formas de seguimiento sino cada vértice.
Creo que está en el camino equivocado;)
Tanto porque no puede verificar si el borde entre los puntos de vértice se cruza con el polígono como porque está moviendo la iteración entre los puntos de vértice a Python en lugar de alguna implementación de C, que creo que es mucho más rápido . Entonces tienes ese problema con los índices. Para hacer las cosas más rápido, tendrá que construir y manejar algún tipo de índice espacial.
Por otro lado, si está haciendo gran parte del trabajo en su propio código, ¿por qué no hace también la prueba de intersección? Esa prueba es solo un punto en la prueba de polígono si se trata de los puntos de vértice. Google para "punto en polígono" y encontrará varios algoritmos.
Pero, optaría por un enfoque basado en bases de datos. Eso le dará la posibilidad de usar índices espaciales.
/ Nicklas
fuente