ビッグデータセットの空間マッチング

Question

約100000ポイントのデータセットと、約3000ポリゴンのデータセットがあります。それぞれの点について、私は最も近いポリゴン（空間マッチング）を見つける必要があります。ポリゴンの内側の点は、そのポリゴンに一致する必要があります。

すべてのペアの距離を計算することは可能ですが、必要以上に少し時間がかかります。このようなマッチングの問題に空間インデックスを使用するRパッケージはありますか？

私はspパッケージとover機能について知っていますが、ドキュメントではインデックスについては何も教えていません。

Answer 1

これには、rgeosパッケージのgDistance機能を試してみることができます。例として、以下の例を見てみましょう。これはこのold threadから書き直しました。それが役に立てば幸い。

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

私はRについては何も知らないが、私はPostGISのを使用して一つの可能​​な解決策を提供します。 PostGISでデータをロードして、Rを単独で使用するよりも速く処理できます。

二つのテーブルplanet_osm_point（80K行）とplanet_osm_polygon（30K行）が与えられると、次のクエリは、約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 
); 

に実行結果が点とcentre-との間の距離に基づいて近似値でありますポリゴンの境界ボックス（ポリゴン自体の中心点ではありません）のポイントです。多少の作業があれば、このクエリーは、ポリゴン自体の中心点に基づいて最も近いポリゴンを取得するように適応させることができますが、ポリゴン自体は高速に実行されません。