Back to index...

	/*
	* Copyright (c) 1995, 2013, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code 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
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/
	package java.awt;

	import java.awt.geom.AffineTransform;
	import java.awt.geom.PathIterator;
	import java.awt.geom.Point2D;
	import java.awt.geom.Rectangle2D;
	import sun.awt.geom.Crossings;
	import java.util.Arrays;

	/**
	* The <code>Polygon</code> class encapsulates a description of a
	* closed, two-dimensional region within a coordinate space. This
	* region is bounded by an arbitrary number of line segments, each of
	* which is one side of the polygon. Internally, a polygon
	* comprises of a list of {@code (x,y)}
	* coordinate pairs, where each pair defines a <i>vertex</i> of the
	* polygon, and two successive pairs are the endpoints of a
	* line that is a side of the polygon. The first and final
	* pairs of {@code (x,y)} points are joined by a line segment
	* that closes the polygon. This <code>Polygon</code> is defined with
	* an even-odd winding rule. See
	* {@link java.awt.geom.PathIterator#WIND_EVEN_ODD WIND_EVEN_ODD}
	* for a definition of the even-odd winding rule.
	* This class's hit-testing methods, which include the
	* <code>contains</code>, <code>intersects</code> and <code>inside</code>
	* methods, use the <i>insideness</i> definition described in the
	* {@link Shape} class comments.
	*
	* @author Sami Shaio
	* @see Shape
	* @author Herb Jellinek
	* @since 1.0
	*/
	public class Polygon implements Shape, java.io.Serializable {

	/**
	* 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
	* {@link #xpoints xpoints} or {@link #ypoints ypoints}.
	* This value can be NULL.
	*
	* @serial
	* @see #addPoint(int, int)
	* @since 1.0
	*/
	public int npoints;

	/**
	* 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>.
	*
	* @serial
	* @see #addPoint(int, int)
	* @since 1.0
	*/
	public int 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>.
	*
	* @serial
	* @see #addPoint(int, int)
	* @since 1.0
	*/
	public int ypoints[];

	/**
	* The bounds of this {@code Polygon}.
	* This value can be null.
	*
	* @serial
	* @see #getBoundingBox()
	* @see #getBounds()
	* @since 1.0
	*/
	protected Rectangle bounds;

	/*
	* 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.
	* @since 1.0
	*/
	public Polygon() {
	xpoints = new int[MIN_LENGTH];
	ypoints = new int[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>.
	* @since 1.0
	*/
	public Polygon(int xpoints[], int 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 = Arrays.copyOf(xpoints, npoints);
	this.ypoints = Arrays.copyOf(ypoints, npoints);
	}

	/**
	* 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
	* @since 1.4
	*/
	public void reset() {
	npoints = 0;
	bounds = null;
	}

	/**
	* 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
	* @since 1.4
	*/
	public void invalidate() {
	bounds = null;
	}

	/**
	* 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
	* @since 1.1
	*/
	public void translate(int deltaX, int deltaY) {
	for (int i = 0; i < npoints; i++) {
	xpoints[i] += deltaX;
	ypoints[i] += deltaY;
	}
	if (bounds != null) {
	bounds.translate(deltaX, deltaY);
	}
	}

	/*
	* 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(int xpoints[], int ypoints[], int npoints) {
	int boundsMinX = Integer.MAX_VALUE;
	int boundsMinY = Integer.MAX_VALUE;
	int boundsMaxX = Integer.MIN_VALUE;
	int boundsMaxY = Integer.MIN_VALUE;

	for (int i = 0; i < npoints; i++) {
	int x = xpoints[i];
	boundsMinX = Math.min(boundsMinX, x);
	boundsMaxX = Math.max(boundsMaxX, x);
	int y = ypoints[i];
	boundsMinY = Math.min(boundsMinY, y);
	boundsMaxY = Math.max(boundsMaxY, y);
	}
	bounds = new Rectangle(boundsMinX, boundsMinY,
	boundsMaxX - boundsMinX,
	boundsMaxY - boundsMinY);
	}

	/*
	* Resizes the bounding box to accommodate the specified coordinates.
	* @param x, y the specified coordinates
	*/
	void updateBounds(int x, int 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;
	}
	}

	/**
	* 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
	* @since 1.0
	*/
	public void addPoint(int x, int 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);
	}

	xpoints = Arrays.copyOf(xpoints, newLength);
	ypoints = Arrays.copyOf(ypoints, newLength);
	}
	xpoints[npoints] = x;
	ypoints[npoints] = y;
	npoints++;
	if (bounds != null) {
	updateBounds(x, y);
	}
	}

	/**
	* 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>.
	* @since 1.1
	*/
	public Rectangle getBounds() {
	return getBoundingBox();
	}

	/**
	* Returns the bounds of this <code>Polygon</code>.
	* @return the bounds of this <code>Polygon</code>.
	* @deprecated As of JDK version 1.1,
	* replaced by <code>getBounds()</code>.
	* @since 1.0
	*/
	@Deprecated
	public Rectangle getBoundingBox() {
	if (npoints == 0) {
	return new Rectangle();
	}
	if (bounds == null) {
	calculateBounds(xpoints, ypoints, npoints);
	}
	return bounds.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)
	* @since 1.0
	*/
	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)
	* @since 1.1
	*/
	public boolean contains(int x, int y) {
	return contains((double) x, (double) y);
	}

	/**
	* Determines whether the specified coordinates are contained in this
	* <code>Polygon</code>.
	* @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)
	* @deprecated As of JDK version 1.1,
	* replaced by <code>contains(int, int)</code>.
	* @since 1.0
	*/
	@Deprecated
	public boolean inside(int x, int y) {
	return contains((double) x, (double) y);
	}

	/**
	* {@inheritDoc}
	* @since 1.2
	*/
	public Rectangle2D getBounds2D() {
	return getBounds();
	}

	/**
	* {@inheritDoc}
	* @since 1.2
	*/
	public boolean contains(double x, double y) {
	if (npoints <= 2 \|\| !getBoundingBox().contains(x, y)) {
	return false;
	}
	int hits = 0;

	int lastx = xpoints[npoints - 1];
	int lasty = ypoints[npoints - 1];
	int 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;
	}

	int 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);
	}

	private Crossings getCrossings(double xlo, double ylo,
	double xhi, double yhi)
	{
	Crossings cross = new Crossings.EvenOdd(xlo, ylo, xhi, yhi);
	int lastx = xpoints[npoints - 1];
	int lasty = ypoints[npoints - 1];
	int 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;
	}

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

	/**
	* {@inheritDoc}
	* @since 1.2
	*/
	public boolean intersects(double x, double y, double w, double h) {
	if (npoints <= 0 \|\| !getBoundingBox().intersects(x, y, w, h)) {
	return false;
	}

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

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

	/**
	* {@inheritDoc}
	* @since 1.2
	*/
	public boolean contains(double x, double y, double w, double h) {
	if (npoints <= 0 \|\| !getBoundingBox().intersects(x, y, w, h)) {
	return false;
	}

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

	/**
	* {@inheritDoc}
	* @since 1.2
	*/
	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>.
	* @since 1.2
	*/
	public PathIterator getPathIterator(AffineTransform at) {
	return new PolygonPathIterator(this, 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.
	* @since 1.2
	*/
	public PathIterator getPathIterator(AffineTransform at, double flatness) {
	return getPathIterator(at);
	}

	class PolygonPathIterator implements PathIterator {
	Polygon poly;
	AffineTransform transform;
	int index;

	public PolygonPathIterator(Polygon 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, 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] = 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);
	}

	/**
	* 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, 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);
	}
	}
	}

Back to index...