Mercurial > dive4elements > river

annotate backend/src/main/java/org/dive4elements/river/backend/utils/DouglasPeuker.java @ 8187:3bb1c62ad732

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
rev   line source
8187
3bb1c62ad732 Moved package org.dive4elements.river.utils to org.dive4elements.river.backend.utils.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 7730
diff changeset
1 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
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 :
http://dive4elements.wald.intevation.org