Mercurial > dive4elements > river
diff backend/src/main/java/org/dive4elements/river/backend/utils/DouglasPeuker.java @ 8187:3bb1c62ad732
Moved package org.dive4elements.river.utils to org.dive4elements.river.backend.utils.
author | Sascha L. Teichmann <teichmann@intevation.de> |
---|---|
date | Thu, 04 Sep 2014 15:03:25 +0200 |
parents | backend/src/main/java/org/dive4elements/river/utils/DouglasPeuker.java@e1b831fe435a |
children | e8d2042c9639 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/backend/src/main/java/org/dive4elements/river/backend/utils/DouglasPeuker.java Thu Sep 04 15:03:25 2014 +0200 @@ -0,0 +1,81 @@ +package org.dive4elements.river.backend.utils; + +import org.dive4elements.river.importer.XY; // TODO: Move to a more common package. + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +public final class DouglasPeuker +{ + public static final double EPSILON = 1e-4; + + private DouglasPeuker() { + } + + public static List<XY> simplify(List<XY> input) { + return simplify(input, EPSILON); + } + + public static List<XY> simplify(List<XY> input, double epsilon) { + + int N = input.size(); + + if (N < 3) { + return new ArrayList<XY>(input); + } + + List<XY> simplified = recursiveSimplify(input, 0, N-1, epsilon); + + List<XY> output = new ArrayList<XY>(simplified.size()+2); + output.add(input.get(0)); + output.addAll(simplified); + output.add(input.get(N-1)); + + return output; + } + + private static List recursiveSimplify( + List<XY> input, + int start, + int end, + double epsilon + ) { + XY a = input.get(start); + XY b = input.get(end); + + // Normal of hesse normal form. + XY n = new XY(b).sub(a).ortho().normalize(); + + // distance offset of the hesse normal form. + double d = n.lineOffset(a); + + double maxDist = -Double.MAX_VALUE; + int maxIdx = -1; + + for (int i = start+1; i < end; ++i) { + double dist = Math.abs(n.dot(input.get(i)) + d); + if (dist > maxDist) { + maxDist = dist; + maxIdx = i; + } + } + + if (maxDist < epsilon) { + // All points between a and b can be ignored. + return Collections.<XY>emptyList(); + } + + // Split by input[maxIdx]. + List<XY> before = recursiveSimplify(input, start, maxIdx, epsilon); + List<XY> after = recursiveSimplify(input, maxIdx, end, epsilon); + + List<XY> output = new ArrayList<XY>(before.size()+1+after.size()); + output.addAll(before); + output.add(input.get(maxIdx)); + output.addAll(after); + + return output; + } +} +// vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :