001    /* Polygon.java -- class representing a polygon
002       Copyright (C) 1999, 2002, 2004, 2005  Free Software Foundation, Inc.
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    
039    package java.awt;
040    
041    import java.awt.geom.AffineTransform;
042    import java.awt.geom.Line2D;
043    import java.awt.geom.PathIterator;
044    import java.awt.geom.Point2D;
045    import java.awt.geom.Rectangle2D;
046    import java.io.Serializable;
047    
048    /**
049     * This class represents a polygon, a closed, two-dimensional region in a
050     * coordinate space. The region is bounded by an arbitrary number of line
051     * segments, between (x,y) coordinate vertices. The polygon has even-odd
052     * winding, meaning that a point is inside the shape if it crosses the
053     * boundary an odd number of times on the way to infinity.
054     *
055     * <p>There are some public fields; if you mess with them in an inconsistent
056     * manner, it is your own fault when you get NullPointerException,
057     * ArrayIndexOutOfBoundsException, or invalid results. Also, this class is
058     * not threadsafe.
059     *
060     * @author Aaron M. Renn (arenn@urbanophile.com)
061     * @author Eric Blake (ebb9@email.byu.edu)
062     * @since 1.0
063     * @status updated to 1.4
064     */
065    public class Polygon implements Shape, Serializable
066    {
067      /**
068       * Compatible with JDK 1.0+.
069       */
070      private static final long serialVersionUID = -6460061437900069969L;
071    
072      /**
073       * This total number of endpoints.
074       *
075       * @serial the number of endpoints, possibly less than the array sizes
076       */
077      public int npoints;
078    
079      /**
080       * The array of X coordinates of endpoints. This should not be null.
081       *
082       * @see #addPoint(int, int)
083       * @serial the x coordinates
084       */
085      public int[] xpoints;
086    
087      /**
088       * The array of Y coordinates of endpoints. This should not be null.
089       *
090       * @see #addPoint(int, int)
091       * @serial the y coordinates
092       */
093      public int[] ypoints;
094    
095      /**
096       * The bounding box of this polygon. This is lazily created and cached, so
097       * it must be invalidated after changing points.
098       *
099       * @see #getBounds()
100       * @serial the bounding box, or null
101       */
102      protected Rectangle bounds;
103    
104      /** A big number, but not so big it can't survive a few float operations */
105      private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0;
106    
107      /**
108       * Initializes an empty polygon.
109       */
110      public Polygon()
111      {
112        // Leave room for growth.
113        xpoints = new int[4];
114        ypoints = new int[4];
115      }
116    
117      /**
118       * Create a new polygon with the specified endpoints. The arrays are copied,
119       * so that future modifications to the parameters do not affect the polygon.
120       *
121       * @param xpoints the array of X coordinates for this polygon
122       * @param ypoints the array of Y coordinates for this polygon
123       * @param npoints the total number of endpoints in this polygon
124       * @throws NegativeArraySizeException if npoints is negative
125       * @throws IndexOutOfBoundsException if npoints exceeds either array
126       * @throws NullPointerException if xpoints or ypoints is null
127       */
128      public Polygon(int[] xpoints, int[] ypoints, int npoints)
129      {
130        this.xpoints = new int[npoints];
131        this.ypoints = new int[npoints];
132        System.arraycopy(xpoints, 0, this.xpoints, 0, npoints);
133        System.arraycopy(ypoints, 0, this.ypoints, 0, npoints);
134        this.npoints = npoints;
135      }
136    
137      /**
138       * Reset the polygon to be empty. The arrays are left alone, to avoid object
139       * allocation, but the number of points is set to 0, and all cached data
140       * is discarded. If you are discarding a huge number of points, it may be
141       * more efficient to just create a new Polygon.
142       *
143       * @see #invalidate()
144       * @since 1.4
145       */
146      public void reset()
147      {
148        npoints = 0;
149        invalidate();
150      }
151    
152      /**
153       * Invalidate or flush all cached data. After direct manipulation of the
154       * public member fields, this is necessary to avoid inconsistent results
155       * in methods like <code>contains</code>.
156       *
157       * @see #getBounds()
158       * @since 1.4
159       */
160      public void invalidate()
161      {
162        bounds = null;
163      }
164    
165      /**
166       * Translates the polygon by adding the specified values to all X and Y
167       * coordinates. This updates the bounding box, if it has been calculated.
168       *
169       * @param dx the amount to add to all X coordinates
170       * @param dy the amount to add to all Y coordinates
171       * @since 1.1
172       */
173      public void translate(int dx, int dy)
174      {
175        int i = npoints;
176        while (--i >= 0)
177          {
178            xpoints[i] += dx;
179            ypoints[i] += dy;
180          }
181        if (bounds != null)
182          {
183            bounds.x += dx;
184            bounds.y += dy;
185          }
186      }
187    
188      /**
189       * Adds the specified endpoint to the polygon. This updates the bounding
190       * box, if it has been created.
191       *
192       * @param x the X coordinate of the point to add
193       * @param y the Y coordiante of the point to add
194       */
195      public void addPoint(int x, int y)
196      {
197        if (npoints + 1 > xpoints.length)
198          {
199            int[] newx = new int[npoints + 1];
200            System.arraycopy(xpoints, 0, newx, 0, npoints);
201            xpoints = newx;
202          }
203        if (npoints + 1 > ypoints.length)
204          {
205            int[] newy = new int[npoints + 1];
206            System.arraycopy(ypoints, 0, newy, 0, npoints);
207            ypoints = newy;
208          }
209        xpoints[npoints] = x;
210        ypoints[npoints] = y;
211        npoints++;
212        if (bounds != null)
213          {
214            if (npoints == 1)
215              {
216                bounds.x = x;
217                bounds.y = y;
218              }
219            else
220              {
221                if (x < bounds.x)
222                  {
223                    bounds.width += bounds.x - x;
224                    bounds.x = x;
225                  }
226                else if (x > bounds.x + bounds.width)
227                  bounds.width = x - bounds.x;
228                if (y < bounds.y)
229                  {
230                    bounds.height += bounds.y - y;
231                    bounds.y = y;
232                  }
233                else if (y > bounds.y + bounds.height)
234                  bounds.height = y - bounds.y;
235              }
236          }
237      }
238    
239      /**
240       * Returns the bounding box of this polygon. This is the smallest
241       * rectangle with sides parallel to the X axis that will contain this
242       * polygon.
243       *
244       * @return the bounding box for this polygon
245       * @see #getBounds2D()
246       * @since 1.1
247       */
248      public Rectangle getBounds()
249      {
250        return getBoundingBox();
251      }
252    
253      /**
254       * Returns the bounding box of this polygon. This is the smallest
255       * rectangle with sides parallel to the X axis that will contain this
256       * polygon.
257       *
258       * @return the bounding box for this polygon
259       * @see #getBounds2D()
260       * @deprecated use {@link #getBounds()} instead
261       */
262      public Rectangle getBoundingBox()
263      {
264        if (bounds == null)
265          {
266            if (npoints == 0)
267              return bounds = new Rectangle();
268            int i = npoints - 1;
269            int minx = xpoints[i];
270            int maxx = minx;
271            int miny = ypoints[i];
272            int maxy = miny;
273            while (--i >= 0)
274              {
275                int x = xpoints[i];
276                int y = ypoints[i];
277                if (x < minx)
278                  minx = x;
279                else if (x > maxx)
280                  maxx = x;
281                if (y < miny)
282                  miny = y;
283                else if (y > maxy)
284                  maxy = y;
285              }
286            bounds = new Rectangle(minx, miny, maxx - minx, maxy - miny);
287          }
288        return bounds;
289      }
290    
291      /**
292       * Tests whether or not the specified point is inside this polygon.
293       *
294       * @param p the point to test
295       * @return true if the point is inside this polygon
296       * @throws NullPointerException if p is null
297       * @see #contains(double, double)
298       */
299      public boolean contains(Point p)
300      {
301        return contains(p.getX(), p.getY());
302      }
303    
304      /**
305       * Tests whether or not the specified point is inside this polygon.
306       *
307       * @param x the X coordinate of the point to test
308       * @param y the Y coordinate of the point to test
309       * @return true if the point is inside this polygon
310       * @see #contains(double, double)
311       * @since 1.1
312       */
313      public boolean contains(int x, int y)
314      {
315        return contains((double) x, (double) y);
316      }
317    
318      /**
319       * Tests whether or not the specified point is inside this polygon.
320       *
321       * @param x the X coordinate of the point to test
322       * @param y the Y coordinate of the point to test
323       * @return true if the point is inside this polygon
324       * @see #contains(double, double)
325       * @deprecated use {@link #contains(int, int)} instead
326       */
327      public boolean inside(int x, int y)
328      {
329        return contains((double) x, (double) y);
330      }
331    
332      /**
333       * Returns a high-precision bounding box of this polygon. This is the
334       * smallest rectangle with sides parallel to the X axis that will contain
335       * this polygon.
336       *
337       * @return the bounding box for this polygon
338       * @see #getBounds()
339       * @since 1.2
340       */
341      public Rectangle2D getBounds2D()
342      {
343        // For polygons, the integer version is exact!
344        return getBounds();
345      }
346    
347      /**
348       * Tests whether or not the specified point is inside this polygon.
349       *
350       * @param x the X coordinate of the point to test
351       * @param y the Y coordinate of the point to test
352       * @return true if the point is inside this polygon
353       * @since 1.2
354       */
355      public boolean contains(double x, double y)
356      {
357        return ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0);
358      }
359    
360      /**
361       * Tests whether or not the specified point is inside this polygon.
362       *
363       * @param p the point to test
364       * @return true if the point is inside this polygon
365       * @throws NullPointerException if p is null
366       * @see #contains(double, double)
367       * @since 1.2
368       */
369      public boolean contains(Point2D p)
370      {
371        return contains(p.getX(), p.getY());
372      }
373    
374      /**
375       * Test if a high-precision rectangle intersects the shape. This is true
376       * if any point in the rectangle is in the shape. This implementation is
377       * precise.
378       *
379       * @param x the x coordinate of the rectangle
380       * @param y the y coordinate of the rectangle
381       * @param w the width of the rectangle, treated as point if negative
382       * @param h the height of the rectangle, treated as point if negative
383       * @return true if the rectangle intersects this shape
384       * @since 1.2
385       */
386      public boolean intersects(double x, double y, double w, double h)
387      {
388        /* Does any edge intersect? */
389        if (evaluateCrossings(x, y, false, w) != 0 /* top */
390            || evaluateCrossings(x, y + h, false, w) != 0 /* bottom */
391            || evaluateCrossings(x + w, y, true, h) != 0 /* right */
392            || evaluateCrossings(x, y, true, h) != 0) /* left */
393          return true;
394    
395        /* No intersections, is any point inside? */
396        if ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0)
397          return true;
398    
399        return false;
400      }
401    
402      /**
403       * Test if a high-precision rectangle intersects the shape. This is true
404       * if any point in the rectangle is in the shape. This implementation is
405       * precise.
406       *
407       * @param r the rectangle
408       * @return true if the rectangle intersects this shape
409       * @throws NullPointerException if r is null
410       * @see #intersects(double, double, double, double)
411       * @since 1.2
412       */
413      public boolean intersects(Rectangle2D r)
414      {
415        return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
416      }
417    
418      /**
419       * Test if a high-precision rectangle lies completely in the shape. This is
420       * true if all points in the rectangle are in the shape. This implementation
421       * is precise.
422       *
423       * @param x the x coordinate of the rectangle
424       * @param y the y coordinate of the rectangle
425       * @param w the width of the rectangle, treated as point if negative
426       * @param h the height of the rectangle, treated as point if negative
427       * @return true if the rectangle is contained in this shape
428       * @since 1.2
429       */
430      public boolean contains(double x, double y, double w, double h)
431      {
432        if (! getBounds2D().intersects(x, y, w, h))
433          return false;
434    
435        /* Does any edge intersect? */
436        if (evaluateCrossings(x, y, false, w) != 0 /* top */
437            || evaluateCrossings(x, y + h, false, w) != 0 /* bottom */
438            || evaluateCrossings(x + w, y, true, h) != 0 /* right */
439            || evaluateCrossings(x, y, true, h) != 0) /* left */
440          return false;
441    
442        /* No intersections, is any point inside? */
443        if ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0)
444          return true;
445    
446        return false;
447      }
448    
449      /**
450       * Test if a high-precision rectangle lies completely in the shape. This is
451       * true if all points in the rectangle are in the shape. This implementation
452       * is precise.
453       *
454       * @param r the rectangle
455       * @return true if the rectangle is contained in this shape
456       * @throws NullPointerException if r is null
457       * @see #contains(double, double, double, double)
458       * @since 1.2
459       */
460      public boolean contains(Rectangle2D r)
461      {
462        return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
463      }
464    
465      /**
466       * Return an iterator along the shape boundary. If the optional transform
467       * is provided, the iterator is transformed accordingly. Each call returns
468       * a new object, independent from others in use. This class is not
469       * threadsafe to begin with, so the path iterator is not either.
470       *
471       * @param transform an optional transform to apply to the iterator
472       * @return a new iterator over the boundary
473       * @since 1.2
474       */
475      public PathIterator getPathIterator(final AffineTransform transform)
476      {
477        return new PathIterator()
478          {
479            /** The current vertex of iteration. */
480            private int vertex;
481    
482            public int getWindingRule()
483            {
484              return WIND_EVEN_ODD;
485            }
486    
487            public boolean isDone()
488            {
489              return vertex > npoints;
490            }
491    
492            public void next()
493            {
494              vertex++;
495            }
496    
497            public int currentSegment(float[] coords)
498            {
499              if (vertex >= npoints)
500                return SEG_CLOSE;
501              coords[0] = xpoints[vertex];
502              coords[1] = ypoints[vertex];
503              if (transform != null)
504                transform.transform(coords, 0, coords, 0, 1);
505              return vertex == 0 ? SEG_MOVETO : SEG_LINETO;
506            }
507    
508            public int currentSegment(double[] coords)
509            {
510              if (vertex >= npoints)
511                return SEG_CLOSE;
512              coords[0] = xpoints[vertex];
513              coords[1] = ypoints[vertex];
514              if (transform != null)
515                transform.transform(coords, 0, coords, 0, 1);
516              return vertex == 0 ? SEG_MOVETO : SEG_LINETO;
517            }
518          };
519      }
520    
521      /**
522       * Return an iterator along the flattened version of the shape boundary.
523       * Since polygons are already flat, the flatness parameter is ignored, and
524       * the resulting iterator only has SEG_MOVETO, SEG_LINETO and SEG_CLOSE
525       * points. If the optional transform is provided, the iterator is
526       * transformed accordingly. Each call returns a new object, independent
527       * from others in use. This class is not threadsafe to begin with, so the
528       * path iterator is not either.
529       *
530       * @param transform an optional transform to apply to the iterator
531       * @param flatness the maximum distance for deviation from the real boundary
532       * @return a new iterator over the boundary
533       * @since 1.2
534       */
535      public PathIterator getPathIterator(AffineTransform transform,
536                                          double flatness)
537      {
538        return getPathIterator(transform);
539      }
540    
541      /**
542       * Helper for contains, intersects, calculates the number of intersections
543       * between the polygon and a line extending from the point (x, y) along
544       * the positive X, or Y axis, within a given interval.
545       *
546       * @return the winding number.
547       * @see #contains(double, double)
548       */
549      private int evaluateCrossings(double x, double y, boolean useYaxis,
550                                    double distance)
551      {
552        double x0;
553        double x1;
554        double y0;
555        double y1;
556        double epsilon = 0.0;
557        int crossings = 0;
558        int[] xp;
559        int[] yp;
560    
561        if (useYaxis)
562          {
563            xp = ypoints;
564            yp = xpoints;
565            double swap;
566            swap = y;
567            y = x;
568            x = swap;
569          }
570        else
571          {
572            xp = xpoints;
573            yp = ypoints;
574          }
575    
576        /* Get a value which is small but not insignificant relative the path. */
577        epsilon = 1E-7;
578    
579        x0 = xp[0] - x;
580        y0 = yp[0] - y;
581        for (int i = 1; i < npoints; i++)
582          {
583            x1 = xp[i] - x;
584            y1 = yp[i] - y;
585    
586            if (y0 == 0.0)
587              y0 -= epsilon;
588            if (y1 == 0.0)
589              y1 -= epsilon;
590            if (y0 * y1 < 0)
591              if (Line2D.linesIntersect(x0, y0, x1, y1, epsilon, 0.0, distance, 0.0))
592                ++crossings;
593    
594            x0 = xp[i] - x;
595            y0 = yp[i] - y;
596          }
597    
598        // end segment
599        x1 = xp[0] - x;
600        y1 = yp[0] - y;
601        if (y0 == 0.0)
602          y0 -= epsilon;
603        if (y1 == 0.0)
604          y1 -= epsilon;
605        if (y0 * y1 < 0)
606          if (Line2D.linesIntersect(x0, y0, x1, y1, epsilon, 0.0, distance, 0.0))
607            ++crossings;
608    
609        return crossings;
610      }
611    } // class Polygon