Mercurial > dive4elements > river

annotate backend/src/main/java/org/dive4elements/river/backend/utils/DouglasPeuker.java @ 9801:1d7a72a50183 3.2.x tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Assume Compose V2, consistently
author Tom Gottfried <tom@intevation.de>
date Thu, 23 Nov 2023 10:14:13 +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 :
http://dive4elements.wald.intevation.org