diff options
Diffstat (limited to 'libjava/java/awt/Polygon.java')
| -rw-r--r-- | libjava/java/awt/Polygon.java | 963 |
1 files changed, 646 insertions, 317 deletions
diff --git a/libjava/java/awt/Polygon.java b/libjava/java/awt/Polygon.java index ad4df2c47a0..1f51ac811d6 100644 --- a/libjava/java/awt/Polygon.java +++ b/libjava/java/awt/Polygon.java @@ -1,422 +1,751 @@ -/* Copyright (C) 2001 Free Software Foundation +/* 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 +02111-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. */ - 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. */ 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 <tromey@redhat.com> - * @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 <arenn@urbanophile.com> + * @author Eric Blake <ebb9@email.byu.edu> + * @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. */ - protected Rectangle bounds; + /** + * Compatible with JDK 1.0+. + */ + private static final long serialVersionUID = -6460061437900069969L; - /** The number of points in the polygon. */ + /** + * This total number of endpoints. + * + * @serial the number of endpoints, possibly less than the array sizes + */ public int npoints; - /** The x coordinates of the points. */ + /** + * The array of X coordinates of endpoints. This should not be null. + * + * @see #addPoint(int, int) + * @serial the x coordinates + */ public int[] xpoints; - /** The y coordinates of the points. */ + /** + * The array of Y coordinates of endpoints. This should not be null. + * + * @see #addPoint(int, int) + * @serial the y coordinates + */ public int[] ypoints; - /** Create a new, empty Polygon. */ - public Polygon () + /** + * 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; + + /** + * 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() { - this.xpoints = new int[0]; - this.ypoints = new int[0]; - this.npoints = 0; + // Leave room for growth. + xpoints = new int[4]; + ypoints = new int[4]; } - /** Create a new Polygon from the given vertices. - * @param xpoints The x coordinates - * @param ypoints The y coordinates - * @param npoints The number of points + /** + * 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) + 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. 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); + System.arraycopy(xpoints, 0, this.xpoints, 0, npoints); + System.arraycopy(ypoints, 0, this.ypoints, 0, npoints); + this.npoints = npoints; } - /** Append the specified point to this Polygon. - * @param x The x coordinate - * @param y The y coordinate + /** + * 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 addPoint (int x, int y) + public void reset() { - 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. - if (bounds != null) - computeBoundingBox (); + npoints = 0; + invalidate(); } - /** 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. + /** + * 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 boolean contains (double x, double y) + public void invalidate() { - // 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. - boolean inside = false; - for (int i = 0; i < npoints; ++i) + 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) { - // 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; + xpoints[i] += dx; + xpoints[i] += dy; } - - return inside; + if (bounds != null) + { + bounds.x += dx; + bounds.y += dy; + } + condensed = null; } - /** 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. + /** + * 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 boolean contains (double x, double y, double w, double h) + public void addPoint(int x, int y) { - return intersectOrContains (x, y, w, h, false); + 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; } - /** 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. + /** + * 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 boolean contains (int x, int y) + public Rectangle getBounds() { - return contains ((double) x, (double) y); + 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; } - /** 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. + /** + * 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 boolean contains (Point p) + public Rectangle getBoundingBox() { - return contains (p.x, p.y); + return getBounds(); } - /** 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. + /** + * 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 (Point2D p) + public boolean contains(Point p) { - return contains (p.getX (), p.getY ()); + 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. + /** + * 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 (Rectangle2D r) + public boolean contains(int x, int y) { - return contains (r.getX (), r.getY (), r.getWidth (), r.getHeight ()); + return contains((double) x, (double) y); } - /** Returns the bounds of this Polygon. - * @deprecated Use getBounds() instead. + /** + * 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 Rectangle getBoundingBox () + public boolean inside(int x, int y) { - if (bounds == null) - computeBoundingBox (); - return bounds; + return contains((double) x, (double) y); } - /** Returns the bounds of this Polygon. */ - public Rectangle getBounds () + /** + * 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() { - if (bounds == null) - computeBoundingBox (); - return bounds; + // For polygons, the integer version is exact! + return getBounds(); } - /** Returns the bounds of this Polygon. */ - public Rectangle2D getBounds2D () + /** + * 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) { - if (bounds == null) - computeBoundingBox (); - return bounds; // Why not? + // 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; + 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 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. + /** + * 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 PathIterator getPathIterator (AffineTransform at) + public boolean contains(Point2D p) { - return new Iterator (at); + return contains(p.getX(), p.getY()); } - /** 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. + /** + * 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 PathIterator getPathIterator (AffineTransform at, double flatness) + public boolean intersects(double x, double y, double w, double h) { - // We ignore the flatness. - return new Iterator (at); + // 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; } - /** @deprecated use contains(int,int). */ - public boolean inside (int x, int y) + /** + * 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 contains (x, y); + return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight()); } - /** 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 + /** + * 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 intersects (double x, double y, double w, double h) + public boolean contains(double x, double y, double w, double h) { - return intersectOrContains (x, y, w, h, true); + // First, the obvious bounds checks. + if (w <= 0 || h <= 0 || ! contains(x, y) + || ! bounds.contains(x, y, w, h)) + return false; + // 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; } - /** Return true if this Polygon's interior intersects the given - * rectangle's interior. - * @param r The rectangle + /** + * 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 intersects (Rectangle2D r) + public boolean contains(Rectangle2D r) { - return intersects (r.getX (), r.getY (), r.getWidth (), r.getHeight ()); + return contains(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) + /** + * 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) { - // 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) - return false; - - double[] crosses = new double[npoints + 1]; + return new PathIterator() + { + /** The current vertex of iteration. */ + private int vertex; - for (; miny < maxy; ++miny) + public int getWindingRule() { - // 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 WIND_EVEN_ODD; } - 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) + public boolean isDone() { - xpoints[i] += deltaX; - ypoints[i] += deltaY; + return vertex > npoints; } - if (bounds != null) + public void next() { - bounds.x += deltaX; - bounds.y += deltaY; + vertex++; } - } - // This computes the bounding box if required. - private void computeBoundingBox () - { - if (npoints == 0) + public int currentSegment(float[] coords) { - // This is wrong if the user adds a new point, but we - // account for that in addPoint(). - bounds = new Rectangle (0, 0, 0, 0); + 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; } - else + + public int currentSegment(double[] coords) { - 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); + 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; } + }; } - private class Iterator implements PathIterator + /** + * 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) { - public AffineTransform xform; - public int where; - - public Iterator (AffineTransform xform) - { - 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; - } + return getPathIterator(transform); + } - public void next () - { - ++where; - } + /** + * 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 |