1 /*
2 * Copyright (c) 1995, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25 package java.awt;
26
27 import java.awt.geom.AffineTransform;
28 import java.awt.geom.PathIterator;
29 import java.awt.geom.Point2D;
30 import java.awt.geom.Rectangle2D;
31 import sun.awt.geom.Crossings;
32 import java.util.Arrays;
33
34 /**
35 * The <code>Polygon</code> class encapsulates a description of a
36 * closed, two-dimensional region within a coordinate space. This
37 * region is bounded by an arbitrary number of line segments, each of
38 * which is one side of the polygon. Internally, a polygon
39 * comprises of a list of {@code (x,y)}
40 * coordinate pairs, where each pair defines a <i>vertex</i> of the
41 * polygon, and two successive pairs are the endpoints of a
42 * line that is a side of the polygon. The first and final
43 * pairs of {@code (x,y)} points are joined by a line segment
44 * that closes the polygon. This <code>Polygon</code> is defined with
45 * an even-odd winding rule. See
46 * {@link java.awt.geom.PathIterator#WIND_EVEN_ODD WIND_EVEN_ODD}
47 * for a definition of the even-odd winding rule.
48 * This class's hit-testing methods, which include the
49 * <code>contains</code>, <code>intersects</code> and <code>inside</code>
50 * methods, use the <i>insideness</i> definition described in the
51 * {@link Shape} class comments.
52 *
53 * @author Sami Shaio
54 * @see Shape
55 * @author Herb Jellinek
56 * @since 1.0
57 */
58 public class Polygon implements Shape, java.io.Serializable {
59
60 /**
61 * The total number of points. The value of <code>npoints</code>
62 * represents the number of valid points in this <code>Polygon</code>
63 * and might be less than the number of elements in
64 * {@link #xpoints xpoints} or {@link #ypoints ypoints}.
65 * This value can be NULL.
66 *
67 * @serial
68 * @see #addPoint(int, int)
69 * @since 1.0
70 */
71 public int npoints;
72
73 /**
74 * The array of X coordinates. The number of elements in
75 * this array might be more than the number of X coordinates
76 * in this <code>Polygon</code>. The extra elements allow new points
77 * to be added to this <code>Polygon</code> without re-creating this
78 * array. The value of {@link #npoints npoints} is equal to the
79 * number of valid points in this <code>Polygon</code>.
80 *
81 * @serial
82 * @see #addPoint(int, int)
83 * @since 1.0
84 */
85 public int xpoints[];
86
87 /**
88 * The array of Y coordinates. The number of elements in
89 * this array might be more than the number of Y coordinates
90 * in this <code>Polygon</code>. The extra elements allow new points
91 * to be added to this <code>Polygon</code> without re-creating this
92 * array. The value of <code>npoints</code> is equal to the
93 * number of valid points in this <code>Polygon</code>.
94 *
95 * @serial
96 * @see #addPoint(int, int)
97 * @since 1.0
98 */
99 public int ypoints[];
100
101 /**
102 * The bounds of this {@code Polygon}.
103 * This value can be null.
104 *
105 * @serial
106 * @see #getBoundingBox()
107 * @see #getBounds()
108 * @since 1.0
109 */
110 protected Rectangle bounds;
111
112 /*
113 * JDK 1.1 serialVersionUID
114 */
115 private static final long serialVersionUID = -6460061437900069969L;
116
117 /*
118 * Default length for xpoints and ypoints.
119 */
120 private static final int MIN_LENGTH = 4;
121
122 /**
123 * Creates an empty polygon.
124 * @since 1.0
125 */
126 public Polygon() {
127 xpoints = new int[MIN_LENGTH];
128 ypoints = new int[MIN_LENGTH];
129 }
130
131 /**
132 * Constructs and initializes a <code>Polygon</code> from the specified
133 * parameters.
134 * @param xpoints an array of X coordinates
135 * @param ypoints an array of Y coordinates
136 * @param npoints the total number of points in the
137 * <code>Polygon</code>
138 * @exception NegativeArraySizeException if the value of
139 * <code>npoints</code> is negative.
140 * @exception IndexOutOfBoundsException if <code>npoints</code> is
141 * greater than the length of <code>xpoints</code>
142 * or the length of <code>ypoints</code>.
143 * @exception NullPointerException if <code>xpoints</code> or
144 * <code>ypoints</code> is <code>null</code>.
145 * @since 1.0
146 */
147 public Polygon(int xpoints[], int ypoints[], int npoints) {
148 // Fix 4489009: should throw IndexOutofBoundsException instead
149 // of OutofMemoryException if npoints is huge and > {x,y}points.length
150 if (npoints > xpoints.length || npoints > ypoints.length) {
151 throw new IndexOutOfBoundsException("npoints > xpoints.length || "+
152 "npoints > ypoints.length");
153 }
154 // Fix 6191114: should throw NegativeArraySizeException with
155 // negative npoints
156 if (npoints < 0) {
157 throw new NegativeArraySizeException("npoints < 0");
158 }
159 // Fix 6343431: Applet compatibility problems if arrays are not
160 // exactly npoints in length
161 this.npoints = npoints;
162 this.xpoints = Arrays.copyOf(xpoints, npoints);
163 this.ypoints = Arrays.copyOf(ypoints, npoints);
164 }
165
166 /**
167 * Resets this <code>Polygon</code> object to an empty polygon.
168 * The coordinate arrays and the data in them are left untouched
169 * but the number of points is reset to zero to mark the old
170 * vertex data as invalid and to start accumulating new vertex
171 * data at the beginning.
172 * All internally-cached data relating to the old vertices
173 * are discarded.
174 * Note that since the coordinate arrays from before the reset
175 * are reused, creating a new empty <code>Polygon</code> might
176 * be more memory efficient than resetting the current one if
177 * the number of vertices in the new polygon data is significantly
178 * smaller than the number of vertices in the data from before the
179 * reset.
180 * @see java.awt.Polygon#invalidate
181 * @since 1.4
182 */
183 public void reset() {
184 npoints = 0;
185 bounds = null;
186 }
187
188 /**
189 * Invalidates or flushes any internally-cached data that depends
190 * on the vertex coordinates of this <code>Polygon</code>.
191 * This method should be called after any direct manipulation
192 * of the coordinates in the <code>xpoints</code> or
193 * <code>ypoints</code> arrays to avoid inconsistent results
194 * from methods such as <code>getBounds</code> or <code>contains</code>
195 * that might cache data from earlier computations relating to
196 * the vertex coordinates.
197 * @see java.awt.Polygon#getBounds
198 * @since 1.4
199 */
200 public void invalidate() {
201 bounds = null;
202 }
203
204 /**
205 * Translates the vertices of the <code>Polygon</code> by
206 * <code>deltaX</code> along the x axis and by
207 * <code>deltaY</code> along the y axis.
208 * @param deltaX the amount to translate along the X axis
209 * @param deltaY the amount to translate along the Y axis
210 * @since 1.1
211 */
212 public void translate(int deltaX, int deltaY) {
213 for (int i = 0; i < npoints; i++) {
214 xpoints[i] += deltaX;
215 ypoints[i] += deltaY;
216 }
217 if (bounds != null) {
218 bounds.translate(deltaX, deltaY);
219 }
220 }
221
222 /*
223 * Calculates the bounding box of the points passed to the constructor.
224 * Sets <code>bounds</code> to the result.
225 * @param xpoints[] array of <i>x</i> coordinates
226 * @param ypoints[] array of <i>y</i> coordinates
227 * @param npoints the total number of points
228 */
229 void calculateBounds(int xpoints[], int ypoints[], int npoints) {
230 int boundsMinX = Integer.MAX_VALUE;
231 int boundsMinY = Integer.MAX_VALUE;
232 int boundsMaxX = Integer.MIN_VALUE;
233 int boundsMaxY = Integer.MIN_VALUE;
234
235 for (int i = 0; i < npoints; i++) {
236 int x = xpoints[i];
237 boundsMinX = Math.min(boundsMinX, x);
238 boundsMaxX = Math.max(boundsMaxX, x);
239 int y = ypoints[i];
240 boundsMinY = Math.min(boundsMinY, y);
241 boundsMaxY = Math.max(boundsMaxY, y);
242 }
243 bounds = new Rectangle(boundsMinX, boundsMinY,
244 boundsMaxX - boundsMinX,
245 boundsMaxY - boundsMinY);
246 }
247
248 /*
249 * Resizes the bounding box to accommodate the specified coordinates.
250 * @param x, y the specified coordinates
251 */
252 void updateBounds(int x, int y) {
253 if (x < bounds.x) {
254 bounds.width = bounds.width + (bounds.x - x);
255 bounds.x = x;
256 }
257 else {
258 bounds.width = Math.max(bounds.width, x - bounds.x);
259 // bounds.x = bounds.x;
260 }
261
262 if (y < bounds.y) {
263 bounds.height = bounds.height + (bounds.y - y);
264 bounds.y = y;
265 }
266 else {
267 bounds.height = Math.max(bounds.height, y - bounds.y);
268 // bounds.y = bounds.y;
269 }
270 }
271
272 /**
273 * Appends the specified coordinates to this <code>Polygon</code>.
274 * <p>
275 * If an operation that calculates the bounding box of this
276 * <code>Polygon</code> has already been performed, such as
277 * <code>getBounds</code> or <code>contains</code>, then this
278 * method updates the bounding box.
279 * @param x the specified X coordinate
280 * @param y the specified Y coordinate
281 * @see java.awt.Polygon#getBounds
282 * @see java.awt.Polygon#contains
283 * @since 1.0
284 */
285 public void addPoint(int x, int y) {
286 if (npoints >= xpoints.length || npoints >= ypoints.length) {
287 int newLength = npoints * 2;
288 // Make sure that newLength will be greater than MIN_LENGTH and
289 // aligned to the power of 2
290 if (newLength < MIN_LENGTH) {
291 newLength = MIN_LENGTH;
292 } else if ((newLength & (newLength - 1)) != 0) {
293 newLength = Integer.highestOneBit(newLength);
294 }
295
296 xpoints = Arrays.copyOf(xpoints, newLength);
297 ypoints = Arrays.copyOf(ypoints, newLength);
298 }
299 xpoints[npoints] = x;
300 ypoints[npoints] = y;
301 npoints++;
302 if (bounds != null) {
303 updateBounds(x, y);
304 }
305 }
306
307 /**
308 * Gets the bounding box of this <code>Polygon</code>.
309 * The bounding box is the smallest {@link Rectangle} whose
310 * sides are parallel to the x and y axes of the
311 * coordinate space, and can completely contain the <code>Polygon</code>.
312 * @return a <code>Rectangle</code> that defines the bounds of this
313 * <code>Polygon</code>.
314 * @since 1.1
315 */
316 public Rectangle getBounds() {
317 return getBoundingBox();
318 }
319
320 /**
321 * Returns the bounds of this <code>Polygon</code>.
322 * @return the bounds of this <code>Polygon</code>.
323 * @deprecated As of JDK version 1.1,
324 * replaced by <code>getBounds()</code>.
325 * @since 1.0
326 */
327 @Deprecated
328 public Rectangle getBoundingBox() {
329 if (npoints == 0) {
330 return new Rectangle();
331 }
332 if (bounds == null) {
333 calculateBounds(xpoints, ypoints, npoints);
334 }
335 return bounds.getBounds();
336 }
337
338 /**
339 * Determines whether the specified {@link Point} is inside this
340 * <code>Polygon</code>.
341 * @param p the specified <code>Point</code> to be tested
342 * @return <code>true</code> if the <code>Polygon</code> contains the
343 * <code>Point</code>; <code>false</code> otherwise.
344 * @see #contains(double, double)
345 * @since 1.0
346 */
347 public boolean contains(Point p) {
348 return contains(p.x, p.y);
349 }
350
351 /**
352 * Determines whether the specified coordinates are inside this
353 * <code>Polygon</code>.
354 * <p>
355 * @param x the specified X coordinate to be tested
356 * @param y the specified Y coordinate to be tested
357 * @return {@code true} if this {@code Polygon} contains
358 * the specified coordinates {@code (x,y)};
359 * {@code false} otherwise.
360 * @see #contains(double, double)
361 * @since 1.1
362 */
363 public boolean contains(int x, int y) {
364 return contains((double) x, (double) y);
365 }
366
367 /**
368 * Determines whether the specified coordinates are contained in this
369 * <code>Polygon</code>.
370 * @param x the specified X coordinate to be tested
371 * @param y the specified Y coordinate to be tested
372 * @return {@code true} if this {@code Polygon} contains
373 * the specified coordinates {@code (x,y)};
374 * {@code false} otherwise.
375 * @see #contains(double, double)
376 * @deprecated As of JDK version 1.1,
377 * replaced by <code>contains(int, int)</code>.
378 * @since 1.0
379 */
380 @Deprecated
381 public boolean inside(int x, int y) {
382 return contains((double) x, (double) y);
383 }
384
385 /**
386 * {@inheritDoc}
387 * @since 1.2
388 */
389 public Rectangle2D getBounds2D() {
390 return getBounds();
391 }
392
393 /**
394 * {@inheritDoc}
395 * @since 1.2
396 */
397 public boolean contains(double x, double y) {
398 if (npoints <= 2 || !getBoundingBox().contains(x, y)) {
399 return false;
400 }
401 int hits = 0;
402
403 int lastx = xpoints[npoints - 1];
404 int lasty = ypoints[npoints - 1];
405 int curx, cury;
406
407 // Walk the edges of the polygon
408 for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) {
409 curx = xpoints[i];
410 cury = ypoints[i];
411
412 if (cury == lasty) {
413 continue;
414 }
415
416 int leftx;
417 if (curx < lastx) {
418 if (x >= lastx) {
419 continue;
420 }
421 leftx = curx;
422 } else {
423 if (x >= curx) {
424 continue;
425 }
426 leftx = lastx;
427 }
428
429 double test1, test2;
430 if (cury < lasty) {
431 if (y < cury || y >= lasty) {
432 continue;
433 }
434 if (x < leftx) {
435 hits++;
436 continue;
437 }
438 test1 = x - curx;
439 test2 = y - cury;
440 } else {
441 if (y < lasty || y >= cury) {
442 continue;
443 }
444 if (x < leftx) {
445 hits++;
446 continue;
447 }
448 test1 = x - lastx;
449 test2 = y - lasty;
450 }
451
452 if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {
453 hits++;
454 }
455 }
456
457 return ((hits & 1) != 0);
458 }
459
460 private Crossings getCrossings(double xlo, double ylo,
461 double xhi, double yhi)
462 {
463 Crossings cross = new Crossings.EvenOdd(xlo, ylo, xhi, yhi);
464 int lastx = xpoints[npoints - 1];
465 int lasty = ypoints[npoints - 1];
466 int curx, cury;
467
468 // Walk the edges of the polygon
469 for (int i = 0; i < npoints; i++) {
470 curx = xpoints[i];
471 cury = ypoints[i];
472 if (cross.accumulateLine(lastx, lasty, curx, cury)) {
473 return null;
474 }
475 lastx = curx;
476 lasty = cury;
477 }
478
479 return cross;
480 }
481
482 /**
483 * {@inheritDoc}
484 * @since 1.2
485 */
486 public boolean contains(Point2D p) {
487 return contains(p.getX(), p.getY());
488 }
489
490 /**
491 * {@inheritDoc}
492 * @since 1.2
493 */
494 public boolean intersects(double x, double y, double w, double h) {
495 if (npoints <= 0 || !getBoundingBox().intersects(x, y, w, h)) {
496 return false;
497 }
498
499 Crossings cross = getCrossings(x, y, x+w, y+h);
500 return (cross == null || !cross.isEmpty());
501 }
502
503 /**
504 * {@inheritDoc}
505 * @since 1.2
506 */
507 public boolean intersects(Rectangle2D r) {
508 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
509 }
510
511 /**
512 * {@inheritDoc}
513 * @since 1.2
514 */
515 public boolean contains(double x, double y, double w, double h) {
516 if (npoints <= 0 || !getBoundingBox().intersects(x, y, w, h)) {
517 return false;
518 }
519
520 Crossings cross = getCrossings(x, y, x+w, y+h);
521 return (cross != null && cross.covers(y, y+h));
522 }
523
524 /**
525 * {@inheritDoc}
526 * @since 1.2
527 */
528 public boolean contains(Rectangle2D r) {
529 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
530 }
531
532 /**
533 * Returns an iterator object that iterates along the boundary of this
534 * <code>Polygon</code> and provides access to the geometry
535 * of the outline of this <code>Polygon</code>. An optional
536 * {@link AffineTransform} can be specified so that the coordinates
537 * returned in the iteration are transformed accordingly.
538 * @param at an optional <code>AffineTransform</code> to be applied to the
539 * coordinates as they are returned in the iteration, or
540 * <code>null</code> if untransformed coordinates are desired
541 * @return a {@link PathIterator} object that provides access to the
542 * geometry of this <code>Polygon</code>.
543 * @since 1.2
544 */
545 public PathIterator getPathIterator(AffineTransform at) {
546 return new PolygonPathIterator(this, at);
547 }
548
549 /**
550 * Returns an iterator object that iterates along the boundary of
551 * the <code>Shape</code> and provides access to the geometry of the
552 * outline of the <code>Shape</code>. Only SEG_MOVETO, SEG_LINETO, and
553 * SEG_CLOSE point types are returned by the iterator.
554 * Since polygons are already flat, the <code>flatness</code> parameter
555 * is ignored. An optional <code>AffineTransform</code> can be specified
556 * in which case the coordinates returned in the iteration are transformed
557 * accordingly.
558 * @param at an optional <code>AffineTransform</code> to be applied to the
559 * coordinates as they are returned in the iteration, or
560 * <code>null</code> if untransformed coordinates are desired
561 * @param flatness the maximum amount that the control points
562 * for a given curve can vary from colinear before a subdivided
563 * curve is replaced by a straight line connecting the
564 * endpoints. Since polygons are already flat the
565 * <code>flatness</code> parameter is ignored.
566 * @return a <code>PathIterator</code> object that provides access to the
567 * <code>Shape</code> object's geometry.
568 * @since 1.2
569 */
570 public PathIterator getPathIterator(AffineTransform at, double flatness) {
571 return getPathIterator(at);
572 }
573
574 class PolygonPathIterator implements PathIterator {
575 Polygon poly;
576 AffineTransform transform;
577 int index;
578
579 public PolygonPathIterator(Polygon pg, AffineTransform at) {
580 poly = pg;
581 transform = at;
582 if (pg.npoints == 0) {
583 // Prevent a spurious SEG_CLOSE segment
584 index = 1;
585 }
586 }
587
588 /**
589 * Returns the winding rule for determining the interior of the
590 * path.
591 * @return an integer representing the current winding rule.
592 * @see PathIterator#WIND_NON_ZERO
593 */
594 public int getWindingRule() {
595 return WIND_EVEN_ODD;
596 }
597
598 /**
599 * Tests if there are more points to read.
600 * @return <code>true</code> if there are more points to read;
601 * <code>false</code> otherwise.
602 */
603 public boolean isDone() {
604 return index > poly.npoints;
605 }
606
607 /**
608 * Moves the iterator forwards, along the primary direction of
609 * traversal, to the next segment of the path when there are
610 * more points in that direction.
611 */
612 public void next() {
613 index++;
614 }
615
616 /**
617 * Returns the coordinates and type of the current path segment in
618 * the iteration.
619 * The return value is the path segment type:
620 * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE.
621 * A <code>float</code> array of length 2 must be passed in and
622 * can be used to store the coordinates of the point(s).
623 * Each point is stored as a pair of <code>float</code> x, y
624 * coordinates. SEG_MOVETO and SEG_LINETO types return one
625 * point, and SEG_CLOSE does not return any points.
626 * @param coords a <code>float</code> array that specifies the
627 * coordinates of the point(s)
628 * @return an integer representing the type and coordinates of the
629 * current path segment.
630 * @see PathIterator#SEG_MOVETO
631 * @see PathIterator#SEG_LINETO
632 * @see PathIterator#SEG_CLOSE
633 */
634 public int currentSegment(float[] coords) {
635 if (index >= poly.npoints) {
636 return SEG_CLOSE;
637 }
638 coords[0] = poly.xpoints[index];
639 coords[1] = poly.ypoints[index];
640 if (transform != null) {
641 transform.transform(coords, 0, coords, 0, 1);
642 }
643 return (index == 0 ? SEG_MOVETO : SEG_LINETO);
644 }
645
646 /**
647 * Returns the coordinates and type of the current path segment in
648 * the iteration.
649 * The return value is the path segment type:
650 * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE.
651 * A <code>double</code> array of length 2 must be passed in and
652 * can be used to store the coordinates of the point(s).
653 * Each point is stored as a pair of <code>double</code> x, y
654 * coordinates.
655 * SEG_MOVETO and SEG_LINETO types return one point,
656 * and SEG_CLOSE does not return any points.
657 * @param coords a <code>double</code> array that specifies the
658 * coordinates of the point(s)
659 * @return an integer representing the type and coordinates of the
660 * current path segment.
661 * @see PathIterator#SEG_MOVETO
662 * @see PathIterator#SEG_LINETO
663 * @see PathIterator#SEG_CLOSE
664 */
665 public int currentSegment(double[] coords) {
666 if (index >= poly.npoints) {
667 return SEG_CLOSE;
668 }
669 coords[0] = poly.xpoints[index];
670 coords[1] = poly.ypoints[index];
671 if (transform != null) {
672 transform.transform(coords, 0, coords, 0, 1);
673 }
674 return (index == 0 ? SEG_MOVETO : SEG_LINETO);
675 }
676 }
677 }