Dopasowywanie przestrzenne dużych zestawów danych

Question

Mam zestaw danych zawierający około 100 000 punktów i inny zestaw danych zawierający około 3000 wielokątów. Dla każdego z punktów muszę znaleźć najbliższy wielokąt (dopasowanie przestrzenne). Punkty wewnątrz wielokąta powinny pasować do tego wielokąta.

Obliczanie odległości wszystkich par jest wykonalne, ale zajmuje nieco więcej czasu niż jest to konieczne. Czy istnieje pakiet R, który użyje indeksu przestrzennego dla tego rodzaju problemu dopasowania?

Jestem świadomy pakietu sp i funkcji over, ale dokumentacja nie mówi nic o indeksach.

Answer 1

Możesz spróbować użyć funkcji gDistance w pakiecie w tym celu. Jako przykład spójrz na poniższy przykład, który przerobiłem z tego old thread. Mam nadzieję, że to pomoże.

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

ja nie wiem nic na temat R ale złożę jedno możliwe rozwiązanie używając PostGIS. Możesz być w stanie załadować dane w PostGIS i przetworzyć je szybciej niż w przypadku użycia samego R.

podawana dwa stoły planet_osm_point (80k) i rzędy planet_osm_polygon (30k rzędy) dodaje realizuje zapytania w około 30.

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

wynik jest przybliżeniem w oparciu o odległość pomiędzy punktem i inne ośrodki punkt ramki granicznej wielokątów (nie jest to środkowy punkt samego wielokąta). Przy odrobinie więcej pracy, zapytanie to można zaadaptować, aby uzyskać najbliższy wielokąt w oparciu o punkt środkowy samego wielokąta, chociaż nie będzie on wykonywany tak szybko.