Grundlegendes zur Verwendung von räumlichen Indizes mit RTree?

13

Ich habe Probleme, die Verwendung von räumlichen Indizes mit RTree zu verstehen.

Beispiel: Ich habe 300 gepufferte Punkte und muss den Schnittbereich jedes Puffers mit einem Polygon-Shapefile kennen. Das Polygon Shapefile hat> 20.000 Polygone. Es wurde vorgeschlagen, räumliche Indizes zu verwenden, um den Prozess zu beschleunigen.

SO ... Wenn ich einen räumlichen Index für mein Polygon-Shapefile erstelle, wird dieser in irgendeiner Weise an die Datei "angehängt", oder wird der Index eigenständig sein? Das heißt, kann ich nach dem Erstellen einfach meine Schnittfunktion für die Polygondatei ausführen und schnellere Ergebnisse erzielen? Wird intersection "sehen", dass es räumliche Indizes gibt und wissen, was zu tun ist? Oder muss ich es auf dem Index ausführen und diese Ergebnisse dann über FIDs oder dergleichen wieder mit meiner ursprünglichen Polygondatei verknüpfen?

Die RTree-Dokumentation hilft mir nicht sehr (wahrscheinlich, weil ich gerade Programmieren lerne). Sie zeigen, wie Sie einen Index erstellen, indem Sie manuell erstellte Punkte einlesen und ihn dann mit anderen manuell erstellten Punkten abfragen. Dabei werden die im Fenster enthaltenen IDs zurückgegeben. Macht Sinn. Sie erklären jedoch nicht, wie sich dies auf eine Originaldatei beziehen würde, aus der der Index stammen würde.

Ich denke, es muss ungefähr so ​​gehen:

  1. Ziehen Sie Bboxes für jedes Polygon-Feature aus meinem Polygon-Shapefile und platzieren Sie sie in einem räumlichen Index. Geben Sie ihnen eine ID, die mit ihrer ID im Shapefile identisch ist.
  2. Fragen Sie diesen Index ab, um die IDs zu ermitteln, die sich überschneiden.
  3. Führen Sie dann meine Überschneidung nur für die Features in meinem ursprünglichen Shapefile erneut aus, die durch Abfragen meines Index identifiziert wurden (nicht sicher, wie ich diesen letzten Teil ausführen würde).

Habe ich die richtige idee Vermisse ich etwas?


Im Moment versuche ich, diesen Code für ein Punkt-Shapefile zu verwenden, das nur ein Punkt-Feature und ein Polygon-Shapefile mit mehr als 20.000 Polygon-Features enthält.

Ich importiere die Shapefiles mit Fiona, füge den räumlichen Index mit RTree hinzu und versuche, die Schnittmenge mit Shapely zu erstellen.

Mein Testcode sieht so aus:

#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)

Aber ich bekomme immer wieder TypeError: Das Objekt 'Polygon' kann nicht aufgerufen werden

CSB
quelle
1
Ein räumlicher Index ist für das Dataset vollständig und transparent (aus Benutzersicht keine einzelne Entität). Die Software, die die Kreuzungen durchführt, ist sich dessen bewusst und verwendet räumliche Indizes, um eine kurze Liste zu erstellen, mit der die tatsächliche Kreuzung durch schnelle Informationen ausgeführt werden kann die Software, deren Merkmale für eine genauere Betrachtung in Betracht gezogen werden sollten und die sich eindeutig bei weitem nicht überschneiden. Wie Sie eines erstellen, hängt von Ihrer Software und Ihrem Datentyp ab. Weitere Informationen zu diesen Punkten finden Sie in der Hilfe. Bei einer Formdatei handelt es sich um die SHX-Datei.
Michael Stimson
4
.shx ist kein räumlicher Index. Es ist nur die dynamische Zugriffsoffsetdatei mit variabler Breite. .sbn / .sbx ist das räumliche ArcGIS-Shapefile-Indexpaar, obwohl die Spezifikation für diese nicht veröffentlicht wurde.
Vince
1
.qixIst auch der MapServer / GDAL / OGR / SpatiaLite Quadtree- Index
Mike T
Ihre Idee ist genau richtig für Spatialite, das keinen wirklichen räumlichen Index hat. Die meisten anderen Formate, sofern sie räumliche Indizes unterstützen, tun dies transparent.
user30184
2
Sie werden immer TypeError: 'Polygon' object is not callablemit Ihrem Aktualisierungsbeispiel shapefor i, shape in enumerate(gl):
fortfahren,

Antworten:

12

Das ist das Wesentliche. Mit dem R-Tree können Sie einen sehr schnellen ersten Durchgang durchführen und erhalten eine Reihe von Ergebnissen, die "falsch-positive" Ergebnisse liefern (Begrenzungsrahmen können sich schneiden, wenn die Geometrien nicht genau übereinstimmen). Dann gehen Sie die Kandidatenmenge durch (holen sie anhand ihres Index aus dem Shapefile) und führen einen mathematisch präzisen Schnittpunkttest durch, z. B. mit Shapely. Dies ist die gleiche Strategie, die in räumlichen Datenbanken wie PostGIS angewendet wird.

sgillies
quelle
1
Schönes Wortspiel (GiST)! GiST wird normalerweise als B-Tree-Variante beschrieben, Postgresql verfügt jedoch über eine GiST-Implementierung von R-Tree. Obwohl Wiki nicht unbedingt die beste Referenz zum Zitieren ist, enthält es ein schönes Diagramm , um die Suche nach Begrenzungsrahmen zu erläutern.
MappaGnosis
Es kann sich lohnen, eine manuelle Methode zur Verwendung des R-Tree-Index zu erlernen, wie in Schritt 2 und 3 beschrieben. Dieser Blog über OGC GeoPackage, der auch R-Tree unterstützt, da separate Datenbanktabellen einige SQL- und Screenshots von openjump.blogspot.fi zeigen / 2014/02 /… .
User30184
9

Sie haben es fast geschafft, aber Sie haben einen kleinen Fehler gemacht. Sie müssen die intersectionMethode für den räumlichen Index verwenden, anstatt den Index an die intersectionMethode für den gepufferten Punkt zu übergeben. Wenn Sie eine Liste von Features gefunden haben, bei denen sich die Begrenzungsrahmen überlappen, müssen Sie überprüfen, ob der gepufferte Punkt tatsächlich die Geometrien schneidet.

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

Wenn Sie Punkte finden möchten, die sich in einem Mindestabstand zu Ihrer Landklasse befinden, können Sie distancestattdessen die Methode verwenden (tauschen Sie den entsprechenden Abschnitt aus dem vorherigen Abschnitt aus).

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!')

Wenn die Erstellung Ihres räumlichen Index sehr lange dauert und Sie dies mehrmals tun, sollten Sie den Index in eine Datei serialisieren. Die Dokumentation beschreibt die Vorgehensweise : http://toblerity.org/rtree/tutorial.html#serializing-your-index-to-a-file

Sie können sich auch ansehen, wie Sie die Begrenzungsrahmen mithilfe eines Generators in den rtree laden:

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
quelle
2

Ja das ist die Idee. Hier ist ein Auszug aus diesem Tutorial über die Verwendung eines räumlichen R-Tree-Index in Python unter Verwendung von Shapely, Fiona und Geopandas:

Ein R-Baum repräsentiert einzelne Objekte und ihre Begrenzungsrahmen (das „R“ steht für „Rechteck“) als unterste Ebene des räumlichen Index. Anschließend werden benachbarte Objekte aggregiert und mit ihrem aggregierten Begrenzungsrahmen auf der nächsthöheren Indexebene dargestellt. Auf noch höheren Ebenen aggregiert der r-Baum Begrenzungsrahmen und repräsentiert sie durch ihren Begrenzungsrahmen iterativ, bis alles in einem Begrenzungsrahmen der obersten Ebene verschachtelt ist. Um zu suchen, nimmt der R-Baum ein Abfragefeld und sieht, beginnend auf der obersten Ebene, welche (falls vorhanden) Begrenzungsfelder es schneiden. Anschließend wird jeder sich überschneidende Begrenzungsrahmen erweitert und es wird angezeigt, welcher der untergeordneten Begrenzungsrahmen das Abfragefeld überschneidet. Dies wird rekursiv fortgesetzt, bis alle sich überschneidenden Kästchen auf die unterste Ebene abgesucht wurden und die übereinstimmenden Objekte von der untersten Ebene zurückgegeben wurden.

eos
quelle