检查一个点是否位于路线中 - Google地图

Question

当用户请求路线时，我需要在谷歌地图中突出显示相关位置。 我找到了几个步骤来实现。但有一点卡住了。

我们假设我们有大量点（数千）的集合。我们需要找出它们中的哪一个位于（动态）路线中。

第一步：先根据路线滤出点。这意味着，找到路线的最大经度，最小纬度，最大纬度，最小纬度，并将此滤波器应用于我们的组。这样我们可以找出更少的合格候选人。

第2步：我们仍然可以使用名为RouteBoxer的实用程序库过滤掉不必要的点。 （http://google-maps-utility-library-v3.googlecode.com/svn/tags/routeboxer/1.0/examples/routeboxer-v3.html）

第3步：经过上述2个步骤后，我们减少了从几千点到几百点。而这些点将会在那条路线的某个地方，尽管不完全在它上面。这是我面对挑战的地方。如何检查这些点是否在该路线中？我不认为让所有的点成为一条路线，并检查距离是一个好的解决方案（是的，它会工作，但..），因为路线可以是任何距离。有什么方法可以检查点和路线之间的最小距离吗？

Answer 1

RouteBoxer会给你一个多边形列表或LatLngBounds（如果如果给出多边形，你可以从任何方面得到LatLngBounds）。您可以遍历每个点，并使用LatLngBounds类的contains方法检查该点是否位于任何边界上。

Answer 2

是的，有dijkstra或kruskal算法。