DP paper (Journal of RESGAT) coding (v1_8august2016)

import ij.gui.Line;

import java.awt.Point;
import java.util.*;

//douglas peucker algorithm for using to reduce vertex
public class DouglasPeucker{

    static final double PI_HALF = Math.PI / 2;

    public static Double euclideanDist(Point p1, Point p2) {
        return Math.sqrt(Math.pow(p1.getX() - p2.getX(), 2)
                + Math.pow(p1.getY() - p2.getY(), 2));
    }

    private static double getDistance(Point p, Point s, Point e) {
        // Calculate the side lenghts of the triangle that is given by the three
        // points.
        double a = euclideanDist(p, s);
        double b = euclideanDist(p, e);
        double c = euclideanDist(s, e);

        // Calculate the angles of that triangle
        // Due to rounding errors this values could become 1.00000004 or
        // -1.0000004
        // Which would lead to NaN passing them into acos
        double betaCos = (b * b - a * a - c * c) / (-2 * a * c);
        betaCos = Math.max(-1., Math.min(1., betaCos));
        double alphaCos = (a * a - b * b - c * c) / (-2 * b * c);
        alphaCos = Math.max(-1, Math.min(1., alphaCos));

        // Alpha and beta are the angles between the line base from either one
        // of the line endpoints and the point whose distance should be found
        double alpha = Math.acos(alphaCos);
        double beta = Math.acos(betaCos);

        // Calculate the (signed) distance to a straight
        double numerator = (e.getX() - s.getX())
                * (s.getY() - p.getY()) - (s.getX() - p.getX())
                * (e.getY() - s.getY());
        double denominator = Math.sqrt(Math.pow(e.getX()
                - s.getX(), 2)
                + Math.pow(e.getY() - s.getY(), 2));
        double signedDistance = numerator / denominator;

        if (alpha > PI_HALF || beta > PI_HALF) {
            // One of the angles is bigger than 90 deg, so the distance is not
            // the distance to the straight but the minimum of the distances to
            // either one of the line endpoints.
            // SignedDistance had to be calculated anyway to keep the correct
            // sign in the result.
            return signedDistance > 0 ? Math.min(a, b) : -1 * Math.min(a, b);
        } else {
            // None of the angles is bigger than 90 deg, so the distance is just
            // the distance to a straight.
            return signedDistance;
        }
    }

    /**
     * See en.wikipedia.org/wiki/Douglas-Peucker_algorithm
     * @param points
     *            If less than 3 points, the algorithm cannot reduce anything.
     * @param epsilon
     *            Must be >= 0
     * @return
     */
    public static ArrayList<Point> reduce(ArrayList<Point> points, double epsilon) {
        int n = points.size();
        if (epsilon <= 0 || n < 3) {
            return points;
        }

        boolean[] marked = new boolean[n];
        marked[0] = marked[n - 1] = true;

        reduceRec(points, marked, epsilon, 0, n - 1);

        ArrayList<Point> result = new ArrayList<Point>(n);
        for (int i = 0; i < n; i++) {
            if (marked[i]) {
                result.add(points.get(i));
            }
        }
        return result;
    }

    private static void reduceRec(ArrayList<Point> points, boolean[] marked,
            double epsilon, int first, int last) {
        if (last <= first + 1) {
            return;
        }

        double maxDistance = -1.;
        int maxIndex = 0;

        for (int i = first + 1; i < last; i++) {
            Point current = points.get(i);
            double distance = Math.abs(getDistance(current, points.get(first), points.get(last)));
            if (distance > maxDistance) {
                maxDistance = distance;
                maxIndex = i;
            }
        }

        if (maxDistance > epsilon) {
            marked[maxIndex] = true;
            reduceRec(points, marked, epsilon, first, maxIndex);
            reduceRec(points, marked, epsilon, maxIndex, last);
        }
    }
}