View Javadoc
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,&nbsp;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,&nbsp;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,&nbsp;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 }