001 /*
002 * Copyright 1995-2006 Sun Microsystems, Inc. All Rights Reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation. Sun designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Sun in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022 * CA 95054 USA or visit www.sun.com if you need additional information or
023 * have any questions.
024 */
025 package java.awt;
026
027 import java.awt.geom.AffineTransform;
028 import java.awt.geom.PathIterator;
029 import java.awt.geom.Point2D;
030 import java.awt.geom.Rectangle2D;
031 import sun.awt.geom.Crossings;
032 import java.util.Arrays;
033
034 /**
035 * The <code>Polygon</code> class encapsulates a description of a
036 * closed, two-dimensional region within a coordinate space. This
037 * region is bounded by an arbitrary number of line segments, each of
038 * which is one side of the polygon. Internally, a polygon
039 * comprises of a list of {@code (x,y)}
040 * coordinate pairs, where each pair defines a <i>vertex</i> of the
041 * polygon, and two successive pairs are the endpoints of a
042 * line that is a side of the polygon. The first and final
043 * pairs of {@code (x,y)} points are joined by a line segment
044 * that closes the polygon. This <code>Polygon</code> is defined with
045 * an even-odd winding rule. See
046 * {@link java.awt.geom.PathIterator#WIND_EVEN_ODD WIND_EVEN_ODD}
047 * for a definition of the even-odd winding rule.
048 * This class's hit-testing methods, which include the
049 * <code>contains</code>, <code>intersects</code> and <code>inside</code>
050 * methods, use the <i>insideness</i> definition described in the
051 * {@link Shape} class comments.
052 *
053 * @version 1.26, 07/24/98
054 * @author Sami Shaio
055 * @see Shape
056 * @author Herb Jellinek
057 * @since 1.0
058 */
059 public class Polygon implements Shape, java.io.Serializable {
060
061 /**
062 * The total number of points. The value of <code>npoints</code>
063 * represents the number of valid points in this <code>Polygon</code>
064 * and might be less than the number of elements in
065 * {@link #xpoints xpoints} or {@link #ypoints ypoints}.
066 * This value can be NULL.
067 *
068 * @serial
069 * @see #addPoint(int, int)
070 * @since 1.0
071 */
072 public int npoints;
073
074 /**
075 * The array of X coordinates. The number of elements in
076 * this array might be more than the number of X coordinates
077 * in this <code>Polygon</code>. The extra elements allow new points
078 * to be added to this <code>Polygon</code> without re-creating this
079 * array. The value of {@link #npoints npoints} is equal to the
080 * number of valid points in this <code>Polygon</code>.
081 *
082 * @serial
083 * @see #addPoint(int, int)
084 * @since 1.0
085 */
086 public int xpoints[];
087
088 /**
089 * The array of Y coordinates. The number of elements in
090 * this array might be more than the number of Y coordinates
091 * in this <code>Polygon</code>. The extra elements allow new points
092 * to be added to this <code>Polygon</code> without re-creating this
093 * array. The value of <code>npoints</code> is equal to the
094 * number of valid points in this <code>Polygon</code>.
095 *
096 * @serial
097 * @see #addPoint(int, int)
098 * @since 1.0
099 */
100 public int ypoints[];
101
102 /**
103 * The bounds of this {@code Polygon}.
104 * This value can be null.
105 *
106 * @serial
107 * @see #getBoundingBox()
108 * @see #getBounds()
109 * @since 1.0
110 */
111 protected Rectangle bounds;
112
113 /*
114 * JDK 1.1 serialVersionUID
115 */
116 private static final long serialVersionUID = -6460061437900069969L;
117
118 /*
119 * Default length for xpoints and ypoints.
120 */
121 private static final int MIN_LENGTH = 4;
122
123 /**
124 * Creates an empty polygon.
125 * @since 1.0
126 */
127 public Polygon() {
128 xpoints = new int[MIN_LENGTH];
129 ypoints = new int[MIN_LENGTH];
130 }
131
132 /**
133 * Constructs and initializes a <code>Polygon</code> from the specified
134 * parameters.
135 * @param xpoints an array of X coordinates
136 * @param ypoints an array of Y coordinates
137 * @param npoints the total number of points in the
138 * <code>Polygon</code>
139 * @exception NegativeArraySizeException if the value of
140 * <code>npoints</code> is negative.
141 * @exception IndexOutOfBoundsException if <code>npoints</code> is
142 * greater than the length of <code>xpoints</code>
143 * or the length of <code>ypoints</code>.
144 * @exception NullPointerException if <code>xpoints</code> or
145 * <code>ypoints</code> is <code>null</code>.
146 * @since 1.0
147 */
148 public Polygon(int xpoints[], int ypoints[], int npoints) {
149 // Fix 4489009: should throw IndexOutofBoundsException instead
150 // of OutofMemoryException if npoints is huge and > {x,y}points.length
151 if (npoints > xpoints.length || npoints > ypoints.length) {
152 throw new IndexOutOfBoundsException(
153 "npoints > xpoints.length || "
154 + "npoints > ypoints.length");
155 }
156 // Fix 6191114: should throw NegativeArraySizeException with
157 // negative npoints
158 if (npoints < 0) {
159 throw new NegativeArraySizeException("npoints < 0");
160 }
161 // Fix 6343431: Applet compatibility problems if arrays are not
162 // exactly npoints in length
163 this .npoints = npoints;
164 this .xpoints = Arrays.copyOf(xpoints, npoints);
165 this .ypoints = Arrays.copyOf(ypoints, npoints);
166 }
167
168 /**
169 * Resets this <code>Polygon</code> object to an empty polygon.
170 * The coordinate arrays and the data in them are left untouched
171 * but the number of points is reset to zero to mark the old
172 * vertex data as invalid and to start accumulating new vertex
173 * data at the beginning.
174 * All internally-cached data relating to the old vertices
175 * are discarded.
176 * Note that since the coordinate arrays from before the reset
177 * are reused, creating a new empty <code>Polygon</code> might
178 * be more memory efficient than resetting the current one if
179 * the number of vertices in the new polygon data is significantly
180 * smaller than the number of vertices in the data from before the
181 * reset.
182 * @see java.awt.Polygon#invalidate
183 * @since 1.4
184 */
185 public void reset() {
186 npoints = 0;
187 bounds = null;
188 }
189
190 /**
191 * Invalidates or flushes any internally-cached data that depends
192 * on the vertex coordinates of this <code>Polygon</code>.
193 * This method should be called after any direct manipulation
194 * of the coordinates in the <code>xpoints</code> or
195 * <code>ypoints</code> arrays to avoid inconsistent results
196 * from methods such as <code>getBounds</code> or <code>contains</code>
197 * that might cache data from earlier computations relating to
198 * the vertex coordinates.
199 * @see java.awt.Polygon#getBounds
200 * @since 1.4
201 */
202 public void invalidate() {
203 bounds = null;
204 }
205
206 /**
207 * Translates the vertices of the <code>Polygon</code> by
208 * <code>deltaX</code> along the x axis and by
209 * <code>deltaY</code> along the y axis.
210 * @param deltaX the amount to translate along the X axis
211 * @param deltaY the amount to translate along the Y axis
212 * @since 1.1
213 */
214 public void translate(int deltaX, int deltaY) {
215 for (int i = 0; i < npoints; i++) {
216 xpoints[i] += deltaX;
217 ypoints[i] += deltaY;
218 }
219 if (bounds != null) {
220 bounds.translate(deltaX, deltaY);
221 }
222 }
223
224 /*
225 * Calculates the bounding box of the points passed to the constructor.
226 * Sets <code>bounds</code> to the result.
227 * @param xpoints[] array of <i>x</i> coordinates
228 * @param ypoints[] array of <i>y</i> coordinates
229 * @param npoints the total number of points
230 */
231 void calculateBounds(int xpoints[], int ypoints[], int npoints) {
232 int boundsMinX = Integer.MAX_VALUE;
233 int boundsMinY = Integer.MAX_VALUE;
234 int boundsMaxX = Integer.MIN_VALUE;
235 int boundsMaxY = Integer.MIN_VALUE;
236
237 for (int i = 0; i < npoints; i++) {
238 int x = xpoints[i];
239 boundsMinX = Math.min(boundsMinX, x);
240 boundsMaxX = Math.max(boundsMaxX, x);
241 int y = ypoints[i];
242 boundsMinY = Math.min(boundsMinY, y);
243 boundsMaxY = Math.max(boundsMaxY, y);
244 }
245 bounds = new Rectangle(boundsMinX, boundsMinY, boundsMaxX
246 - boundsMinX, boundsMaxY - boundsMinY);
247 }
248
249 /*
250 * Resizes the bounding box to accomodate the specified coordinates.
251 * @param x, y the specified coordinates
252 */
253 void updateBounds(int x, int y) {
254 if (x < bounds.x) {
255 bounds.width = bounds.width + (bounds.x - x);
256 bounds.x = x;
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 } else {
266 bounds.height = Math.max(bounds.height, y - bounds.y);
267 // bounds.y = bounds.y;
268 }
269 }
270
271 /**
272 * Appends the specified coordinates to this <code>Polygon</code>.
273 * <p>
274 * If an operation that calculates the bounding box of this
275 * <code>Polygon</code> has already been performed, such as
276 * <code>getBounds</code> or <code>contains</code>, then this
277 * method updates the bounding box.
278 * @param x the specified X coordinate
279 * @param y the specified Y coordinate
280 * @see java.awt.Polygon#getBounds
281 * @see java.awt.Polygon#contains
282 * @since 1.0
283 */
284 public void addPoint(int x, int y) {
285 if (npoints >= xpoints.length || npoints >= ypoints.length) {
286 int newLength = npoints * 2;
287 // Make sure that newLength will be greater than MIN_LENGTH and
288 // aligned to the power of 2
289 if (newLength < MIN_LENGTH) {
290 newLength = MIN_LENGTH;
291 } else if ((newLength & (newLength - 1)) != 0) {
292 newLength = Integer.highestOneBit(newLength);
293 }
294
295 xpoints = Arrays.copyOf(xpoints, newLength);
296 ypoints = Arrays.copyOf(ypoints, newLength);
297 }
298 xpoints[npoints] = x;
299 ypoints[npoints] = y;
300 npoints++;
301 if (bounds != null) {
302 updateBounds(x, y);
303 }
304 }
305
306 /**
307 * Gets the bounding box of this <code>Polygon</code>.
308 * The bounding box is the smallest {@link Rectangle} whose
309 * sides are parallel to the x and y axes of the
310 * coordinate space, and can completely contain the <code>Polygon</code>.
311 * @return a <code>Rectangle</code> that defines the bounds of this
312 * <code>Polygon</code>.
313 * @since 1.1
314 */
315 public Rectangle getBounds() {
316 return getBoundingBox();
317 }
318
319 /**
320 * Returns the bounds of this <code>Polygon</code>.
321 * @return the bounds of this <code>Polygon</code>.
322 * @deprecated As of JDK version 1.1,
323 * replaced by <code>getBounds()</code>.
324 * @since 1.0
325 */
326 @Deprecated
327 public Rectangle getBoundingBox() {
328 if (npoints == 0) {
329 return new Rectangle();
330 }
331 if (bounds == null) {
332 calculateBounds(xpoints, ypoints, npoints);
333 }
334 return bounds.getBounds();
335 }
336
337 /**
338 * Determines whether the specified {@link Point} is inside this
339 * <code>Polygon</code>.
340 * @param p the specified <code>Point</code> to be tested
341 * @return <code>true</code> if the <code>Polygon</code> contains the
342 * <code>Point</code>; <code>false</code> otherwise.
343 * @see #contains(double, double)
344 * @since 1.0
345 */
346 public boolean contains(Point p) {
347 return contains(p.x, p.y);
348 }
349
350 /**
351 * Determines whether the specified coordinates are inside this
352 * <code>Polygon</code>.
353 * <p>
354 * @param x the specified X coordinate to be tested
355 * @param y the specified Y coordinate to be tested
356 * @return {@code true} if this {@code Polygon} contains
357 * the specified coordinates {@code (x,y)};
358 * {@code false} otherwise.
359 * @see #contains(double, double)
360 * @since 1.1
361 */
362 public boolean contains(int x, int y) {
363 return contains((double) x, (double) y);
364 }
365
366 /**
367 * Determines whether the specified coordinates are contained in this
368 * <code>Polygon</code>.
369 * @param x the specified X coordinate to be tested
370 * @param y the specified Y coordinate to be tested
371 * @return {@code true} if this {@code Polygon} contains
372 * the specified coordinates {@code (x,y)};
373 * {@code false} otherwise.
374 * @see #contains(double, double)
375 * @deprecated As of JDK version 1.1,
376 * replaced by <code>contains(int, int)</code>.
377 * @since 1.0
378 */
379 @Deprecated
380 public boolean inside(int x, int y) {
381 return contains((double) x, (double) y);
382 }
383
384 /**
385 * {@inheritDoc}
386 * @since 1.2
387 */
388 public Rectangle2D getBounds2D() {
389 return getBounds();
390 }
391
392 /**
393 * {@inheritDoc}
394 * @since 1.2
395 */
396 public boolean contains(double x, double y) {
397 if (npoints <= 2 || !getBoundingBox().contains(x, y)) {
398 return false;
399 }
400 int hits = 0;
401
402 int lastx = xpoints[npoints - 1];
403 int lasty = ypoints[npoints - 1];
404 int curx, cury;
405
406 // Walk the edges of the polygon
407 for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) {
408 curx = xpoints[i];
409 cury = ypoints[i];
410
411 if (cury == lasty) {
412 continue;
413 }
414
415 int leftx;
416 if (curx < lastx) {
417 if (x >= lastx) {
418 continue;
419 }
420 leftx = curx;
421 } else {
422 if (x >= curx) {
423 continue;
424 }
425 leftx = lastx;
426 }
427
428 double test1, test2;
429 if (cury < lasty) {
430 if (y < cury || y >= lasty) {
431 continue;
432 }
433 if (x < leftx) {
434 hits++;
435 continue;
436 }
437 test1 = x - curx;
438 test2 = y - cury;
439 } else {
440 if (y < lasty || y >= cury) {
441 continue;
442 }
443 if (x < leftx) {
444 hits++;
445 continue;
446 }
447 test1 = x - lastx;
448 test2 = y - lasty;
449 }
450
451 if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {
452 hits++;
453 }
454 }
455
456 return ((hits & 1) != 0);
457 }
458
459 private Crossings getCrossings(double xlo, double ylo, double xhi,
460 double yhi) {
461 Crossings cross = new Crossings.EvenOdd(xlo, ylo, xhi, yhi);
462 int lastx = xpoints[npoints - 1];
463 int lasty = ypoints[npoints - 1];
464 int curx, cury;
465
466 // Walk the edges of the polygon
467 for (int i = 0; i < npoints; i++) {
468 curx = xpoints[i];
469 cury = ypoints[i];
470 if (cross.accumulateLine(lastx, lasty, curx, cury)) {
471 return null;
472 }
473 lastx = curx;
474 lasty = cury;
475 }
476
477 return cross;
478 }
479
480 /**
481 * {@inheritDoc}
482 * @since 1.2
483 */
484 public boolean contains(Point2D p) {
485 return contains(p.getX(), p.getY());
486 }
487
488 /**
489 * {@inheritDoc}
490 * @since 1.2
491 */
492 public boolean intersects(double x, double y, double w, double h) {
493 if (npoints <= 0 || !getBoundingBox().intersects(x, y, w, h)) {
494 return false;
495 }
496
497 Crossings cross = getCrossings(x, y, x + w, y + h);
498 return (cross == null || !cross.isEmpty());
499 }
500
501 /**
502 * {@inheritDoc}
503 * @since 1.2
504 */
505 public boolean intersects(Rectangle2D r) {
506 return intersects(r.getX(), r.getY(), r.getWidth(), r
507 .getHeight());
508 }
509
510 /**
511 * {@inheritDoc}
512 * @since 1.2
513 */
514 public boolean contains(double x, double y, double w, double h) {
515 if (npoints <= 0 || !getBoundingBox().intersects(x, y, w, h)) {
516 return false;
517 }
518
519 Crossings cross = getCrossings(x, y, x + w, y + h);
520 return (cross != null && cross.covers(y, y + h));
521 }
522
523 /**
524 * {@inheritDoc}
525 * @since 1.2
526 */
527 public boolean contains(Rectangle2D r) {
528 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
529 }
530
531 /**
532 * Returns an iterator object that iterates along the boundary of this
533 * <code>Polygon</code> and provides access to the geometry
534 * of the outline of this <code>Polygon</code>. An optional
535 * {@link AffineTransform} can be specified so that the coordinates
536 * returned in the iteration are transformed accordingly.
537 * @param at an optional <code>AffineTransform</code> to be applied to the
538 * coordinates as they are returned in the iteration, or
539 * <code>null</code> if untransformed coordinates are desired
540 * @return a {@link PathIterator} object that provides access to the
541 * geometry of this <code>Polygon</code>.
542 * @since 1.2
543 */
544 public PathIterator getPathIterator(AffineTransform at) {
545 return new PolygonPathIterator(this , at);
546 }
547
548 /**
549 * Returns an iterator object that iterates along the boundary of
550 * the <code>Shape</code> and provides access to the geometry of the
551 * outline of the <code>Shape</code>. Only SEG_MOVETO, SEG_LINETO, and
552 * SEG_CLOSE point types are returned by the iterator.
553 * Since polygons are already flat, the <code>flatness</code> parameter
554 * is ignored. An optional <code>AffineTransform</code> can be specified
555 * in which case the coordinates returned in the iteration are transformed
556 * accordingly.
557 * @param at an optional <code>AffineTransform</code> to be applied to the
558 * coordinates as they are returned in the iteration, or
559 * <code>null</code> if untransformed coordinates are desired
560 * @param flatness the maximum amount that the control points
561 * for a given curve can vary from colinear before a subdivided
562 * curve is replaced by a straight line connecting the
563 * endpoints. Since polygons are already flat the
564 * <code>flatness</code> parameter is ignored.
565 * @return a <code>PathIterator</code> object that provides access to the
566 * <code>Shape</code> object's geometry.
567 * @since 1.2
568 */
569 public PathIterator getPathIterator(AffineTransform at,
570 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 }
|