Mercurial > dive4elements > river
view backend/src/main/java/org/dive4elements/river/utils/DouglasPeuker.java @ 7730:e1b831fe435a slt-simplify-cross-sections
Merged default into slt-simplify-cross-sections branch and updated package and class names.
author | Tom Gottfried <tom@intevation.de> |
---|---|
date | Mon, 20 Jan 2014 14:04:20 +0100 |
parents | flys-backend/src/main/java/de/intevation/flys/utils/DouglasPeuker.java@7bbee0cfc171 |
children |
line wrap: on
line source
package org.dive4elements.river.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 :