谷歌地图：如何在给定点的基础上查找所有在给定路程范围内的点？

Question

在我的应用程序中，GPS会获取车辆的位置。然后，它应该在所有可能在1公里范围内的点上放置标记（请注意，道路在1公里范围内可能会分叉多次）。

有人可以建议我如何做到这一点吗？提前感谢您。

- user315067

---

你是否正在寻找一种不允许“折返”的解决方案，这样你就不能重复走同一条路或回到起点？在市中心的情况下，你可以只绕着一个1公里的街区反复行驶！ - chillysapien

是的，不要重复回溯。实际上，这就像在说...如果你还有1公里的备用燃料，而所有加油站都在你的可达范围内。 - user315067

如果你特别在寻找加油站，那么找出半径范围内的所有加油站，然后检查每个候选目的地的驾车路线距离，会不会更快呢？ - Jason Kleban

@Jason：好主意。我也会首先探索那个选项。 - Daniel Vassallo

值得一看（源代码中的JavaScript）：http://www.freemaptools.com/how-far-can-i-travel.htm - heltonbiker

Answer 1

这是一个使用Google Maps API解决的非常棘手的问题。以下是一种您可能要考虑的方法：

1. 您可以轻松地计算出1公里范围内的边界圆，也很容易计算出落在该圆周上的点，对于任何角度。这个距离将是"直线距离"而不是实际的路程距离，但您可能想查看以下Stack Overflow帖子，了解具体实现方法：

   如何计算距离另一个点一定距离的latlng？

   在半径为1公里的边界圆上以20度间隔标记的截图：

已删除ImageShack链接 - 如何计算距离另一个点一定距离的latlng？

2. 还有一个技巧可以将这些点捕捉到最近的街道。您可以查看Mike Williams的捕捉点到街道示例以获得良好的实现。

   使用Google Maps API的方向服务可以计算从GPS点到每个捕捉道路点的道路距离。请注意，这仅适用于支持Google Maps中方向的国家，但更重要的是，道路距离几乎总是大于1km，因为我们的边界圆半径为1km。然而，如果您可以使用大致信息进行工作，则可能已经是一种可能的解决方案。

3. 您还可以考虑从上述解决方案开始（1km边界圆，在圆周上计算x个点，并将它们捕捉到最近的道路），然后计算每条路径的道路距离（从GPS点到每个捕捉点），然后您可以为每条路径递归地重复此操作，每次使用较小的边界圆，直到接近1km的道路距离。您可以在每次递归中按比例减小边界圆的大小，以使算法更加高效。

---

更新：

我找到了一个非常不错的实现方式，似乎使用了与我上面描述的类似的方法：

• 行车半径（多目的地）

请注意，您可以更改从顶部的度数间隔。使用宽间隔，您将获得快速结果，但可能会错过一些路线。

截图：

已删除失效的ImageShack链接 - 行车半径

- Daniel Vassallo

---

你能提供一些解释吗，关于你是如何创建第一个图像的？（具有沿着圆周的点坐标的边界圆）谢谢！ - bradleygriffith

我想通了。这是我的做法： http://jsfiddle.net/bradleygriffith/eh4NJ/这个做法很大程度上基于ConroyP在这里提供的函数： https://dev59.com/YU_Ta4cB1Zd3GeqPFfys - bradleygriffith

不错！在使用前，您应该将边界圆形成一个圆形（在您的代码中实际上是一个椭圆形（只需检查更高纬度，比如70度即可）。虽然这可以通过正确的数学方法轻松修复。 - Hannes

给定的链接 http://maps.forum.nu/gm_driving_radius.html 已经失效，请提供一个新的链接（如果可能的话）。 - Aman Jain

Answer 2

自然暴力算法是建立一个包含每个十字路口的每个可能决策的所有可能节点列表。

我怀疑在1公里范围内，平均交叉口数量不会超过10个，并假设每个交叉口平均有3个选择，你将得到3^10 - 大约59,049个最终节点（请注意，您需要在道路的每个分支上都有10个十字路口才能达到完整数字）。

实际上，这个数字会下降，我认为通过不同的路线到达相同的节点并不罕见，特别是在城市中。

这种方法将给出一个确切的答案（前提是您有好的街道地图作为输入）。它是潜在的时间，但n似乎并不那么高，所以它可能是实用的。

根据您需要这些节点的目的（或者您会考虑哪种场景足够相似以剪枝），进一步的改进和优化可能是可能的。

- Unreason

---

各位朋友们，非常感谢你们的回复。显然这不是一个容易解决的问题。我目前暂停了对它的研究...但当我重新开始研究时，一定会让大家知道最新情况。非常非常感谢大家的帮助。因为 Stack Overflow 不允许我标记多个正确答案，所以我将把 Daniel 的答案标记为正确答案。 - user315067

Answer 3

稍微详细阐述一下Daniel的方法，首先要找到所有直线半径范围内的点，这就是你的起始节点集合。现在包括与这些节点相连的边和其他起始节点集合中的节点。现在检查节点是否连接，并且没有漂浮在外无法到达的节点。现在从你的车辆节点开始创建一个 "最短路径树"。

该树将为您提供从起始节点到所有其他节点的最短路径。请注意，如果您从最远的节点开始创建路径，则任何子路径也是途中到达这些节点的最短路径。确保标记沿途的这些子路径上的节点，以便您无需计算它们。最坏情况下，您需要为所有节点开发最短路径，但实际上，这应该花费更少的时间。

- Grembo

Answer 4

1. 考虑每个十字路口上的每个可能决策，列出所有可能的节点。 （但如何自动化地完成呢？）
2. 使用Dijkstra算法找到到达所有点的最近路径。
3. 可视化数据。 （这有点棘手，因为在可到达区域内可能存在无法到达的区域。）

- Dolik