¿Comprender el uso de índices espaciales con RTree?

13

Tengo problemas para comprender el uso de índices espaciales con RTree.

Ejemplo: tengo 300 puntos almacenados en búfer, y necesito saber el área de intersección de cada búfer con un archivo de forma poligonal. El archivo de forma poligonal tiene> 20,000 polígonos. Se sugirió que usara índices espaciales para acelerar el proceso.

SO ... Si creo un índice espacial para mi archivo de forma poligonal, ¿se "adjuntará" al archivo de alguna manera, o el índice se mantendrá solo? Es decir, después de crearlo, ¿puedo ejecutar mi función de intersección en el archivo de polígono y obtener resultados más rápidos? ¿La intersección "verá" que hay índices espaciales y sabrá qué hacer? ¿O necesito ejecutarlo en el índice y luego relacionar esos resultados con mi archivo de polígono original a través de FID o algo así?

La documentación de RTree no me está ayudando mucho (probablemente porque solo estoy aprendiendo programación). Muestran cómo crear un índice mediante la lectura de puntos creados manualmente y luego consultarlo en relación con otros puntos creados manualmente, lo que devuelve los identificadores contenidos en la ventana. Tiene sentido. Pero, no explican cómo eso se relacionaría con algún archivo original del que habría provenido el índice.

Estoy pensando que debe ser algo como esto:

  1. Extraiga bboxes para cada entidad poligonal del archivo de formas de mi polígono y colóquelos en un índice espacial, dándoles una identificación que sea la misma que su identificación en el archivo de formas.
  2. Consulta ese índice para obtener los identificadores que se cruzan.
  3. Luego, vuelva a ejecutar mi intersección solo en las características de mi archivo de forma original que se identificaron al consultar mi índice (no estoy seguro de cómo haría esta última parte).

¿Tengo la idea correcta? ¿Me estoy perdiendo algo?


En este momento estoy tratando de hacer que este código funcione en un archivo de forma de punto que contiene solo una entidad de punto, y un archivo de forma de polígono que contiene> 20,000 entidades de polígono.

Estoy importando los archivos de forma con Fiona, agregando el índice espacial con RTree y tratando de hacer la intersección con Shapely.

Mi código de prueba se ve así:

#point shapefile representing location of desired focal statistic
traps = fiona.open('single_pt_speed_test.shp', 'r') 

#polygon shapefile representing land cover of interest 
gl = MultiPolygon([shape(pol['geometry']) for pol in fiona.open('class3_aa.shp', 'r')]) 

#search area
areaKM2 = 20

#create empty spatial index
idx = index.Index()

#set initial search radius for buffer
areaM2 = areaKM2 * 1000000
r = (math.sqrt(areaM2/math.pi))

#create spatial index from gl
for i, shape in enumerate(gl):
    idx.insert(i, shape.bounds)

#query index for ids that intersect with buffer (will eventually have multiple points)
for point in traps:
        pt_buffer = shape(point['geometry']).buffer(r)
        intersect_ids = pt_buffer.intersection(idx)

Pero sigo obteniendo TypeError: el objeto 'Polígono' no es invocable

CSB
fuente
1
Un índice espacial es integral y transparente para el conjunto de datos (contenido, ni una sola entidad desde la perspectiva del usuario). El software que realiza las intersecciones es consciente y utilizará índices espaciales para crear una lista corta para realizar la intersección real al informar rápidamente El software cuyas características deben considerarse para una inspección más cercana y que claramente no se cruzan. La forma en que cree uno depende de su software y su tipo de datos ... proporcione más información sobre estos puntos para obtener ayuda más específica. Para un archivo de forma es el archivo .shx.
Michael Stimson
44
.shx no es un índice espacial. Es solo el archivo de desplazamiento de acceso dinámico de registro de ancho variable. .sbn / .sbx es el par de índice espacial de ArcGIS shapefile, aunque no se publicó la especificación correspondiente.
Vince
1
También .qixes el MapServer / GDAL / OGR / SpatiaLite árbol cuádruple índice
Mike T
Su idea es perfectamente correcta para Spatialite que no tiene un índice espacial real. La mayoría de los otros formatos, si admiten índices espaciales, lo hacen de forma transparente.
user30184
2
Sigue obteniendo TypeError: 'Polygon' object is not callablesu ejemplo de actualización porque sobrescribe la shapefunción que importó de forma con un objeto Polygon que crea con esta línea:for i, shape in enumerate(gl):
user2856

Respuestas:

12

Esa es la esencia de esto. El árbol R le permite realizar una primera pasada muy rápida y le proporciona un conjunto de resultados que tendrán "falsos positivos" (los cuadros delimitadores pueden cruzarse cuando las geometrías no lo hacen). Luego revisa el conjunto de candidatos (recuperándolos del archivo de forma por su índice) y realiza una prueba de intersección matemáticamente precisa utilizando, por ejemplo, Shapely. Esta es la misma estrategia que se emplea en bases de datos espaciales como PostGIS.

sgillies
fuente
1
Buen juego de palabras (GiST)! GiST se describe normalmente como una variante B-Tree, pero Postgresql tiene una implementación GiST de R-Tree. Aunque wiki no es necesariamente la mejor referencia para citar, tiene un buen diagrama para explicar las búsquedas de cuadro delimitador.
MappaGnosis
Puede valer la pena aprender una forma manual de usar el índice R-tree como en los pasos 2 y 3. Este blog sobre OGC GeoPackage que también admite R-tree como tablas de base de datos separadas muestra algunas capturas de pantalla y SQL openjump.blogspot.fi / 2014/02 /… .
user30184
9

Casi lo tienes, pero has cometido un pequeño error. Debe usar el intersectionmétodo en el índice espacial, en lugar de pasar el índice al intersectionmétodo en el punto almacenado. Una vez que haya encontrado una lista de entidades en las que se superponen los cuadros delimitadores, debe verificar si su punto de protección realmente intersecta las geometrías.

import fiona
from shapely.geometry import mapping
import rtree
import math

areaM2 = areaKM2 * 1000000
r = (math.sqrt(areaM2/math.pi))

# open both layers
with fiona.open('single_pt_speed_test.shp', 'r') as layer_pnt:
    with fiona.open('class3_aa.shp', 'r') as layer_land:

        # create an empty spatial index object
        index = rtree.index.Index()

        # populate the spatial index
        for fid, feature in layer_land.items():
            geometry = shape(feature['geometry'])
            idx.insert(fid, geometry.bounds)

        for feature in layer_pnt:
            # buffer the point
            geometry = shape(feature['geometry'])
            geometry_buffered = geometry.buffer(r)

            # get list of fids where bounding boxes intersect
            fids = [int(i) for i in index.intersection(geometry_buffered.bounds)]

            # access the features that those fids reference
            for fid in fids:
                feature_land = layer_land[fid]
                geometry_land = shape(feature_land['geometry'])

                # check the geometries intersect, not just their bboxs
                if geometry.intersects(geometry_land):
                    print('Found an intersection!')  # do something useful here

Si está interesado en encontrar puntos que estén dentro de una distancia mínima a su clase de tierra, puede usar el distancemétodo en su lugar (cambie la sección correspondiente de la anterior).

for feature in layer_pnt:
    geometry = shape(feature['geometry'])

    # expand bounds by r in all directions
    bounds = [a+b*r for a,b in zip(geometry.bounds, [-1, -1, 1, 1])]

    # get list of fids where bounding boxes intersect
    fids = [int(i) for i in index.intersection(geometry_buffered.bounds)]

    for fid in fids:
        feature_land = layer_land[fid]
        geometry_land = shape(feature_land['geometry'])

        # check the geometries are within r metres
        if geometry.distance(geometry_land) <= r:
            print('Found a match!')

Si está tomando mucho tiempo construir su índice espacial y va a hacer esto más de unas pocas veces, debería considerar serializar el índice en un archivo. La documentación describe cómo hacer esto: http://toblerity.org/rtree/tutorial.html#serializing-your-index-to-a-file

También puede ver la carga masiva de los cuadros delimitadores en el árbol utilizando un generador, como este:

def gen(collection):
    for fid, feature in collection.items():
        geometry = shape(feature['geometry'])
        yield((fid, geometry.bounds, None))
index = rtree.index.Index(gen(layer_land))
Snorfalorpagus
fuente
2

Sí, esa es la idea. Aquí hay un extracto de este tutorial sobre el uso de un índice espacial r-tree en Python , usando shapely, Fiona y geopandas:

Un árbol r representa objetos individuales y sus cuadros delimitadores (la "r" es para "rectángulo") como el nivel más bajo del índice espacial. Luego agrega objetos cercanos y los representa con su cuadro de límite agregado en el siguiente nivel más alto del índice. En niveles aún más altos, el árbol r agrega cuadros delimitadores y los representa por su cuadro delimitador, iterativamente, hasta que todo esté anidado en un cuadro delimitador de nivel superior. Para buscar, el r-tree toma un cuadro de consulta y, comenzando en el nivel superior, ve qué cuadros delimitadores (si los hay) lo intersecan. Luego expande cada cuadro delimitador de intersección y ve cuáles de los cuadros delimitadores secundarios dentro de él se cruzan con el cuadro de consulta. Esto continúa de manera recursiva hasta que todos los cuadros de intersección se buscan en el nivel más bajo y devuelve los objetos coincidentes desde el nivel más bajo.

eos
fuente