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 */ Polygon()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 */ Polygon(int[] xpoints, int[] ypoints, int npoints)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 */ reset()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 */ invalidate()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 */ translate(int dx, int dy)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 */ addPoint(int x, int y)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 */ getBounds()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 */ getBoundingBox()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 */ contains(Point p)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 */ contains(int x, int y)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 */ inside(int x, int y)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 */ getBounds2D()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 */ contains(double x, double y)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 */ contains(Point2D p)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 */ intersects(double x, double y, double w, double h)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 */ intersects(Rectangle2D r)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 */ contains(double x, double y, double w, double h)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 */ contains(Rectangle2D r)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 */ getPathIterator(final AffineTransform transform)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 */ getPathIterator(AffineTransform transform, double flatness)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 */ evaluateCrossings(double x, double y, boolean useYaxis, double distance)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 612