| /* | |
| * Copyright (c) 1995, 2021, 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 java.io.Serial; | |
| import java.util.Arrays; | |
| import sun.awt.geom.Crossings; | |
| /** | |
| * The {@code Polygon} 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} 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 intersects} and {@code inside} | |
| * 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} | |
| * represents the number of valid points in this {@code Polygon} | |
| * and might be less than the number of elements in | |
| * {@link #xpoints xpoints} or {@link #ypoints ypoints}. | |
| * This value can be 0. | |
| * | |
| * @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}. The extra elements allow new points | |
| * to be added to this {@code Polygon} without re-creating this | |
| * array. The value of {@link #npoints npoints} is equal to the | |
| * number of valid points in this {@code Polygon}. | |
| * | |
| * @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}. The extra elements allow new points | |
| * to be added to this {@code Polygon} without re-creating this | |
| * array. The value of {@code npoints} is equal to the | |
| * number of valid points in this {@code Polygon}. | |
| * | |
| * @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; | |
| /** | |
| * Use serialVersionUID from JDK 1.1 for interoperability. | |
| */ | |
| @Serial | |
| 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} 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} | |
| * @throws NegativeArraySizeException if the value of | |
| * {@code npoints} is negative. | |
| * @throws IndexOutOfBoundsException if {@code npoints} is | |
| * greater than the length of {@code xpoints} | |
| * or the length of {@code ypoints}. | |
| * @throws NullPointerException if {@code xpoints} or | |
| * {@code ypoints} is {@code null}. | |
| * @since 1.0 | |
| */ | |
| public Polygon(int[] xpoints, int[] ypoints, int npoints) { | |
| // Fix 4489009: should throw IndexOutOfBoundsException instead | |
| // of OutOfMemoryError 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} 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} 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}. | |
| * This method should be called after any direct manipulation | |
| * of the coordinates in the {@code xpoints} or | |
| * {@code ypoints} arrays to avoid inconsistent results | |
| * from methods such as {@code getBounds} or {@code contains} | |
| * 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} by | |
| * {@code deltaX} along the x axis and by | |
| * {@code deltaY} 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} 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}. | |
| * <p> | |
| * If an operation that calculates the bounding box of this | |
| * {@code Polygon} has already been performed, such as | |
| * {@code getBounds} or {@code contains}, 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}. | |
| * 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}. | |
| * @return a {@code Rectangle} that defines the bounds of this | |
| * {@code Polygon}. | |
| * @since 1.1 | |
| */ | |
| public Rectangle getBounds() { | |
| return getBoundingBox(); | |
| } | |
| /** | |
| * Returns the bounds of this {@code Polygon}. | |
| * @return the bounds of this {@code Polygon}. | |
| * @deprecated As of JDK version 1.1, | |
| * replaced by {@code getBounds()}. | |
| * @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}. | |
| * @param p the specified {@code Point} to be tested | |
| * @return {@code true} if the {@code Polygon} contains the | |
| * {@code Point}; {@code false} 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}. | |
| * | |
| * @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}. | |
| * @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)}. | |
| * @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} and provides access to the geometry | |
| * of the outline of this {@code Polygon}. An optional | |
| * {@link AffineTransform} can be specified so that the coordinates | |
| * returned in the iteration are transformed accordingly. | |
| * @param at an optional {@code AffineTransform} to be applied to the | |
| * coordinates as they are returned in the iteration, or | |
| * {@code null} if untransformed coordinates are desired | |
| * @return a {@link PathIterator} object that provides access to the | |
| * geometry of this {@code Polygon}. | |
| * @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} and provides access to the geometry of the | |
| * outline of the {@code Shape}. Only SEG_MOVETO, SEG_LINETO, and | |
| * SEG_CLOSE point types are returned by the iterator. | |
| * Since polygons are already flat, the {@code flatness} parameter | |
| * is ignored. An optional {@code AffineTransform} can be specified | |
| * in which case the coordinates returned in the iteration are transformed | |
| * accordingly. | |
| * @param at an optional {@code AffineTransform} to be applied to the | |
| * coordinates as they are returned in the iteration, or | |
| * {@code null} if untransformed coordinates are desired | |
| * @param flatness the maximum amount that the control points | |
| * for a given curve can vary from collinear before a subdivided | |
| * curve is replaced by a straight line connecting the | |
| * endpoints. Since polygons are already flat the | |
| * {@code flatness} parameter is ignored. | |
| * @return a {@code PathIterator} object that provides access to the | |
| * {@code Shape} object's geometry. | |
| * @since 1.2 | |
| */ | |
| public PathIterator getPathIterator(AffineTransform at, double flatness) { | |
| return getPathIterator(at); | |
| } | |
| static 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} if there are more points to read; | |
| * {@code false} 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} 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} 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} 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} 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} 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} 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); | |
| } | |
| } | |
| } |