如何找到每個房子的最近的地鐵站

Question

我有一個龐大的數據集A的經緯度在紐約市每個房子/公寓。 以及紐約市各地鐵站/入口的經緯度數據集B.

對於每個房子我想確定最近的地鐵站和到該站的距離。 問題是我有成千上萬的房屋和數百個地鐵站。如果我要計算每棟房屋的距離，那麼是浪費時間了。 什麼是最快的方式來確定最近的一個？ R或Python中有沒有包可以幫我快速完成？

Answer 1

我可能會嘗試與四叉樹。

R和蟒蛇有實現：

• R：SearchTrees
• 的Python：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

如果我要計算每個房子的距離，它的時間 浪費。

這不是計算機的用途。我無法想象這會花費幾個小時在一個普通的桌面上。

這是未經測試，認爲這是僞代碼：

# 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]) 

我打賭了50K房屋和500個地鐵你有一個答案在一個小時內。