Context Navigation

-              r1390
+              r1391
+/* Copyright (C) 2001  Free Software Foundation
+   This file is part of libjava.
+This software is copyrighted work licensed under the terms of the
+Libjava License.  Please consult the file "LIBJAVA_LICENSE" for
+details.  */
+/* Polygon.java -- class representing a polygon
+   Copyright (C) 1999, 2002 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., 59 Temple Place, Suite 330, Boston, MA
+-1307 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.*;
+import java.awt.geom.AffineTransform;
+import java.awt.geom.PathIterator;
+import java.awt.geom.Point2D;
+import java.awt.geom.Rectangle2D;
 import java.io.Serializable;
-import java.util.Arrays;
 /**
+ * @author Tom Tromey <[email protected]>
+ * @date May 10, 2001
+ * 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 <[email protected]>
+ * @author Eric Blake <[email protected]>
+ * @since 1.0
+ * @status updated to 1.4
  */
-/** The Polygon class represents a closed region whose boundary is
-    made of line segments.  The Polygon is defined by its vertices.  */
 public class Polygon implements Shape, Serializable
+{
+  /** The bounds of the polygon.  This is null until the bounds have
+   *  been computed for the first time; then it is correctly
+   *  maintained whenever it is modified.  */
+  /**
+   * 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;
+  /** The number of points in the polygon.  */
+  public int npoints;
+  /** The x coordinates of the points.  */
+  public int[] xpoints;
+  /** The y coordinates of the points.  */
+  public int[] ypoints;
+  /** Create a new, empty Polygon.  */
+  public Polygon ()
+  {
+    this.xpoints = new int[0];
+    this.ypoints = new int[0];
+    this.npoints = 0;
+  }
+  /** Create a new Polygon from the given vertices.
+   * @param xpoints The x coordinates
+   * @param ypoints The y coordinates
+   * @param npoints The number of points
+   */
+  public Polygon (int[] xpoints, int[] ypoints, int npoints)
+  {
+    // We make explicit copies instead of relying on clone so that we
+    // ensure the new arrays are the same size.
+  /**
+   * Cached flattened version - condense points and parallel lines, so the
+   * result has area if there are >= 3 condensed vertices. flat[0] is the
+   * number of condensed points, and (flat[odd], flat[odd+1]) form the
+   * condensed points.
+   *
+   * @see #condense()
+   * @see #contains(double, double)
+   * @see #contains(double, double, double, double)
+   */
+  private transient int[] condensed;
+  /**
+   * 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);
+  }
+  /** Append the specified point to this Polygon.
+   * @param x The x coordinate
+   * @param y The y coordinate
+   */
+  public void addPoint (int x, int y)
+  {
+    int[] newx = new int[npoints + 1];
+    System.arraycopy (xpoints, 0, newx, 0, npoints);
+    int[] newy = new int[npoints + 1];
+    System.arraycopy (ypoints, 0, newy, 0, npoints);
+    newx[npoints] = x;
+    newy[npoints] = y;
+    ++npoints;
+    xpoints = newx;
+    ypoints = newy;
+    // It is simpler to just recompute.
+    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;
+    condensed = 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;
+        xpoints[i] += dy;
+      }
     if (bounds != null)
+      computeBoundingBox ();
+  }
+  /** Return true if the indicated point is inside this Polygon.
+   * This uses an even-odd rule to determine insideness.
+   * @param x The x coordinate
+   * @param y The y coordinate
+   * @returns true if the point is contained by this Polygon.
+   */
+  public boolean contains (double x, double y)
+  {
+    // What we do is look at each line segment.  If the line segment
+    // crosses the "scan line" at y at a point x' < x, then we
+    // increment our counter.  At the end, an even number means the
+    // point is outside the polygon.  Instead of a number, though, we
+    // use a boolean.
+      {
+        bounds.x += dx;
+        bounds.y += dy;
+      }
+    condensed = null;
+  }
+  /**
+   * 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;
+          }
+      }
+    condensed = null;
+  }
+  /**
+   * 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()
+  {
+    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, maxy, maxx - minx, maxy - miny);
+      }
+    return bounds;
+  }
+  /**
+   * 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()
+  {
+    return getBounds();
+  }
+  /**
+   * 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)
+  {
+    // First, the obvious bounds checks.
+    if (! condense() || ! getBounds().contains(x, y))
+      return false;
+    // A point is contained if a ray to (-inf, y) crosses an odd number
+    // of segments. This must obey the semantics of Shape when the point is
+    // exactly on a segment or vertex: a point is inside only if the adjacent
+    // point in the increasing x or y direction is also inside. Note that we
+    // are guaranteed that the condensed polygon has area, and no consecutive
+    // segments with identical slope.
     boolean inside = false;
+    for (int i = 0; i < npoints; ++i)
+      {
+        // Handle the wrap case.
+        int x2 = (i == npoints) ? xpoints[0] : xpoints[i + 1];
+        int y2 = (i == npoints) ? ypoints[0] : ypoints[i + 1];
+        if (ypoints[i] == y2)
+          {
+            // We ignore horizontal lines.  This might give weird
+            // results in some situations -- ?
+            continue;
+          }
+        double t = (y - ypoints[i]) / (double) (y2 - ypoints[i]);
+        double x3 = xpoints[i] + t * (x2 - xpoints[i]);
+        if (x3 < x)
+          inside = ! inside;
+      }
+    int limit = condensed[0];
+    int curx = condensed[(limit << 1) - 1];
+    int cury = condensed[limit << 1];
+    for (int i = 1; i <= limit; i++)
+      {
+        int priorx = curx;
+        int priory = cury;
+        curx = condensed[(i << 1) - 1];
+        cury = condensed[i << 1];
+        if ((priorx > x && curx > x) // Left of segment, or NaN.
+            || (priory > y && cury > y) // Below segment, or NaN.
+            || (priory < y && cury < y)) // Above segment.
+          continue;
+        if (priory == cury) // Horizontal segment, y == cury == priory
+          {
+            if (priorx < x && curx < x) // Right of segment.
+              {
+                inside = ! inside;
+                continue;
+              }
+            // Did we approach this segment from above or below?
+            // This mess is necessary to obey rules of Shape.
+            priory = condensed[((limit + i - 2) % limit) << 1];
+            boolean above = priory > cury;
+            if ((curx == x && (curx > priorx || above))
+                || (priorx == x && (curx < priorx || ! above))
+                || (curx > priorx && ! above) || above)
+              inside = ! inside;
+            continue;
+          }
+        if (priorx == x && priory == y) // On prior vertex.
+          continue;
+        if (priorx == curx // Vertical segment.
+            || (priorx < x && curx < x)) // Right of segment.
+          {
+            inside = ! inside;
+            continue;
+          }
+        // The point is inside the segment's bounding box, compare slopes.
+        double leftx = curx > priorx ? priorx : curx;
+        double lefty = curx > priorx ? priory : cury;
+        double slopeseg = (double) (cury - priory) / (curx - priorx);
+        double slopepoint = (double) (y - lefty) / (x - leftx);
+        if ((slopeseg > 0 && slopeseg > slopepoint)
+            || slopeseg < slopepoint)
+          inside = ! inside;
+      }
     return inside;
+  }
+  /** Return true if the indicated rectangle is entirely inside this
+   * Polygon.
+   * This uses an even-odd rule to determine insideness.
+   * @param x The x coordinate
+   * @param y The y coordinate
+   * @param w The width
+   * @param h The height
+   * @returns true if the rectangle is contained by this Polygon.
+   */
+  public boolean contains (double x, double y, double w, double h)
+  {
+    return intersectOrContains (x, y, w, h, false);
+  }
+  /** Return true if the indicated point is inside this Polygon.
+   * This uses an even-odd rule to determine insideness.
+   * @param x The x coordinate
+   * @param y The y coordinate
+   * @returns true if the point is contained by this Polygon.
+   */
+  public boolean contains (int x, int y)
+  {
+    return contains ((double) x, (double) y);
+  }
+  /** Return true if the indicated point is inside this Polygon.
+   * This uses an even-odd rule to determine insideness.
+   * @param p The point
+   * @returns true if the point is contained by this Polygon.
+   */
+  public boolean contains (Point p)
+  {
+    return contains (p.x, p.y);
+  }
+  /** Return true if the indicated point is inside this Polygon.
+   * This uses an even-odd rule to determine insideness.
+   * @param p The point
+   * @returns true if the point is contained by this Polygon.
+   */
+  public boolean contains (Point2D p)
+  {
+    return contains (p.getX (), p.getY ());
+  }
+  /** Return true if the indicated rectangle is entirely inside this
+   * Polygon.  This uses an even-odd rule to determine insideness.
+   * @param r The rectangle
+   * @returns true if the rectangle is contained by this Polygon.
+   */
+  public boolean contains (Rectangle2D r)
+  {
+    return contains (r.getX (), r.getY (), r.getWidth (), r.getHeight ());
+  }
+  /** Returns the bounds of this Polygon.
+   * @deprecated Use getBounds() instead.
+   */
+  public Rectangle getBoundingBox ()
+  {
+    if (bounds == null)
+      computeBoundingBox ();
+    return bounds;
+  }
+  /** Returns the bounds of this Polygon.  */
+  public Rectangle getBounds ()
+  {
+    if (bounds == null)
+      computeBoundingBox ();
+    return bounds;
+  }
+  /** Returns the bounds of this Polygon.  */
+  public Rectangle2D getBounds2D ()
+  {
+    if (bounds == null)
+      computeBoundingBox ();
+    return bounds;              // Why not?
+  }
+  /** Return an iterator for the boundary of this Polygon.
+   * @param at A transform to apply to the coordinates.
+   * @returns A path iterator for the Polygon's boundary.
+   */
+  public PathIterator getPathIterator (AffineTransform at)
+  {
+    return new Iterator (at);
+  }
+  /** Return an iterator for the boundary of this Polygon.
+   * @param at A transform to apply to the coordinates.
+   * @param flatness The flatness of the result; it is ignored by
+   *                 this class.
+   * @returns A path iterator for the Polygon's boundary.
+   */
+  public PathIterator getPathIterator (AffineTransform at, double flatness)
+  {
+    // We ignore the flatness.
+    return new Iterator (at);
+  }
+  /** @deprecated use contains(int,int).  */
+  public boolean inside (int x, int y)
+  {
+    return contains (x, y);
+  }
+  /** Return true if this Polygon's interior intersects the given
+   * rectangle's interior.
+   * @param x The x coordinate
+   * @param y The y coordinate
+   * @param w The width
+   * @param h The height
+   */
+  public boolean intersects (double x, double y, double w, double h)
+  {
+    return intersectOrContains (x, y, w, h, true);
+  }
+  /** Return true if this Polygon's interior intersects the given
+   * rectangle's interior.
+   * @param r The rectangle
+   */
+  public boolean intersects (Rectangle2D r)
+  {
+    return intersects (r.getX (), r.getY (), r.getWidth (), r.getHeight ());
+  }
+  // This tests for intersection with or containment of a rectangle,
+  // depending on the INTERSECT argument.
+  private boolean intersectOrContains (double x, double y, double w, double h,
+                                       boolean intersect)
+  {
+    // First compute the rectangle of possible intersection points.
+    Rectangle r = getBounds ();
+    int minx = Math.max (r.x, (int) x);
+    int maxx = Math.min (r.x + r.width, (int) (x + w));
+    int miny = Math.max (r.y, (int) y);
+    int maxy = Math.min (r.y + r.height, (int) (y + h));
+    if (miny > maxy)
+  /**
+   * 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)
+  {
+    // First, the obvious bounds checks.
+    if (w <= 0 || h <= 0 || npoints == 0 ||
+        ! getBounds().intersects(x, y, w, h))
+      return false; // Disjoint bounds.
+    if ((x <= bounds.x && x + w >= bounds.x + bounds.width
+         && y <= bounds.y && y + h >= bounds.y + bounds.height)
+        || contains(x, y))
+      return true; // Rectangle contains the polygon, or one point matches.
+    // If any vertex is in the rectangle, the two might intersect.
+    int curx = 0;
+    int cury = 0;
+    for (int i = 0; i < npoints; i++)
+      {
+        curx = xpoints[i];
+        cury = ypoints[i];
+        if (curx >= x && curx < x + w && cury >= y && cury < y + h
+            && contains(curx, cury)) // Boundary check necessary.
+          return true;
+      }
+    // Finally, if at least one of the four bounding lines intersect any
+    // segment of the polygon, return true. Be careful of the semantics of
+    // Shape; coinciding lines do not necessarily return true.
+    for (int i = 0; i < npoints; i++)
+      {
+        int priorx = curx;
+        int priory = cury;
+        curx = xpoints[i];
+        cury = ypoints[i];
+        if (priorx == curx) // Vertical segment.
+          {
+            if (curx < x || curx >= x + w) // Outside rectangle.
+              continue;
+            if ((cury >= y + h && priory <= y)
+                || (cury <= y && priory >= y + h))
+              return true; // Bisects rectangle.
+            continue;
+          }
+        if (priory == cury) // Horizontal segment.
+          {
+            if (cury < y || cury >= y + h) // Outside rectangle.
+              continue;
+            if ((curx >= x + w && priorx <= x)
+                || (curx <= x && priorx >= x + w))
+              return true; // Bisects rectangle.
+            continue;
+          }
+        // Slanted segment.
+        double slope = (double) (cury - priory) / (curx - priorx);
+        double intersect = slope * (x - curx) + cury;
+        if (intersect > y && intersect < y + h) // Intersects left edge.
+          return true;
+        intersect = slope * (x + w - curx) + cury;
+        if (intersect > y && intersect < y + h) // Intersects right edge.
+          return true;
+        intersect = (y - cury) / slope + curx;
+        if (intersect > x && intersect < x + w) // Intersects bottom edge.
+          return true;
+        intersect = (y + h - cury) / slope + cury;
+        if (intersect > x && intersect < x + w) // Intersects top edge.
+          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)
+  {
+    // First, the obvious bounds checks.
+    if (w <= 0 || h <= 0 || ! contains(x, y)
+        || ! bounds.contains(x, y, w, h))
       return false;
+    double[] crosses = new double[npoints + 1];
+    for (; miny < maxy; ++miny)
+      {
+        // First compute every place where the polygon might intersect
+        // the scan line at Y.
+        int ins = 0;
+        for (int i = 0; i < npoints; ++i)
+          {
+            // Handle the wrap case.
+            int x2 = (i == npoints) ? xpoints[0] : xpoints[i + 1];
+            int y2 = (i == npoints) ? ypoints[0] : ypoints[i + 1];
+            if (ypoints[i] == y2)
+              {
+                // We ignore horizontal lines.  This might give weird
+                // results in some situations -- ?
+                continue;
+              }
+            double t = (((double) miny - ypoints[i])
+                        / (double) (y2 - ypoints[i]));
+            double x3 = xpoints[i] + t * (x2 - xpoints[i]);
+            crosses[ins++] = x3;
+          }
+        // Now we can sort into increasing order and look to see if
+        // any point in the rectangle is in the polygon.  We examine
+        // every other pair due to our even-odd rule.
+        Arrays.sort (crosses, 0, ins);
+        int i = intersect ? 0 : 1;
+        for (; i < ins - 1; i += 2)
+          {
+            // Pathological case.
+            if (crosses[i] == crosses[i + 1])
+              continue;
+            // Found a point on the inside.
+            if ((crosses[i] >= x && crosses[i] < x + w)
+                || (crosses[i + 1] >= x && crosses[i + 1] < x + w))
+              {
+                // If we're checking containment then we just lost.
+                // But if we're checking intersection then we just
+                // won.
+                return intersect;
+              }
+          }
+      }
+    return false;
+  }
+  /** Translates all the vertices of the polygon via a given vector.
+   * @param deltaX The X offset
+   * @param deltaY The Y offset
+   */
+  public void translate (int deltaX, int deltaY)
+  {
+    for (int i = 0; i < npoints; ++i)
+      {
+        xpoints[i] += deltaX;
+        ypoints[i] += deltaY;
+      }
+    if (bounds != null)
+      {
+        bounds.x += deltaX;
+        bounds.y += deltaY;
+      }
+  }
+  // This computes the bounding box if required.
+  private void computeBoundingBox ()
+  {
+    if (npoints == 0)
+      {
+        // This is wrong if the user adds a new point, but we
+        // account for that in addPoint().
+        bounds = new Rectangle (0, 0, 0, 0);
+      }
+    else
+      {
+        int maxx = xpoints[0];
+        int minx = xpoints[0];
+        int maxy = ypoints[0];
+        int miny = ypoints[0];
+        for (int i = 1; i < npoints; ++i)
+          {
+            maxx = Math.max (maxx, xpoints[i]);
+            minx = Math.min (minx, xpoints[i]);
+            maxy = Math.max (maxy, ypoints[i]);
+            miny = Math.min (miny, ypoints[i]);
+          }
+        bounds = new Rectangle (minx, miny, maxx - minx, maxy - miny);
+      }
+  }
+  private class Iterator implements PathIterator
+  {
+    public AffineTransform xform;
+    public int where;
+    public Iterator (AffineTransform xform)
+    // Now, if any of the four bounding lines intersects a polygon segment,
+    // return false. The previous check had the side effect of setting
+    // the condensed array, which we use. Be careful of the semantics of
+    // Shape; coinciding lines do not necessarily return false.
+    int limit = condensed[0];
+    int curx = condensed[(limit << 1) - 1];
+    int cury = condensed[limit << 1];
+    for (int i = 1; i <= limit; i++)
+      {
+        int priorx = curx;
+        int priory = cury;
+        curx = condensed[(i << 1) - 1];
+        cury = condensed[i << 1];
+        if (curx > x && curx < x + w && cury > y && cury < y + h)
+          return false; // Vertex is in rectangle.
+        if (priorx == curx) // Vertical segment.
+          {
+            if (curx < x || curx > x + w) // Outside rectangle.
+              continue;
+            if ((cury >= y + h && priory <= y)
+                || (cury <= y && priory >= y + h))
+              return false; // Bisects rectangle.
+            continue;
+          }
+        if (priory == cury) // Horizontal segment.
+          {
+            if (cury < y || cury > y + h) // Outside rectangle.
+              continue;
+            if ((curx >= x + w && priorx <= x)
+                || (curx <= x && priorx >= x + w))
+              return false; // Bisects rectangle.
+            continue;
+          }
+        // Slanted segment.
+        double slope = (double) (cury - priory) / (curx - priorx);
+        double intersect = slope * (x - curx) + cury;
+        if (intersect > y && intersect < y + h) // Intersects left edge.
+          return false;
+        intersect = slope * (x + w - curx) + cury;
+        if (intersect > y && intersect < y + h) // Intersects right edge.
+          return false;
+        intersect = (y - cury) / slope + curx;
+        if (intersect > x && intersect < x + w) // Intersects bottom edge.
+          return false;
+        intersect = (y + h - cury) / slope + cury;
+        if (intersect > x && intersect < x + w) // Intersects top edge.
+          return false;
+      }
+    return true;
+  }
+  /**
+   * 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()
+    {
+      this.xform = xform;
+      where = 0;
+    }
+    public int currentSegment (double[] coords)
+    {
+      int r;
+      if (where < npoints)
+        {
+          coords[0] = xpoints[where];
+          coords[1] = ypoints[where];
+          r = (where == 0) ? SEG_MOVETO : SEG_LINETO;
+          xform.transform (coords, 0, coords, 0, 1);
+          ++where;
+        }
+      else
+        r = SEG_CLOSE;
+      return r;
+    }
+    public int currentSegment (float[] coords)
+    {
+      int r;
+      if (where < npoints)
+        {
+          coords[0] = xpoints[where];
+          coords[1] = ypoints[where];
+          r = (where == 0) ? SEG_MOVETO : SEG_LINETO;
+          xform.transform (coords, 0, coords, 0, 1);
+        }
+      else
+        r = SEG_CLOSE;
+      return r;
+    }
+    public int getWindingRule ()
+    {
+      return WIND_EVEN_ODD;
+    }
+    public boolean isDone ()
+    {
+      return where == npoints + 1;
+    }
+    public void next ()
+    {
+      ++where;
+    }
+  }
+}
+      /** 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 double 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, which caches a condensed version of the polygon.
+   * This condenses all colinear points, so that consecutive segments in
+   * the condensed version always have different slope.
+   *
+   * @return true if the condensed polygon has area
+   * @see #condensed
+   * @see #contains(double, double)
+   */
+  private boolean condense()
+  {
+    if (npoints <= 2)
+      return false;
+    if (condensed != null)
+      return condensed[0] > 2;
+    condensed = new int[npoints * 2 + 1];
+    int curx = xpoints[npoints - 1];
+    int cury = ypoints[npoints - 1];
+    double curslope = Double.NaN;
+    int count = 0;
+  outer:
+    for (int i = 0; i < npoints; i++)
+      {
+        int priorx = curx;
+        int priory = cury;
+        double priorslope = curslope;
+        curx = xpoints[i];
+        cury = ypoints[i];
+        while (curx == priorx && cury == priory)
+          {
+            if (++i == npoints)
+              break outer;
+            curx = xpoints[i];
+            cury = ypoints[i];
+          }
+        curslope = (curx == priorx ? Double.POSITIVE_INFINITY
+                    : (double) (cury - priory) / (curx - priorx));
+        if (priorslope == curslope)
+          {
+            if (count > 1 && condensed[(count << 1) - 3] == curx
+                && condensed[(count << 1) - 2] == cury)
+              {
+                count--;
+                continue;
+              }
+          }
+        else
+          count++;
+        condensed[(count << 1) - 1] = curx;
+        condensed[count << 1] = cury;
+      }
+    condensed[0] = count;
+    return count > 2;
+  }
+} // class Polygon

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 1391 for branches/GNU/src/gcc/libjava/java/awt/Polygon.java

Legend:

branches/GNU/src/gcc

branches/GNU/src/gcc/libjava/java/awt/Polygon.java

Download in other formats: