Mercurial > dive4elements > river

comparison flys-artifacts/src/main/java/de/intevation/flys/artifacts/geom/Polygon2D.java @ 3318:dbe2f85bf160

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merged flys-artifacts/2.8
author Thomas Arendsen Hein <thomas@intevation.de>
date Fri, 28 Sep 2012 12:14:35 +0200
parents 3c006a53e551
children
comparison
equal deleted inserted replaced
2987:98c7a46ec5ae 3318:dbe2f85bf160
1 package de.intevation.flys.artifacts.geom;
2
3 import java.awt.Shape;
4 import java.awt.geom.Path2D;
5 import java.awt.geom.Point2D;
6 import java.io.Serializable;
7 import java.util.ArrayList;
8 import java.util.Arrays;
9 import java.util.Collections;
10 import java.util.Comparator;
11 import java.util.List;
12
13 import de.intevation.flys.artifacts.math.Linear;
14 import static de.intevation.flys.artifacts.geom.VectorUtils.EPSILON;
15 import static de.intevation.flys.artifacts.geom.VectorUtils.X;
16 import static de.intevation.flys.artifacts.geom.VectorUtils.Y;
17
18 public class Polygon2D
19 implements Serializable
20 {
21 public static final Comparator<Point2D> POINT_X_CMP =
22 new Comparator<Point2D>() {
23 public int compare(Point2D a, Point2D b) {
24 double d = X(a) - X(b);
25 if (d < 0d) return -1;
26 return d > 0d ? + 1 : 0;
27 }
28 };
29
30 public static final Comparator<Point2D []> FIRST_POINT_X =
31 new Comparator<Point2D []>() {
32 public int compare(Point2D [] a, Point2D [] b) {
33 if (a.length == 0) return -1; // should not happen.
34 if (b.length == 0) return +1; // should not happen.
35 double d = X(a[0]) - Y(b[0]);
36 if (d < 0d) return -1;
37 return d > 0d ? + 1 : 0;
38 }
39 };
40
41 protected List<Point2D> points;
42
43 public Polygon2D() {
44 points = new ArrayList<Point2D>();
45 }
46
47 public Polygon2D(List<Point2D> points) {
48 this.points = points;
49 }
50
51 public void add(double x, double y) {
52 points.add(new Point2D.Double(x, y));
53 }
54
55 protected static boolean addCheck(Point2D p, List<Point2D> points) {
56 switch (points.size()) {
57 case 0:
58 points.add(p);
59 return true;
60 case 1:
61 if (VectorUtils.epsilonEquals(points.get(0), p)) {
62 return false;
63 }
64 points.add(p);
65 return true;
66 default:
67 int L = points.size()-1;
68 Point2D last = points.get(L);
69 if (VectorUtils.epsilonEquals(last, p)) {
70 return false;
71 }
72 Point2D before = points.get(L-1);
73 if (VectorUtils.collinear(before, last, p)) {
74 points.set(L, p);
75 }
76 else {
77 points.add(p);
78 }
79 return true;
80 }
81 }
82
83 public boolean addCheck(Point2D p) {
84 return addCheck(p, points);
85 }
86
87 public void addReversed(List<Point2D> other) {
88 for (int i = other.size()-1; i >= 0; --i) {
89 addCheck(other.get(i));
90 }
91 }
92
93 public double area() {
94 double area = 0d;
95
96 for (int i = 0, N = points.size(); i < N; ++i) {
97 int j = (i + 1) % N;
98 Point2D pi = points.get(i);
99 Point2D pj = points.get(j);
100 area += X(pi)*Y(pj);
101 area -= X(pj)*Y(pi);
102 }
103
104 return 0.5d*area;
105 }
106
107 public Shape toShape() {
108 Path2D.Double path = new Path2D.Double();
109
110 int N = points.size();
111
112 if (N > 0) {
113 Point2D p = points.get(0);
114 path.moveTo(X(p), Y(p));
115 for (int i = 1; i < N; ++i) {
116 p = points.get(i);
117 path.lineTo(X(p), Y(p));
118 }
119 path.closePath();
120 }
121
122 return path;
123 }
124
125 protected static List<Point2D []> splitByNaNs(
126 double [] xs,
127 double [] ys
128 ) {
129 List<Point2D []> parts = new ArrayList<Point2D []>();
130
131 List<Point2D> tmp = new ArrayList<Point2D>(xs.length);
132
133 for (int i = 0; i < xs.length; ++i) {
134 double x = xs[i];
135 double y = ys[i];
136
137 if (Double.isNaN(x) || Double.isNaN(y)) {
138 if (!tmp.isEmpty()) {
139 Point2D [] part = new Point2D[tmp.size()];
140 parts.add(tmp.toArray(part));
141 tmp.clear();
142 }
143 }
144 else {
145 tmp.add(new Point2D.Double(x, y));
146 }
147 }
148
149 if (!tmp.isEmpty()) {
150 Point2D [] part = new Point2D[tmp.size()];
151 parts.add(tmp.toArray(part));
152 }
153
154 return parts;
155 }
156
157 protected static boolean removeNoneIntersecting(
158 List<Point2D []> As,
159 List<Point2D []> Bs
160 ) {
161 int B = Bs.size()-1;
162 OUTER: for (int i = 0; i < As.size();) {
163 Point2D [] a = As.get(i);
164 int lo = 0, hi = B;
165 while (lo <= hi) {
166 int mid = (lo + hi) >> 1;
167 Point2D [] b = Bs.get(mid);
168 if (X(a[0]) > X(b[b.length-1])) lo = mid+1;
169 else if (X(a[a.length-1]) < X(b[0])) hi = mid-1;
170 else {
171 // found: keep
172 ++i;
173 continue OUTER;
174 }
175 }
176 // not found: remove
177 As.remove(i);
178 }
179
180 return As.isEmpty();
181 }
182
183 protected static void buildPolygons(
184 Point2D [] as,
185 Point2D [] bs,
186 Point2D [][] rest,
187 List<Polygon2D> positives,
188 List<Polygon2D> negatives
189 ) {
190 List<Point2D> apoints = new ArrayList<Point2D>();
191 List<Point2D> bpoints = new ArrayList<Point2D>();
192
193 double ax = X(as[0]);
194 double bx = X(bs[0]);
195
196 int ai = 1;
197 int bi = 1;
198
199 boolean intersect = false;
200
201 if (ax == bx) {
202 apoints.add(as[0]);
203 bpoints.add(bs[0]);
204 }
205 else if (ax > bx) {
206 apoints.add(as[0]);
207 double bx1;
208 while ((bx1 = X(bs[bi])) < ax) ++bi;
209 if (bx1 == ax) {
210 bpoints.add(bs[bi]);
211 }
212 else { // need to calculate start b point.
213 intersect = true;
214 double by1 = Linear.linear(
215 ax,
216 X(bs[bi-1]), bx1,
217 Y(bs[bi-1]), Y(bs[bi]));
218
219 bpoints.add(new Point2D.Double(ax, by1));
220 }
221 }
222 else { // bx > ax: Symmetric case
223 bpoints.add(bs[0]);
224 double ax1;
225 while ((ax1 = X(as[ai])) < bx) ++ai;
226 if (ax1 == bx) {
227 apoints.add(as[ai]);
228 }
229 else { // need to calculate start b point.
230 intersect = true;
231 double ay1 = Linear.linear(
232 bx,
233 X(as[ai-1]), ax1,
234 Y(as[ai-1]), Y(as[ai]));
235
236 apoints.add(new Point2D.Double(bx, ay1));
237 }
238 }
239
240 // now we have a point in each list, decide if neg/pos.
241 boolean neg = Y(bpoints.get(0)) > Y(apoints.get(0));
242
243 // Continue with inner points
244
245 Line line = new Line();
246
247 while (ai < as.length && bi < bs.length) {
248 double xan = X(as[ai]);
249 double xbn = X(bs[bi]);
250 if (xan == xbn) {
251 double yan = Y(as[ai]);
252 double ybn = Y(bs[ai]);
253
254 if (neg) {
255 if (yan > ybn) { // intersection
256 Point2D ip = VectorUtils.intersection(
257 apoints.get(apoints.size()-1), as[ai],
258 bpoints.get(bpoints.size()-1), bs[bi]);
259 addCheck(ip, apoints);
260 addCheck(ip, bpoints);
261 Polygon2D p = new Polygon2D(
262 new ArrayList<Point2D>(apoints));
263 p.addReversed(bpoints);
264 negatives.add(p);
265 apoints.clear();
266 bpoints.clear();
267 apoints.add(ip);
268 bpoints.add(ip);
269 neg = !neg;
270 }
271 else { // no intersection
272 addCheck(as[ai], apoints);
273 addCheck(bs[bi], bpoints);
274 }
275 }
276 else { // not neg
277 if (ybn > yan) { // intersection
278 Point2D ip = VectorUtils.intersection(
279 apoints.get(apoints.size()-1), as[ai],
280 bpoints.get(bpoints.size()-1), bs[bi]);
281 addCheck(ip, apoints);
282 addCheck(ip, bpoints);
283 Polygon2D p = new Polygon2D(
284 new ArrayList<Point2D>(apoints));
285 p.addReversed(bpoints);
286 positives.add(p);
287 apoints.clear();
288 bpoints.clear();
289 apoints.add(ip);
290 bpoints.add(ip);
291 neg = !neg;
292 }
293 else { // no intersection
294 addCheck(as[ai], apoints);
295 addCheck(bs[bi], bpoints);
296 }
297 }
298 ++ai;
299 ++bi;
300 }
301 else if (xan > xbn) {
302 line.set(apoints.get(apoints.size()-1), as[ai]);
303 double dir = neg ? -1d: 1d; // XXX: correct sign?
304 while (bi < bs.length
305 && X(bs[bi]) < xan
306 && line.eval(bs[bi])*dir > EPSILON)
307 ++bi;
308 if (bi == bs.length) {
309 // b run out of points
310 // calculate Y(last_a, as[ai]) for X(bs[bi-1])
311 double ay1 = Linear.linear(
312 X(bs[bi-1]),
313 X(apoints.get(apoints.size()-1)), X(as[ai]),
314 Y(apoints.get(apoints.size()-1)), Y(as[ai]));
315 addCheck(new Point2D.Double(X(bs[bi-1]), ay1), apoints);
316 addCheck(bs[bi-1], bpoints);
317 Polygon2D p = new Polygon2D(
318 new ArrayList<Point2D>(apoints));
319 p.addReversed(bpoints);
320 apoints.clear();
321 bpoints.clear();
322 (neg ? negatives : positives).add(p);
323 break;
324 }
325 else {
326 // TODO: intersect line and/or X(bs[bi]) >= xan?
327 }
328 }
329 else { // xbn > xan
330 line.set(bpoints.get(bpoints.size()-1), bs[bi]);
331 // TODO: continue symmetric
332 }
333 }
334
335 // TODO: Continue with closing segment
336 }
337
338 public static final class Line {
339
340 private double a;
341 private double b;
342 private double c;
343
344 public Line() {
345 }
346
347 public Line(Point2D p1, Point2D p2) {
348 set(p1, p2);
349 }
350
351 public void set(Point2D p1, Point2D p2) {
352 Point2D p3 =
353 VectorUtils.normalize(
354 VectorUtils.sub(p1, p2));
355
356 Point2D n = VectorUtils.ortho(p3);
357
358 a = X(n);
359 b = Y(n);
360
361 // a*x + b*y + c = 0
362 // c = -a*x -b*y
363
364 c = -a*X(p1) - b*Y(p1);
365 }
366
367 public double eval(Point2D p) {
368 return a*X(p) + b*Y(p) + c;
369 }
370 }
371
372 public static void createPolygons(
373 double [] xAs, double [] yAs,
374 double [] xBs, double [] yBs,
375 List<Polygon2D> positives,
376 List<Polygon2D> negatives
377 ) {
378 if (xAs.length == 0 || xBs.length == 0) {
379 return;
380 }
381
382 List<Point2D []> splAs = splitByNaNs(xAs, yAs);
383 List<Point2D []> splBs = splitByNaNs(xBs, yBs);
384
385 // They feeded us with NaNs only.
386 if (splAs.isEmpty() || splBs.isEmpty()) {
387 return;
388 }
389
390 // Sort each part by x to ensure that the first
391 // is the smallest.
392 for (Point2D [] splA: splAs) {
393 Arrays.sort(splA, POINT_X_CMP);
394 }
395
396 for (Point2D [] splB: splBs) {
397 Arrays.sort(splB, POINT_X_CMP);
398 }
399
400 // Now sort all parts by there first elements.
401 // Should be good enough to find overlapping regions.
402 Collections.sort(splAs, FIRST_POINT_X);
403 Collections.sort(splBs, FIRST_POINT_X);
404
405 // Check if the two series intersect at all.
406 // If no then there will be no area between them.
407
408 Point2D [] p1 = splAs.get(0);
409 Point2D [] p2 = splBs.get(splBs.size()-1);
410
411 // Sort out the ranges that are not intersecting
412 // the ranges in the other series.
413 // We are going to merge them anyway
414 // so this is not strictly required.
415 // Keep it to recude cases.
416 if (removeNoneIntersecting(splAs, splBs)
417 || removeNoneIntersecting(splBs, splAs)
418 ) {
419 // They do not intersect at all.
420 return;
421 }
422
423 // TODO: Intersect/split the two series parts.
424 }
425 }
426 // vim:set ts=4 sw=4 si et sta sts=4 fenc=utf8 :
http://dive4elements.wald.intevation.org