4

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

在此处输入图像描述

在此处输入图像描述

此处存在哪条路线以及哪条路线是新路线并不重要。无论如何，我想得到结果，这些路线是相似的（好吧，可能它们不是 90% 相似，但我们假设它们是相似的）。

目前，我正在使用蛮力将新的折线与现有的折线一一进行比较。在此之前，我使用此算法将折线分割成点并比较每个点以查看是否有匹配项。如果这些点之间的距离小于 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;
}

显然，这个算法很糟糕（特别是在最坏的情况下，当没有匹配新的折线时），因为有两个循环，并且可能有太多的点无法比较。

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

4

1 回答 1

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并将 a 传递LatLng[]给isMostlyCovered. 如果您可以预先计算现有多段线的数据，那么将它们存储起来LatLng[]也会有所帮助。保留每条折线的极端纬度和经度以及线长可以帮助您尽早排除明显的不匹配。

也许你甚至应该超越它：连同经度和纬度，存储以地球为中心、地球固定的坐标，并将它们保存在kd 树中，以便于最近邻查找。这是我对算法的最佳加速的赌注，代价是额外的数据。

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

于 2014-03-01T09:51:03.270 回答