¿Encontrar polígonos cruzados por línea usando OGR?

8

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 )

Bagazo
fuente

Respuestas:

7

Para una solución de Python, es posible que desee ver Shapely http://gispython.org/shapely/docs/1.2/ y RTree http://pypi.python.org/pypi/Rtree/

Rtree te ayudará a crear índices espaciales.

DavidF
fuente
Ya he visto bien, pero no sabía sobre rtree! ¡Gracias!
Marc
Ok, he podido (finalmente) probar rtree. Funciona bien, ya que puedo reducir el conjunto de pruebas de 1096 a 19 :). Estoy pensando en usar Shapely, pero tengo que entender mejor lo que implica (Shapely no maneja las proyecciones, no quiero perder nada en el proceso).
Marc
5

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.

mloskot
fuente
3

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

johanvdw
fuente
Creo que buscaré soluciones con BBoxes. Mis datos no son aleatorios: las pistas son vuelos en parapente / ala delta y los polígonos son los espacios aéreos. Echaré un vistazo para ver si puedo encontrar un filtro simple en el bbox. No estoy usando directamente archivos de forma, pero he escrito un script que lee el formato OpenAIR (descriptores de espacio aéreo "estándar") a OGR (desde el cual puedo exportar directamente a shp)
Marc
2

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

Nicklas Avén
fuente
Estaba pensando lo mismo en la cadena lineal. No estoy tan familiarizado con SIG y python, pero debería haber una manera de construir índices espaciales en la memoria (sé que hay varias opciones de .net para hacer esto). Esta podría ser otra buena pregunta para gis.se.
Jay Cummins
Gracias por la respuesta. No estoy usando una base de datos para simplificar la configuración. Pero si evitar DB implica demasiada complejidad de código, entonces cambiaré de opinión :). En cuanto a los "índices espaciales", tendré que buscar un poco en Google para comprender exactamente qué es.
Marc
En cuanto a "Leí tu pregunta nuevamente y me di cuenta de que no estás usando la cadena lineal de las formas de trac sino cada vértice". Supongo que también podría probar la intersección del objeto de cadena lineal, pero luego tendré que extraer la parte que se cruza. Pero eso puede ser más rápido, ¡tienes toda la razón!
Marc
Acerca de los índices espaciales debe google gist e índices multidimensionales. La idea es construir un índice multidimensional de los cuadros delimitadores. En db-evironment, el planificador decide si vale la pena buscar primero el índice para encontrar los cuadros delimitadores que se cruzan antes de hacer la prueba de intersección real.
Nicklas Avén