1/* 2 * Copyright (c) 1995, 2014, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25package java.awt; 26 27import java.awt.geom.AffineTransform; 28import java.awt.geom.PathIterator; 29import java.awt.geom.Point2D; 30import java.awt.geom.Rectangle2D; 31import sun.awt.geom.Crossings; 32import java.util.Arrays; 33 34/** 35 * The {@code Polygon} class encapsulates a description of a 36 * closed, two-dimensional region within a coordinate space. This 37 * region is bounded by an arbitrary number of line segments, each of 38 * which is one side of the polygon. Internally, a polygon 39 * comprises of a list of {@code (x,y)} 40 * coordinate pairs, where each pair defines a <i>vertex</i> of the 41 * polygon, and two successive pairs are the endpoints of a 42 * line that is a side of the polygon. The first and final 43 * pairs of {@code (x,y)} points are joined by a line segment 44 * that closes the polygon. This {@code Polygon} is defined with 45 * an even-odd winding rule. See 46 * {@link java.awt.geom.PathIterator#WIND_EVEN_ODD WIND_EVEN_ODD} 47 * for a definition of the even-odd winding rule. 48 * This class's hit-testing methods, which include the 49 * {@code contains}, {@code intersects} and {@code inside} 50 * methods, use the <i>insideness</i> definition described in the 51 * {@link Shape} class comments. 52 * 53 * @author Sami Shaio 54 * @see Shape 55 * @author Herb Jellinek 56 * @since 1.0 57 */ 58public class Polygon implements Shape, java.io.Serializable { 59 60 /** 61 * The total number of points. The value of {@code npoints} 62 * represents the number of valid points in this {@code Polygon} 63 * and might be less than the number of elements in 64 * {@link #xpoints xpoints} or {@link #ypoints ypoints}. 65 * This value can be NULL. 66 * 67 * @serial 68 * @see #addPoint(int, int) 69 * @since 1.0 70 */ 71 public int npoints; 72 73 /** 74 * The array of X coordinates. The number of elements in 75 * this array might be more than the number of X coordinates 76 * in this {@code Polygon}. The extra elements allow new points 77 * to be added to this {@code Polygon} without re-creating this 78 * array. The value of {@link #npoints npoints} is equal to the 79 * number of valid points in this {@code Polygon}. 80 * 81 * @serial 82 * @see #addPoint(int, int) 83 * @since 1.0 84 */ 85 public int xpoints[]; 86 87 /** 88 * The array of Y coordinates. The number of elements in 89 * this array might be more than the number of Y coordinates 90 * in this {@code Polygon}. The extra elements allow new points 91 * to be added to this {@code Polygon} without re-creating this 92 * array. The value of {@code npoints} is equal to the 93 * number of valid points in this {@code Polygon}. 94 * 95 * @serial 96 * @see #addPoint(int, int) 97 * @since 1.0 98 */ 99 public int ypoints[]; 100 101 /** 102 * The bounds of this {@code Polygon}. 103 * This value can be null. 104 * 105 * @serial 106 * @see #getBoundingBox() 107 * @see #getBounds() 108 * @since 1.0 109 */ 110 protected Rectangle bounds; 111 112 /* 113 * JDK 1.1 serialVersionUID 114 */ 115 private static final long serialVersionUID = -6460061437900069969L; 116 117 /* 118 * Default length for xpoints and ypoints. 119 */ 120 private static final int MIN_LENGTH = 4; 121 122 /** 123 * Creates an empty polygon. 124 * @since 1.0 125 */ 126 public Polygon() { 127 xpoints = new int[MIN_LENGTH]; 128 ypoints = new int[MIN_LENGTH]; 129 } 130 131 /** 132 * Constructs and initializes a {@code Polygon} from the specified 133 * parameters. 134 * @param xpoints an array of X coordinates 135 * @param ypoints an array of Y coordinates 136 * @param npoints the total number of points in the 137 * {@code Polygon} 138 * @exception NegativeArraySizeException if the value of 139 * {@code npoints} is negative. 140 * @exception IndexOutOfBoundsException if {@code npoints} is 141 * greater than the length of {@code xpoints} 142 * or the length of {@code ypoints}. 143 * @exception NullPointerException if {@code xpoints} or 144 * {@code ypoints} is {@code null}. 145 * @since 1.0 146 */ 147 public Polygon(int xpoints[], int ypoints[], int npoints) { 148 // Fix 4489009: should throw IndexOutOfBoundsException instead 149 // of OutOfMemoryError if npoints is huge and > {x,y}points.length 150 if (npoints > xpoints.length || npoints > ypoints.length) { 151 throw new IndexOutOfBoundsException("npoints > xpoints.length || "+ 152 "npoints > ypoints.length"); 153 } 154 // Fix 6191114: should throw NegativeArraySizeException with 155 // negative npoints 156 if (npoints < 0) { 157 throw new NegativeArraySizeException("npoints < 0"); 158 } 159 // Fix 6343431: Applet compatibility problems if arrays are not 160 // exactly npoints in length 161 this.npoints = npoints; 162 this.xpoints = Arrays.copyOf(xpoints, npoints); 163 this.ypoints = Arrays.copyOf(ypoints, npoints); 164 } 165 166 /** 167 * Resets this {@code Polygon} object to an empty polygon. 168 * The coordinate arrays and the data in them are left untouched 169 * but the number of points is reset to zero to mark the old 170 * vertex data as invalid and to start accumulating new vertex 171 * data at the beginning. 172 * All internally-cached data relating to the old vertices 173 * are discarded. 174 * Note that since the coordinate arrays from before the reset 175 * are reused, creating a new empty {@code Polygon} might 176 * be more memory efficient than resetting the current one if 177 * the number of vertices in the new polygon data is significantly 178 * smaller than the number of vertices in the data from before the 179 * reset. 180 * @see java.awt.Polygon#invalidate 181 * @since 1.4 182 */ 183 public void reset() { 184 npoints = 0; 185 bounds = null; 186 } 187 188 /** 189 * Invalidates or flushes any internally-cached data that depends 190 * on the vertex coordinates of this {@code Polygon}. 191 * This method should be called after any direct manipulation 192 * of the coordinates in the {@code xpoints} or 193 * {@code ypoints} arrays to avoid inconsistent results 194 * from methods such as {@code getBounds} or {@code contains} 195 * that might cache data from earlier computations relating to 196 * the vertex coordinates. 197 * @see java.awt.Polygon#getBounds 198 * @since 1.4 199 */ 200 public void invalidate() { 201 bounds = null; 202 } 203 204 /** 205 * Translates the vertices of the {@code Polygon} by 206 * {@code deltaX} along the x axis and by 207 * {@code deltaY} along the y axis. 208 * @param deltaX the amount to translate along the X axis 209 * @param deltaY the amount to translate along the Y axis 210 * @since 1.1 211 */ 212 public void translate(int deltaX, int deltaY) { 213 for (int i = 0; i < npoints; i++) { 214 xpoints[i] += deltaX; 215 ypoints[i] += deltaY; 216 } 217 if (bounds != null) { 218 bounds.translate(deltaX, deltaY); 219 } 220 } 221 222 /* 223 * Calculates the bounding box of the points passed to the constructor. 224 * Sets {@code bounds} to the result. 225 * @param xpoints[] array of <i>x</i> coordinates 226 * @param ypoints[] array of <i>y</i> coordinates 227 * @param npoints the total number of points 228 */ 229 void calculateBounds(int xpoints[], int ypoints[], int npoints) { 230 int boundsMinX = Integer.MAX_VALUE; 231 int boundsMinY = Integer.MAX_VALUE; 232 int boundsMaxX = Integer.MIN_VALUE; 233 int boundsMaxY = Integer.MIN_VALUE; 234 235 for (int i = 0; i < npoints; i++) { 236 int x = xpoints[i]; 237 boundsMinX = Math.min(boundsMinX, x); 238 boundsMaxX = Math.max(boundsMaxX, x); 239 int y = ypoints[i]; 240 boundsMinY = Math.min(boundsMinY, y); 241 boundsMaxY = Math.max(boundsMaxY, y); 242 } 243 bounds = new Rectangle(boundsMinX, boundsMinY, 244 boundsMaxX - boundsMinX, 245 boundsMaxY - boundsMinY); 246 } 247 248 /* 249 * Resizes the bounding box to accommodate the specified coordinates. 250 * @param x, y the specified coordinates 251 */ 252 void updateBounds(int x, int y) { 253 if (x < bounds.x) { 254 bounds.width = bounds.width + (bounds.x - x); 255 bounds.x = x; 256 } 257 else { 258 bounds.width = Math.max(bounds.width, x - bounds.x); 259 // bounds.x = bounds.x; 260 } 261 262 if (y < bounds.y) { 263 bounds.height = bounds.height + (bounds.y - y); 264 bounds.y = y; 265 } 266 else { 267 bounds.height = Math.max(bounds.height, y - bounds.y); 268 // bounds.y = bounds.y; 269 } 270 } 271 272 /** 273 * Appends the specified coordinates to this {@code Polygon}. 274 * <p> 275 * If an operation that calculates the bounding box of this 276 * {@code Polygon} has already been performed, such as 277 * {@code getBounds} or {@code contains}, then this 278 * method updates the bounding box. 279 * @param x the specified X coordinate 280 * @param y the specified Y coordinate 281 * @see java.awt.Polygon#getBounds 282 * @see java.awt.Polygon#contains 283 * @since 1.0 284 */ 285 public void addPoint(int x, int y) { 286 if (npoints >= xpoints.length || npoints >= ypoints.length) { 287 int newLength = npoints * 2; 288 // Make sure that newLength will be greater than MIN_LENGTH and 289 // aligned to the power of 2 290 if (newLength < MIN_LENGTH) { 291 newLength = MIN_LENGTH; 292 } else if ((newLength & (newLength - 1)) != 0) { 293 newLength = Integer.highestOneBit(newLength); 294 } 295 296 xpoints = Arrays.copyOf(xpoints, newLength); 297 ypoints = Arrays.copyOf(ypoints, newLength); 298 } 299 xpoints[npoints] = x; 300 ypoints[npoints] = y; 301 npoints++; 302 if (bounds != null) { 303 updateBounds(x, y); 304 } 305 } 306 307 /** 308 * Gets the bounding box of this {@code Polygon}. 309 * The bounding box is the smallest {@link Rectangle} whose 310 * sides are parallel to the x and y axes of the 311 * coordinate space, and can completely contain the {@code Polygon}. 312 * @return a {@code Rectangle} that defines the bounds of this 313 * {@code Polygon}. 314 * @since 1.1 315 */ 316 public Rectangle getBounds() { 317 return getBoundingBox(); 318 } 319 320 /** 321 * Returns the bounds of this {@code Polygon}. 322 * @return the bounds of this {@code Polygon}. 323 * @deprecated As of JDK version 1.1, 324 * replaced by {@code getBounds()}. 325 * @since 1.0 326 */ 327 @Deprecated 328 public Rectangle getBoundingBox() { 329 if (npoints == 0) { 330 return new Rectangle(); 331 } 332 if (bounds == null) { 333 calculateBounds(xpoints, ypoints, npoints); 334 } 335 return bounds.getBounds(); 336 } 337 338 /** 339 * Determines whether the specified {@link Point} is inside this 340 * {@code Polygon}. 341 * @param p the specified {@code Point} to be tested 342 * @return {@code true} if the {@code Polygon} contains the 343 * {@code Point}; {@code false} otherwise. 344 * @see #contains(double, double) 345 * @since 1.0 346 */ 347 public boolean contains(Point p) { 348 return contains(p.x, p.y); 349 } 350 351 /** 352 * Determines whether the specified coordinates are inside this 353 * {@code Polygon}. 354 * 355 * @param x the specified X coordinate to be tested 356 * @param y the specified Y coordinate to be tested 357 * @return {@code true} if this {@code Polygon} contains 358 * the specified coordinates {@code (x,y)}; 359 * {@code false} otherwise. 360 * @see #contains(double, double) 361 * @since 1.1 362 */ 363 public boolean contains(int x, int y) { 364 return contains((double) x, (double) y); 365 } 366 367 /** 368 * Determines whether the specified coordinates are contained in this 369 * {@code Polygon}. 370 * @param x the specified X coordinate to be tested 371 * @param y the specified Y coordinate to be tested 372 * @return {@code true} if this {@code Polygon} contains 373 * the specified coordinates {@code (x,y)}; 374 * {@code false} otherwise. 375 * @see #contains(double, double) 376 * @deprecated As of JDK version 1.1, 377 * replaced by {@code contains(int, int)}. 378 * @since 1.0 379 */ 380 @Deprecated 381 public boolean inside(int x, int y) { 382 return contains((double) x, (double) y); 383 } 384 385 /** 386 * {@inheritDoc} 387 * @since 1.2 388 */ 389 public Rectangle2D getBounds2D() { 390 return getBounds(); 391 } 392 393 /** 394 * {@inheritDoc} 395 * @since 1.2 396 */ 397 public boolean contains(double x, double y) { 398 if (npoints <= 2 || !getBoundingBox().contains(x, y)) { 399 return false; 400 } 401 int hits = 0; 402 403 int lastx = xpoints[npoints - 1]; 404 int lasty = ypoints[npoints - 1]; 405 int curx, cury; 406 407 // Walk the edges of the polygon 408 for (int i = 0; i < npoints; lastx = curx, lasty = cury, i++) { 409 curx = xpoints[i]; 410 cury = ypoints[i]; 411 412 if (cury == lasty) { 413 continue; 414 } 415 416 int leftx; 417 if (curx < lastx) { 418 if (x >= lastx) { 419 continue; 420 } 421 leftx = curx; 422 } else { 423 if (x >= curx) { 424 continue; 425 } 426 leftx = lastx; 427 } 428 429 double test1, test2; 430 if (cury < lasty) { 431 if (y < cury || y >= lasty) { 432 continue; 433 } 434 if (x < leftx) { 435 hits++; 436 continue; 437 } 438 test1 = x - curx; 439 test2 = y - cury; 440 } else { 441 if (y < lasty || y >= cury) { 442 continue; 443 } 444 if (x < leftx) { 445 hits++; 446 continue; 447 } 448 test1 = x - lastx; 449 test2 = y - lasty; 450 } 451 452 if (test1 < (test2 / (lasty - cury) * (lastx - curx))) { 453 hits++; 454 } 455 } 456 457 return ((hits & 1) != 0); 458 } 459 460 private Crossings getCrossings(double xlo, double ylo, 461 double xhi, double yhi) 462 { 463 Crossings cross = new Crossings.EvenOdd(xlo, ylo, xhi, yhi); 464 int lastx = xpoints[npoints - 1]; 465 int lasty = ypoints[npoints - 1]; 466 int curx, cury; 467 468 // Walk the edges of the polygon 469 for (int i = 0; i < npoints; i++) { 470 curx = xpoints[i]; 471 cury = ypoints[i]; 472 if (cross.accumulateLine(lastx, lasty, curx, cury)) { 473 return null; 474 } 475 lastx = curx; 476 lasty = cury; 477 } 478 479 return cross; 480 } 481 482 /** 483 * {@inheritDoc} 484 * @since 1.2 485 */ 486 public boolean contains(Point2D p) { 487 return contains(p.getX(), p.getY()); 488 } 489 490 /** 491 * {@inheritDoc} 492 * @since 1.2 493 */ 494 public boolean intersects(double x, double y, double w, double h) { 495 if (npoints <= 0 || !getBoundingBox().intersects(x, y, w, h)) { 496 return false; 497 } 498 499 Crossings cross = getCrossings(x, y, x+w, y+h); 500 return (cross == null || !cross.isEmpty()); 501 } 502 503 /** 504 * {@inheritDoc} 505 * @since 1.2 506 */ 507 public boolean intersects(Rectangle2D r) { 508 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 509 } 510 511 /** 512 * {@inheritDoc} 513 * @since 1.2 514 */ 515 public boolean contains(double x, double y, double w, double h) { 516 if (npoints <= 0 || !getBoundingBox().intersects(x, y, w, h)) { 517 return false; 518 } 519 520 Crossings cross = getCrossings(x, y, x+w, y+h); 521 return (cross != null && cross.covers(y, y+h)); 522 } 523 524 /** 525 * {@inheritDoc} 526 * @since 1.2 527 */ 528 public boolean contains(Rectangle2D r) { 529 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 530 } 531 532 /** 533 * Returns an iterator object that iterates along the boundary of this 534 * {@code Polygon} and provides access to the geometry 535 * of the outline of this {@code Polygon}. An optional 536 * {@link AffineTransform} can be specified so that the coordinates 537 * returned in the iteration are transformed accordingly. 538 * @param at an optional {@code AffineTransform} to be applied to the 539 * coordinates as they are returned in the iteration, or 540 * {@code null} if untransformed coordinates are desired 541 * @return a {@link PathIterator} object that provides access to the 542 * geometry of this {@code Polygon}. 543 * @since 1.2 544 */ 545 public PathIterator getPathIterator(AffineTransform at) { 546 return new PolygonPathIterator(this, at); 547 } 548 549 /** 550 * Returns an iterator object that iterates along the boundary of 551 * the {@code Shape} and provides access to the geometry of the 552 * outline of the {@code Shape}. Only SEG_MOVETO, SEG_LINETO, and 553 * SEG_CLOSE point types are returned by the iterator. 554 * Since polygons are already flat, the {@code flatness} parameter 555 * is ignored. An optional {@code AffineTransform} can be specified 556 * in which case the coordinates returned in the iteration are transformed 557 * accordingly. 558 * @param at an optional {@code AffineTransform} to be applied to the 559 * coordinates as they are returned in the iteration, or 560 * {@code null} if untransformed coordinates are desired 561 * @param flatness the maximum amount that the control points 562 * for a given curve can vary from collinear before a subdivided 563 * curve is replaced by a straight line connecting the 564 * endpoints. Since polygons are already flat the 565 * {@code flatness} parameter is ignored. 566 * @return a {@code PathIterator} object that provides access to the 567 * {@code Shape} object's geometry. 568 * @since 1.2 569 */ 570 public PathIterator getPathIterator(AffineTransform at, double flatness) { 571 return getPathIterator(at); 572 } 573 574 class PolygonPathIterator implements PathIterator { 575 Polygon poly; 576 AffineTransform transform; 577 int index; 578 579 public PolygonPathIterator(Polygon pg, AffineTransform at) { 580 poly = pg; 581 transform = at; 582 if (pg.npoints == 0) { 583 // Prevent a spurious SEG_CLOSE segment 584 index = 1; 585 } 586 } 587 588 /** 589 * Returns the winding rule for determining the interior of the 590 * path. 591 * @return an integer representing the current winding rule. 592 * @see PathIterator#WIND_NON_ZERO 593 */ 594 public int getWindingRule() { 595 return WIND_EVEN_ODD; 596 } 597 598 /** 599 * Tests if there are more points to read. 600 * @return {@code true} if there are more points to read; 601 * {@code false} otherwise. 602 */ 603 public boolean isDone() { 604 return index > poly.npoints; 605 } 606 607 /** 608 * Moves the iterator forwards, along the primary direction of 609 * traversal, to the next segment of the path when there are 610 * more points in that direction. 611 */ 612 public void next() { 613 index++; 614 } 615 616 /** 617 * Returns the coordinates and type of the current path segment in 618 * the iteration. 619 * The return value is the path segment type: 620 * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE. 621 * A {@code float} array of length 2 must be passed in and 622 * can be used to store the coordinates of the point(s). 623 * Each point is stored as a pair of {@code float} x, y 624 * coordinates. SEG_MOVETO and SEG_LINETO types return one 625 * point, and SEG_CLOSE does not return any points. 626 * @param coords a {@code float} array that specifies the 627 * coordinates of the point(s) 628 * @return an integer representing the type and coordinates of the 629 * current path segment. 630 * @see PathIterator#SEG_MOVETO 631 * @see PathIterator#SEG_LINETO 632 * @see PathIterator#SEG_CLOSE 633 */ 634 public int currentSegment(float[] coords) { 635 if (index >= poly.npoints) { 636 return SEG_CLOSE; 637 } 638 coords[0] = poly.xpoints[index]; 639 coords[1] = poly.ypoints[index]; 640 if (transform != null) { 641 transform.transform(coords, 0, coords, 0, 1); 642 } 643 return (index == 0 ? SEG_MOVETO : SEG_LINETO); 644 } 645 646 /** 647 * Returns the coordinates and type of the current path segment in 648 * the iteration. 649 * The return value is the path segment type: 650 * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE. 651 * A {@code double} array of length 2 must be passed in and 652 * can be used to store the coordinates of the point(s). 653 * Each point is stored as a pair of {@code double} x, y 654 * coordinates. 655 * SEG_MOVETO and SEG_LINETO types return one point, 656 * and SEG_CLOSE does not return any points. 657 * @param coords a {@code double} array that specifies the 658 * coordinates of the point(s) 659 * @return an integer representing the type and coordinates of the 660 * current path segment. 661 * @see PathIterator#SEG_MOVETO 662 * @see PathIterator#SEG_LINETO 663 * @see PathIterator#SEG_CLOSE 664 */ 665 public int currentSegment(double[] coords) { 666 if (index >= poly.npoints) { 667 return SEG_CLOSE; 668 } 669 coords[0] = poly.xpoints[index]; 670 coords[1] = poly.ypoints[index]; 671 if (transform != null) { 672 transform.transform(coords, 0, coords, 0, 1); 673 } 674 return (index == 0 ? SEG_MOVETO : SEG_LINETO); 675 } 676 } 677} 678