Mercurial > dive4elements > river
comparison 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 |
comparison
equal
deleted
inserted
replaced
| 8186:a1ceacf15d3a | 8187:3bb1c62ad732 |
|---|---|
| 1 package org.dive4elements.river.backend.utils; | |
| 2 | |
| 3 import org.dive4elements.river.importer.XY; // TODO: Move to a more common package. | |
| 4 | |
| 5 import java.util.ArrayList; | |
| 6 import java.util.Collections; | |
| 7 import java.util.List; | |
| 8 | |
| 9 public final class DouglasPeuker | |
| 10 { | |
| 11 public static final double EPSILON = 1e-4; | |
| 12 | |
| 13 private DouglasPeuker() { | |
| 14 } | |
| 15 | |
| 16 public static List<XY> simplify(List<XY> input) { | |
| 17 return simplify(input, EPSILON); | |
| 18 } | |
| 19 | |
| 20 public static List<XY> simplify(List<XY> input, double epsilon) { | |
| 21 | |
| 22 int N = input.size(); | |
| 23 | |
| 24 if (N < 3) { | |
| 25 return new ArrayList<XY>(input); | |
| 26 } | |
| 27 | |
| 28 List<XY> simplified = recursiveSimplify(input, 0, N-1, epsilon); | |
| 29 | |
| 30 List<XY> output = new ArrayList<XY>(simplified.size()+2); | |
| 31 output.add(input.get(0)); | |
| 32 output.addAll(simplified); | |
| 33 output.add(input.get(N-1)); | |
| 34 | |
| 35 return output; | |
| 36 } | |
| 37 | |
| 38 private static List recursiveSimplify( | |
| 39 List<XY> input, | |
| 40 int start, | |
| 41 int end, | |
| 42 double epsilon | |
| 43 ) { | |
| 44 XY a = input.get(start); | |
| 45 XY b = input.get(end); | |
| 46 | |
| 47 // Normal of hesse normal form. | |
| 48 XY n = new XY(b).sub(a).ortho().normalize(); | |
| 49 | |
| 50 // distance offset of the hesse normal form. | |
| 51 double d = n.lineOffset(a); | |
| 52 | |
| 53 double maxDist = -Double.MAX_VALUE; | |
| 54 int maxIdx = -1; | |
| 55 | |
| 56 for (int i = start+1; i < end; ++i) { | |
| 57 double dist = Math.abs(n.dot(input.get(i)) + d); | |
| 58 if (dist > maxDist) { | |
| 59 maxDist = dist; | |
| 60 maxIdx = i; | |
| 61 } | |
| 62 } | |
| 63 | |
| 64 if (maxDist < epsilon) { | |
| 65 // All points between a and b can be ignored. | |
| 66 return Collections.<XY>emptyList(); | |
| 67 } | |
| 68 | |
| 69 // Split by input[maxIdx]. | |
| 70 List<XY> before = recursiveSimplify(input, start, maxIdx, epsilon); | |
| 71 List<XY> after = recursiveSimplify(input, maxIdx, end, epsilon); | |
| 72 | |
| 73 List<XY> output = new ArrayList<XY>(before.size()+1+after.size()); | |
| 74 output.addAll(before); | |
| 75 output.add(input.get(maxIdx)); | |
| 76 output.addAll(after); | |
| 77 | |
| 78 return output; | |
| 79 } | |
| 80 } | |
| 81 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 : |