001/* Polygon.java -- class representing a polygon
002   Copyright (C) 1999, 2002, 2004, 2005  Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038
039package java.awt;
040
041import java.awt.geom.AffineTransform;
042import java.awt.geom.Line2D;
043import java.awt.geom.PathIterator;
044import java.awt.geom.Point2D;
045import java.awt.geom.Rectangle2D;
046import 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 */
065public 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
612