1 /* Polygon.java -- class representing a polygon 2 Copyright (C) 1999, 2002 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., 59 Temple Place, Suite 330, Boston, MA 19 02111-1307 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.PathIterator; 43 import java.awt.geom.Point2D; 44 import java.awt.geom.Rectangle2D; 45 import java.io.Serializable; 46 47 /** 48 * This class represents a polygon, a closed, two-dimensional region in a 49 * coordinate space. The region is bounded by an arbitrary number of line 50 * segments, between (x,y) coordinate vertices. The polygon has even-odd 51 * winding, meaning that a point is inside the shape if it crosses the 52 * boundary an odd number of times on the way to infinity. 53 * 54 * <p>There are some public fields; if you mess with them in an inconsistent 55 * manner, it is your own fault when you get NullPointerException, 56 * ArrayIndexOutOfBoundsException, or invalid results. Also, this class is 57 * not threadsafe. 58 * 59 * @author Aaron M. Renn <arenn@urbanophile.com> 60 * @author Eric Blake <ebb9@email.byu.edu> 61 * @since 1.0 62 * @status updated to 1.4 63 */ 64 public class Polygon implements Shape, Serializable 65 { 66 /** 67 * Compatible with JDK 1.0+. 68 */ 69 private static final long serialVersionUID = -6460061437900069969L; 70 71 /** 72 * This total number of endpoints. 73 * 74 * @serial the number of endpoints, possibly less than the array sizes 75 */ 76 public int npoints; 77 78 /** 79 * The array of X coordinates of endpoints. This should not be null. 80 * 81 * @see #addPoint(int, int) 82 * @serial the x coordinates 83 */ 84 public int[] xpoints; 85 86 /** 87 * The array of Y coordinates of endpoints. This should not be null. 88 * 89 * @see #addPoint(int, int) 90 * @serial the y coordinates 91 */ 92 public int[] ypoints; 93 94 /** 95 * The bounding box of this polygon. This is lazily created and cached, so 96 * it must be invalidated after changing points. 97 * 98 * @see #getBounds() 99 * @serial the bounding box, or null 100 */ 101 protected Rectangle bounds; 102 103 /** 104 * Cached flattened version - condense points and parallel lines, so the 105 * result has area if there are >= 3 condensed vertices. flat[0] is the 106 * number of condensed points, and (flat[odd], flat[odd+1]) form the 107 * condensed points. 108 * 109 * @see #condense() 110 * @see #contains(double, double) 111 * @see #contains(double, double, double, double) 112 */ 113 private transient int[] condensed; 114 115 /** 116 * Initializes an empty polygon. 117 */ Polygon()118 public Polygon() 119 { 120 // Leave room for growth. 121 xpoints = new int[4]; 122 ypoints = new int[4]; 123 } 124 125 /** 126 * Create a new polygon with the specified endpoints. The arrays are copied, 127 * so that future modifications to the parameters do not affect the polygon. 128 * 129 * @param xpoints the array of X coordinates for this polygon 130 * @param ypoints the array of Y coordinates for this polygon 131 * @param npoints the total number of endpoints in this polygon 132 * @throws NegativeArraySizeException if npoints is negative 133 * @throws IndexOutOfBoundsException if npoints exceeds either array 134 * @throws NullPointerException if xpoints or ypoints is null 135 */ Polygon(int[] xpoints, int[] ypoints, int npoints)136 public Polygon(int[] xpoints, int[] ypoints, int npoints) 137 { 138 this.xpoints = new int[npoints]; 139 this.ypoints = new int[npoints]; 140 System.arraycopy(xpoints, 0, this.xpoints, 0, npoints); 141 System.arraycopy(ypoints, 0, this.ypoints, 0, npoints); 142 this.npoints = npoints; 143 } 144 145 /** 146 * Reset the polygon to be empty. The arrays are left alone, to avoid object 147 * allocation, but the number of points is set to 0, and all cached data 148 * is discarded. If you are discarding a huge number of points, it may be 149 * more efficient to just create a new Polygon. 150 * 151 * @see #invalidate() 152 * @since 1.4 153 */ reset()154 public void reset() 155 { 156 npoints = 0; 157 invalidate(); 158 } 159 160 /** 161 * Invalidate or flush all cached data. After direct manipulation of the 162 * public member fields, this is necessary to avoid inconsistent results 163 * in methods like <code>contains</code>. 164 * 165 * @see #getBounds() 166 * @since 1.4 167 */ invalidate()168 public void invalidate() 169 { 170 bounds = null; 171 condensed = null; 172 } 173 174 /** 175 * Translates the polygon by adding the specified values to all X and Y 176 * coordinates. This updates the bounding box, if it has been calculated. 177 * 178 * @param dx the amount to add to all X coordinates 179 * @param dy the amount to add to all Y coordinates 180 * @since 1.1 181 */ translate(int dx, int dy)182 public void translate(int dx, int dy) 183 { 184 int i = npoints; 185 while (--i >= 0) 186 { 187 xpoints[i] += dx; 188 ypoints[i] += dy; 189 } 190 if (bounds != null) 191 { 192 bounds.x += dx; 193 bounds.y += dy; 194 } 195 condensed = null; 196 } 197 198 /** 199 * Adds the specified endpoint to the polygon. This updates the bounding 200 * box, if it has been created. 201 * 202 * @param x the X coordinate of the point to add 203 * @param y the Y coordiante of the point to add 204 */ addPoint(int x, int y)205 public void addPoint(int x, int y) 206 { 207 if (npoints + 1 > xpoints.length) 208 { 209 int[] newx = new int[npoints + 1]; 210 System.arraycopy(xpoints, 0, newx, 0, npoints); 211 xpoints = newx; 212 } 213 if (npoints + 1 > ypoints.length) 214 { 215 int[] newy = new int[npoints + 1]; 216 System.arraycopy(ypoints, 0, newy, 0, npoints); 217 ypoints = newy; 218 } 219 xpoints[npoints] = x; 220 ypoints[npoints] = y; 221 npoints++; 222 if (bounds != null) 223 { 224 if (npoints == 1) 225 { 226 bounds.x = x; 227 bounds.y = y; 228 } 229 else 230 { 231 if (x < bounds.x) 232 { 233 bounds.width += bounds.x - x; 234 bounds.x = x; 235 } 236 else if (x > bounds.x + bounds.width) 237 bounds.width = x - bounds.x; 238 if (y < bounds.y) 239 { 240 bounds.height += bounds.y - y; 241 bounds.y = y; 242 } 243 else if (y > bounds.y + bounds.height) 244 bounds.height = y - bounds.y; 245 } 246 } 247 condensed = null; 248 } 249 250 /** 251 * Returns the bounding box of this polygon. This is the smallest 252 * rectangle with sides parallel to the X axis that will contain this 253 * polygon. 254 * 255 * @return the bounding box for this polygon 256 * @see #getBounds2D() 257 * @since 1.1 258 */ getBounds()259 public Rectangle getBounds() 260 { 261 if (bounds == null) 262 { 263 if (npoints == 0) 264 return bounds = new Rectangle(); 265 int i = npoints - 1; 266 int minx = xpoints[i]; 267 int maxx = minx; 268 int miny = ypoints[i]; 269 int maxy = miny; 270 while (--i >= 0) 271 { 272 int x = xpoints[i]; 273 int y = ypoints[i]; 274 if (x < minx) 275 minx = x; 276 else if (x > maxx) 277 maxx = x; 278 if (y < miny) 279 miny = y; 280 else if (y > maxy) 281 maxy = y; 282 } 283 bounds = new Rectangle(minx, maxy, maxx - minx, maxy - miny); 284 } 285 return bounds; 286 } 287 288 /** 289 * Returns the bounding box of this polygon. This is the smallest 290 * rectangle with sides parallel to the X axis that will contain this 291 * polygon. 292 * 293 * @return the bounding box for this polygon 294 * @see #getBounds2D() 295 * @deprecated use {@link #getBounds()} instead 296 */ getBoundingBox()297 public Rectangle getBoundingBox() 298 { 299 return getBounds(); 300 } 301 302 /** 303 * Tests whether or not the specified point is inside this polygon. 304 * 305 * @param p the point to test 306 * @return true if the point is inside this polygon 307 * @throws NullPointerException if p is null 308 * @see #contains(double, double) 309 */ contains(Point p)310 public boolean contains(Point p) 311 { 312 return contains(p.getX(), p.getY()); 313 } 314 315 /** 316 * Tests whether or not the specified point is inside this polygon. 317 * 318 * @param x the X coordinate of the point to test 319 * @param y the Y coordinate of the point to test 320 * @return true if the point is inside this polygon 321 * @see #contains(double, double) 322 * @since 1.1 323 */ contains(int x, int y)324 public boolean contains(int x, int y) 325 { 326 return contains((double) x, (double) y); 327 } 328 329 /** 330 * Tests whether or not the specified point is inside this polygon. 331 * 332 * @param x the X coordinate of the point to test 333 * @param y the Y coordinate of the point to test 334 * @return true if the point is inside this polygon 335 * @see #contains(double, double) 336 * @deprecated use {@link #contains(int, int)} instead 337 */ inside(int x, int y)338 public boolean inside(int x, int y) 339 { 340 return contains((double) x, (double) y); 341 } 342 343 /** 344 * Returns a high-precision bounding box of this polygon. This is the 345 * smallest rectangle with sides parallel to the X axis that will contain 346 * this polygon. 347 * 348 * @return the bounding box for this polygon 349 * @see #getBounds() 350 * @since 1.2 351 */ getBounds2D()352 public Rectangle2D getBounds2D() 353 { 354 // For polygons, the integer version is exact! 355 return getBounds(); 356 } 357 358 /** 359 * Tests whether or not the specified point is inside this polygon. 360 * 361 * @param x the X coordinate of the point to test 362 * @param y the Y coordinate of the point to test 363 * @return true if the point is inside this polygon 364 * @since 1.2 365 */ contains(double x, double y)366 public boolean contains(double x, double y) 367 { 368 // First, the obvious bounds checks. 369 if (! condense() || ! getBounds().contains(x, y)) 370 return false; 371 // A point is contained if a ray to (-inf, y) crosses an odd number 372 // of segments. This must obey the semantics of Shape when the point is 373 // exactly on a segment or vertex: a point is inside only if the adjacent 374 // point in the increasing x or y direction is also inside. Note that we 375 // are guaranteed that the condensed polygon has area, and no consecutive 376 // segments with identical slope. 377 boolean inside = false; 378 int limit = condensed[0]; 379 int curx = condensed[(limit << 1) - 1]; 380 int cury = condensed[limit << 1]; 381 for (int i = 1; i <= limit; i++) 382 { 383 int priorx = curx; 384 int priory = cury; 385 curx = condensed[(i << 1) - 1]; 386 cury = condensed[i << 1]; 387 if ((priorx > x && curx > x) // Left of segment, or NaN. 388 || (priory > y && cury > y) // Below segment, or NaN. 389 || (priory < y && cury < y)) // Above segment. 390 continue; 391 if (priory == cury) // Horizontal segment, y == cury == priory 392 { 393 if (priorx < x && curx < x) // Right of segment. 394 { 395 inside = ! inside; 396 continue; 397 } 398 // Did we approach this segment from above or below? 399 // This mess is necessary to obey rules of Shape. 400 priory = condensed[((limit + i - 2) % limit) << 1]; 401 boolean above = priory > cury; 402 if ((curx == x && (curx > priorx || above)) 403 || (priorx == x && (curx < priorx || ! above)) 404 || (curx > priorx && ! above) || above) 405 inside = ! inside; 406 continue; 407 } 408 if (priorx == x && priory == y) // On prior vertex. 409 continue; 410 if (priorx == curx // Vertical segment. 411 || (priorx < x && curx < x)) // Right of segment. 412 { 413 inside = ! inside; 414 continue; 415 } 416 // The point is inside the segment's bounding box, compare slopes. 417 double leftx = curx > priorx ? priorx : curx; 418 double lefty = curx > priorx ? priory : cury; 419 double slopeseg = (double) (cury - priory) / (curx - priorx); 420 double slopepoint = (double) (y - lefty) / (x - leftx); 421 if ((slopeseg > 0 && slopeseg > slopepoint) 422 || slopeseg < slopepoint) 423 inside = ! inside; 424 } 425 return inside; 426 } 427 428 /** 429 * Tests whether or not the specified point is inside this polygon. 430 * 431 * @param p the point to test 432 * @return true if the point is inside this polygon 433 * @throws NullPointerException if p is null 434 * @see #contains(double, double) 435 * @since 1.2 436 */ contains(Point2D p)437 public boolean contains(Point2D p) 438 { 439 return contains(p.getX(), p.getY()); 440 } 441 442 /** 443 * Test if a high-precision rectangle intersects the shape. This is true 444 * if any point in the rectangle is in the shape. This implementation is 445 * precise. 446 * 447 * @param x the x coordinate of the rectangle 448 * @param y the y coordinate of the rectangle 449 * @param w the width of the rectangle, treated as point if negative 450 * @param h the height of the rectangle, treated as point if negative 451 * @return true if the rectangle intersects this shape 452 * @since 1.2 453 */ intersects(double x, double y, double w, double h)454 public boolean intersects(double x, double y, double w, double h) 455 { 456 // First, the obvious bounds checks. 457 if (w <= 0 || h <= 0 || npoints == 0 || 458 ! getBounds().intersects(x, y, w, h)) 459 return false; // Disjoint bounds. 460 if ((x <= bounds.x && x + w >= bounds.x + bounds.width 461 && y <= bounds.y && y + h >= bounds.y + bounds.height) 462 || contains(x, y)) 463 return true; // Rectangle contains the polygon, or one point matches. 464 // If any vertex is in the rectangle, the two might intersect. 465 int curx = 0; 466 int cury = 0; 467 for (int i = 0; i < npoints; i++) 468 { 469 curx = xpoints[i]; 470 cury = ypoints[i]; 471 if (curx >= x && curx < x + w && cury >= y && cury < y + h 472 && contains(curx, cury)) // Boundary check necessary. 473 return true; 474 } 475 // Finally, if at least one of the four bounding lines intersect any 476 // segment of the polygon, return true. Be careful of the semantics of 477 // Shape; coinciding lines do not necessarily return true. 478 for (int i = 0; i < npoints; i++) 479 { 480 int priorx = curx; 481 int priory = cury; 482 curx = xpoints[i]; 483 cury = ypoints[i]; 484 if (priorx == curx) // Vertical segment. 485 { 486 if (curx < x || curx >= x + w) // Outside rectangle. 487 continue; 488 if ((cury >= y + h && priory <= y) 489 || (cury <= y && priory >= y + h)) 490 return true; // Bisects rectangle. 491 continue; 492 } 493 if (priory == cury) // Horizontal segment. 494 { 495 if (cury < y || cury >= y + h) // Outside rectangle. 496 continue; 497 if ((curx >= x + w && priorx <= x) 498 || (curx <= x && priorx >= x + w)) 499 return true; // Bisects rectangle. 500 continue; 501 } 502 // Slanted segment. 503 double slope = (double) (cury - priory) / (curx - priorx); 504 double intersect = slope * (x - curx) + cury; 505 if (intersect > y && intersect < y + h) // Intersects left edge. 506 return true; 507 intersect = slope * (x + w - curx) + cury; 508 if (intersect > y && intersect < y + h) // Intersects right edge. 509 return true; 510 intersect = (y - cury) / slope + curx; 511 if (intersect > x && intersect < x + w) // Intersects bottom edge. 512 return true; 513 intersect = (y + h - cury) / slope + cury; 514 if (intersect > x && intersect < x + w) // Intersects top edge. 515 return true; 516 } 517 return false; 518 } 519 520 /** 521 * Test if a high-precision rectangle intersects the shape. This is true 522 * if any point in the rectangle is in the shape. This implementation is 523 * precise. 524 * 525 * @param r the rectangle 526 * @return true if the rectangle intersects this shape 527 * @throws NullPointerException if r is null 528 * @see #intersects(double, double, double, double) 529 * @since 1.2 530 */ intersects(Rectangle2D r)531 public boolean intersects(Rectangle2D r) 532 { 533 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 534 } 535 536 /** 537 * Test if a high-precision rectangle lies completely in the shape. This is 538 * true if all points in the rectangle are in the shape. This implementation 539 * is precise. 540 * 541 * @param x the x coordinate of the rectangle 542 * @param y the y coordinate of the rectangle 543 * @param w the width of the rectangle, treated as point if negative 544 * @param h the height of the rectangle, treated as point if negative 545 * @return true if the rectangle is contained in this shape 546 * @since 1.2 547 */ contains(double x, double y, double w, double h)548 public boolean contains(double x, double y, double w, double h) 549 { 550 // First, the obvious bounds checks. 551 if (w <= 0 || h <= 0 || ! contains(x, y) 552 || ! bounds.contains(x, y, w, h)) 553 return false; 554 // Now, if any of the four bounding lines intersects a polygon segment, 555 // return false. The previous check had the side effect of setting 556 // the condensed array, which we use. Be careful of the semantics of 557 // Shape; coinciding lines do not necessarily return false. 558 int limit = condensed[0]; 559 int curx = condensed[(limit << 1) - 1]; 560 int cury = condensed[limit << 1]; 561 for (int i = 1; i <= limit; i++) 562 { 563 int priorx = curx; 564 int priory = cury; 565 curx = condensed[(i << 1) - 1]; 566 cury = condensed[i << 1]; 567 if (curx > x && curx < x + w && cury > y && cury < y + h) 568 return false; // Vertex is in rectangle. 569 if (priorx == curx) // Vertical segment. 570 { 571 if (curx < x || curx > x + w) // Outside rectangle. 572 continue; 573 if ((cury >= y + h && priory <= y) 574 || (cury <= y && priory >= y + h)) 575 return false; // Bisects rectangle. 576 continue; 577 } 578 if (priory == cury) // Horizontal segment. 579 { 580 if (cury < y || cury > y + h) // Outside rectangle. 581 continue; 582 if ((curx >= x + w && priorx <= x) 583 || (curx <= x && priorx >= x + w)) 584 return false; // Bisects rectangle. 585 continue; 586 } 587 // Slanted segment. 588 double slope = (double) (cury - priory) / (curx - priorx); 589 double intersect = slope * (x - curx) + cury; 590 if (intersect > y && intersect < y + h) // Intersects left edge. 591 return false; 592 intersect = slope * (x + w - curx) + cury; 593 if (intersect > y && intersect < y + h) // Intersects right edge. 594 return false; 595 intersect = (y - cury) / slope + curx; 596 if (intersect > x && intersect < x + w) // Intersects bottom edge. 597 return false; 598 intersect = (y + h - cury) / slope + cury; 599 if (intersect > x && intersect < x + w) // Intersects top edge. 600 return false; 601 } 602 return true; 603 } 604 605 /** 606 * Test if a high-precision rectangle lies completely in the shape. This is 607 * true if all points in the rectangle are in the shape. This implementation 608 * is precise. 609 * 610 * @param r the rectangle 611 * @return true if the rectangle is contained in this shape 612 * @throws NullPointerException if r is null 613 * @see #contains(double, double, double, double) 614 * @since 1.2 615 */ contains(Rectangle2D r)616 public boolean contains(Rectangle2D r) 617 { 618 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 619 } 620 621 /** 622 * Return an iterator along the shape boundary. If the optional transform 623 * is provided, the iterator is transformed accordingly. Each call returns 624 * a new object, independent from others in use. This class is not 625 * threadsafe to begin with, so the path iterator is not either. 626 * 627 * @param transform an optional transform to apply to the iterator 628 * @return a new iterator over the boundary 629 * @since 1.2 630 */ getPathIterator(final AffineTransform transform)631 public PathIterator getPathIterator(final AffineTransform transform) 632 { 633 return new PathIterator() 634 { 635 /** The current vertex of iteration. */ 636 private int vertex; 637 638 public int getWindingRule() 639 { 640 return WIND_EVEN_ODD; 641 } 642 643 public boolean isDone() 644 { 645 return vertex > npoints; 646 } 647 648 public void next() 649 { 650 vertex++; 651 } 652 653 public int currentSegment(float[] coords) 654 { 655 if (vertex >= npoints) 656 return SEG_CLOSE; 657 coords[0] = xpoints[vertex]; 658 coords[1] = ypoints[vertex]; 659 if (transform != null) 660 transform.transform(coords, 0, coords, 0, 1); 661 return vertex == 0 ? SEG_MOVETO : SEG_LINETO; 662 } 663 664 public int currentSegment(double[] coords) 665 { 666 if (vertex >= npoints) 667 return SEG_CLOSE; 668 coords[0] = xpoints[vertex]; 669 coords[1] = ypoints[vertex]; 670 if (transform != null) 671 transform.transform(coords, 0, coords, 0, 1); 672 return vertex == 0 ? SEG_MOVETO : SEG_LINETO; 673 } 674 }; 675 } 676 677 /** 678 * Return an iterator along the flattened version of the shape boundary. 679 * Since polygons are already flat, the flatness parameter is ignored, and 680 * the resulting iterator only has SEG_MOVETO, SEG_LINETO and SEG_CLOSE 681 * points. If the optional transform is provided, the iterator is 682 * transformed accordingly. Each call returns a new object, independent 683 * from others in use. This class is not threadsafe to begin with, so the 684 * path iterator is not either. 685 * 686 * @param transform an optional transform to apply to the iterator 687 * @param double the maximum distance for deviation from the real boundary 688 * @return a new iterator over the boundary 689 * @since 1.2 690 */ getPathIterator(AffineTransform transform, double flatness)691 public PathIterator getPathIterator(AffineTransform transform, 692 double flatness) 693 { 694 return getPathIterator(transform); 695 } 696 697 /** 698 * Helper for contains, which caches a condensed version of the polygon. 699 * This condenses all colinear points, so that consecutive segments in 700 * the condensed version always have different slope. 701 * 702 * @return true if the condensed polygon has area 703 * @see #condensed 704 * @see #contains(double, double) 705 */ condense()706 private boolean condense() 707 { 708 if (npoints <= 2) 709 return false; 710 if (condensed != null) 711 return condensed[0] > 2; 712 condensed = new int[npoints * 2 + 1]; 713 int curx = xpoints[npoints - 1]; 714 int cury = ypoints[npoints - 1]; 715 double curslope = Double.NaN; 716 int count = 0; 717 outer: 718 for (int i = 0; i < npoints; i++) 719 { 720 int priorx = curx; 721 int priory = cury; 722 double priorslope = curslope; 723 curx = xpoints[i]; 724 cury = ypoints[i]; 725 while (curx == priorx && cury == priory) 726 { 727 if (++i == npoints) 728 break outer; 729 curx = xpoints[i]; 730 cury = ypoints[i]; 731 } 732 curslope = (curx == priorx ? Double.POSITIVE_INFINITY 733 : (double) (cury - priory) / (curx - priorx)); 734 if (priorslope == curslope) 735 { 736 if (count > 1 && condensed[(count << 1) - 3] == curx 737 && condensed[(count << 1) - 2] == cury) 738 { 739 count--; 740 continue; 741 } 742 } 743 else 744 count++; 745 condensed[(count << 1) - 1] = curx; 746 condensed[count << 1] = cury; 747 } 748 condensed[0] = count; 749 return count > 2; 750 } 751 } // class Polygon 752