android - 查找 Polyline 的哪一部分包含在另一条 Polyline 中的高效算法

Question

我正在尝试比较由 Google Directions API 生成的 Polyline - overview_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;
}

显然，这个算法很糟糕(尤其是在最坏的情况下，当没有匹配新折线时)，因为有两个循环并且可能有太多的点需要比较。

所以，我想知道是否有更有效的方法来相互比较多段线。

Answer 1

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

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

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 中便于最近邻查找。我敢打赌，以额外数据为代价，您的算法将获得最佳加速。

最好不要为每条多段线创建一个新列表然后从中删除，而是保持列表完整并保留一个本地“已用”集，这应该比删除点更快地查找。