source: trunk/src/org/expeditee/core/bounds/PolygonBounds.java@ 1097

Last change on this file since 1097 was 1097, checked in by davidb, 6 years ago

Newly structured files from Corey's work on logic/graphics separation
File size: 13.4 KB
Line 
1package org.expeditee.core.bounds;
2
3import java.util.LinkedList;
4import java.util.List;
5
6import org.expeditee.core.Line;
7import org.expeditee.core.Point;
8
9/**
10 * A bounds that is defined as the area enclosed by a polygon formed
11 * from a set of points. When considering if something is enclosed by
12 * a polygon, the set of points is always considered closed (even if
13 * the first and last points arenn't equal).
14 *
15 * @author cts16
16 */
17public class PolygonBounds extends Bounds {
18
19 /** The points that form this polygon. */
20 private List<Point> _points;
21
22 /** The right-most extent of this bounds. */
23 Integer _maxX;
24 /** The left-most extent of this bounds. */
25 Integer _minX;
26 /** The down-most extent of this bounds. */
27 Integer _maxY;
28 /** The up-most extent of this bounds. */
29 Integer _minY;
30
31 /** Standard constructor (creates a degenerate polygon with no points). */
32 public PolygonBounds()
33 {
34 _points = new LinkedList<Point>();
35 _maxX = _minX = _maxY = _minY = null;
36 }
37
38 /** Copy constructor. */
39 public PolygonBounds(PolygonBounds other)
40 {
41 this();
42 for (Point p : other._points) {
43 addPoint(p);
44 }
45 }
46
47 /**
48 * Constructs a polygon from a set of lines. Lines should be connected
49 * end to end, otherwise the resulting polygon may not match the given input.
50 */
51 public PolygonBounds(Line[] lines)
52 {
53 this();
54 for (Line line : lines) {
55 addPoint(line.getFirstEnd());
56 }
57 addPoint(lines[lines.length - 1].getSecondEnd());
58 }
59
60 /** Adds a new point to the polygon. */
61 public void addPoint(Point p)
62 {
63 addPoint(p.x, p.y);
64 }
65
66 /** Adds a new point to the polygon. */
67 public void addPoint(int x, int y)
68 {
69 _points.add(new Point(x, y));
70 if (_maxX == null || x > _maxX.intValue()) _maxX = new Integer(x);
71 if (_minX == null || x < _minX.intValue()) _minX = new Integer(x);
72 if (_maxY == null || y > _maxY.intValue()) _maxY = new Integer(y);
73 if (_minY == null || y < _minY.intValue()) _minY = new Integer(y);
74 }
75
76 /** Gets the point at the given index in this polygon. */
77 public Point getPoint(int index)
78 {
79 if (0 <= index && index < getPointCount()) return _points.get(index).clone();
80
81 return null;
82 }
83
84 /** Returns the number of points in this polygon. */
85 public int getPointCount()
86 {
87 return _points.size();
88 }
89
90 /** Returns a copy of the points of this polygon as an array. */
91 public Point[] toArray()
92 {
93 Point[] ret = new Point[_points.size()];
94
95 for (int i = 0; i < _points.size(); i++) {
96 ret[i] = _points.get(i).clone();
97 }
98
99 return ret;
100 }
101
102 @Override
103 public PolygonBounds translate(int x, int y)
104 {
105 for (Point p : _points) p.add(x, y);
106
107 if (_maxX != null) _maxX = new Integer(_maxX.intValue() + x);
108 if (_minX != null) _minX = new Integer(_minX.intValue() + x);
109 if (_maxY != null) _maxY = new Integer(_maxY.intValue() + y);
110 if (_minY != null) _minY = new Integer(_minY.intValue() + y);
111
112 return this;
113 }
114
115 /**
116 * Rotates all of the points in this polygon about the given x/y coordinate.
117 *
118 * @param angle Clockwise angle of rotation in radians.
119 */
120 public PolygonBounds rotate(double angle, int x, int y)
121 {
122 // Rotate each point
123 for (Point p : _points) {
124 p.rotate(angle, x, y);
125 }
126
127 // Non-trivial change to mins/maxs, so recalculate
128 recalculateExtents();
129
130 return this;
131 }
132
133 /**
134 * Rotates the polygon around a point.
135 *
136 * @param angle
137 * The clockwise angle to rotate the polygon through (in radians).
138 *
139 * @param cor
140 * The centre of rotation.
141 */
142 public void rotate(double angle, Point cor)
143 {
144 rotate(angle, cor.x, cor.y);
145 }
146
147 /**
148 * Code adapted from java.awt.Polygon.contains(double x, double y).
149 *
150 * @author cts16
151 */
152 @Override
153 public boolean contains(int x, int y) {
154 int npoints = _points.size();
155 if (npoints <= 2) {
156 return false;
157 }
158
159 int hits = 0;
160
161 int lastx = _points.get(npoints - 1).x;
162 int lasty = _points.get(npoints - 1).y;
163 int curx, cury;
164
165 // Walk the edges of the polygon
166 for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) {
167 curx = _points.get(i).x;
168 cury = _points.get(i).y;
169
170 if (cury == lasty) {
171 continue;
172 }
173
174 int leftx;
175 if (curx < lastx) {
176 if (x >= lastx) {
177 continue;
178 }
179 leftx = curx;
180 } else {
181 if (x >= curx) {
182 continue;
183 }
184 leftx = lastx;
185 }
186
187 double test1, test2;
188 if (cury < lasty) {
189 if (y < cury || y >= lasty) {
190 continue;
191 }
192 if (x < leftx) {
193 hits++;
194 continue;
195 }
196 test1 = x - curx;
197 test2 = y - cury;
198 } else {
199 if (y < lasty || y >= cury) {
200 continue;
201 }
202 if (x < leftx) {
203 hits++;
204 continue;
205 }
206 test1 = x - lastx;
207 test2 = y - lasty;
208 }
209
210 if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {
211 hits++;
212 }
213 }
214
215 return ((hits & 1) != 0);
216 }
217
218 @Override
219 public int getMaxX() {
220 return _maxX != null ? _maxX : 0;
221 }
222
223 @Override
224 public int getMinX() {
225 return _minX != null ? _minX : 0;
226 }
227
228 @Override
229 public int getMaxY() {
230 return _maxY != null ? _maxY : 0;
231 }
232
233 @Override
234 public int getMinY() {
235 return _minY != null ? _minY : 0;
236 }
237
238 @Override
239 public boolean equals(Bounds other) {
240 if (other instanceof PolygonBounds) {
241 PolygonBounds p = (PolygonBounds) other;
242 if (p._points.size() == this._points.size()) {
243 for (int i = 0; i < p._points.size(); i++) {
244 if (!(p._points.get(i).equals(this._points.get(i)))) return false;
245 }
246 return true;
247 }
248 }
249
250 return false;
251 }
252
253 /** Convenience method to create a polygon in the shape of a diamond. */
254 public static PolygonBounds getDiamond(int width, int height)
255 {
256 PolygonBounds diamond = new PolygonBounds();
257
258 diamond.addPoint(0, -height / 2);
259 diamond.addPoint(width / 2, 0);
260 diamond.addPoint(0, height / 2);
261 diamond.addPoint(-width / 2, 0);
262
263 return diamond;
264 }
265
266 /** Convenience method to create a polygon in the shape of a triangle. */
267 public static PolygonBounds getTriangle(int base, int height)
268 {
269 PolygonBounds triangle = new PolygonBounds();
270
271 triangle.addPoint(0, -height / 2);
272 triangle.addPoint(base / 2, height / 2);
273 triangle.addPoint(-base / 2, height / 2);
274
275 return triangle;
276 }
277
278 @Override
279 public boolean intersects(AxisAlignedBoxBounds other) {
280 // Check if any polygon points are inside the box
281 for (Point p : _points) {
282 if (other.contains(p)) return true;
283 }
284
285 // Check if any of the border lines intersect
286 Line[] boxLines = other.getBorderLines();
287 Line[] polyLines = getBorderLines();
288 if (Line.anyIntersections(boxLines, polyLines, Line.PIXEL_ERROR)) return true;
289
290 // Check if any of the box points are inside the polygon
291 // (only test p1 as p2 is the p1 of another line)
292 for (Line boxLine : boxLines) {
293 if (contains(boxLine.getFirstEnd())) return true;
294 }
295
296 // If all tests fail, no intersection
297 return false;
298 }
299
300 @Override
301 public boolean intersects(CombinationBounds other) {
302 // Defer to the CombinationBounds routine
303 return other.intersects(this);
304 }
305
306 @Override
307 public boolean intersects(EllipticalBounds other) {
308 // Defer to the EllipticalBounds routine
309 return other.intersects(this);
310 }
311
312 @Override
313 public boolean intersects(PolygonBounds other) {
314 // Check if any of the border lines intersect
315 Line[] otherLines = other.getBorderLines();
316 Line[] thisLines = getBorderLines();
317 if (Line.anyIntersections(otherLines, thisLines, Line.PIXEL_ERROR)) return true;
318
319 // If no line intersections, one polygon must be inside the other to intersect
320 return other.contains(thisLines[0].getFirstEnd()) || this.contains(otherLines[0].getFirstEnd());
321 }
322
323 /** Gets an array of the vertices that make up this polygon. */
324 public Point[] getVertices()
325 {
326 Point[] ret = new Point[_points.size()];
327
328 for (int i = 0; i < _points.size(); i++) {
329 ret[i] = _points.get(i).clone();
330 }
331
332 return ret;
333 }
334
335 /** Gets an array of lines that represent the (closed) border of this polygon. */
336 public Line[] getBorderLines()
337 {
338 return getBorderLines(true);
339 }
340
341 /**
342 * Gets an array of lines that represent the border of this polygon.
343 *
344 * @param autoClose
345 * Whether to automatically create a line from the last point to the
346 * first to close this polygon (ignored if first and last point are equal).
347 *
348 * @return
349 * The array of border lines.
350 */
351 public Line[] getBorderLines(boolean autoClose)
352 {
353 // Don't need to autoClose if first and last points are equal
354 autoClose = autoClose && _points.get(0).equals(_points.get(_points.size() - 1));
355
356 // Calculate how many lines we will need to generate
357 int nLines = _points.size();
358 if (!autoClose) nLines--;
359
360 // Generate the lines
361 Line[] lines = new Line[nLines];
362 for (int i = 0; i < nLines; i++) {
363 Point p1 = new Point(_points.get(i));
364 Point p2 = new Point(_points.get((i + 1) % _points.size()));
365 lines[i] = new Line(p1, p2);
366 }
367
368 return lines;
369 }
370
371 @Override
372 public double getArea()
373 {
374 if (_points.size() < 3) return 0.0;
375
376 double area = 0.0;
377
378 for (int i = 0; i < _points.size(); i++) {
379 Point p1 = _points.get(i);
380 Point p2 = _points.get((i + 1) % _points.size());
381 area += p1.x * p2.y - p2.x * p1.y;
382 }
383
384 return Math.abs(area / 2);
385 }
386
387 @Override
388 public boolean perimeterContains(Point p, double error) {
389 Line[] lines = getBorderLines();
390
391 for (Line line : lines) {
392 if (line.contains(p, error)) return true;
393 }
394
395 return false;
396 }
397
398 @Override
399 public boolean completelyContains(AxisAlignedBoxBounds other)
400 {
401 // Treat the box as a polygon
402 return completelyContains(other.getPolygon());
403 }
404
405 @Override
406 public boolean completelyContains(CombinationBounds other)
407 {
408 // Can't contain nothing
409 if (other == null) return false;
410
411 // Must contain all sub-bounds of the combination bounds
412 for (Bounds bounds : other._bounds) {
413 if (!completelyContains(bounds)) return false;
414 }
415
416 return true;
417 }
418
419 @Override
420 public boolean completelyContains(EllipticalBounds other)
421 {
422 // Can't contain nothing
423 if (other == null) return false;
424
425 // No polygon vertices can be inside the ellipse
426 for (Point vertex : _points) {
427 if (other.contains(vertex)) return false;
428 }
429
430 // No boundary lines can intersect the ellipse
431 for (Line line : getBorderLines()) {
432 if (other.isIntersectedByLine(line)) return false;
433 }
434
435 return true;
436 }
437
438 @Override
439 public boolean completelyContains(PolygonBounds other)
440 {
441 // Can't contain nothing
442 if (other == null) return false;
443
444 // Must contain all points of other
445 for (Point p : other._points) {
446 if (!contains(p)) return false;
447 }
448
449 // Can't be any line intersections
450 Line[] thisLines = getBorderLines();
451 Line[] otherLines = other.getBorderLines();
452 if (Line.anyIntersections(thisLines, otherLines, Line.PIXEL_ERROR)) return false;
453
454 return true;
455 }
456
457 /** Whether the given point is a vertex of this polygon. */
458 public boolean isVertex(Point p)
459 {
460 return _points.contains(p);
461 }
462
463 /** Whether or not this polygon is closed (first and last points are equal). */
464 public boolean isClosed()
465 {
466 return _points.get(0).equals(_points.get(getPointCount() - 1));
467 }
468
469 /** Closes this polygon (adds the first point as the last). */
470 public PolygonBounds close()
471 {
472 if (!isClosed()) addPoint(_points.get(0).clone());
473
474 return this;
475 }
476
477 /** Creates a polygon that represents the same area as a box bounds. */
478 public static PolygonBounds fromBox(AxisAlignedBoxBounds box)
479 {
480 if (box == null) return null;
481
482 // Get the corners of the box
483 Point[] corners = box.getCorners();
484
485 // Add the corners to a new polygon
486 PolygonBounds ret = new PolygonBounds();
487 for (Point corner : corners) ret.addPoint(corner);
488
489 return ret.close();
490 }
491
492 /**
493 * Creates a polygon that approximates the given ellipse.
494 *
495 * @param nSegments
496 * The number of segments the resulting polygon should have. Must be at least 3.
497 */
498 public static PolygonBounds fromEllipse(EllipticalBounds ellipse, int nSegments)
499 {
500 if (ellipse == null || nSegments < 3) return null;
501
502 int centreX = ellipse.getCentre().x;
503 int centreY = ellipse.getCentre().y;
504 double xRadius = ellipse.getDiameters().width / 2.0;
505 double yRadius = ellipse.getDiameters().height / 2.0;
506 double radians = 0.0;
507
508 PolygonBounds ret = new PolygonBounds();
509 for (int i = 0; i < nSegments; i++) {
510 int x = (int) (xRadius * Math.cos(radians)) + centreX;
511 int y = (int) (yRadius * Math.sin(radians)) + centreY;
512 ret.addPoint(x, y);
513 radians += (2.0 * Math.PI) / nSegments;
514 }
515
516 return ret.close();
517 }
518
519 @Override
520 public PolygonBounds clone()
521 {
522 return new PolygonBounds(this);
523 }
524
525 /**
526 * Recalculates the min/max x/y coordinates. Normally this should be done incrementally
527 * as points are added, but sometimes you just need to completely redo them.
528 */
529 private void recalculateExtents()
530 {
531 _maxX = _minX = _maxY = _minY = null;
532
533 for (Point p : _points) {
534 if (_maxX == null || p.x > _maxX.intValue()) _maxX = new Integer(p.x);
535 if (_minX == null || p.x < _minX.intValue()) _minX = new Integer(p.x);
536 if (_maxY == null || p.y > _maxY.intValue()) _maxY = new Integer(p.y);
537 if (_minY == null || p.y < _minY.intValue()) _minY = new Integer(p.y);
538 }
539 }
540
541}
Note: See TracBrowser for help on using the repository browser.