001: /*
002: * @(#)Polygon.java 1.15 06/10/10
003: *
004: * Copyright 1990-2006 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: *
026: */
027: package java.awt;
028:
029: /**
030: * The <code>Polygon</code> class encapsulates a description of a
031: * closed, two-dimensional region within a coordinate space. This
032: * region is bounded by an arbitrary number of line segments, each of
033: * which is one side of the polygon. Internally, a polygon
034: * comprises of a list of (<i>x</i>, <i>y</i>) coordinate pairs,
035: * where each pair defines a <i>vertex</i> of the polygon, and two
036: * successive pairs are the endpoints of a line that is a side of the
037: * polygon. The first and final pairs of (<i>x</i>, <i>y</i>)
038: * points are joined by a line segment that closes the polygon.
039: *
040: * @version 1.18, 07/01/98
041: * @author Sami Shaio
042: * @author Herb Jellinek
043: * @since JDK1.0
044: */
045: public class Polygon implements Shape, java.io.Serializable {
046: /**
047: * The total number of points.
048: * @since JDK1.0
049: */
050: public int npoints = 0;
051: /**
052: * The array of <i>x</i> coordinates.
053: * @since JDK1.0
054: */
055: public int xpoints[] = new int[4];
056: /**
057: * The array of <i>y</i> coordinates.
058: * @since JDK1.0
059: */
060: public int ypoints[] = new int[4];
061: /*
062: * Bounds of the polygon.
063: */
064: protected Rectangle bounds = null;
065: /*
066: * JDK 1.1 serialVersionUID
067: */
068: private static final long serialVersionUID = -6460061437900069969L;
069:
070: /**
071: * Creates an empty polygon.
072: * @since JDK1.0
073: */
074: public Polygon() {
075: }
076:
077: /**
078: * Constructs and initializes a polygon from the specified
079: * parameters.
080: * @param xpoints an array of <i>x</i> coordinates.
081: * @param ypoints an array of <i>y</i> coordinates.
082: * @param npoints the total number of points in the polygon.
083: * @exception NegativeArraySizeException if the value of
084: * <code>npoints</code> is negative.
085: * @since JDK1.0
086: */
087: public Polygon(int xpoints[], int ypoints[], int npoints) {
088: // J2SDK 1.4 Fix 4489009: should throw IndexOutofBoundsException instead
089: // of OutofMemoryException if npoints is huge and > {x,y}points.length
090: // Compliant with Personal Basis Profile Specification.
091: if (npoints > xpoints.length || npoints > ypoints.length) {
092: throw new IndexOutOfBoundsException(
093: "npoints > xpoints.length || npoints > ypoints.length");
094: }
095: this .npoints = npoints;
096: this .xpoints = new int[npoints];
097: this .ypoints = new int[npoints];
098: System.arraycopy(xpoints, 0, this .xpoints, 0, npoints);
099: System.arraycopy(ypoints, 0, this .ypoints, 0, npoints);
100: }
101:
102: /**
103: * Resets this <code>Polygon</code> object to an empty polygon.
104: * The coordinate arrays and the data in them are left untouched
105: * but the number of points is reset to zero to mark the old
106: * vertex data as invalid and to start accumulating new vertex
107: * data at the beginning.
108: * All internally-cached data relating to the old vertices
109: * are discarded.
110: * Note that since the coordinate arrays from before the reset
111: * are reused, creating a new empty <code>Polygon</code> might
112: * be more memory efficient than resetting the current one if
113: * the number of vertices in the new polygon data is significantly
114: * smaller than the number of vertices in the data from before the
115: * reset.
116: * @see java.awt.Polygon#invalidate
117: * @since 1.4
118: */
119: public void reset() {
120: npoints = 0;
121: bounds = null;
122: }
123:
124: /**
125: * Invalidates or flushes any internally-cached data that depends
126: * on the vertex coordinates of this <code>Polygon</code>.
127: * This method should be called after any direct manipulation
128: * of the coordinates in the <code>xpoints</code> or
129: * <code>ypoints</code> arrays to avoid inconsistent results
130: * from methods such as <code>getBounds</code> or <code>contains</code>
131: * that might cache data from earlier computations relating to
132: * the vertex coordinates.
133: * @see java.awt.Polygon#getBounds
134: * @since 1.4
135: */
136: public void invalidate() {
137: bounds = null;
138: }
139:
140: /**
141: * Translates the vertices by <code>deltaX</code> along the
142: * <i>x</i> axis and by <code>deltaY</code> along the
143: * <i>y</i> axis.
144: * @param deltaX the amount to translate along the <i>x</i> axis
145: * @param deltaY the amount to translate along the <i>y</i> axis
146: * @since JDK1.1
147: */
148: public void translate(int deltaX, int deltaY) {
149: for (int i = 0; i < npoints; i++) {
150: xpoints[i] += deltaX;
151: ypoints[i] += deltaY;
152: }
153: if (bounds != null) {
154: bounds.translate(deltaX, deltaY);
155: }
156: }
157:
158: /*
159: * Calculate the bounding box of the points passed to the constructor.
160: * Sets 'bounds' to the result.
161: */
162: void calculateBounds(int xpoints[], int ypoints[], int npoints) {
163: int boundsMinX = Integer.MAX_VALUE;
164: int boundsMinY = Integer.MAX_VALUE;
165: int boundsMaxX = Integer.MIN_VALUE;
166: int boundsMaxY = Integer.MIN_VALUE;
167: for (int i = 0; i < npoints; i++) {
168: int x = xpoints[i];
169: boundsMinX = Math.min(boundsMinX, x);
170: boundsMaxX = Math.max(boundsMaxX, x);
171: int y = ypoints[i];
172: boundsMinY = Math.min(boundsMinY, y);
173: boundsMaxY = Math.max(boundsMaxY, y);
174: }
175: bounds = new Rectangle(boundsMinX, boundsMinY, boundsMaxX
176: - boundsMinX, boundsMaxY - boundsMinY);
177: }
178:
179: /*
180: * Update the bounding box to fit the point x, y.
181: */
182: void updateBounds(int x, int y) {
183: if (x < bounds.x) {
184: bounds.width = bounds.width + (bounds.x - x);
185: bounds.x = x;
186: } else {
187: bounds.width = Math.max(bounds.width, x - bounds.x);
188: // bounds.x = bounds.x;
189: }
190: if (y < bounds.y) {
191: bounds.height = bounds.height + (bounds.y - y);
192: bounds.y = y;
193: } else {
194: bounds.height = Math.max(bounds.height, y - bounds.y);
195: // bounds.y = bounds.y;
196: }
197: }
198:
199: /**
200: * Appends a point to this polygon.
201: * <p>
202: * If an operation that calculates the bounding box of this polygon
203: * has already been performed, such as <code>getBounds</code>
204: * or <code>contains</code>, then this method updates the bounding box.
205: * @param x the <i>x</i> coordinate of the point.
206: * @param y the <i>y</i> coordinate of the point.
207: * @see java.awt.Polygon#getBounds
208: * @see java.awt.Polygon#contains
209: * @since JDK1.0
210: */
211: public void addPoint(int x, int y) {
212: if (npoints == xpoints.length) {
213: int tmp[];
214: tmp = new int[npoints * 2];
215: System.arraycopy(xpoints, 0, tmp, 0, npoints);
216: xpoints = tmp;
217: tmp = new int[npoints * 2];
218: System.arraycopy(ypoints, 0, tmp, 0, npoints);
219: ypoints = tmp;
220: }
221: xpoints[npoints] = x;
222: ypoints[npoints] = y;
223: npoints++;
224: if (bounds != null) {
225: updateBounds(x, y);
226: }
227: }
228:
229: /**
230: * Gets the bounding box of this polygon. The bounding box is the
231: * smallest rectangle whose sides are parallel to the <i>x</i> and
232: * <i>y</i> axes of the coordinate space, and that can completely
233: * contain the polygon.
234: * @return a rectangle that defines the bounds of this polygon.
235: * @since JDK1.1
236: */
237: public Rectangle getBounds() {
238: return getBoundingBox();
239: }
240:
241: /**
242: * @deprecated As of JDK version 1.1,
243: * replaced by <code>getBounds()</code>.
244: */
245: public Rectangle getBoundingBox() {
246: if (npoints == 0) {
247: return new Rectangle();
248: }
249: if (bounds == null) {
250: calculateBounds(xpoints, ypoints, npoints);
251: }
252: return bounds;
253: }
254:
255: /**
256: * Determines whether the specified point is inside the Polygon.
257: * Uses an even-odd insideness rule (also known as an alternating
258: * rule).
259: * @param p the point to be tested
260: */
261: public boolean contains(Point p) {
262: return contains(p.x, p.y);
263: }
264:
265: /**
266: * Determines whether the specified point is contained by this polygon.
267: * @param x the <i>x</i> coordinate of the point to be tested.
268: * @param y the <i>y</i> coordinate of the point to be tested.
269: * @return <code>true</code> if the point (<i>x</i>, <i>y</i>)
270: * is contained by this polygon;
271: * <code>false</code> otherwise.
272: * @since JDK1.1
273: */
274: public boolean contains(int x, int y) {
275: return contains((double) x, (double) y);
276: }
277:
278: /**
279: * @deprecated As of JDK version 1.1,
280: * replaced by <code>contains(int, int)</code>.
281: */
282: public boolean inside(int x, int y) {
283: return contains((double) x, (double) y);
284: }
285:
286: private boolean contains(double x, double y) {
287: if (npoints <= 2 || !getBoundingBox().contains(x, y)) {
288: return false;
289: }
290: int hits = 0;
291: int lastx = xpoints[npoints - 1];
292: int lasty = ypoints[npoints - 1];
293: int curx, cury;
294: // Walk the edges of the polygon
295: for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) {
296: curx = xpoints[i];
297: cury = ypoints[i];
298: if (cury == lasty) {
299: continue;
300: }
301: int leftx;
302: if (curx < lastx) {
303: if (x >= lastx) {
304: continue;
305: }
306: leftx = curx;
307: } else {
308: if (x >= curx) {
309: continue;
310: }
311: leftx = lastx;
312: }
313: double test1, test2;
314: if (cury < lasty) {
315: if (y < cury || y >= lasty) {
316: continue;
317: }
318: if (x < leftx) {
319: hits++;
320: continue;
321: }
322: test1 = x - curx;
323: test2 = y - cury;
324: } else {
325: if (y < lasty || y >= cury) {
326: continue;
327: }
328: if (x < leftx) {
329: hits++;
330: continue;
331: }
332: test1 = x - lastx;
333: test2 = y - lasty;
334: }
335: if (test1 < (test2 / (lasty - cury) * (lastx - curx))) {
336: hits++;
337: }
338: }
339: return ((hits & 1) != 0);
340: }
341: }
|