地理网格搜索算法

许多基于位置的服务都提供了用于查找给定纬度经度对周围的地点/场所/地点的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

地理网格搜索算法

回答

相关问题