/*
 * @(#)Polygon2D.java
 * 
 * Copyright (c) 2009-2010 by the original authors of JHotDraw
 * and all its contributors.
 * All rights reserved.
 * 
 * The copyright of this software is owned by the authors and  
 * contributors of the JHotDraw project ("the copyright holders").  
 * You may not use, copy or modify this software, except in  
 * accordance with the license agreement you entered into with  
 * the copyright holders. For details see accompanying license terms. 
 */
package org.jhotdraw.geom;

import java.awt.Point;
import java.awt.Polygon;
import java.awt.Rectangle;
import java.awt.Shape;
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 sun.awt.geom.Crossings;

/**
 * Polygon2D.
 *
 * @author Werner Randelshofer
 * @version $Id: Polygon2D.java 666 2010-07-28 19:11:46Z rawcoder $
 */
public abstract class Polygon2D implements Shape, Cloneable {

    /**
     * The total number of points.  The value of <code>npoints</code>
     * represents the number of valid points in this <code>Polygon</code>
     * and might be less than the number of elements in 
     * {@code xpoints} or {@code ypoints}.
     * This value can be NULL.
     *
     */
    public int npoints;

    /* 
     * JDK 1.1 serialVersionUID 
     */
    private static final long serialVersionUID = -6460061437900069969L;
    /*
     * Default length for xpoints and ypoints.
     */
    private static final int MIN_LENGTH = 4;

    /**
     * Creates an empty polygon.
     * 
     */
    public Polygon2D() {
    }

    /**
     * Resets this <code>Polygon</code> object to an empty polygon.
     * The coordinate arrays and the data in them are left untouched
     * but the number of points is reset to zero to mark the old
     * vertex data as invalid and to start accumulating new vertex
     * data at the beginning.
     * All internally-cached data relating to the old vertices
     * are discarded.
     * Note that since the coordinate arrays from before the reset
     * are reused, creating a new empty <code>Polygon</code> might
     * be more memory efficient than resetting the current one if
     * the number of vertices in the new polygon data is significantly
     * smaller than the number of vertices in the data from before the
     * reset.
     * @see         java.awt.Polygon#invalidate
     * 
     */
    public void reset() {
        npoints = 0;
        invalidate();
    }

    /**
     * Invalidates or flushes any internally-cached data that depends
     * on the vertex coordinates of this <code>Polygon</code>.
     * This method should be called after any direct manipulation
     * of the coordinates in the <code>xpoints</code> or
     * <code>ypoints</code> arrays to avoid inconsistent results
     * from methods such as <code>getBounds</code> or <code>contains</code>
     * that might cache data from earlier computations relating to
     * the vertex coordinates.
     * @see         java.awt.Polygon#getBounds
     * 
     */
    public abstract void invalidate();

    /**
     * Translates the vertices of the <code>Polygon</code> by 
     * <code>deltaX</code> along the x axis and by 
     * <code>deltaY</code> along the y axis.
     * @param deltaX the amount to translate along the X axis
     * @param deltaY the amount to translate along the Y axis
     * 
     */
    public abstract void translate(double deltaX, double deltaY);

    /**
     * Appends the specified coordinates to this <code>Polygon</code>. 
     * <p>
     * If an operation that calculates the bounding box of this     
     * <code>Polygon</code> has already been performed, such as  
     * <code>getBounds</code> or <code>contains</code>, then this 
     * method updates the bounding box. 
     * @param       x the specified X coordinate
     * @param       y the specified Y coordinate
     * @see         java.awt.Polygon#getBounds
     * @see         java.awt.Polygon#contains
     * 
     */
    public abstract void addPoint(double x, double y);

    public void add(Point2D p) {
        addPoint(p.getX(), p.getY());
    }

    /**
     * Gets the bounding box of this <code>Polygon</code>. 
     * The bounding box is the smallest {@link Rectangle} whose
     * sides are parallel to the x and y axes of the 
     * coordinate space, and can completely contain the <code>Polygon</code>.
     * @return a <code>Rectangle</code> that defines the bounds of this 
     * <code>Polygon</code>.
     * 
     */
    
    public Rectangle getBounds() {
        return getBounds2D().getBounds();
    }

    /**
     * Determines whether the specified {@link Point} is inside this 
     * <code>Polygon</code>.
     * @param p the specified <code>Point</code> to be tested
     * @return <code>true</code> if the <code>Polygon</code> contains the
     * 			<code>Point</code>; <code>false</code> otherwise.
     * @see #contains(double, double)
     * 
     */
    public boolean contains(Point p) {
        return contains(p.x, p.y);
    }

    /**
     * Determines whether the specified coordinates are inside this 
     * <code>Polygon</code>.   
     * <p>
     * @param x the specified X coordinate to be tested
     * @param y the specified Y coordinate to be tested
     * @return {@code true} if this {@code Polygon} contains
     *         the specified coordinates {@code (x,y)};
     *         {@code false} otherwise.
     * @see #contains(double, double)
     * 
     */
    public boolean contains(int x, int y) {
        return contains((double) x, (double) y);
    }

    /**
     * {@inheritDoc}
     * 
     */
    
    public abstract Rectangle2D getBounds2D();

    /**
     * {@inheritDoc}
     * 
     */
    
    public abstract boolean contains(double x, double y);

    /**
     * {@inheritDoc}
     * 
     */
    
    public boolean contains(Point2D p) {
        return contains(p.getX(), p.getY());
    }

    /**
     * {@inheritDoc}
     * 
     */
    
    public abstract boolean intersects(double x, double y, double w, double h);

    /**
     * {@inheritDoc}
     * 
     */
    
    public boolean intersects(Rectangle2D r) {
        return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
    }

    /**
     * {@inheritDoc}
     * 
     */
    
    public abstract boolean contains(double x, double y, double w, double h);

    /**
     * {@inheritDoc}
     * 
     */
    
    public boolean contains(Rectangle2D r) {
        return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
    }

    /**
     * Returns an iterator object that iterates along the boundary of this 
     * <code>Polygon</code> and provides access to the geometry
     * of the outline of this <code>Polygon</code>.  An optional
     * {@link AffineTransform} can be specified so that the coordinates 
     * returned in the iteration are transformed accordingly.
     * @param at an optional <code>AffineTransform</code> to be applied to the
     * 		coordinates as they are returned in the iteration, or 
     *		<code>null</code> if untransformed coordinates are desired
     * @return a {@link PathIterator} object that provides access to the
     *		geometry of this <code>Polygon</code>.      
     * 
     */
    
    public abstract PathIterator getPathIterator(AffineTransform at);

    /**
     * Returns an iterator object that iterates along the boundary of
     * the <code>Shape</code> and provides access to the geometry of the 
     * outline of the <code>Shape</code>.  Only SEG_MOVETO, SEG_LINETO, and 
     * SEG_CLOSE point types are returned by the iterator.
     * Since polygons are already flat, the <code>flatness</code> parameter
     * is ignored.  An optional <code>AffineTransform</code> can be specified 
     * in which case the coordinates returned in the iteration are transformed
     * accordingly.
     * @param at an optional <code>AffineTransform</code> to be applied to the
     * 		coordinates as they are returned in the iteration, or 
     *		<code>null</code> if untransformed coordinates are desired
     * @param flatness the maximum amount that the control points
     * 		for a given curve can vary from colinear before a subdivided
     *		curve is replaced by a straight line connecting the 
     * 		endpoints.  Since polygons are already flat the
     * 		<code>flatness</code> parameter is ignored.
     * @return a <code>PathIterator</code> object that provides access to the
     * 		<code>Shape</code> object's geometry.
     * 
     */
    
    public PathIterator getPathIterator(AffineTransform at, double flatness) {
        return getPathIterator(at);
    }

    /**
     * The {@code Double} class defines a polygon with
     * coordinates stored in double precision floating point.
     */
    public static class Double extends Polygon2D implements Serializable {

        /**
         * The array of X coordinates.  The number of elements in
         * this array might be more than the number of X coordinates
         * in this <code>Polygon</code>.  The extra elements allow new points
         * to be added to this <code>Polygon</code> without re-creating this
         * array.  The value of {@link #npoints npoints} is equal to the
         * number of valid points in this <code>Polygon</code>.
         *
         */
        public double xpoints[];
        /**
         * The array of Y coordinates.  The number of elements in
         * this array might be more than the number of Y coordinates
         * in this <code>Polygon</code>.  The extra elements allow new points
         * to be added to this <code>Polygon</code> without re-creating this
         * array.  The value of <code>npoints</code> is equal to the
         * number of valid points in this <code>Polygon</code>.
         *
         */
        public double ypoints[];
        /**
         * The bounds of this {@code Polygon}.
         * This value can be null.
         *
         * 
         */
        protected Rectangle2D.Double bounds;

        public Double() {
            xpoints = new double[MIN_LENGTH];
            ypoints = new double[MIN_LENGTH];
        }

        /**
         * Constructs and initializes a <code>Polygon</code> from the specified
         * parameters.
         * @param xpoints an array of X coordinates
         * @param ypoints an array of Y coordinates
         * @param npoints the total number of points in the
         *				<code>Polygon</code>
         * @exception  NegativeArraySizeException if the value of
         *                       <code>npoints</code> is negative.
         * @exception  IndexOutOfBoundsException if <code>npoints</code> is
         *             greater than the length of <code>xpoints</code>
         *             or the length of <code>ypoints</code>.
         * @exception  NullPointerException if <code>xpoints</code> or
         *             <code>ypoints</code> is <code>null</code>.
         * 
         */
        public Double(double xpoints[], double ypoints[], int npoints) {
            // Fix 4489009: should throw IndexOutofBoundsException instead
            // of OutofMemoryException if npoints is huge and > {x,y}points.length
            if (npoints > xpoints.length || npoints > ypoints.length) {
                throw new IndexOutOfBoundsException("npoints > xpoints.length || "
                        + "npoints > ypoints.length");
            }
            // Fix 6191114: should throw NegativeArraySizeException with
            // negative npoints
            if (npoints < 0) {
                throw new NegativeArraySizeException("npoints < 0");
            }
            // Fix 6343431: Applet compatibility problems if arrays are not
            // exactly npoints in length
            this.npoints = npoints;
            this.xpoints = new double[npoints];
            System.arraycopy(xpoints, 0, this.xpoints, 0,
                    npoints);

            this.ypoints = new double[npoints];
            System.arraycopy(ypoints, 0, this.ypoints, 0,
                    npoints);
        }

        /**
         * Translates the vertices of the <code>Polygon</code> by
         * <code>deltaX</code> along the x axis and by
         * <code>deltaY</code> along the y axis.
         * @param deltaX the amount to translate along the X axis
         * @param deltaY the amount to translate along the Y axis
         * 
         */
        
        public void translate(double deltaX, double deltaY) {
            for (int i = 0; i < npoints; i++) {
                xpoints[i] += deltaX;
                ypoints[i] += deltaY;
            }
            if (bounds != null) {
                bounds.x += deltaX;
                bounds.y += deltaY;
            }
        }

        
        public void invalidate() {
            bounds = null;
        }
        /*
         * Calculates the bounding box of the points passed to the constructor.
         * Sets <code>bounds</code> to the result.
         * @param xpoints[] array of <i>x</i> coordinates
         * @param ypoints[] array of <i>y</i> coordinates
         * @param npoints the total number of points
         */

        void calculateBounds(double xpoints[], double ypoints[], int npoints) {
            double boundsMinX = java.lang.Double.MAX_VALUE;
            double boundsMinY = java.lang.Double.MAX_VALUE;
            double boundsMaxX = -java.lang.Double.MAX_VALUE;
            double boundsMaxY = -java.lang.Double.MAX_VALUE;

            for (int i = 0; i < npoints; i++) {
                double x = xpoints[i];
                boundsMinX = Math.min(boundsMinX, x);
                boundsMaxX = Math.max(boundsMaxX, x);
                double y = ypoints[i];
                boundsMinY = Math.min(boundsMinY, y);
                boundsMaxY = Math.max(boundsMaxY, y);
            }
            bounds = new Rectangle2D.Double(boundsMinX, boundsMinY,
                    boundsMaxX - boundsMinX,
                    boundsMaxY - boundsMinY);
        }
        /*
         * Resizes the bounding box to accomodate the specified coordinates.
         * @param x,&nbsp;y the specified coordinates
         */

        void updateBounds(double x, double y) {
            if (x < bounds.x) {
                bounds.width = bounds.width + (bounds.x - x);
                bounds.x = x;
            } else {
                bounds.width = Math.max(bounds.width, x - bounds.x);
                // bounds.x = bounds.x;
            }

            if (y < bounds.y) {
                bounds.height = bounds.height + (bounds.y - y);
                bounds.y = y;
            } else {
                bounds.height = Math.max(bounds.height, y - bounds.y);
                // bounds.y = bounds.y;
            }
        }

        
        public boolean contains(double x, double y) {
            if (npoints <= 2 || !getBounds2D().contains(x, y)) {
                return false;
            }
            int hits = 0;

            double lastx = xpoints[npoints - 1];
            double lasty = ypoints[npoints - 1];
            double curx, cury;

            // Walk the edges of the polygon
            for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) {
                curx = xpoints[i];
                cury = ypoints[i];

                if (cury == lasty) {
                    continue;
                }

                double leftx;
                if (curx < lastx) {
                    if (x >= lastx) {
                        continue;
                    }
                    leftx = curx;
                } else {
                    if (x >= curx) {
                        continue;
                    }
                    leftx = lastx;
                }

                double test1, test2;
                if (cury < lasty) {
                    if (y < cury || y >= lasty) {
                        continue;
                    }
                    if (x < leftx) {
                        hits++;
                        continue;
                    }
                    test1 = x - curx;
                    test2 = y - cury;
                } else {
                    if (y < lasty || y >= cury) {
                        continue;
                    }
                    if (x < leftx) {
                        hits++;
                        continue;
                    }
                    test1 = x - lastx;
                    test2 = y - lasty;
                }

                if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {
                    hits++;
                }
            }

            return ((hits & 1) != 0);
        }

        
        public boolean intersects(double x, double y, double w, double h) {
            if (npoints <= 0 || !getBounds2D().intersects(x, y, w, h)) {
                return false;
            }

            Crossings cross = getCrossings(x, y, x + w, y + h);
            return (cross == null || !cross.isEmpty());
        }

        private Crossings getCrossings(double xlo, double ylo,
                double xhi, double yhi) {
            Crossings cross = new Crossings.EvenOdd(xlo, ylo, xhi, yhi);
            double lastx = xpoints[npoints - 1];
            double lasty = ypoints[npoints - 1];
            double curx, cury;

            // Walk the edges of the polygon
            for (int i = 0; i < npoints; i++) {
                curx = xpoints[i];
                cury = ypoints[i];
                if (cross.accumulateLine(lastx, lasty, curx, cury)) {
                    return null;
                }
                lastx = curx;
                lasty = cury;
            }

            return cross;
        }

        
        public void addPoint(double x, double y) {
            if (npoints >= xpoints.length || npoints >= ypoints.length) {
                int newLength = npoints * 2;
                // Make sure that newLength will be greater than MIN_LENGTH and
                // aligned to the power of 2
                if (newLength < MIN_LENGTH) {
                    newLength = MIN_LENGTH;
                } else if ((newLength & (newLength - 1)) != 0) {
                    newLength = Integer.highestOneBit(newLength);
                }

                double[] helper = new double[newLength];
                System.arraycopy(xpoints, 0, helper, 0,
                        npoints);
                xpoints = helper;

                helper = new double[newLength];
                System.arraycopy(ypoints, 0, helper, 0,
                        npoints);
                ypoints = helper;
            }
            xpoints[npoints] = x;
            ypoints[npoints] = y;
            npoints++;
            if (bounds != null) {
                updateBounds(x, y);
            }
        }

        
        public Rectangle getBounds() {
            Polygon x;
            throw new UnsupportedOperationException("Not supported yet.");
        }

        
        public Rectangle2D getBounds2D() {
            if (npoints == 0) {
                return new Rectangle2D.Double();
            }
            if (bounds == null) {
                calculateBounds(xpoints, ypoints, npoints);
            }
            return (Rectangle2D) bounds.clone();
        }

        
        public boolean contains(double x, double y, double w, double h) {
            if (npoints <= 0 || !getBounds2D().intersects(x, y, w, h)) {
                return false;
            }

            Crossings cross = getCrossings(x, y, x + w, y + h);
            return (cross != null && cross.covers(y, y + h));
        }

        
        public PathIterator getPathIterator(AffineTransform at) {
            return new PolygonPathIteratorDouble(this, at);
        }
    }

    /**
     * The {@code Float} class defines a polygon with
     * coordinates stored in double precision floating point.
     */
    /**
     * The {@code Float} class defines a polygon with
     * coordinates stored in float precision floating point.
     */
    public static class Float extends Polygon2D implements Serializable {

        /**
         * The array of X coordinates.  The number of elements in
         * this array might be more than the number of X coordinates
         * in this <code>Polygon</code>.  The extra elements allow new points
         * to be added to this <code>Polygon</code> without re-creating this
         * array.  The value of {@link #npoints npoints} is equal to the
         * number of valid points in this <code>Polygon</code>.
         */
        public float xpoints[];
        /**
         * The array of Y coordinates.  The number of elements in
         * this array might be more than the number of Y coordinates
         * in this <code>Polygon</code>.  The extra elements allow new points
         * to be added to this <code>Polygon</code> without re-creating this
         * array.  The value of <code>npoints</code> is equal to the
         * number of valid points in this <code>Polygon</code>.
         */
        public float ypoints[];
        /**
         * The bounds of this {@code Polygon}.
         * This value can be null.
         */
        protected Rectangle2D.Float bounds;

        public Float() {
            xpoints = new float[MIN_LENGTH];
            ypoints = new float[MIN_LENGTH];
        }

        /**
         * Constructs and initializes a <code>Polygon</code> from the specified
         * parameters.
         * @param xpoints an array of X coordinates
         * @param ypoints an array of Y coordinates
         * @param npoints the total number of points in the
         *				<code>Polygon</code>
         * @exception  NegativeArraySizeException if the value of
         *                       <code>npoints</code> is negative.
         * @exception  IndexOutOfBoundsException if <code>npoints</code> is
         *             greater than the length of <code>xpoints</code>
         *             or the length of <code>ypoints</code>.
         * @exception  NullPointerException if <code>xpoints</code> or
         *             <code>ypoints</code> is <code>null</code>.
         * 
         */
        public Float(float xpoints[], float ypoints[], int npoints) {
            // Fix 4489009: should throw IndexOutofBoundsException instead
            // of OutofMemoryException if npoints is huge and > {x,y}points.length
            if (npoints > xpoints.length || npoints > ypoints.length) {
                throw new IndexOutOfBoundsException("npoints > xpoints.length || "
                        + "npoints > ypoints.length");
            }
            // Fix 6191114: should throw NegativeArraySizeException with
            // negative npoints
            if (npoints < 0) {
                throw new NegativeArraySizeException("npoints < 0");
            }
            // Fix 6343431: Applet compatibility problems if arrays are not
            // exactly npoints in length
            this.npoints = npoints;
            this.xpoints = new float[npoints];
            System.arraycopy(xpoints, 0, this.xpoints, 0,
                    npoints);

            this.ypoints = new float[npoints];
            System.arraycopy(ypoints, 0, this.ypoints, 0,
                    npoints);
        }

        /**
         * Translates the vertices of the <code>Polygon</code> by
         * <code>deltaX</code> along the x axis and by
         * <code>deltaY</code> along the y axis.
         * @param deltaX the amount to translate along the X axis
         * @param deltaY the amount to translate along the Y axis
         * 
         */
        
        public void translate(double deltaX, double deltaY) {
            translate((float) deltaX, (float) deltaY);
        }

        public void translate(float deltaX, float deltaY) {
            for (int i = 0; i < npoints; i++) {
                xpoints[i] += deltaX;
                ypoints[i] += deltaY;
            }
            if (bounds != null) {
                bounds.x += deltaX;
                bounds.y += deltaY;
            }
        }

        
        public void invalidate() {
            bounds = null;
        }
        /*
         * Calculates the bounding box of the points passed to the constructor.
         * Sets <code>bounds</code> to the result.
         * @param xpoints[] array of <i>x</i> coordinates
         * @param ypoints[] array of <i>y</i> coordinates
         * @param npoints the total number of points
         */

        void calculateBounds(float xpoints[], float ypoints[], int npoints) {
            float boundsMinX = java.lang.Float.MAX_VALUE;
            float boundsMinY = java.lang.Float.MAX_VALUE;
            float boundsMaxX = -java.lang.Float.MAX_VALUE;
            float boundsMaxY = -java.lang.Float.MAX_VALUE;

            for (int i = 0; i < npoints; i++) {
                float x = xpoints[i];
                boundsMinX = Math.min(boundsMinX, x);
                boundsMaxX = Math.max(boundsMaxX, x);
                float y = ypoints[i];
                boundsMinY = Math.min(boundsMinY, y);
                boundsMaxY = Math.max(boundsMaxY, y);
            }
            bounds = new Rectangle2D.Float(boundsMinX, boundsMinY,
                    boundsMaxX - boundsMinX,
                    boundsMaxY - boundsMinY);
        }
        /*
         * Resizes the bounding box to accomodate the specified coordinates.
         * @param x,&nbsp;y the specified coordinates
         */

        void updateBounds(float x, float y) {
            if (x < bounds.x) {
                bounds.width = bounds.width + (bounds.x - x);
                bounds.x = x;
            } else {
                bounds.width = Math.max(bounds.width, x - bounds.x);
                // bounds.x = bounds.x;
            }

            if (y < bounds.y) {
                bounds.height = bounds.height + (bounds.y - y);
                bounds.y = y;
            } else {
                bounds.height = Math.max(bounds.height, y - bounds.y);
                // bounds.y = bounds.y;
            }
        }

        
        public boolean contains(double x, double y) {
            return contains((float) x, (float) y);
        }

        public boolean contains(float x, float y) {
            if (npoints <= 2 || !getBounds2D().contains(x, y)) {
                return false;
            }
            int hits = 0;

            float lastx = xpoints[npoints - 1];
            float lasty = ypoints[npoints - 1];
            float curx, cury;

            // Walk the edges of the polygon
            for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) {
                curx = xpoints[i];
                cury = ypoints[i];

                if (cury == lasty) {
                    continue;
                }

                float leftx;
                if (curx < lastx) {
                    if (x >= lastx) {
                        continue;
                    }
                    leftx = curx;
                } else {
                    if (x >= curx) {
                        continue;
                    }
                    leftx = lastx;
                }

                float test1, test2;
                if (cury < lasty) {
                    if (y < cury || y >= lasty) {
                        continue;
                    }
                    if (x < leftx) {
                        hits++;
                        continue;
                    }
                    test1 = x - curx;
                    test2 = y - cury;
                } else {
                    if (y < lasty || y >= cury) {
                        continue;
                    }
                    if (x < leftx) {
                        hits++;
                        continue;
                    }
                    test1 = x - lastx;
                    test2 = y - lasty;
                }

                if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {
                    hits++;
                }
            }

            return ((hits & 1) != 0);
        }

        
        public boolean intersects(double x, double y, double w, double h) {
            return intersects((float) x, (float) y, (float) w, (float) h);
        }

        public boolean intersects(float x, float y, float w, float h) {
            if (npoints <= 0 || !getBounds2D().intersects(x, y, w, h)) {
                return false;
            }

            Crossings cross = getCrossings(x, y, x + w, y + h);
            return (cross == null || !cross.isEmpty());
        }

        private Crossings getCrossings(float xlo, float ylo,
                float xhi, float yhi) {
            Crossings cross = new Crossings.EvenOdd(xlo, ylo, xhi, yhi);
            float lastx = xpoints[npoints - 1];
            float lasty = ypoints[npoints - 1];
            float curx, cury;

            // Walk the edges of the polygon
            for (int i = 0; i < npoints; i++) {
                curx = xpoints[i];
                cury = ypoints[i];
                if (cross.accumulateLine(lastx, lasty, curx, cury)) {
                    return null;
                }
                lastx = curx;
                lasty = cury;
            }

            return cross;
        }

        
        public void addPoint(double x, double y) {
            addPoint((float) x, (float) y);
        }

        public void addPoint(float x, float y) {
            if (npoints >= xpoints.length || npoints >= ypoints.length) {
                int newLength = npoints * 2;
                // Make sure that newLength will be greater than MIN_LENGTH and
                // aligned to the power of 2
                if (newLength < MIN_LENGTH) {
                    newLength = MIN_LENGTH;
                } else if ((newLength & (newLength - 1)) != 0) {
                    newLength = Integer.highestOneBit(newLength);
                }
                float[] helper = new float[newLength];
                System.arraycopy(xpoints, 0, helper, 0,
                        npoints);
                xpoints = helper;

                helper = new float[newLength];
                System.arraycopy(ypoints, 0, helper, 0,
                        npoints);
                ypoints = helper;
            }
            xpoints[npoints] = x;
            ypoints[npoints] = y;
            npoints++;
            if (bounds != null) {
                updateBounds(x, y);
            }
        }

        
        public Rectangle getBounds() {
            Polygon x;
            throw new UnsupportedOperationException("Not supported yet.");
        }

        
        public Rectangle2D getBounds2D() {
            if (npoints == 0) {
                return new Rectangle2D.Float();
            }
            if (bounds == null) {
                calculateBounds(xpoints, ypoints, npoints);
            }
            return (Rectangle2D) bounds.clone();
        }

        
        public boolean contains(double x, double y, double w, double h) {
            return contains((float) x, (float) y, (float) w, (float) h);
        }

        public boolean contains(float x, float y, float w, float h) {
            if (npoints <= 0 || !getBounds2D().intersects(x, y, w, h)) {
                return false;
            }

            Crossings cross = getCrossings(x, y, x + w, y + h);
            return (cross != null && cross.covers(y, y + h));
        }

        
        public PathIterator getPathIterator(AffineTransform at) {
            return new PolygonPathIteratorFloat(this, at);
        }
    }

    class PolygonPathIteratorDouble implements PathIterator {

        Polygon2D.Double poly;
        AffineTransform transform;
        int index;

        public PolygonPathIteratorDouble(Polygon2D.Double pg, AffineTransform at) {
            poly = pg;
            transform = at;
            if (pg.npoints == 0) {
                // Prevent a spurious SEG_CLOSE segment
                index = 1;
            }
        }

        /**
         * Returns the winding rule for determining the interior of the
         * path.
         * @return an integer representing the current winding rule.
         * @see PathIterator#WIND_NON_ZERO
         */
        
        public int getWindingRule() {
            return WIND_EVEN_ODD;
        }

        /**
         * Tests if there are more points to read.
         * @return <code>true</code> if there are more points to read;
         *          <code>false</code> otherwise.
         */
        
        public boolean isDone() {
            return index > poly.npoints;
        }

        /**
         * Moves the iterator forwards, along the primary direction of
         * traversal, to the next segment of the path when there are
         * more points in that direction.
         */
        
        public void next() {
            index++;
        }

        /**
         * Returns the coordinates and type of the current path segment in
         * the iteration.
         * The return value is the path segment type:
         * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE.
         * A <code>float</code> array of length 2 must be passed in and
         * can be used to store the coordinates of the point(s).
         * Each point is stored as a pair of <code>float</code> x,&nbsp;y
         * coordinates.  SEG_MOVETO and SEG_LINETO types return one
         * point, and SEG_CLOSE does not return any points.
         * @param coords a <code>float</code> array that specifies the
         * coordinates of the point(s)
         * @return an integer representing the type and coordinates of the
         * 		current path segment.
         * @see PathIterator#SEG_MOVETO
         * @see PathIterator#SEG_LINETO
         * @see PathIterator#SEG_CLOSE
         */
        
        public int currentSegment(float[] coords) {
            if (index >= poly.npoints) {
                return SEG_CLOSE;
            }
            coords[0] = (float) poly.xpoints[index];
            coords[1] = (float) poly.ypoints[index];
            if (transform != null) {
                transform.transform(coords, 0, coords, 0, 1);
            }
            return (index == 0 ? SEG_MOVETO : SEG_LINETO);
        }

        /**
         * Returns the coordinates and type of the current path segment in
         * the iteration.
         * The return value is the path segment type:
         * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE.
         * A <code>double</code> array of length 2 must be passed in and
         * can be used to store the coordinates of the point(s).
         * Each point is stored as a pair of <code>double</code> x,&nbsp;y
         * coordinates.
         * SEG_MOVETO and SEG_LINETO types return one point,
         * and SEG_CLOSE does not return any points.
         * @param coords a <code>double</code> array that specifies the
         * coordinates of the point(s)
         * @return an integer representing the type and coordinates of the
         * 		current path segment.
         * @see PathIterator#SEG_MOVETO
         * @see PathIterator#SEG_LINETO
         * @see PathIterator#SEG_CLOSE
         */
        
        public int currentSegment(double[] coords) {
            if (index >= poly.npoints) {
                return SEG_CLOSE;
            }
            coords[0] = poly.xpoints[index];
            coords[1] = poly.ypoints[index];
            if (transform != null) {
                transform.transform(coords, 0, coords, 0, 1);
            }
            return (index == 0 ? SEG_MOVETO : SEG_LINETO);
        }
    }

    class PolygonPathIteratorFloat implements PathIterator {

        Polygon2D.Float poly;
        AffineTransform transform;
        int index;

        public PolygonPathIteratorFloat(Polygon2D.Float pg, AffineTransform at) {
            poly = pg;
            transform = at;
            if (pg.npoints == 0) {
                // Prevent a spurious SEG_CLOSE segment
                index = 1;
            }
        }

        /**
         * Returns the winding rule for determining the interior of the
         * path.
         * @return an integer representing the current winding rule.
         * @see PathIterator#WIND_NON_ZERO
         */
        
        public int getWindingRule() {
            return WIND_EVEN_ODD;
        }

        /**
         * Tests if there are more points to read.
         * @return <code>true</code> if there are more points to read;
         *          <code>false</code> otherwise.
         */
        
        public boolean isDone() {
            return index > poly.npoints;
        }

        /**
         * Moves the iterator forwards, along the primary direction of
         * traversal, to the next segment of the path when there are
         * more points in that direction.
         */
        
        public void next() {
            index++;
        }

        /**
         * Returns the coordinates and type of the current path segment in
         * the iteration.
         * The return value is the path segment type:
         * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE.
         * A <code>float</code> array of length 2 must be passed in and
         * can be used to store the coordinates of the point(s).
         * Each point is stored as a pair of <code>float</code> x,&nbsp;y
         * coordinates.  SEG_MOVETO and SEG_LINETO types return one
         * point, and SEG_CLOSE does not return any points.
         * @param coords a <code>float</code> array that specifies the
         * coordinates of the point(s)
         * @return an integer representing the type and coordinates of the
         * 		current path segment.
         * @see PathIterator#SEG_MOVETO
         * @see PathIterator#SEG_LINETO
         * @see PathIterator#SEG_CLOSE
         */
        
        public int currentSegment(float[] coords) {
            if (index >= poly.npoints) {
                return SEG_CLOSE;
            }
            coords[0] = (float) poly.xpoints[index];
            coords[1] = (float) poly.ypoints[index];
            if (transform != null) {
                transform.transform(coords, 0, coords, 0, 1);
            }
            return (index == 0 ? SEG_MOVETO : SEG_LINETO);
        }

        /**
         * Returns the coordinates and type of the current path segment in
         * the iteration.
         * The return value is the path segment type:
         * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE.
         * A <code>double</code> array of length 2 must be passed in and
         * can be used to store the coordinates of the point(s).
         * Each point is stored as a pair of <code>double</code> x,&nbsp;y
         * coordinates.
         * SEG_MOVETO and SEG_LINETO types return one point,
         * and SEG_CLOSE does not return any points.
         * @param coords a <code>double</code> array that specifies the
         * coordinates of the point(s)
         * @return an integer representing the type and coordinates of the
         * 		current path segment.
         * @see PathIterator#SEG_MOVETO
         * @see PathIterator#SEG_LINETO
         * @see PathIterator#SEG_CLOSE
         */
        
        public int currentSegment(double[] coords) {
            if (index >= poly.npoints) {
                return SEG_CLOSE;
            }
            coords[0] = poly.xpoints[index];
            coords[1] = poly.ypoints[index];
            if (transform != null) {
                transform.transform(coords, 0, coords, 0, 1);
            }
            return (index == 0 ? SEG_MOVETO : SEG_LINETO);
        }
    }
}
