地理網格搜索算法

許多基於位置的服務都提供了用於查找給定緯度經度對周圍的地點/場所/地點的API。我正在研究如何在整個城市中搜索這些地方。地理網格搜索算法

我可以通過從Google地圖地理編碼器中獲取邊界來構建城市的網格，然後遞增緯度/經度以放置點以形成網格。我已經prototyped this grid（點擊填充網格按鈕查看所有的要點）來可視化這個想法。

// gather a collection of lat/long pairs that represents a grid of the city 
    var latIncrement = .04; 
    var lngIncrement = .04; 
    var newLat = nw.lat(); 
    while(newLat >= sw.lat()) { 
     var newLng = nw.lng(); 
     while(newLng <= ne.lng()) { 
     // western and northern border as well as grid infill 
     addMarker(new google.maps.LatLng(newLat, newLng)); 
     newLng += lngIncrement; 
     } 

     // eastern border 
     addMarker(new google.maps.LatLng(newLat, ne.lng())); 
     newLat -= latIncrement; 
    } 

    // southern border 
    var newLng = sw.lng(); 
    while(newLng <= se.lng()) { 
     addMarker(new google.maps.LatLng(sw.lat(), newLng)); 
     newLng += lngIncrement; 
    } 
    addMarker(se);

我可以採取所有這些要點，並針對LBS API運行搜索。

我的問題是，有更多的科學方法/算法來建立這個網格？我想了解更多關於他們的信息。我只是任意增加經緯度，直到我到達電網的邊界。城市的密度會隨着城市和城市的不同而變化，所以有時增量會過小，有時也會過大。我正在尋找關於如何調整這個更好一點的想法？

來源

2010-07-01 RyanW

一個也許更有效的/清潔的辦法是找到城市，這與每個邊緣是極端東南西北城際點之間，如果你能找到它們，然後在填充它們的矩形bounding rectangle反覆。但無論如何，這基本上就是你已經在做的事情。

至於地方密度，你有一個特定的API，你將使用它？如果您在檢測位置時知道API的點數「達到」，則您只需要使網格點與其半徑接近即可。

也就是說，你是否看了看，也許如果API直接支持搜索的地方境內？這可能是你最好最乾淨的賭注。

閱讀您的評論後，這裏要說的是我要考慮和未來細化可能是低效的方式，但它可能會幫助您開始使用。

在您的城市中心放置一個點，並觀察檢測到的所有位置。找到您所在位置的convex hull，並在凸包上的每個位置放置一個新點。然後，將這些新增加的點的範圍內的所有位置添加到您的位置列表中。

然後，找到那些凸包，並重復相同的過程。

這實際上可能會減少您對人口稀少城市的積分。對於密集的，它可能不是最佳的，但它可能讓你開始工作的軌道。

來源

2010-07-01 07:11:23

我邊框從API結果我一直在尋找foursquare，twitter，gowalla和yelp API。半徑（範圍）是一個常見參數，但問題變成了返回結果的數量（它們將搜索限制爲少數），所以我無法通過單個搜索來獲取城市中的所有地點。好主意，我很欣賞答案！ – RyanW 2010-07-01 17:19:28

增加了另一個建議=） – 2010-07-01 19:02:28

太好了，這給了我另一種解決方法。我喜歡它，因爲它從中心擴散開來，並不像浪費。通過網格搜索，許多搜索將超出城市範圍。感謝您對此進行了解釋。 – RyanW 2010-07-02 00:26:20

雖然我面臨同樣的問題。我想出了一個解決方案，在那裏你將以自頂向下的遞歸方式進行網格搜索。如果該API支持邊界框搜索，這將工作。最初假設你的城市是一個廣場。現在使用該方塊中的API（邊界框查詢）獲取數據/位置。現在，如果返回的地點數量超過某個閾值，則將城市廣場分成4個相等的廣場，並對每個廣場重複該過程。如果返回的地點數量少，則不要分割。這將防止網格搜索到森林，河流等非商業區域（廣場）。以下是一個原型Python代碼：

這裏的抓取功能，獲取基於與SW作爲西南緯度，logitude元組和ne作爲東北緯度，logitude元組

allresults = [] 

def grid_search(sw,ne): 
    global results 
    results = fetch(sw,ne) 
    if len(results) <= 10: 
     return 
    allresults.append(results) 
    swlat,swlon = sw 
    nelat,nelon = ne 
    grid_search((swlat + delta, swlon), (nelat, sw + delta)) 
    grid_search((swlat + delta, swlon + delta), ne) 
    grid_search(sw, (swlat + delta, swlon + delta)) 
    grid_search((swlat,swlon + delta), (swlat + delta, nelon))

來源

2016-10-27 14:33:01

地理網格搜索算法

回答

相關問題