Kết hợp không gian của các tập dữ liệu lớn

Question

Tôi có một tập dữ liệu với khoảng 100000 điểm và một tập dữ liệu khác với khoảng 3000 đa giác. Đối với mỗi điểm tôi cần tìm đa giác gần nhất (kết hợp không gian). Các điểm trong một đa giác phải khớp với đa giác đó.

Tính toán khoảng cách tất cả các cặp là khả thi, nhưng mất nhiều thời gian hơn mức cần thiết. Có một gói R sẽ sử dụng chỉ mục không gian cho loại vấn đề này không?

Tôi biết gói sp và chức năng over, nhưng tài liệu không cho biết bất kỳ điều gì về chỉ mục.

Answer 1

Bạn có thể thử và sử dụng chức năng gDistance trong gói rgeos cho việc này. Ví dụ như ví dụ dưới đây, tôi đã làm lại từ old thread này. Hy vọng nó giúp.

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

Tôi không biết gì về R nhưng tôi sẽ cung cấp một giải pháp có thể sử dụng PostGIS. Bạn có thể tải dữ liệu trong PostGIS và xử lý dữ liệu nhanh hơn bạn có thể sử dụng R một mình.

Với hai bảng planet_osm_point (80k hàng) và planet_osm_polygon (30k hàng), các truy vấn sau đây thực hiện trong khoảng 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 
); 

Kết quả là một xấp xỉ dựa trên khoảng cách giữa các điểm và centre- điểm của hộp giới hạn của đa giác (không phải chính giữa điểm của đa giác). Với công việc nhiều hơn một chút, truy vấn này có thể được điều chỉnh để có được đa giác gần nhất dựa trên điểm trung tâm của đa giác mặc dù nó sẽ không thực thi nhanh như thế.