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