1 package org.djutils.draw.line;
2
3 import java.awt.geom.Path2D;
4 import java.awt.geom.Path2D.Double;
5 import java.util.ArrayList;
6 import java.util.Arrays;
7 import java.util.Iterator;
8 import java.util.List;
9 import java.util.Locale;
10
11 import org.djutils.draw.DrawRuntimeException;
12 import org.djutils.draw.bounds.Bounds2d;
13 import org.djutils.draw.point.Point2d;
14 import org.djutils.exceptions.Throw;
15
16
17
18
19
20
21
22
23
24
25
26 public class Polygon2d extends PolyLine2d
27 {
28
29 private static final long serialVersionUID = 20209999L;
30
31
32
33
34
35
36
37 public Polygon2d(final double[] x, final double[] y) throws DrawRuntimeException
38 {
39 super(fixClosingPointX(Throw.whenNull(x, "x may not be null"), Throw.whenNull(y, "y may not be null")),
40 fixClosingPointY(x, y));
41 }
42
43
44
45
46
47
48
49 private static double[] fixClosingPointX(final double[] x, final double[] y)
50 {
51 if (x.length > 1 && y.length == x.length && x[0] == x[x.length - 1] && y[0] == y[x.length - 1])
52 {
53 return Arrays.copyOf(x, x.length - 1);
54 }
55 return x;
56 }
57
58
59
60
61
62
63
64 private static double[] fixClosingPointY(final double[] x, final double[] y)
65 {
66 if (x.length > 1 && y.length == x.length && x[0] == x[x.length - 1] && y[0] == y[x.length - 1])
67 {
68 return Arrays.copyOf(y, x.length - 1);
69 }
70 return y;
71 }
72
73
74
75
76
77
78
79 public Polygon2d(final Point2d[] points) throws NullPointerException, DrawRuntimeException
80 {
81 this(PolyLine2d.makeArray(points, p -> p.x), PolyLine2d.makeArray(points, p -> p.y));
82 }
83
84
85
86
87
88
89
90
91
92
93 public Polygon2d(final Point2d point1, final Point2d point2, final Point2d... otherPoints)
94 throws NullPointerException, DrawRuntimeException
95 {
96 super(Throw.whenNull(point1, "point1 may not be null"), Throw.whenNull(point2, "point2 may not be null"),
97 fixClosingPoint(point1, otherPoints));
98 }
99
100
101
102
103
104
105
106 private static Point2d[] fixClosingPoint(final Point2d point1, final Point2d[] otherPoints)
107 {
108 if (otherPoints == null || otherPoints.length == 0)
109 {
110 return otherPoints;
111 }
112 Point2d[] result = otherPoints;
113 Point2d lastPoint = result[result.length - 1];
114 if (point1.x == lastPoint.x && point1.y == lastPoint.y)
115 {
116 result = Arrays.copyOf(otherPoints, result.length - 1);
117 lastPoint = result[result.length - 1];
118 }
119 Throw.when(point1.x == lastPoint.x && point1.y == lastPoint.y, DrawRuntimeException.class,
120 "Before last point and last point are at same location");
121 return result;
122 }
123
124
125
126
127
128
129
130 public Polygon2d(final List<Point2d> points) throws NullPointerException, DrawRuntimeException
131 {
132 super(fixClosingPoint(true, Throw.whenNull(points, "points may not be null")));
133
134 }
135
136
137
138
139
140
141
142
143
144
145 private static List<Point2d> fixClosingPoint(final boolean doNotModifyList, final List<Point2d> points)
146 throws DrawRuntimeException
147 {
148 Throw.when(points.size() < 2, DrawRuntimeException.class, "Need at least two points");
149 Point2d firstPoint = points.get(0);
150 Point2d lastPoint = points.get(points.size() - 1);
151 List<Point2d> result = points;
152 if (firstPoint.x == lastPoint.x && firstPoint.y == lastPoint.y)
153 {
154 if (doNotModifyList)
155 {
156 result = new ArrayList<>(points.size() - 1);
157 for (int i = 0; i < points.size() - 1; i++)
158 {
159 result.add(points.get(i));
160 }
161 }
162 else
163 {
164 result.remove(points.size() - 1);
165 }
166 lastPoint = result.get(result.size() - 1);
167 }
168 Throw.when(firstPoint.x == lastPoint.x && firstPoint.y == lastPoint.y, DrawRuntimeException.class,
169 "Before last point and last point are at same location");
170 return result;
171 }
172
173
174
175
176
177 public Polygon2d(final Iterator<Point2d> iterator)
178 {
179 this(fixClosingPoint(false, iteratorToList(Throw.whenNull(iterator, "iterator cannot be null"))));
180 }
181
182
183
184
185
186
187
188 public Polygon2d(final boolean filterDuplicates, final Point2d... points) throws DrawRuntimeException
189 {
190 this(PolyLine2d.cleanPoints(filterDuplicates, Arrays.stream(points).iterator()));
191 }
192
193
194
195
196
197
198
199
200 public Polygon2d(final boolean filterDuplicates, final List<Point2d> pointList) throws DrawRuntimeException
201 {
202 this(PolyLine2d.cleanPoints(filterDuplicates, pointList.iterator()));
203 }
204
205
206
207
208
209
210 public final boolean isConvex()
211 {
212 int flag = 0;
213 for (int i = 0; i < size(); i++)
214 {
215 int j = (i + 1) % size();
216 int k = (j + 1) % size();
217 double z = (getX(j) - getX(i)) * (getY(k) - getY(j)) - (getY(j) - getY(i)) * (getX(k) - getX(j));
218 if (z < 0)
219 {
220 flag |= 1;
221 }
222 else if (z > 0)
223 {
224 flag |= 2;
225 }
226 if (flag == 3)
227 {
228 return false;
229 }
230 }
231 return flag != 0;
232 }
233
234
235
236
237
238
239
240 public boolean contains(final Point2d point)
241 {
242 return contains(point.x, point.y);
243 }
244
245
246
247
248
249
250
251
252
253 public boolean contains(final double x, final double y)
254 {
255 if (!getBounds().contains(x, y))
256 {
257 return false;
258 }
259 int counter = 0;
260
261 double prevPointX = getX(size() - 1);
262 double prevPointY = getY(size() - 1);
263 for (int i = 0; i < size(); i++)
264 {
265 double curPointX = getX(i);
266 double curPointY = getY(i);
267
268 if (y >= Math.min(prevPointY, curPointY) && y <= Math.max(prevPointY, curPointY)
269 && x <= Math.max(prevPointX, curPointX) && prevPointY != curPointY)
270 {
271 double xIntersection = (y - prevPointY) * (curPointX - prevPointX) / (curPointY - prevPointY) + prevPointX;
272 if (prevPointX == curPointX || x <= xIntersection)
273 {
274 counter++;
275 }
276 }
277 prevPointX = curPointX;
278 prevPointY = curPointY;
279 }
280 return counter % 2 != 0;
281 }
282
283
284
285
286
287
288
289 public boolean contains(final Bounds2d bounds)
290 {
291
292 if (getBounds().disjoint(bounds))
293 {
294 return false;
295 }
296
297 return toPath2D().contains(bounds.getMinX(), bounds.getMinY(), bounds.getDeltaX(), bounds.getDeltaY());
298 }
299
300
301
302
303
304
305 public boolean intersects(final Polygon2d other)
306 {
307
308 if (!getBounds().intersects(other.getBounds()))
309 {
310 return false;
311 }
312
313
314 for (Iterator<Point2d> iterator = getPoints(); iterator.hasNext();)
315 {
316 if (other.contains(iterator.next()))
317 {
318 return true;
319 }
320 }
321
322
323 for (Iterator<Point2d> iterator = other.getPoints(); iterator.hasNext();)
324 {
325 if (contains(iterator.next()))
326 {
327 return true;
328 }
329 }
330
331
332 for (int i = 0; i < this.size(); i++)
333 {
334 LineSegment2d ourSegment = getSegment(i);
335 for (int j = 0; j < other.size(); j++)
336 {
337 LineSegment2d otherSegment = other.getSegment(j);
338 Point2d intersection = Point2d.intersectionOfLineSegments(ourSegment, otherSegment);
339 if (intersection != null)
340 {
341 double p1x = ourSegment.startX, p1y = ourSegment.startY;
342 double d1x = ourSegment.endX - p1x, d1y = ourSegment.endY - p1y;
343 double p2x = otherSegment.startX, p2y = otherSegment.startY;
344 double d2x = otherSegment.endX - p2x, d2y = otherSegment.endY - p2y;
345
346 double det = d2x * d1y - d2y * d1x;
347 if (det != 0)
348 {
349 double z = (d2x * (p2y - p1y) + d2y * (p1x - p2x)) / det;
350 if (Math.abs(z) < 10.0 * Math.ulp(1.0) || Math.abs(z - 1.0) > 10.0 * Math.ulp(1.0))
351 {
352 return true;
353 }
354 }
355
356 }
357 }
358 }
359 return false;
360 }
361
362
363
364
365
366
367 public double surface()
368 {
369
370 Point2d midPoint = getBounds().midPoint();
371 double result = 0;
372
373 double prevX = getX(size() - 1) - midPoint.x;
374 double prevY = getY(size() - 1) - midPoint.y;
375 for (int i = 0; i < size(); i++)
376 {
377 double thisX = getX(i) - midPoint.x;
378 double thisY = getY(i) - midPoint.y;
379 result += prevX * thisY - thisX * prevY;
380 prevX = thisX;
381 prevY = thisY;
382 }
383 return result / 2;
384 }
385
386
387 @Override
388 public double getLength()
389 {
390
391 return super.getLength() + Math.hypot(getX(size() - 1) - getX(0), getY(size() - 1) - getY(0));
392 }
393
394
395 @Override
396 public LineSegment2d getSegment(final int index)
397 {
398 if (index < size() - 1)
399 {
400 return super.getSegment(index);
401 }
402 Throw.when(index != size() - 1, DrawRuntimeException.class, "index must be in range 0..size() - 1");
403 return new LineSegment2d(getX(index), getY(index), getX(0), getY(0));
404 }
405
406
407 @Override
408 public Polygon2d reverse()
409 {
410 return new Polygon2d(super.reverse().getPoints());
411 }
412
413
414
415
416
417 @Override
418 public Path2D toPath2D()
419 {
420 Path2D.Double result = (Double) super.toPath2D();
421 result.closePath();
422 return result;
423 }
424
425
426 @Override
427 public final String toExcel()
428 {
429 StringBuffer s = new StringBuffer();
430 for (int i = 0; i < size(); i++)
431 {
432 s.append(getX(i) + "\t" + getY(i) + "\n");
433 }
434 s.append(getX(0) + "\t" + getY(0) + "\n");
435 return s.toString();
436 }
437
438
439 @Override
440 public final String toPlot()
441 {
442 StringBuffer result = new StringBuffer();
443 for (int i = 0; i < size(); i++)
444 {
445 result.append(String.format(Locale.US, "%s%.3f,%.3f", 0 == result.length() ? "M" : " L", getX(i), getY(i)));
446 }
447 result.append(String.format(Locale.US, " L%.3f,%.3f", getX(0), getY(0)));
448 result.append("\n");
449 return result.toString();
450 }
451
452
453 @Override
454 public final String toString()
455 {
456 return toString("%f", false);
457 }
458
459
460 @Override
461 public String toString(final String doubleFormat, final boolean doNotIncludeClassName)
462 {
463 StringBuilder result = new StringBuilder();
464 if (!doNotIncludeClassName)
465 {
466 result.append("Polygon2d ");
467 }
468 result.append("[super=");
469 result.append(super.toString(doubleFormat, false));
470 result.append("]");
471 return result.toString();
472 }
473
474 }