Mercurial > dive4elements > river
comparison flys-artifacts/src/main/java/de/intevation/flys/artifacts/geom/Polygon2D.java @ 1795:fe7f9264a2ed
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 : |