teichmann@8187: package org.dive4elements.river.backend.utils;
teichmann@5083: 
tom@7730: import org.dive4elements.river.importer.XY; // TODO: Move to a more common package.
teichmann@5083: 
teichmann@5083: import java.util.ArrayList;
teichmann@5083: import java.util.Collections;
teichmann@5083: import java.util.List;
teichmann@5083: 
teichmann@5083: public final class DouglasPeuker
teichmann@5083: {
teichmann@5083:     public static final double EPSILON = 1e-4;
teichmann@5083: 
teichmann@5083:     private DouglasPeuker() {
teichmann@5083:     }
teichmann@5083: 
teichmann@5083:     public static List<XY> simplify(List<XY> input) {
teichmann@5083:         return simplify(input, EPSILON);
teichmann@5083:     }
teichmann@5083: 
teichmann@5083:     public static List<XY> simplify(List<XY> input, double epsilon) {
teichmann@5083: 
teichmann@5083:         int N = input.size();
teichmann@5083: 
teichmann@5083:         if (N < 3) {
teichmann@5083:             return new ArrayList<XY>(input);
teichmann@5083:         }
teichmann@5083: 
teichmann@5083:         List<XY> simplified = recursiveSimplify(input, 0, N-1, epsilon);
teichmann@5083: 
teichmann@5083:         List<XY> output = new ArrayList<XY>(simplified.size()+2);
teichmann@5083:         output.add(input.get(0));
teichmann@5083:         output.addAll(simplified);
teichmann@5083:         output.add(input.get(N-1));
teichmann@5083: 
teichmann@5083:         return output;
teichmann@5083:     }
teichmann@5083: 
teichmann@5083:     private static List recursiveSimplify(
teichmann@5083:         List<XY> input,
teichmann@5083:         int      start,
teichmann@5083:         int      end,
teichmann@5083:         double   epsilon
teichmann@5083:     ) {
teichmann@5083:         XY a = input.get(start);
teichmann@5083:         XY b = input.get(end);
teichmann@5083: 
teichmann@5083:         // Normal of hesse normal form.
teichmann@5083:         XY n = new XY(b).sub(a).ortho().normalize();
teichmann@5083: 
teichmann@5083:         // distance offset of the hesse normal form.
teichmann@5083:         double d = n.lineOffset(a);
teichmann@5083: 
teichmann@5083:         double maxDist = -Double.MAX_VALUE;
teichmann@5083:         int maxIdx = -1;
teichmann@5083: 
teichmann@5083:         for (int i = start+1; i < end; ++i) {
teichmann@5083:             double dist = Math.abs(n.dot(input.get(i)) + d);
teichmann@5083:             if (dist > maxDist) {
teichmann@5083:                 maxDist = dist;
teichmann@5083:                 maxIdx  = i;
teichmann@5083:             }
teichmann@5083:         }
teichmann@5083: 
teichmann@5083:         if (maxDist < epsilon) {
teichmann@5083:             // All points between a and b can be ignored.
teichmann@5083:             return Collections.<XY>emptyList();
teichmann@5083:         }
teichmann@5083: 
teichmann@5083:         // Split by input[maxIdx].
teichmann@5083:         List<XY> before = recursiveSimplify(input, start, maxIdx, epsilon);
teichmann@5083:         List<XY> after  = recursiveSimplify(input, maxIdx, end, epsilon);
teichmann@5083: 
teichmann@5083:         List<XY> output = new ArrayList<XY>(before.size()+1+after.size());
teichmann@5083:         output.addAll(before);
teichmann@5083:         output.add(input.get(maxIdx));
teichmann@5083:         output.addAll(after);
teichmann@5083: 
teichmann@5083:         return output;
teichmann@5083:     }
teichmann@5083: }
teichmann@5083: // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :