Source for java.awt.Polygon

   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