まえがき
最近、仕事中にタスクを依頼しました-GPSデバイスを使用しているクライアントがいます。 彼は歩いて、街を意味し、毎秒このデバイスに自分の位置の座標を書き込みます。 次に、彼は私たちのサイトを訪れ、ルート記録を含むファイルを送信します。 それに応じて、彼は地図の画像と、彼が移動したときに描かれたルートの上に画像を受け取ります。 すべては何もないように見えますが、1つの問題があります。クライアントは少なくとも1日記録して巨大なファイルを送信でき、ルートの描画には多くの時間がかかります。 しかし、彼はまっすぐに行くことができ、それからすべてのポイントを描くポイントが消えます（2つの極端な価値があります）。 さらに、クライアント側のJavaScriptで描画され、クライアント側がモバイルデバイスの場合、ルートが表示されない可能性があります（（
したがって、破線を最適化するために、少し最適化する必要がありました。 この問題には、Douglas-Peckerメソッドがありますが、このメソッドの説明がロシア語で見つからなかったため、このRunetの空白を埋めることにしました。
アルゴリズム
すぐに理解した記事へのリンク （英語）を提供してください。
そこからも写真。
したがって、ポイントのリスト{V}と、指定された最大許容偏差（e）があります。
1）まず、破線全体を検討します
1.1）線[V0、Vn]から最も遠い点を探しています（図では[V0、V7]）
1.2）チェック-このポイント（図V3）からライン[V0、Vn]までの距離が（e）より小さい場合、セグメント上のすべてのポイント（V0、Vn）を破棄できます。
1.3）それ以外の場合、問題のセグメントを2つの部分に分割します（図では（V0、V3）および（V0、V7））。
2）その後、すべてが再帰的に繰り返されます。 個別に、セグメント（V0、V3）および（V0、V7）を考慮します。 それらのそれぞれで、セグメント上の主方向から可能な限り逸脱する点を見つけます。 このポイントが（e）を超えて逸脱していないかどうかをチェックし、セグメント上のすべてのポイントをスローします。 それ以外の場合、このセグメントは2つに分割され、再帰的な関数呼び出しが繰り返されます。
以下の図は、読者に残る可能性のあるアルゴリズムを理解する上で残っているすべてのギャップを埋めます。
実装
アルゴリズムはJavaで作成しました。 C ++のオプションに興味がある場合は、 こちらまたはPascal- thereに従ってください 。
public class DouglasPoikerSimplification { private static double tolerant; // - () private static Point[] polyline; // private static ArrayList<Integer> markedPoints; // ( ) public static Point[] getSimplificatedPolyline(Point[] plots, double tolerant){//tolerant = 0.00005 DouglasPoikerSimplification.tolerant = tolerant; DouglasPoikerSimplification.polyline = plots; DouglasPoikerSimplification.markedPoints = new ArrayList<Integer>(); markedPoints.add(0); simplify(0, plots.length-1); // markedPoints.add(polyline.length-1); return writePointArray(); } private static Point[] writePointArray(){ Integer[] idx = new Integer[markedPoints.size()]; idx = markedPoints.toArray(idx); Arrays.sort(idx); Point[] result = new Point[idx.length]; for (int i = 0; i < result.length; i++) { result[i] = polyline[idx[i]]; } return result; } private static void simplify(int j, int k){ if(k == j+1){ // , return; // }else{ double maxd = -1; // int maxi = j; // . . for (int i = j+1; i < k; i++) { // // double dv = Point.getDistance(polyline[j], polyline[k], polyline[i]); if(dv > maxd){// , maxi = i; // maxd = dv; // . } } if(maxd > tolerant ){// , markedPoints.add(maxi); // // System.out.println(polyline[maxi].getLat() + "\t\t " + polyline[maxi].getLng()); simplify(j, maxi);// simplify(maxi, k); } } } }
public class DouglasPoikerSimplification { private static double tolerant; // - () private static Point[] polyline; // private static ArrayList<Integer> markedPoints; // ( ) public static Point[] getSimplificatedPolyline(Point[] plots, double tolerant){//tolerant = 0.00005 DouglasPoikerSimplification.tolerant = tolerant; DouglasPoikerSimplification.polyline = plots; DouglasPoikerSimplification.markedPoints = new ArrayList<Integer>(); markedPoints.add(0); simplify(0, plots.length-1); // markedPoints.add(polyline.length-1); return writePointArray(); } private static Point[] writePointArray(){ Integer[] idx = new Integer[markedPoints.size()]; idx = markedPoints.toArray(idx); Arrays.sort(idx); Point[] result = new Point[idx.length]; for (int i = 0; i < result.length; i++) { result[i] = polyline[idx[i]]; } return result; } private static void simplify(int j, int k){ if(k == j+1){ // , return; // }else{ double maxd = -1; // int maxi = j; // . . for (int i = j+1; i < k; i++) { // // double dv = Point.getDistance(polyline[j], polyline[k], polyline[i]); if(dv > maxd){// , maxi = i; // maxd = dv; // . } } if(maxd > tolerant ){// , markedPoints.add(maxi); // // System.out.println(polyline[maxi].getLat() + "\t\t " + polyline[maxi].getLng()); simplify(j, maxi);// simplify(maxi, k); } } } }
結果
0.00005をとった偏差は約5.5メートルです。 サイトに送信されるファイルは、平均で1MBから1.5MBでした。
ビフォーアフタービフォア/アフター
65529 3535 18.5371994342291
56996 4131 13.7971435487775
41198 4699 8.76739731857842
35166 2408 14.6038205980066
34906 1437 24.2908837856646
平均15.9992889370513
平均して、ポイント数が16倍減少したことがわかります。