Mercurial > dive4elements > river
view backend/src/main/java/org/dive4elements/river/utils/DouglasPeuker.java @ 8166:72c0d4682cf6
Renamed tag in sq relation defaults to a more fitting name.
author | Sascha L. Teichmann <teichmann@intevation.de> |
---|---|
date | Fri, 29 Aug 2014 16:24:12 +0200 |
parents | e1b831fe435a |
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 :