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