Mercurial > dive4elements > river
annotate backend/src/main/java/org/dive4elements/river/backend/utils/DouglasPeuker.java @ 9709:b74f817435fe
comment removed
author | dnt_bjoernsen <d.tironi@bjoernsen.de> |
---|---|
date | Wed, 27 Jan 2021 11:47:38 +0100 |
parents | e8d2042c9639 |
children |
rev | line source |
---|---|
8841
e8d2042c9639
Add missing copyright headers.
Tom Gottfried <tom@intevation.de>
parents:
8187
diff
changeset
|
1 /* Copyright (C) 2011, 2012, 2013 by Bundesanstalt für Gewässerkunde |
e8d2042c9639
Add missing copyright headers.
Tom Gottfried <tom@intevation.de>
parents:
8187
diff
changeset
|
2 * Software engineering by Intevation GmbH |
e8d2042c9639
Add missing copyright headers.
Tom Gottfried <tom@intevation.de>
parents:
8187
diff
changeset
|
3 * |
e8d2042c9639
Add missing copyright headers.
Tom Gottfried <tom@intevation.de>
parents:
8187
diff
changeset
|
4 * This file is Free Software under the GNU AGPL (>=v3) |
e8d2042c9639
Add missing copyright headers.
Tom Gottfried <tom@intevation.de>
parents:
8187
diff
changeset
|
5 * and comes with ABSOLUTELY NO WARRANTY! Check out the |
e8d2042c9639
Add missing copyright headers.
Tom Gottfried <tom@intevation.de>
parents:
8187
diff
changeset
|
6 * documentation coming with Dive4Elements River for details. |
e8d2042c9639
Add missing copyright headers.
Tom Gottfried <tom@intevation.de>
parents:
8187
diff
changeset
|
7 */ |
e8d2042c9639
Add missing copyright headers.
Tom Gottfried <tom@intevation.de>
parents:
8187
diff
changeset
|
8 |
8187
3bb1c62ad732
Moved package org.dive4elements.river.utils to org.dive4elements.river.backend.utils.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
7730
diff
changeset
|
9 package org.dive4elements.river.backend.utils; |
5083
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
10 |
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
|
11 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
|
12 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
13 import java.util.ArrayList; |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
14 import java.util.Collections; |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
15 import java.util.List; |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
16 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
17 public final class DouglasPeuker |
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 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
|
20 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
21 private DouglasPeuker() { |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
22 } |
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 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
|
25 return simplify(input, EPSILON); |
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 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
|
29 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
30 int N = input.size(); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
31 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
32 if (N < 3) { |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
33 return new ArrayList<XY>(input); |
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 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
36 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
|
37 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
38 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
|
39 output.add(input.get(0)); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
40 output.addAll(simplified); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
41 output.add(input.get(N-1)); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
42 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
43 return output; |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
44 } |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
45 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
46 private static List recursiveSimplify( |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
47 List<XY> input, |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
48 int start, |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
49 int end, |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
50 double epsilon |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
51 ) { |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
52 XY a = input.get(start); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
53 XY b = input.get(end); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
54 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
55 // Normal of hesse normal form. |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
56 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
|
57 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
58 // 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
|
59 double d = n.lineOffset(a); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
60 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
61 double maxDist = -Double.MAX_VALUE; |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
62 int maxIdx = -1; |
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 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
|
65 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
|
66 if (dist > maxDist) { |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
67 maxDist = dist; |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
68 maxIdx = i; |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
69 } |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
70 } |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
71 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
72 if (maxDist < epsilon) { |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
73 // 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
|
74 return Collections.<XY>emptyList(); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
75 } |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
76 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
77 // Split by input[maxIdx]. |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
78 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
|
79 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
|
80 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
81 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
|
82 output.addAll(before); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
83 output.add(input.get(maxIdx)); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
84 output.addAll(after); |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
85 |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
86 return output; |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
87 } |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
88 } |
7bbee0cfc171
Added experimental Douglas Peuker simplification of cross sections.
Sascha L. Teichmann <teichmann@intevation.de>
parents:
diff
changeset
|
89 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 : |