查找節點定列表最接近的節點，並協調

L1（X1，Y1） L2（X2，Y2） L3（X3，Y3 ） ... L10000（10000倍，Y10000）

我有一個返回2點位置之間的距離的函數：（L1，L2）=5英里

對於給定的位置的距離，我怎麼找到100英里內的所有地點？或者如果它更容易，50個最近的位置

我們的設置是一個位置及其郵政編碼的SQL Server表。該功能需要2個郵政編碼，查找每個緯度和經度並返回距離。我們可以緩存結果，因爲它們不會經常更改。

2012-11-03 user46372

看到這個問題：http://stackoverflow.com/questions/1751698/sql-query-for-total-points-within-radius-of-a-location/我沒有時間斷言如果兩個問題是重複的，但我相信你可以找到很好的線索解決上述問題。 – mjv

我認爲你正在尋找的可能是SQL Server的[空間索引]（http://msdn.microsoft.com/zh-cn/library/default.aspx）。COM/EN-US /庫/ bb933876％28V = SQL.105％29.aspx）。從算法上來說，你可以做的很少，以防止沒有特殊索引支持的O（n）（半徑內的所有點）或O（n lg k）（k個最近點）時間。 –

使用空間索引（他們使用[R-Tree的]（http://en.wikipedia.org/wiki/R-tree）） – goat

你將不得不通過他們循環，並簡單地拋棄一切都漸行漸遠的是百英里的位置，這將是O（N）

SELECT Location FROM Table WHERE (POWER(Location.X-Selected.X,2) + POWER(Location.Y-Selected.Y,2)) < POWER(Distance,2)

位置將是位置條目。選定的將是您所選擇的城市，只需將其替換爲X和Y以及相應的位置即可。

我的SQL有點生疏，所以如果出現錯誤，我會修復它。

來源

2012-11-03 16:20:46 Xonar

你真的沒有給我們很多關於表結構的信息，所以很難給你一個確切的答案。但是，假設目標郵政編碼作爲參數P1提供給查詢。進一步來說，表T有id，名稱和zip字段。爲了找100英里範圍內的所有位置，我們可以使用

select id, name, zip, distance(zip,P1) as distance 
from T 
where distance(zip,P1) <= 100

對於排名前50位的查詢

select top 50 id, name, zip, distance(zip,P1) as distance 
from T 
order by distance(zip,P1)

一個更好的解決辦法是計算每個位置的緯度和經度並將其存儲在數據庫中。您可以考慮跳過功能中的緯度/經度查找並大幅提高速度。我假設你已經有了代碼來計算現有函數中的大圓距離。

來源

2012-11-03 16:22:06 tvanfosson

一種解決方案是編寫一個函數一樣，是通用的，將允許cutstomization如下：

Location[] findLocationsWithinDist(Location L1, Integer dist, LocationsList locations){ 
    LocationList results; 
    foreach(location : locations){ 
     if(dist(L1, location) <= dist) 
      results.add(location); 
    } 
    return results; 
}

可能您存儲與在一定範圍內的位置列表中的每個位置的數據結構。然後，每次添加新位置時都需要更新此數據結構。這似乎是一個單獨的問題，但。

來源

2012-11-03 16:23:22 rharrison33

如果您可以在內存中存儲所有位置（緯度/經度/ ID），請使用Kd樹。查看我的回答another question Kd-tree允許有效的最近鄰居搜索和k-最近鄰居搜索。平均時間複雜度爲O（log n）。如果您不能在內存中存儲所有位置，請檢查您的數據庫是否支持空間索引。

來源

2012-11-03 21:40:05 gvd

查找節點定列表最接近的節點，並協調

回答

相關問題