Mercurial > dive4elements > river

comparison flys-artifacts/src/main/java/de/intevation/flys/artifacts/geom/Polygon2D.java @ 1795:fe7f9264a2ed

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Interim checkin for polygon calculation. flys-artifacts/trunk@3118 c6561f87-3c4e-4783-a992-168aeb5c3f6f
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Sun, 30 Oct 2011 19:28:59 +0000
parents 2ad7ba85a2b3
children 5eec623db50a
comparison
equal deleted inserted replaced
1794:2ad7ba85a2b3 1795:fe7f9264a2ed
1 package de.intevation.flys.geom; 1 package de.intevation.flys.geom;
2
3 import gnu.trove.TDoubleArrayList;
4 2
5 import java.io.Serializable; 3 import java.io.Serializable;
6 4
7 import java.awt.Shape; 5 import java.awt.Shape;
8 6
16 import java.util.Collections; 14 import java.util.Collections;
17 15
18 public class Polygon2D 16 public class Polygon2D
19 implements Serializable 17 implements Serializable
20 { 18 {
19 public static final double EPSILON = 1e-4;
20
21 private static final double X(Point2D p) {
22 return p.getX();
23 }
24
25 private static final double Y(Point2D p) {
26 return p.getY();
27 }
28
21 public static final Comparator<Point2D> POINT_X_CMP = 29 public static final Comparator<Point2D> POINT_X_CMP =
22 new Comparator<Point2D>() { 30 new Comparator<Point2D>() {
23 public int compare(Point2D a, Point2D b) { 31 public int compare(Point2D a, Point2D b) {
24 double d = a.getX() - b.getX(); 32 double d = X(a) - X(b);
25 if (d < 0d) return -1; 33 if (d < 0d) return -1;
26 return d > 0d ? + 1 : 0; 34 return d > 0d ? + 1 : 0;
27 } 35 }
28 }; 36 };
29 37
30 public static final Comparator<Point2D []> FIRST_POINT_X = 38 public static final Comparator<Point2D []> FIRST_POINT_X =
31 new Comparator<Point2D []>() { 39 new Comparator<Point2D []>() {
32 public int compare(Point2D [] a, Point2D [] b) { 40 public int compare(Point2D [] a, Point2D [] b) {
33 if (a.length == 0) return -1; // should not happen. 41 if (a.length == 0) return -1; // should not happen.
34 if (b.length == 0) return +1; // should not happen. 42 if (b.length == 0) return +1; // should not happen.
35 double d = a[0].getX() - b[0].getX(); 43 double d = X(a[0]) - Y(b[0]);
36 if (d < 0d) return -1; 44 if (d < 0d) return -1;
37 return d > 0d ? + 1 : 0; 45 return d > 0d ? + 1 : 0;
38 } 46 }
39 }; 47 };
40 48
41 protected TDoubleArrayList xs; 49 protected List<Point2D> points;
42 protected TDoubleArrayList ys;
43 50
44 public Polygon2D() { 51 public Polygon2D() {
45 xs = new TDoubleArrayList(); 52 points = new ArrayList<Point2D>();
46 ys = new TDoubleArrayList(); 53 }
54
55 public static boolean epsilonEquals(Point2D a, Point2D b) {
56 return Math.abs(X(a)-X(b)) < EPSILON
57 && Math.abs(Y(a)-Y(b)) < EPSILON;
47 } 58 }
48 59
49 public void add(double x, double y) { 60 public void add(double x, double y) {
50 xs.add(x); 61 points.add(new Point2D.Double(x, y));
51 ys.add(y); 62 }
63
64 public boolean addCheck(Point2D p) {
65 switch (points.size()) {
66 case 0:
67 points.add(p);
68 return true;
69 case 1:
70 if (epsilonEquals(points.get(0), p)) {
71 return false;
72 }
73 points.add(p);
74 return true;
75 default:
76 int L = points.size()-1;
77 Point2D last = points.get(L);
78 if (epsilonEquals(last, p)) {
79 return false;
80 }
81 Point2D before = points.get(L-1);
82 if (collinear(before, last, p)) {
83 points.set(L, p);
84 }
85 else {
86 points.add(p);
87 }
88 return true;
89 }
90 }
91
92 public void addReversed(List<Point2D> other) {
93 for (int i = other.size()-1; i >= 0; --i) {
94 addCheck(other.get(i));
95 }
96 }
97
98 private static final double L1(Point2D a, Point2D b) {
99 return Math.abs(X(a)-X(b)) + Math.abs(Y(a)-Y(b));
100 }
101
102 public static boolean collinear(Point2D a, Point2D b, Point2D c) {
103 double dab = L1(a, b);
104 double dac = L1(a, c);
105 double dbc = L1(b, c);
106
107 Point2D p1, p2, p3;
108
109 if (dab > dac) {
110 if (dab > dbc) {
111 p1 = a;
112 p2 = b;
113 p3 = c;
114 }
115 else { // dbc >= dab
116 p1 = b;
117 p2 = c;
118 p3 = a;
119 }
120 }
121 else { // dac >= dab
122 if (dac > dbc) {
123 p1 = a;
124 p2 = c;
125 p3 = b;
126 }
127 else { // dbc >= dac
128 p1 = b;
129 p2 = c;
130 p3 = a;
131 }
132 }
133
134 // TODO: Continue here.
135
136
137 return true;
138 }
139
140 public static Point2D sub(Point2D a, Point2D b) {
141 return new Point2D.Double(X(a)-X(b), Y(a)-Y(b));
142 }
143
144 public static Point2D scale(Point2D a, double s) {
145 return new Point2D.Double(s*X(a), s*Y(a));
52 } 146 }
53 147
54 public double area() { 148 public double area() {
55 double area = 0d; 149 double area = 0d;
56 150
57 for (int i = 0, N = xs.size(); i < N; ++i) { 151 for (int i = 0, N = points.size(); i < N; ++i) {
58 int j = (i + 1) % N; 152 int j = (i + 1) % N;
59 area += xs.getQuick(i)*ys.getQuick(j); 153 Point2D pi = points.get(i);
60 area -= xs.getQuick(j)*ys.getQuick(i); 154 Point2D pj = points.get(j);
155 area += X(pi)*Y(pj);
156 area -= X(pj)*Y(pi);
61 } 157 }
62 158
63 return 0.5d*area; 159 return 0.5d*area;
64 } 160 }
65 161
66 public Shape toShape() { 162 public Shape toShape() {
67 Path2D.Double path = new Path2D.Double(); 163 Path2D.Double path = new Path2D.Double();
68 164
69 int N = xs.size(); 165 int N = points.size();
70 166
71 if (N > 0) { 167 if (N > 0) {
72 path.moveTo(xs.getQuick(0), ys.getQuick(0)); 168 Point2D p = points.get(0);
169 path.moveTo(X(p), Y(p));
73 for (int i = 1; i < N; ++i) { 170 for (int i = 1; i < N; ++i) {
74 path.lineTo(xs.getQuick(i), ys.getQuick(i)); 171 p = points.get(i);
172 path.lineTo(X(p), Y(p));
75 } 173 }
76 path.closePath(); 174 path.closePath();
77 } 175 }
78 176
79 return path; 177 return path;
107 Point2D [] part = new Point2D[tmp.size()]; 205 Point2D [] part = new Point2D[tmp.size()];
108 parts.add(tmp.toArray(part)); 206 parts.add(tmp.toArray(part));
109 } 207 }
110 208
111 return parts; 209 return parts;
210 }
211
212 protected static boolean removeNoneIntersecting(
213 List<Point2D []> As,
214 List<Point2D []> Bs
215 ) {
216 OUTER: for (int i = 0; i < As.size();) {
217 Point2D [] a = As.get(i);
218 int lo = 0, hi = Bs.size()-1;
219 while (lo <= hi) {
220 int mid = (lo + hi) >> 1;
221 Point2D [] b = Bs.get(mid);
222 if (X(a[0]) > X(b[b.length-1])) lo = mid+1;
223 else if (X(a[a.length-1]) < X(b[0])) hi = mid-1;
224 else {
225 // found: keep
226 ++i;
227 continue OUTER;
228 }
229 }
230 // not found: remove
231 As.remove(i);
232 }
233
234 return As.isEmpty();
235 }
236
237 protected static void buildPolygons(
238 Point2D [] as,
239 Point2D [] bs,
240 Point2D [][] rest,
241 List<Polygon2D> positives,
242 List<Polygon2D> negatives
243 ) {
112 } 244 }
113 245
114 public static void createPolygons( 246 public static void createPolygons(
115 double [] xAs, double [] yAs, 247 double [] xAs, double [] yAs,
116 double [] xBs, double [] yBs, 248 double [] xBs, double [] yBs,
148 // If no then there will be no area between them. 280 // If no then there will be no area between them.
149 281
150 Point2D [] p1 = splAs.get(0); 282 Point2D [] p1 = splAs.get(0);
151 Point2D [] p2 = splBs.get(splBs.size()-1); 283 Point2D [] p2 = splBs.get(splBs.size()-1);
152 284
153 // First of As greater than last of Bs. 285 // Sort out the ranges that are not intersecting
154 if (POINT_X_CMP.compare(p1[0], p2[p2.length-1]) > 0) { 286 // the ranges in the other series.
287 // We are going to merge them anyway
288 // so this is not strictly required.
289 // Keep it to recude cases.
290 if (removeNoneIntersecting(splAs, splBs)
291 || removeNoneIntersecting(splBs, splAs)
292 ) {
293 // They do not intersect at all.
155 return; 294 return;
156 } 295 }
157 296
158 p2 = splAs.get(splAs.size()-1);
159 p1 = splBs.get(0);
160
161 // First of Bs greater than last of As.
162 if (POINT_X_CMP.compare(p1[0], p2[p2.length-1]) > 0) {
163 return;
164 }
165
166 // TODO: Intersect/split the two series parts. 297 // TODO: Intersect/split the two series parts.
167
168 } 298 }
169 } 299 }
170 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 : 300 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :
http://dive4elements.wald.intevation.org