-1

I am trying to implement Douglas-Peucker Algorithm with point count tolerance. I mean that i specifies that i want 50% compression. I found this algorithm on this page http://psimpl.sourceforge.net/douglas-peucker.html under Douglas-Peucker N. But i am not sure how this algorithm is working. Is there any implementation of this in java or some good specification about this version of algorithm?

What i dont understand from psimpl explanation is what will happend after we choose fist point into simplification? We will broke the edge into two new edges and rank all points and choose best point from both edges?

user1816532
  • 185
  • 4
  • 13
  • searching on google found this http://www.sanfoundry.com/java-program-douglas-peucker-algorithm-implementation/ it might help – Arachnid Hivemind Feb 24 '16 at 17:50
  • This is normal version of algorithm. I am looking for version where you can specify number of points in result. Look into link mentioned above and you will see normal version of this algorithm working with threshold and second working with number of points. – user1816532 Feb 24 '16 at 18:06
  • you can you just have to edit the array in main it shouldn't be too hard – Arachnid Hivemind Feb 24 '16 at 18:09
  • If you are not particular about using Douglas-Peucker Algorithm , [Visvalingam-Whyatt](https://github.com/ofZach/Visvalingam-Whyatt) will definitely give you this control. See some comparisons [I posted here](http://stackoverflow.com/questions/35290973/line-simplification-algorithm-visvalingam-vs-douglas-peucker) . I have similar requirements as posted here. – sith Mar 31 '17 at 07:51

2 Answers2

1

DP searches the polyline for the farthest vertex from the baseline. If this vertex is farther than the tolerance, the polyline is split there and the procedure applied recursively.

Unfortunately, there is no relation between this distance and the number of points to keep. Usually the "compression" is better than 50%, so you may try to continue the recursion deeper. But achieving a good balance of point density looks challenging.

  • Code mentioned above functions nearly same. But after you find farthest vertex from baseline you add him into new graph and split baseline into two baselines. And again you find farthest point from those two baselines and brake one of those baselines into two. So now you have three baselines. Using this principle you can choose how many points you will have in new graph. But i am not sure if this algorithm is "correct" or understand it right. – user1816532 Feb 24 '16 at 19:06
  • @user1816532: splitting in three rather than two doesn't help. –  Feb 25 '16 at 07:57
0

Combine the Douglas-peucker algorithm with iteration, and consider the remained points as a judge criteria. Here is my algorithm, array 'points' stores the points of the trajectory.Integer 'd' is the threshold.

public static Point[] divi(Point[] points,double d)
    {
    System.out.println("threshold"+d);
    System.out.println("the nth divi iteration");
    int i = 0;
    Point[] p1 = new Point[points.length];
    for (i = 0;i<points.length;i++)
        p1[i] = points[i];
    compress(p1, 0,p1.length - 1,d); //first compression
    int size = 0;                
    for (Point p : p1)    //trajectory after compression
        if(p != null)
        size ++;
    System.out.println("size of points"+size);
    if(size<=200 && size>=100)
        return p1;
    else if(size>200)
        return divi(p1,d + d/2.0);
    else
        return divi(points,d/2.0);
   }
public static void compress(Point[] points,int m, int n,double D) 
   {  
        System.out.println("threshold"+D);
        System.out.println("startIndex"+m);
        System.out.println("endIndex"+n);

        while (points[m] == null)
            m ++;

        Point from = points[m];
        while(points[n] == null)
            n--;

        Point to = points[n];

        double A = (from.x() - to.x()) /(from.y() - to.y());
        /** -
         * 由起始点和终止点构成的直线方程一般式的系数 
         */  
        double B = -1;

        double C = from.x() - A *from.y();
        double d = 0;  
        double dmax = 0;  
        if (n == m + 1)  
            return;    
       List<Double> distance = new ArrayList<Double>(); 
       for (int i = m + 1; i < n; i++) {
        if (points[i] ==null)
        {
            distance.add(0.0);
            continue; 
        }
        else
        {
         Point p = points[i];
       d = Math.abs(A * (p.y()) + B * (p.x()) + C)  / Math.sqrt(Math.pow(A, 2) + Math.pow(B, 2));  
       distance.add(d); 
        }
        }  
        dmax= Collections.max(distance);    

        if (dmax < D) 
            for(int i = n-1;i > m;i--)  
                 points[i] = null;
        else  
           {  
            int  middle = distance.indexOf(dmax) + m + 1;

            compress(points,m, middle,D);  

            compress(points,middle, n,D);  

           }  
    }
user6645042
  • 1
  • 1