Simplify Polyline with Douglas-Pecker

Foreword

Recently, at work they set a task - there is a client with a GPS device. He walks, he means in the city and writes down the location of his location on the device every second. Then he visits our website and sends a file with route entries. And in response, he receives an image of a map and on top of a drawn route along which he moved. Everything seems to be nothing, but there is one problem - the client can record at least a whole day and send a huge file, and drawing the route takes a lot of time. But he could go in a straight line and then the point of drawing all the points disappears (only two extreme values ​​are valuable). Moreover, it is drawn on JavaScript on the client side and if the client side of this mobile device is likely that it will not see the route ((
And because I had to do a little optimization - optimally simplify the broken line. For this task, there is a Douglas-Pecker method, but I did not find a description of this method in Russian, so I decided to fill this Runet space.

Algorithm

Immediately cite a link (English) to the article on which I understood.
Pictures too from there.

So, we have a list of points {V} and a given maximum allowable deviation (e).
1) We first consider the entire broken line
1.1) We are looking for a point which is the most distant from the line [V0, Vn] (in the figure [V0, V7])
1.2) Check - if the distance from this point (in Figure V3) to the line [V0, Vn] is less than (e), then all points on the segment (V0, Vn) can be thrown out.
1.3) Otherwise, we divide the segment under consideration into 2 parts (in the figure (V0, V3) and (V0, V7)).
2) Then everything recursively repeats. We separately consider the segments (V0, V3) and (V0, V7). At each of them we find a point which deviates as much as possible from the main direction on the segment. We check if this point deviates by no more than (e), then all points on the segment are thrown. Otherwise, this segment is divided into 2 and recursive function calls are repeated.

The illustration below will fill in any remaining gaps in the understanding of the algorithm that the reader might have.

Implementation

I wrote the algorithm in Java. Who is interested in the option for C + + follow here , or 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); } } } }

')

Result

The deviation I took is 0.00005 approximately 5.5 meters. Files sent to the site were average from 1MB to 1.5MB.

before after before / after
65529 3535 18.5371994342291
56996 4131 13.7971435487775
41198 4699 8.76739731857842
35166 2408 14.6038205980066
34906 1437 24.2908837856646

average 15.9992889370513

We see that on average the number of points decreased by 16 times.