Spatial Matching von großen Datensätzen

Question

Ich habe einen Datensatz mit etwa 100000 Punkten und einen weiteren Datensatz mit etwa 3000 Polygonen. Für jeden der Punkte muss ich das nächstgelegene Polygon finden (räumliche Übereinstimmung). Punkte innerhalb eines Polygons sollten mit diesem Polygon übereinstimmen.

Die Berechnung der Abstände aller Paare ist möglich, dauert aber etwas länger als nötig. Gibt es ein R-Paket, das einen räumlichen Index für diese Art von passendem Problem verwendet?

Ich kenne das sp Paket und die over Funktion, aber die Dokumentation sagt nichts über Indizes.

Answer 1

Sie könnten versuchen, die gDistance Funktion im rgeos Paket dafür zu verwenden. Als Beispiel schauen Sie sich das folgende Beispiel an, das ich aus dieser old thread überarbeitet habe. Ich hoffe es hilft.

require(rgeos) 
require(sp) 

# Make some polygons 
grd <- GridTopology(c(1,1), c(1,1), c(10,10)) 
polys <- as.SpatialPolygons.GridTopology(grd) 

# Make some points and label with letter ID 
set.seed(1091) 
pts = matrix(runif(20 , 1 , 10) , ncol = 2) 
sp_pts <- SpatialPoints(pts) 
row.names(pts) <- letters[1:10] 

# Plot 
plot(polys) 
text(pts , labels = row.names(pts) , col = 2 , cex = 2) 
text(coordinates(polys) , labels = row.names(polys) , col = "#313131" , cex = 0.75) 

# Find which polygon each point is nearest 
cbind(row.names(pts) , apply(gDistance(sp_pts , polys , byid = TRUE) , 2 , which.min)) 
# [,1] [,2] 
#1 "a" "86" 
#2 "b" "54" 
#3 "c" "12" 
#4 "d" "13" 
#5 "e" "78" 
#6 "f" "25" 
#7 "g" "36" 
#8 "h" "62" 
#9 "i" "40" 
#10 "j" "55" 

Answer 2

Ich weiß nichts über R nicht, aber ich werde eine mögliche Lösung mit PostGIS bieten. Möglicherweise können Sie die Daten in PostGIS laden und schneller verarbeiten als mit R alleine.

Gegeben seien zwei Tabellen planet_osm_point (80K Zeilen) und planet_osm_polygon (30K Zeilen), die folgende Abfrage in der Umgebung von 30 s führt

create table knn as 
select 
    pt.osm_id point_osm_id, 
    poly.osm_id poly_osm_id 
from planet_osm_point pt, planet_osm_polygon poly 
where poly.osm_id = (
    select p2.osm_id 
    from planet_osm_polygon p2 
    order by pt.way <-> p2.way limit 1 
); 

Das Ergebnis ist eine Annäherung an die Distanz zwischen dem Punkt und dem auf Basis Zentrum- Punkt des Begrenzungsrahmens des Polygons (nicht der Mittelpunkt des Polygons selbst). Mit ein wenig mehr Arbeit kann diese Abfrage angepasst werden, um das nächstgelegene Polygon basierend auf dem Mittelpunkt des Polygons selbst zu erhalten, obwohl es nicht so schnell ausgeführt wird.