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 : |