Polygon


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