Initial revision

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@102074 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 613 insertions, 0 deletions

diff --git a/libjava/classpath/java/awt/Polygon.java b/libjava/classpath/java/awt/Polygon.java
new file mode 100644
index 00000000000..a72522cb089
--- /dev/null
+++ b/libjava/classpath/java/awt/Polygon.java
@@ -0,0 +1,613 @@
+/* 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 #condensed
+   * @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
+