各家の最寄り地下鉄駅を探す方法

Question

私はNewYorkCityの各家の緯度と経度の巨大なデータセットAを持っています。 NYCの各地下鉄駅/玄関の緯度と経度のデータセットBもあります。

各家屋について、最も近い地下鉄駅とその駅までの距離を特定したいと思います。 問題は、私には数万の家屋と数百の地下鉄駅があることです。もし私が各家の距離を計算しようとするなら、それは時間を無駄にしています。 最も近いものを特定する最も速い方法は何ですか？ RやPythonの中には、すばやく手助けできるパッケージはありますか？

Answer 1

私はおそらくQuadtreeで試してみます。

RとPythonの両方持って実装：

• R：SearchTrees
• パイソン：pyqtree

Answer 2

各行が家を表し、各列はステーションを表す場合は、単純に計算することができ各行の最小値を求める。それは、座標

に基づいて距離を計算しますので、

geosphereパッケージには、あなたが、私は、距離関数distHaversine注文それをこの方法最初の経度を入れていることがわかります、ここで有用です。

read about the package hereを入力してください。私はこの例の指示にちょうど従った。

例：

cities <- data.frame(city = c('Miami', 'Atlanta', 'New York', 'Los Angeles'), 
        lon = c(-80.1917, -84.387982, -74.005941, -118.243685), 
        lat = c(25.76168, 33.748995, 40.712784, 34.052234), 
        stringsAsFactors = FALSE) 

stations <- data.frame(station = c('Orlando', 'Richmond', 'Nashville'), 
         lon = c(-81.379236, -77.436048, -86.781602), 
         lat = c(28.538335, 37.540725, 36.162664), 
         stringsAsFactors = FALSE) 
cities 
#   city  lon  lat 
# 1  Miami -80.19170 25.76168 
# 2  Atlanta -84.38798 33.74900 
# 3 New York -74.00594 40.71278 
# 4 Los Angeles -118.24368 34.05223 

stations 
#  station  lon  lat 
# 1 Orlando -81.37924 28.53834 
# 2 Richmond -77.43605 37.54073 
# 3 Nashville -86.78160 36.16266 

library(geosphere) 
dist_mat <- mapply(function(lon, lat, cty) distHaversine(c(lon, lat), cty), stations[,2], stations[,3], list(cities[-1])) 
min_dist <- apply(dist_mat, 1, which.min) 
cbind(city=cities[,1], closest_station=stations[min_dist,1]) 
#  city   closest_station 
# [1,] "Miami"  "Orlando"  
# [2,] "Atlanta"  "Nashville"  
# [3,] "New York" "Richmond"  
# [4,] "Los Angeles" "Nashville" 

Answer 3

私は、各住宅の距離を計算するつもりならば、それは時間 浪費です。

これは実際のコンピュータのためのものではありません。これは一般的なデスクトップで数時間かかるとは想像できません。

これはテストされていない、それは擬似コードを検討：私はあなたが時間の下に答えを持っていると思い50K住宅や500本の地下鉄のために賭けたい

# distance between points is sqrt((x1-x2)^2 + (y1-y2)^2) 

houses = [[32,54],[3,2],[15,16]] 
subways = [[123,2],[54,3],[56,6],[54,32],[1,65],[43,1],[13,16],[21,6],[5,1]] 

distances = [] 
for i in range(len(houses)): 
     distances.append([]) 
     for j in range(len(subways)): 
      delta_x = house[i][0]-subway[j][0] 
      delta_y = house[i][1]-subway[j][1] 
      distance = (delta_x**2 + delta_y**2)**(0.5) 
      distances[i].append(distance) 
     min_idx = distances.index(min(distances)) 

     print 'closest subway to house number %s at %s is subway number %s at %s' (
      i, house[i], min_idx, subways[min_idx]) 

。