| Frames | No Frames |
1: /* Polygon.java -- class representing a polygon 2: Copyright (C) 1999, 2002, 2004, 2005 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package java.awt; 40: 41: import java.awt.geom.AffineTransform; 42: import java.awt.geom.Line2D; 43: import java.awt.geom.PathIterator; 44: import java.awt.geom.Point2D; 45: import java.awt.geom.Rectangle2D; 46: import java.io.Serializable; 47: 48: /** 49: * This class represents a polygon, a closed, two-dimensional region in a 50: * coordinate space. The region is bounded by an arbitrary number of line 51: * segments, between (x,y) coordinate vertices. The polygon has even-odd 52: * winding, meaning that a point is inside the shape if it crosses the 53: * boundary an odd number of times on the way to infinity. 54: * 55: * <p>There are some public fields; if you mess with them in an inconsistent 56: * manner, it is your own fault when you get NullPointerException, 57: * ArrayIndexOutOfBoundsException, or invalid results. Also, this class is 58: * not threadsafe. 59: * 60: * @author Aaron M. Renn (arenn@urbanophile.com) 61: * @author Eric Blake (ebb9@email.byu.edu) 62: * @since 1.0 63: * @status updated to 1.4 64: */ 65: public class Polygon implements Shape, Serializable 66: { 67: /** 68: * Compatible with JDK 1.0+. 69: */ 70: private static final long serialVersionUID = -6460061437900069969L; 71: 72: /** 73: * This total number of endpoints. 74: * 75: * @serial the number of endpoints, possibly less than the array sizes 76: */ 77: public int npoints; 78: 79: /** 80: * The array of X coordinates of endpoints. This should not be null. 81: * 82: * @see #addPoint(int, int) 83: * @serial the x coordinates 84: */ 85: public int[] xpoints; 86: 87: /** 88: * The array of Y coordinates of endpoints. This should not be null. 89: * 90: * @see #addPoint(int, int) 91: * @serial the y coordinates 92: */ 93: public int[] ypoints; 94: 95: /** 96: * The bounding box of this polygon. This is lazily created and cached, so 97: * it must be invalidated after changing points. 98: * 99: * @see #getBounds() 100: * @serial the bounding box, or null 101: */ 102: protected Rectangle bounds; 103: 104: /** A big number, but not so big it can't survive a few float operations */ 105: private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0; 106: 107: /** 108: * Initializes an empty polygon. 109: */ 110: public Polygon() 111: { 112: // Leave room for growth. 113: xpoints = new int[4]; 114: ypoints = new int[4]; 115: } 116: 117: /** 118: * Create a new polygon with the specified endpoints. The arrays are copied, 119: * so that future modifications to the parameters do not affect the polygon. 120: * 121: * @param xpoints the array of X coordinates for this polygon 122: * @param ypoints the array of Y coordinates for this polygon 123: * @param npoints the total number of endpoints in this polygon 124: * @throws NegativeArraySizeException if npoints is negative 125: * @throws IndexOutOfBoundsException if npoints exceeds either array 126: * @throws NullPointerException if xpoints or ypoints is null 127: */ 128: public Polygon(int[] xpoints, int[] ypoints, int npoints) 129: { 130: this.xpoints = new int[npoints]; 131: this.ypoints = new int[npoints]; 132: System.arraycopy(xpoints, 0, this.xpoints, 0, npoints); 133: System.arraycopy(ypoints, 0, this.ypoints, 0, npoints); 134: this.npoints = npoints; 135: } 136: 137: /** 138: * Reset the polygon to be empty. The arrays are left alone, to avoid object 139: * allocation, but the number of points is set to 0, and all cached data 140: * is discarded. If you are discarding a huge number of points, it may be 141: * more efficient to just create a new Polygon. 142: * 143: * @see #invalidate() 144: * @since 1.4 145: */ 146: public void reset() 147: { 148: npoints = 0; 149: invalidate(); 150: } 151: 152: /** 153: * Invalidate or flush all cached data. After direct manipulation of the 154: * public member fields, this is necessary to avoid inconsistent results 155: * in methods like <code>contains</code>. 156: * 157: * @see #getBounds() 158: * @since 1.4 159: */ 160: public void invalidate() 161: { 162: bounds = null; 163: } 164: 165: /** 166: * Translates the polygon by adding the specified values to all X and Y 167: * coordinates. This updates the bounding box, if it has been calculated. 168: * 169: * @param dx the amount to add to all X coordinates 170: * @param dy the amount to add to all Y coordinates 171: * @since 1.1 172: */ 173: public void translate(int dx, int dy) 174: { 175: int i = npoints; 176: while (--i >= 0) 177: { 178: xpoints[i] += dx; 179: ypoints[i] += dy; 180: } 181: if (bounds != null) 182: { 183: bounds.x += dx; 184: bounds.y += dy; 185: } 186: } 187: 188: /** 189: * Adds the specified endpoint to the polygon. This updates the bounding 190: * box, if it has been created. 191: * 192: * @param x the X coordinate of the point to add 193: * @param y the Y coordiante of the point to add 194: */ 195: public void addPoint(int x, int y) 196: { 197: if (npoints + 1 > xpoints.length) 198: { 199: int[] newx = new int[npoints + 1]; 200: System.arraycopy(xpoints, 0, newx, 0, npoints); 201: xpoints = newx; 202: } 203: if (npoints + 1 > ypoints.length) 204: { 205: int[] newy = new int[npoints + 1]; 206: System.arraycopy(ypoints, 0, newy, 0, npoints); 207: ypoints = newy; 208: } 209: xpoints[npoints] = x; 210: ypoints[npoints] = y; 211: npoints++; 212: if (bounds != null) 213: { 214: if (npoints == 1) 215: { 216: bounds.x = x; 217: bounds.y = y; 218: } 219: else 220: { 221: if (x < bounds.x) 222: { 223: bounds.width += bounds.x - x; 224: bounds.x = x; 225: } 226: else if (x > bounds.x + bounds.width) 227: bounds.width = x - bounds.x; 228: if (y < bounds.y) 229: { 230: bounds.height += bounds.y - y; 231: bounds.y = y; 232: } 233: else if (y > bounds.y + bounds.height) 234: bounds.height = y - bounds.y; 235: } 236: } 237: } 238: 239: /** 240: * Returns the bounding box of this polygon. This is the smallest 241: * rectangle with sides parallel to the X axis that will contain this 242: * polygon. 243: * 244: * @return the bounding box for this polygon 245: * @see #getBounds2D() 246: * @since 1.1 247: */ 248: public Rectangle getBounds() 249: { 250: return getBoundingBox(); 251: } 252: 253: /** 254: * Returns the bounding box of this polygon. This is the smallest 255: * rectangle with sides parallel to the X axis that will contain this 256: * polygon. 257: * 258: * @return the bounding box for this polygon 259: * @see #getBounds2D() 260: * @deprecated use {@link #getBounds()} instead 261: */ 262: public Rectangle getBoundingBox() 263: { 264: if (bounds == null) 265: { 266: if (npoints == 0) 267: return bounds = new Rectangle(); 268: int i = npoints - 1; 269: int minx = xpoints[i]; 270: int maxx = minx; 271: int miny = ypoints[i]; 272: int maxy = miny; 273: while (--i >= 0) 274: { 275: int x = xpoints[i]; 276: int y = ypoints[i]; 277: if (x < minx) 278: minx = x; 279: else if (x > maxx) 280: maxx = x; 281: if (y < miny) 282: miny = y; 283: else if (y > maxy) 284: maxy = y; 285: } 286: bounds = new Rectangle(minx, miny, maxx - minx, maxy - miny); 287: } 288: return bounds; 289: } 290: 291: /** 292: * Tests whether or not the specified point is inside this polygon. 293: * 294: * @param p the point to test 295: * @return true if the point is inside this polygon 296: * @throws NullPointerException if p is null 297: * @see #contains(double, double) 298: */ 299: public boolean contains(Point p) 300: { 301: return contains(p.getX(), p.getY()); 302: } 303: 304: /** 305: * Tests whether or not the specified point is inside this polygon. 306: * 307: * @param x the X coordinate of the point to test 308: * @param y the Y coordinate of the point to test 309: * @return true if the point is inside this polygon 310: * @see #contains(double, double) 311: * @since 1.1 312: */ 313: public boolean contains(int x, int y) 314: { 315: return contains((double) x, (double) y); 316: } 317: 318: /** 319: * Tests whether or not the specified point is inside this polygon. 320: * 321: * @param x the X coordinate of the point to test 322: * @param y the Y coordinate of the point to test 323: * @return true if the point is inside this polygon 324: * @see #contains(double, double) 325: * @deprecated use {@link #contains(int, int)} instead 326: */ 327: public boolean inside(int x, int y) 328: { 329: return contains((double) x, (double) y); 330: } 331: 332: /** 333: * Returns a high-precision bounding box of this polygon. This is the 334: * smallest rectangle with sides parallel to the X axis that will contain 335: * this polygon. 336: * 337: * @return the bounding box for this polygon 338: * @see #getBounds() 339: * @since 1.2 340: */ 341: public Rectangle2D getBounds2D() 342: { 343: // For polygons, the integer version is exact! 344: return getBounds(); 345: } 346: 347: /** 348: * Tests whether or not the specified point is inside this polygon. 349: * 350: * @param x the X coordinate of the point to test 351: * @param y the Y coordinate of the point to test 352: * @return true if the point is inside this polygon 353: * @since 1.2 354: */ 355: public boolean contains(double x, double y) 356: { 357: return ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0); 358: } 359: 360: /** 361: * Tests whether or not the specified point is inside this polygon. 362: * 363: * @param p the point to test 364: * @return true if the point is inside this polygon 365: * @throws NullPointerException if p is null 366: * @see #contains(double, double) 367: * @since 1.2 368: */ 369: public boolean contains(Point2D p) 370: { 371: return contains(p.getX(), p.getY()); 372: } 373: 374: /** 375: * Test if a high-precision rectangle intersects the shape. This is true 376: * if any point in the rectangle is in the shape. This implementation is 377: * precise. 378: * 379: * @param x the x coordinate of the rectangle 380: * @param y the y coordinate of the rectangle 381: * @param w the width of the rectangle, treated as point if negative 382: * @param h the height of the rectangle, treated as point if negative 383: * @return true if the rectangle intersects this shape 384: * @since 1.2 385: */ 386: public boolean intersects(double x, double y, double w, double h) 387: { 388: /* Does any edge intersect? */ 389: if (evaluateCrossings(x, y, false, w) != 0 /* top */ 390: || evaluateCrossings(x, y + h, false, w) != 0 /* bottom */ 391: || evaluateCrossings(x + w, y, true, h) != 0 /* right */ 392: || evaluateCrossings(x, y, true, h) != 0) /* left */ 393: return true; 394: 395: /* No intersections, is any point inside? */ 396: if ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0) 397: return true; 398: 399: return false; 400: } 401: 402: /** 403: * Test if a high-precision rectangle intersects the shape. This is true 404: * if any point in the rectangle is in the shape. This implementation is 405: * precise. 406: * 407: * @param r the rectangle 408: * @return true if the rectangle intersects this shape 409: * @throws NullPointerException if r is null 410: * @see #intersects(double, double, double, double) 411: * @since 1.2 412: */ 413: public boolean intersects(Rectangle2D r) 414: { 415: return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 416: } 417: 418: /** 419: * Test if a high-precision rectangle lies completely in the shape. This is 420: * true if all points in the rectangle are in the shape. This implementation 421: * is precise. 422: * 423: * @param x the x coordinate of the rectangle 424: * @param y the y coordinate of the rectangle 425: * @param w the width of the rectangle, treated as point if negative 426: * @param h the height of the rectangle, treated as point if negative 427: * @return true if the rectangle is contained in this shape 428: * @since 1.2 429: */ 430: public boolean contains(double x, double y, double w, double h) 431: { 432: if (! getBounds2D().intersects(x, y, w, h)) 433: return false; 434: 435: /* Does any edge intersect? */ 436: if (evaluateCrossings(x, y, false, w) != 0 /* top */ 437: || evaluateCrossings(x, y + h, false, w) != 0 /* bottom */ 438: || evaluateCrossings(x + w, y, true, h) != 0 /* right */ 439: || evaluateCrossings(x, y, true, h) != 0) /* left */ 440: return false; 441: 442: /* No intersections, is any point inside? */ 443: if ((evaluateCrossings(x, y, false, BIG_VALUE) & 1) != 0) 444: return true; 445: 446: return false; 447: } 448: 449: /** 450: * Test if a high-precision rectangle lies completely in the shape. This is 451: * true if all points in the rectangle are in the shape. This implementation 452: * is precise. 453: * 454: * @param r the rectangle 455: * @return true if the rectangle is contained in this shape 456: * @throws NullPointerException if r is null 457: * @see #contains(double, double, double, double) 458: * @since 1.2 459: */ 460: public boolean contains(Rectangle2D r) 461: { 462: return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 463: } 464: 465: /** 466: * Return an iterator along the shape boundary. If the optional transform 467: * is provided, the iterator is transformed accordingly. Each call returns 468: * a new object, independent from others in use. This class is not 469: * threadsafe to begin with, so the path iterator is not either. 470: * 471: * @param transform an optional transform to apply to the iterator 472: * @return a new iterator over the boundary 473: * @since 1.2 474: */ 475: public PathIterator getPathIterator(final AffineTransform transform) 476: { 477: return new PathIterator() 478: { 479: /** The current vertex of iteration. */ 480: private int vertex; 481: 482: public int getWindingRule() 483: { 484: return WIND_EVEN_ODD; 485: } 486: 487: public boolean isDone() 488: { 489: return vertex > npoints; 490: } 491: 492: public void next() 493: { 494: vertex++; 495: } 496: 497: public int currentSegment(float[] coords) 498: { 499: if (vertex >= npoints) 500: return SEG_CLOSE; 501: coords[0] = xpoints[vertex]; 502: coords[1] = ypoints[vertex]; 503: if (transform != null) 504: transform.transform(coords, 0, coords, 0, 1); 505: return vertex == 0 ? SEG_MOVETO : SEG_LINETO; 506: } 507: 508: public int currentSegment(double[] coords) 509: { 510: if (vertex >= npoints) 511: return SEG_CLOSE; 512: coords[0] = xpoints[vertex]; 513: coords[1] = ypoints[vertex]; 514: if (transform != null) 515: transform.transform(coords, 0, coords, 0, 1); 516: return vertex == 0 ? SEG_MOVETO : SEG_LINETO; 517: } 518: }; 519: } 520: 521: /** 522: * Return an iterator along the flattened version of the shape boundary. 523: * Since polygons are already flat, the flatness parameter is ignored, and 524: * the resulting iterator only has SEG_MOVETO, SEG_LINETO and SEG_CLOSE 525: * points. If the optional transform is provided, the iterator is 526: * transformed accordingly. Each call returns a new object, independent 527: * from others in use. This class is not threadsafe to begin with, so the 528: * path iterator is not either. 529: * 530: * @param transform an optional transform to apply to the iterator 531: * @param flatness the maximum distance for deviation from the real boundary 532: * @return a new iterator over the boundary 533: * @since 1.2 534: */ 535: public PathIterator getPathIterator(AffineTransform transform, 536: double flatness) 537: { 538: return getPathIterator(transform); 539: } 540: 541: /** 542: * Helper for contains, intersects, calculates the number of intersections 543: * between the polygon and a line extending from the point (x, y) along 544: * the positive X, or Y axis, within a given interval. 545: * 546: * @return the winding number. 547: * @see #contains(double, double) 548: */ 549: private int evaluateCrossings(double x, double y, boolean useYaxis, 550: double distance) 551: { 552: double x0; 553: double x1; 554: double y0; 555: double y1; 556: double epsilon = 0.0; 557: int crossings = 0; 558: int[] xp; 559: int[] yp; 560: 561: if (useYaxis) 562: { 563: xp = ypoints; 564: yp = xpoints; 565: double swap; 566: swap = y; 567: y = x; 568: x = swap; 569: } 570: else 571: { 572: xp = xpoints; 573: yp = ypoints; 574: } 575: 576: /* Get a value which is small but not insignificant relative the path. */ 577: epsilon = 1E-7; 578: 579: x0 = xp[0] - x; 580: y0 = yp[0] - y; 581: for (int i = 1; i < npoints; i++) 582: { 583: x1 = xp[i] - x; 584: y1 = yp[i] - y; 585: 586: if (y0 == 0.0) 587: y0 -= epsilon; 588: if (y1 == 0.0) 589: y1 -= epsilon; 590: if (y0 * y1 < 0) 591: if (Line2D.linesIntersect(x0, y0, x1, y1, epsilon, 0.0, distance, 0.0)) 592: ++crossings; 593: 594: x0 = xp[i] - x; 595: y0 = yp[i] - y; 596: } 597: 598: // end segment 599: x1 = xp[0] - x; 600: y1 = yp[0] - y; 601: if (y0 == 0.0) 602: y0 -= epsilon; 603: if (y1 == 0.0) 604: y1 -= epsilon; 605: if (y0 * y1 < 0) 606: if (Line2D.linesIntersect(x0, y0, x1, y1, epsilon, 0.0, distance, 0.0)) 607: ++crossings; 608: 609: return crossings; 610: } 611: } // class Polygon