问查找折线的哪一部分包含在另一条折线中的有效算法
EN

Stack Overflow用户

提问于 2014-02-28 11:16:34

回答 1查看 2.1K关注 0票数 3

我正在尝试将由Google Directions API转换的Polyline - overview_polyline与一组已经存在的多段线进行比较，看看新多段线的哪一部分已经包含在这些多段线中。对于我来说，polyline是一个行驶路线表示，从Google Directions API检索。它基本上是世界上任何地方的任何路线。为了简化，我们总是可以找到属于一个具体城市或国家的路线，并且只比较这一条。此外，目前它可能最多250公里长。下面是一些示例：

无论哪条路由已经存在，哪条路由是新的都无关紧要。无论如何，我希望得到的结果是，这些路由是相似的(好的，可能它们不是90%相似，但让我们假设它们是相似的)。

目前，我正在使用蛮力将新的折线与现有的折线逐个进行比较。在此之前，我使用this算法将多段线分割为点，并比较每个点以查看是否存在匹配。如果distance between这个点小于100米，我认为这些点是相同的。

如果我发现已经有一些多段线，这些多段线主要覆盖新的多段线，我停止处理。

它看起来是这样的：

Polyline findExistingPolyline(Polyline[] polylines, Polyline polyline) {
  LatLng[] polylinePoints = PolylineDecoder.toLatLng(polyline);
  for (Polyline existing: polylines) {
    LatLng[] existingPoints = PolylineDecoder.toLatLng(existing);
    if (isMostlyCovered(existingPoints , polylinePoints)) {
       return existing;
    }
  }

  return null;

}

boolean isMostlyCovered(LatLng[] existingPoints, LatLng[] polylinePoints) {
  int initialSize = polylinePoints.length;
  for (LatLng point: polylinePoints) {
    for (LatLng existingPoint: existingPoints) {
       if (distanceBetween(existingPoint, point) <= 100) {
         polylinePoints.remove();// I actually use iterator, here it is just demosnstration
       }
    }
  }
  // check how many points are left and decide if polyline is mostly covered
  // if 90% of the points is removed - existing polylines covers new polyline
  return (polylinePoints.length * 100 / initialSize) <= 10;
}

显然，这个算法很糟糕(特别是在最坏的情况下，当没有匹配新折线的时候)，因为有两个很多的周期，可能有太多的点要比较。

所以，我想知道，是否有更有效的方法来比较折线彼此。

google-polyline

android

algorithm

回答 1

Stack Overflow用户

发布于 2014-03-01 09:51:03

您似乎只比较多段线的点，而不是两条线之间的线。这意味着直线和带有额外中心点的同一条直线不会匹配。还是我错过了什么？(如果我的假设是正确的，那么我认为这就是您方法中的弱点。)

您使用的距离计算涉及椭球三角法，并且可能很昂贵。不过，这里不需要精确的度量，只需要匹配两个节点即可。如果您需要覆盖一个不靠近极点的众所周知的范围，您可以将经度/经度考虑为平面坐标，可能需要对经度进行校正。

boolean isWithin100m(LatLng a, LatLng b) {
    double dy = (a.lat - b.lat) * R * pi / 180.0;

    if (dy < -100 || dy > 100) return false;

    double dmid = 0.5 * (a.lat + b.lat) * pi / 180.0;
    double dx = (a.lng - b.lng) * R * pi / 180.0 / cos(dmid);
    return dx*dx + dy*dy <= 10000.0;
}

这里，R是地球的半径。这种方法应该比你的精确解更快。如果最北点和最南点的余弦相似，您甚至可以省略它们，只需在经度中添加一个固定的平均余弦作为恒定因子。

此外，每次比较时都要解码新的多段线。您只能在findExistingPolyline中这样做一次，并将LatLng[]传递给isMostlyCovered。如果可以预先计算现有多段线的数据，则将其存储为LatLng[]也会有所帮助。保持每条折线的极端纬度和经度，也许还有一条线的长度，可以帮助您在早期排除明显的不匹配。

也许您甚至应该超越这一点:除了经度和纬度之外，还要存储Earth-Centered, Earth-fixed坐标，并将它们保存在k-d Tree中，以便方便地进行最近邻查找。这是我对你的算法的最佳加速比的打赌，代价是额外的数据。

最好不要为每条折线创建一个新的列表，然后将其删除，而是保持列表的完整性，并保留一个本地的“已用”集合，这样查找起来应该比删除点更快。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/22093640

复制

客户端 Meteor.call 等待服务端异步函数返回

meteor 服务端函数客户端异步

在 Meteor 项目中，经常会有客户端使用 Meteor.call 方法去调用服务端的一个方法，并等待该方法返回。通常情况下，服务端的方法只需要 return 后，客户端使用回调函数就可以访问到 return 的值了。但如果服务端同样调用了一个异步执行的函数，那么此时就无法判断服务端的异步函数是否已经执行完毕，返回结果就会出现不准确的情况。如下所示：

我与梦想有个约会

2023/10/20