algorithm - 地理网格搜索算法

Question

许多基于位置的服务都提供 API，用于查找给定纬度经度对周围的地点/ field /地点。我正在研究如何在整个城市中搜索这些地点。

我可以通过从 Google map 地理编码器获取城市边界，然后增加纬度/经度以放置点以形成网格，从而为城市构建网格。我有 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 运行搜索。

我的问题是，是否有更科学的方法/算法来建立这个网格？我想更多地了解他们。我只是任意增加纬度/经度直到我到达网格的边界。地点的密度会因城市和城市区域的不同而有很大差异，因此有时增量太小，有时又太大。我正在寻找有关如何更好地调整它的想法？

Answer 1

也许更有效/更干净的方法是找到 bounding rectangle城市的，这是一个矩形，每条边都是城市边界点之间的极端基点，如果你能找到它们，然后迭代地填充它们。但这基本上就是您已经在做的事情。

至于位置密度，您是否有将要与之一起使用的特定 API？如果您在检测地点时知道 API 点的“范围”，则只需让网格点尽可能接近它们的半径即可。

话虽如此，您是否研究过 API 是否直接支持搜索边界内的地点？这可能是您最好和最干净的选择。

---

阅读您的评论后，我将在未来考虑并改进以下可能效率低下的方法，但它可能会帮助您入门。

在您的城市中心放置一个点，并观察检测到的所有位置。找到 convex hull您的位置，并在凸包的每个位置上放置一个新点。然后，将这些新添加的点可及范围内的所有位置添加到您的位置列表中。

然后，求出它们的凸包，重复同样的过程。

这实际上可能会减少您在人烟稀少的城市的积分数量。对于密集的，它可能不是最佳选择，但它可能会让您开始工作。