Polygon.java

/* Polygon.java -- class representing a polygon
   Copyright (C) 1999, 2002, 2004, 2005  Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */


package java.awt;

import java.awt.geom.AffineTransform;
import java.awt.geom.Line2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.io.Serializable;

/**
 * This class represents a polygon, a closed, two-dimensional region in a
 * coordinate space. The region is bounded by an arbitrary number of line
 * segments, between (x,y) coordinate vertices. The polygon has even-odd
 * winding, meaning that a point is inside the shape if it crosses the
 * boundary an odd number of times on the way to infinity.
 *
 * <p>There are some public fields; if you mess with them in an inconsistent
 * manner, it is your own fault when you get NullPointerException,
 * ArrayIndexOutOfBoundsException, or invalid results. Also, this class is
 * not threadsafe.
 *
 * @author Aaron M. Renn (arenn@urbanophile.com)
 * @author Eric Blake (ebb9@email.byu.edu)
 * @since 1.0
 * @status updated to 1.4
 */
public class Polygon implements Shape, Serializable
{
  /**
   * Compatible with JDK 1.0+.
   */
  private static final long serialVersionUID = -6460061437900069969L;

  /**
   * This total number of endpoints.
   *
   * @serial the number of endpoints, possibly less than the array sizes
   */
  public int npoints;

  /**
   * The array of X coordinates of endpoints. This should not be null.
   *
   * @see #addPoint(int, int)
   * @serial the x coordinates
   */
  public int[] xpoints;

  /**
   * The array of Y coordinates of endpoints. This should not be null.
   *
   * @see #addPoint(int, int)
   * @serial the y coordinates
   */
  public int[] ypoints;

  /**
   * The bounding box of this polygon. This is lazily created and cached, so
   * it must be invalidated after changing points.
   *
   * @see #getBounds()
   * @serial the bounding box, or null
   */
  protected Rectangle bounds;

  /** A big number, but not so big it can't survive a few float operations */
  private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0;

  /**
   * Initializes an empty polygon.
   */
  public Polygon()
  {
    // Leave room for growth.
    xpoints = new int[4];
    ypoints = new int[4];
  }

  /**
   * Create a new polygon with the specified endpoints. The arrays are copied,
   * so that future modifications to the parameters do not affect the polygon.
   *
   * @param xpoints the array of X coordinates for this polygon
   * @param ypoints the array of Y coordinates for this polygon
   * @param npoints the total number of endpoints in this polygon
   * @throws NegativeArraySizeException if npoints is negative
   * @throws IndexOutOfBoundsException if npoints exceeds either array
   * @throws NullPointerException if xpoints or ypoints is null
   */
  public Polygon(int[] xpoints, int[] ypoints, int npoints)
  {
    this.xpoints = new int[npoints];
    this.ypoints = new int[npoints];
    System.arraycopy(xpoints, 0, this.xpoints, 0, npoints);
    System.arraycopy(ypoints, 0, this.ypoints, 0, npoints);
    this.npoints = npoints;
  }

  /**
   * Reset the polygon to be empty. The arrays are left alone, to avoid object
   * allocation, but the number of points is set to 0, and all cached data
   * is discarded. If you are discarding a huge number of points, it may be
   * more efficient to just create a new Polygon.
   *
   * @see #invalidate()
   * @since 1.4
   */
  public void reset()
  {
    npoints = 0;
    invalidate();
  }

  /**
   * Invalidate or flush all cached data. After direct manipulation of the
   * public member fields, this is necessary to avoid inconsistent results
   * in methods like <code>contains</code>.
   *
   * @see #getBounds()
   * @since 1.4
   */
  public void invalidate()
  {
    bounds = null;
  }

  /**
   * Translates the polygon by adding the specified values to all X and Y
   * coordinates. This updates the bounding box, if it has been calculated.
   *
   * @param dx the amount to add to all X coordinates
   * @param dy the amount to add to all Y coordinates
   * @since 1.1
   */
  public void translate(int dx, int dy)
  {
    int i = npoints;
    while (--i >= 0)
      {
        xpoints[i] += dx;
        ypoints[i] += dy;
      }
    if (bounds != null)
      {
        bounds.x += dx;
        bounds.y += dy;
      }
  }

  /**
   * Adds the specified endpoint to the polygon. This updates the bounding
   * box, if it has been created.
   *
   * @param x the X coordinate of the point to add
   * @param y the Y coordiante of the point to add
   */
  public void addPoint(int x, int y)
  {
    if (npoints + 1 > xpoints.length)
      {
        int[] newx = new int[npoints + 1];
        System.arraycopy(xpoints, 0, newx, 0, npoints);
        xpoints = newx;
      }
    if (npoints + 1 > ypoints.length)
      {
        int[] newy = new int[npoints + 1];
        System.arraycopy(ypoints, 0, newy, 0, npoints);
        ypoints = newy;
      }
    xpoints[npoints] = x;
    ypoints[npoints] = y;
    npoints++;
    if (bounds != null)
      {
        if (npoints == 1)
          {
            bounds.x = x;
            bounds.y = y;
          }
        else
          {
            if (x < bounds.x)
              {
                bounds.width += bounds.x - x;
                bounds.x = x;
              }
            else if (x > bounds.x + bounds.width)
              bounds.width = x - bounds.x;
            if (y < bounds.y)
              {
                bounds.height += bounds.y - y;
                bounds.y = y;
              }
            else if (y > bounds.y + bounds.height)
              bounds.height = y - bounds.y;
          }
      }
  }

  /**
   * Returns the bounding box of this polygon. This is the smallest
   * rectangle with sides parallel to the X axis that will contain this
   * polygon.
   *
   * @return the bounding box for this polygon
   * @see #getBounds2D()
   * @since 1.1
   */
  public Rectangle getBounds()
  {
    return getBoundingBox();
  }

  /**
   * Returns the bounding box of this polygon. This is the smallest
   * rectangle with sides parallel to the X axis that will contain this
   * polygon.
   *
   * @return the bounding box for this polygon
   * @see #getBounds2D()
   * @deprecated use {@link #getBounds()} instead
   */
  public Rectangle getBoundingBox()
  {
    if (bounds == null)
      {
        if (npoints == 0)
          return bounds = new Rectangle();
        int i = npoints - 1;
        int minx = xpoints[i];
        int maxx = minx;
        int miny = ypoints[i];
        int maxy = miny;
        while (--i >= 0)
          {
            int x = xpoints[i];
            int y = ypoints[i];
            if (x < minx)
              minx = x;
            else if (x > maxx)
              maxx = x;
            if (y < miny)
              miny = y;
            else if (y > maxy)
              maxy = y;
          }
        bounds = new Rectangle(minx, miny, maxx - minx, maxy - miny);
      }
    return bounds;
  }

  /**
   * Tests whether or not the specified point is inside this polygon.
   *
   * @param p the point to test
   * @return true if the point is inside this polygon
   * @throws NullPointerException if p is null
   * @see #contains(double, double)
   */
  public boolean contains(Point p)
  {
    return contains(p.getX(), p.getY());
  }

  /**
   * Tests whether or not the specified point is inside this polygon.
   *
   * @param x the X coordinate of the point to test
   * @param y the Y coordinate of the point to test
   * @return true if the point is inside this polygon
   * @see #contains(double, double)
   * @since 1.1
   */
  public boolean contains(int x, int y)
  {
    return contains((double) x, (double) y);
  }

  /**
   * Tests whether or not the specified point is inside this polygon.
   *
   * @param x the X coordinate of the point to test
   * @param y the Y coordinate of the point to test
   * @return true if the point is inside this polygon
   * @see #contains(double, double)
   * @deprecated use {@link #contains(int, int)} instead
   */
  public boolean inside(int x, int y)
  {
    return contains((double) x, (double) y);
  }

  /**
   * Returns a high-precision bounding box of this polygon. This is the
   * smallest rectangle with sides parallel to the X axis that will contain
   * this polygon.
   *
   * @return the bounding box for this polygon
   * @see #getBounds()
   * @since 1.2
   */
  public Rectangle2D getBounds2D()
  {
    // For polygons, the integer version is exact!
    return getBounds();
  }

  /**
   * Tests whether or not the specified point is inside this polygon.
   *
   * @param x the X coordinate of the point to test
   * @param y the Y coordinate of the point to test
   * @return true if the point is inside this polygon
   * @since 1.2
   */
  public boolean contains(double x, double y)
  {
    return ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0);
  }

  /**
   * Tests whether or not the specified point is inside this polygon.
   *
   * @param p the point to test
   * @return true if the point is inside this polygon
   * @throws NullPointerException if p is null
   * @see #contains(double, double)
   * @since 1.2
   */
  public boolean contains(Point2D p)
  {
    return contains(p.getX(), p.getY());
  }

  /**
   * Test if a high-precision rectangle intersects the shape. This is true
   * if any point in the rectangle is in the shape. This implementation is
   * precise.
   *
   * @param x the x coordinate of the rectangle
   * @param y the y coordinate of the rectangle
   * @param w the width of the rectangle, treated as point if negative
   * @param h the height of the rectangle, treated as point if negative
   * @return true if the rectangle intersects this shape
   * @since 1.2
   */
  public boolean intersects(double x, double y, double w, double h)
  {
    /* Does any edge intersect? */
    if (evaluateCrossings(x, y, false, w) != 0 /* top */
        || evaluateCrossings(x, y + h, false, w) != 0 /* bottom */
        || evaluateCrossings(x + w, y, true, h) != 0 /* right */
        || evaluateCrossings(x, y, true, h) != 0) /* left */
      return true;

    /* No intersections, is any point inside? */
    if ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0)
      return true;

    return false;
  }

  /**
   * Test if a high-precision rectangle intersects the shape. This is true
   * if any point in the rectangle is in the shape. This implementation is
   * precise.
   *
   * @param r the rectangle
   * @return true if the rectangle intersects this shape
   * @throws NullPointerException if r is null
   * @see #intersects(double, double, double, double)
   * @since 1.2
   */
  public boolean intersects(Rectangle2D r)
  {
    return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
  }

  /**
   * Test if a high-precision rectangle lies completely in the shape. This is
   * true if all points in the rectangle are in the shape. This implementation
   * is precise.
   *
   * @param x the x coordinate of the rectangle
   * @param y the y coordinate of the rectangle
   * @param w the width of the rectangle, treated as point if negative
   * @param h the height of the rectangle, treated as point if negative
   * @return true if the rectangle is contained in this shape
   * @since 1.2
   */
  public boolean contains(double x, double y, double w, double h)
  {
    if (! getBounds2D().intersects(x, y, w, h))
      return false;

    /* Does any edge intersect? */
    if (evaluateCrossings(x, y, false, w) != 0 /* top */
        || evaluateCrossings(x, y + h, false, w) != 0 /* bottom */
        || evaluateCrossings(x + w, y, true, h) != 0 /* right */
        || evaluateCrossings(x, y, true, h) != 0) /* left */
      return false;

    /* No intersections, is any point inside? */
    if ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0)
      return true;

    return false;
  }

  /**
   * Test if a high-precision rectangle lies completely in the shape. This is
   * true if all points in the rectangle are in the shape. This implementation
   * is precise.
   *
   * @param r the rectangle
   * @return true if the rectangle is contained in this shape
   * @throws NullPointerException if r is null
   * @see #contains(double, double, double, double)
   * @since 1.2
   */
  public boolean contains(Rectangle2D r)
  {
    return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
  }

  /**
   * Return an iterator along the shape boundary. If the optional transform
   * is provided, the iterator is transformed accordingly. Each call returns
   * a new object, independent from others in use. This class is not
   * threadsafe to begin with, so the path iterator is not either.
   *
   * @param transform an optional transform to apply to the iterator
   * @return a new iterator over the boundary
   * @since 1.2
   */
  public PathIterator getPathIterator(final AffineTransform transform)
  {
    return new PathIterator()
      {
        /** The current vertex of iteration. */
        private int vertex;

        public int getWindingRule()
        {
          return WIND_EVEN_ODD;
        }

        public boolean isDone()
        {
          return vertex > npoints;
        }

        public void next()
        {
          vertex++;
        }

        public int currentSegment(float[] coords)
        {
          if (vertex >= npoints)
            return SEG_CLOSE;
          coords[0] = xpoints[vertex];
          coords[1] = ypoints[vertex];
          if (transform != null)
            transform.transform(coords, 0, coords, 0, 1);
          return vertex == 0 ? SEG_MOVETO : SEG_LINETO;
        }

        public int currentSegment(double[] coords)
        {
          if (vertex >= npoints)
            return SEG_CLOSE;
          coords[0] = xpoints[vertex];
          coords[1] = ypoints[vertex];
          if (transform != null)
            transform.transform(coords, 0, coords, 0, 1);
          return vertex == 0 ? SEG_MOVETO : SEG_LINETO;
        }
      };
  }

  /**
   * Return an iterator along the flattened version of the shape boundary.
   * Since polygons are already flat, the flatness parameter is ignored, and
   * the resulting iterator only has SEG_MOVETO, SEG_LINETO and SEG_CLOSE
   * points. If the optional transform is provided, the iterator is
   * transformed accordingly. Each call returns a new object, independent
   * from others in use. This class is not threadsafe to begin with, so the
   * path iterator is not either.
   *
   * @param transform an optional transform to apply to the iterator
   * @param flatness the maximum distance for deviation from the real boundary
   * @return a new iterator over the boundary
   * @since 1.2
   */
  public PathIterator getPathIterator(AffineTransform transform,
                                      double flatness)
  {
    return getPathIterator(transform);
  }

  /**
   * Helper for contains, intersects, calculates the number of intersections
   * between the polygon and a line extending from the point (x, y) along
   * the positive X, or Y axis, within a given interval.
   *
   * @return the winding number.
   * @see #contains(double, double)
   */
  private int evaluateCrossings(double x, double y, boolean useYaxis,
                                double distance)
  {
    double x0;
    double x1;
    double y0;
    double y1;
    double epsilon = 0.0;
    int crossings = 0;
    int[] xp;
    int[] yp;

    if (useYaxis)
      {
        xp = ypoints;
        yp = xpoints;
        double swap;
        swap = y;
        y = x;
        x = swap;
      }
    else
      {
        xp = xpoints;
        yp = ypoints;
      }

    /* Get a value which is small but not insignificant relative the path. */
    epsilon = 1E-7;

    x0 = xp[0] - x;
    y0 = yp[0] - y;
    for (int i = 1; i < npoints; i++)
      {
        x1 = xp[i] - x;
        y1 = yp[i] - y;

        if (y0 == 0.0)
          y0 -= epsilon;
        if (y1 == 0.0)
          y1 -= epsilon;
        if (y0 * y1 < 0)
          if (Line2D.linesIntersect(x0, y0, x1, y1, epsilon, 0.0, distance, 0.0))
            ++crossings;

        x0 = xp[i] - x;
        y0 = yp[i] - y;
      }

    // end segment
    x1 = xp[0] - x;
    y1 = yp[0] - y;
    if (y0 == 0.0)
      y0 -= epsilon;
    if (y1 == 0.0)
      y1 -= epsilon;
    if (y0 * y1 < 0)
      if (Line2D.linesIntersect(x0, y0, x1, y1, epsilon, 0.0, distance, 0.0))
        ++crossings;

    return crossings;
  }
} // class Polygon