4

Google Directions APIPolyline - overview_polylineによって改ざんされたものを既存のポリラインのセットと比較し、新しいポリラインのどの部分がこれらのポリラインの 1 つに既に含まれているかを確認しようとしています。私にとってポリラインは、Google Directions API から取得した運転ルートの表現です。基本的には世界中のどのルートでも構いません。簡単にするために、具体的な都市または国に属するルートをいつでも見つけて、これだけを比較できます。また、現時点では最大で 250km の長さになる可能性があります。次に例を示します。

ここに画像の説明を入力

ここに画像の説明を入力

ここに既存のルートと新しいルートは関係ありません。いずれにせよ、このルートが類似しているという結果を取得したいと思います（OK、90％類似していない可能性がありますが、類似していると仮定しましょう）。

現時点では、新しいポリラインを既存のポリラインと 1 つずつ比較するためにブルート フォースを使用しています。その前に、このアルゴリズムを使用してポリラインをポイントに分割し、各ポイントを比較して一致するかどうかを確認します。このポイント間の距離が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;
}

2 つの多くのサイクルがあり、比較するにはポイントが多すぎる可能性があるため、明らかに、このアルゴリズムは適切ではありません (特に最悪の場合、新しいポリラインに一致するものがない場合)。

それで、ポリラインを互いに比較するためのより効率的なアプローチがあるかどうか疑問に思っていました。

4

1 に答える 1

1

間の線ではなく、ポリラインのポイントのみを比較しているようです。つまり、直線と追加の中心点を持つ同じ直線は一致しません。または、何か不足していますか？（私の仮定が正しければ、それがあなたの方法の弱点だと思います。）

使用する距離計算には楕円体三角法が含まれており、おそらくコストがかかります。ここでは正確な尺度は必要ありませんが、2 つのノードを一致させたいだけです。極に近くない既知の範囲をカバーする必要がある場合は、緯度/経度を平坦な座標と見なし、経度を補正することもできます。

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は地球の半径です。その方法は、正確な解決策よりも高速である必要があります。最北端と最南端のポイントのコサインが類似している場合は、それらを除外して、経度の定数として固定平均コサインを追加することもできます。

また、すべての比較で新しいポリラインをデコードします。これを一度だけ実行して、 to にfindExistingPolyline渡すことができます。既存のポリラインのデータを事前に計算できる場合は、それらを保存することも役立ちます。各ポリラインの極端な緯度と経度、および場合によってはラインの長さを維持すると、明らかな不一致を早い段階で排除するのに役立ちます。LatLng[]isMostlyCoveredLatLng[]

たぶん、それ以上のことをする必要があります: 経度と緯度とともに、地球中心の地球固定座標を保存し、それらをkd ツリーに保持して、最も近い隣人を簡単に検索できるようにします。これは、追加のデータを犠牲にして、アルゴリズムの最高の高速化に対する私の賭けです。

また、ポリラインごとに新しいリストを作成してから削除するのではなく、リストをそのままにして、ポイントを削除するよりもすばやく検索できるローカルの「使用済み」セットを保持する方がよいでしょう。

于 2014-03-01T09:51:03.270 に答える