Source for java.awt.geom.GeneralPath

   1: /* GeneralPath.java -- represents a shape built from subpaths
   2:    Copyright (C) 2002, 2003, 2004 Free Software Foundation
   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.geom;
  40: 
  41: import java.awt.Rectangle;
  42: import java.awt.Shape;
  43: 
  44: 
  45: /**
  46:  * A general geometric path, consisting of any number of subpaths
  47:  * constructed out of straight lines and cubic or quadratic Bezier
  48:  * curves.
  49:  *
  50:  * <p>The inside of the curve is defined for drawing purposes by a winding
  51:  * rule. Either the WIND_EVEN_ODD or WIND_NON_ZERO winding rule can be chosen.
  52:  *
  53:  * <p><img src="doc-files/GeneralPath-1.png" width="300" height="210"
  54:  * alt="A drawing of a GeneralPath" />
  55:  * <p>The EVEN_ODD winding rule defines a point as inside a path if:
  56:  * A ray from the point towards infinity in an arbitrary direction
  57:  * intersects the path an odd number of times. Points <b>A</b> and
  58:  * <b>C</b> in the image are considered to be outside the path.
  59:  * (both intersect twice)
  60:  * Point <b>B</b> intersects once, and is inside.
  61:  *
  62:  * <p>The NON_ZERO winding rule defines a point as inside a path if:
  63:  * The path intersects the ray in an equal number of opposite directions.
  64:  * Point <b>A</b> in the image is outside (one intersection in the 
  65:  * &#x2019;up&#x2019;
  66:  * direction, one in the &#x2019;down&#x2019; direction) Point <b>B</b> in 
  67:  * the image is inside (one intersection &#x2019;down&#x2019;)
  68:  * Point <b>C</b> in the image is outside (two intersections 
  69:  * &#x2019;down&#x2019;)
  70:  *
  71:  * @see Line2D
  72:  * @see CubicCurve2D
  73:  * @see QuadCurve2D
  74:  *
  75:  * @author Sascha Brawer (brawer@dandelis.ch)
  76:  * @author Sven de Marothy (sven@physto.se)
  77:  *
  78:  * @since 1.2
  79:  */
  80: public final class GeneralPath implements Shape, Cloneable
  81: {
  82:   public static final int WIND_EVEN_ODD = PathIterator.WIND_EVEN_ODD;
  83:   public static final int WIND_NON_ZERO = PathIterator.WIND_NON_ZERO;
  84: 
  85:   /** Initial size if not specified. */
  86:   private static final int INIT_SIZE = 10;
  87: 
  88:   /** A big number, but not so big it can't survive a few float operations */
  89:   private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0;
  90: 
  91:   /** The winding rule.
  92:    * This is package-private to avoid an accessor method.
  93:    */
  94:   int rule;
  95: 
  96:   /**
  97:    * The path type in points. Note that xpoints[index] and ypoints[index] maps
  98:    * to types[index]; the control points of quad and cubic paths map as
  99:    * well but are ignored.
 100:    * This is package-private to avoid an accessor method.
 101:    */
 102:   byte[] types;
 103: 
 104:   /**
 105:    * The list of all points seen. Since you can only append floats, it makes
 106:    * sense for these to be float[]. I have no idea why Sun didn't choose to
 107:    * allow a general path of double precision points.
 108:    * Note: Storing x and y coords seperately makes for a slower transforms,
 109:    * But it speeds up and simplifies box-intersection checking a lot.
 110:    * These are package-private to avoid accessor methods.
 111:    */
 112:   float[] xpoints;
 113:   float[] ypoints;
 114: 
 115:   /** The index of the most recent moveto point, or null. */
 116:   private int subpath = -1;
 117: 
 118:   /** The next available index into points.
 119:    * This is package-private to avoid an accessor method.
 120:    */
 121:   int index;
 122: 
 123:   /**
 124:    * Constructs a GeneralPath with the default (NON_ZERO)
 125:    * winding rule and initial capacity (20).
 126:    */
 127:   public GeneralPath()
 128:   {
 129:     this(WIND_NON_ZERO, INIT_SIZE);
 130:   }
 131: 
 132:   /**
 133:    * Constructs a GeneralPath with a specific winding rule
 134:    * and the default initial capacity (20).
 135:    * @param rule the winding rule (WIND_NON_ZERO or WIND_EVEN_ODD)
 136:    */
 137:   public GeneralPath(int rule)
 138:   {
 139:     this(rule, INIT_SIZE);
 140:   }
 141: 
 142:   /**
 143:    * Constructs a GeneralPath with a specific winding rule
 144:    * and the initial capacity. The initial capacity should be
 145:    * the approximate number of path segments to be used.
 146:    * @param rule the winding rule (WIND_NON_ZERO or WIND_EVEN_ODD)
 147:    * @param capacity the inital capacity, in path segments
 148:    */
 149:   public GeneralPath(int rule, int capacity)
 150:   {
 151:     if (rule != WIND_EVEN_ODD && rule != WIND_NON_ZERO)
 152:       throw new IllegalArgumentException();
 153:     this.rule = rule;
 154:     if (capacity < INIT_SIZE)
 155:       capacity = INIT_SIZE;
 156:     types = new byte[capacity];
 157:     xpoints = new float[capacity];
 158:     ypoints = new float[capacity];
 159:   }
 160: 
 161:   /**
 162:    * Constructs a GeneralPath from an arbitrary shape object.
 163:    * The Shapes PathIterator path and winding rule will be used.
 164:    * @param s the shape
 165:    */
 166:   public GeneralPath(Shape s)
 167:   {
 168:     types = new byte[INIT_SIZE];
 169:     xpoints = new float[INIT_SIZE];
 170:     ypoints = new float[INIT_SIZE];
 171:     PathIterator pi = s.getPathIterator(null);
 172:     setWindingRule(pi.getWindingRule());
 173:     append(pi, false);
 174:   }
 175: 
 176:   /**
 177:    * Adds a new point to a path.
 178:    */
 179:   public void moveTo(float x, float y)
 180:   {
 181:     subpath = index;
 182:     ensureSize(index + 1);
 183:     types[index] = PathIterator.SEG_MOVETO;
 184:     xpoints[index] = x;
 185:     ypoints[index++] = y;
 186:   }
 187: 
 188:   /**
 189:    * Appends a straight line to the current path.
 190:    * @param x x coordinate of the line endpoint.
 191:    * @param y y coordinate of the line endpoint.
 192:    */
 193:   public void lineTo(float x, float y)
 194:   {
 195:     ensureSize(index + 1);
 196:     types[index] = PathIterator.SEG_LINETO;
 197:     xpoints[index] = x;
 198:     ypoints[index++] = y;
 199:   }
 200: 
 201:   /**
 202:    * Appends a quadratic Bezier curve to the current path.
 203:    * @param x1 x coordinate of the control point
 204:    * @param y1 y coordinate of the control point
 205:    * @param x2 x coordinate of the curve endpoint.
 206:    * @param y2 y coordinate of the curve endpoint.
 207:    */
 208:   public void quadTo(float x1, float y1, float x2, float y2)
 209:   {
 210:     ensureSize(index + 2);
 211:     types[index] = PathIterator.SEG_QUADTO;
 212:     xpoints[index] = x1;
 213:     ypoints[index++] = y1;
 214:     xpoints[index] = x2;
 215:     ypoints[index++] = y2;
 216:   }
 217: 
 218:   /**
 219:    * Appends a cubic Bezier curve to the current path.
 220:    * @param x1 x coordinate of the first control point
 221:    * @param y1 y coordinate of the first control point
 222:    * @param x2 x coordinate of the second control point
 223:    * @param y2 y coordinate of the second control point
 224:    * @param x3 x coordinate of the curve endpoint.
 225:    * @param y3 y coordinate of the curve endpoint.
 226:    */
 227:   public void curveTo(float x1, float y1, float x2, float y2, float x3,
 228:                       float y3)
 229:   {
 230:     ensureSize(index + 3);
 231:     types[index] = PathIterator.SEG_CUBICTO;
 232:     xpoints[index] = x1;
 233:     ypoints[index++] = y1;
 234:     xpoints[index] = x2;
 235:     ypoints[index++] = y2;
 236:     xpoints[index] = x3;
 237:     ypoints[index++] = y3;
 238:   }
 239: 
 240:   /**
 241:    * Closes the current subpath by drawing a line
 242:    * back to the point of the last moveTo.
 243:    */
 244:   public void closePath()
 245:   {
 246:     ensureSize(index + 1);
 247:     types[index] = PathIterator.SEG_CLOSE;
 248:     xpoints[index] = xpoints[subpath];
 249:     ypoints[index++] = ypoints[subpath];
 250:   }
 251: 
 252:   /**
 253:    * Appends the segments of a Shape to the path. If <code>connect</code> is 
 254:    * true, the new path segments are connected to the existing one with a line.
 255:    * The winding rule of the Shape is ignored.
 256:    */
 257:   public void append(Shape s, boolean connect)
 258:   {
 259:     append(s.getPathIterator(null), connect);
 260:   }
 261: 
 262:   /**
 263:    * Appends the segments of a PathIterator to this GeneralPath.
 264:    * Optionally, the initial {@link PathIterator#SEG_MOVETO} segment
 265:    * of the appended path is changed into a {@link
 266:    * PathIterator#SEG_LINETO} segment.
 267:    *
 268:    * @param iter the PathIterator specifying which segments shall be
 269:    * appended.
 270:    *
 271:    * @param connect <code>true</code> for substituting the initial
 272:    * {@link PathIterator#SEG_MOVETO} segment by a {@link
 273:    * PathIterator#SEG_LINETO}, or <code>false</code> for not
 274:    * performing any substitution. If this GeneralPath is currently
 275:    * empty, <code>connect</code> is assumed to be <code>false</code>,
 276:    * thus leaving the initial {@link PathIterator#SEG_MOVETO}
 277:    * unchanged.
 278:    */
 279:   public void append(PathIterator iter, boolean connect)
 280:   {
 281:     // A bad implementation of this method had caused Classpath bug #6076.
 282:     float[] f = new float[6];
 283:     while (! iter.isDone())
 284:       {
 285:     switch (iter.currentSegment(f))
 286:       {
 287:       case PathIterator.SEG_MOVETO:
 288:         if (! connect || (index == 0))
 289:           {
 290:         moveTo(f[0], f[1]);
 291:         break;
 292:           }
 293:         if ((index >= 1) && (types[index - 1] == PathIterator.SEG_CLOSE)
 294:             && (f[0] == xpoints[index - 1])
 295:             && (f[1] == ypoints[index - 1]))
 296:           break;
 297: 
 298:       // Fall through.
 299:       case PathIterator.SEG_LINETO:
 300:         lineTo(f[0], f[1]);
 301:         break;
 302:       case PathIterator.SEG_QUADTO:
 303:         quadTo(f[0], f[1], f[2], f[3]);
 304:         break;
 305:       case PathIterator.SEG_CUBICTO:
 306:         curveTo(f[0], f[1], f[2], f[3], f[4], f[5]);
 307:         break;
 308:       case PathIterator.SEG_CLOSE:
 309:         closePath();
 310:         break;
 311:       }
 312: 
 313:     connect = false;
 314:     iter.next();
 315:       }
 316:   }
 317: 
 318:   /**
 319:    * Returns the path&#x2019;s current winding rule.
 320:    */
 321:   public int getWindingRule()
 322:   {
 323:     return rule;
 324:   }
 325: 
 326:   /**
 327:    * Sets the path&#x2019;s winding rule, which controls which areas are 
 328:    * considered &#x2019;inside&#x2019; or &#x2019;outside&#x2019; the path 
 329:    * on drawing. Valid rules are WIND_EVEN_ODD for an even-odd winding rule, 
 330:    * or WIND_NON_ZERO for a non-zero winding rule.
 331:    */
 332:   public void setWindingRule(int rule)
 333:   {
 334:     if (rule != WIND_EVEN_ODD && rule != WIND_NON_ZERO)
 335:       throw new IllegalArgumentException();
 336:     this.rule = rule;
 337:   }
 338: 
 339:   /**
 340:    * Returns the current appending point of the path.
 341:    */
 342:   public Point2D getCurrentPoint()
 343:   {
 344:     if (subpath < 0)
 345:       return null;
 346:     return new Point2D.Float(xpoints[index - 1], ypoints[index - 1]);
 347:   }
 348: 
 349:   /**
 350:    * Resets the path. All points and segments are destroyed.
 351:    */
 352:   public void reset()
 353:   {
 354:     subpath = -1;
 355:     index = 0;
 356:   }
 357: 
 358:   /**
 359:    * Applies a transform to the path.
 360:    */
 361:   public void transform(AffineTransform xform)
 362:   {
 363:     double nx;
 364:     double ny;
 365:     double[] m = new double[6];
 366:     xform.getMatrix(m);
 367:     for (int i = 0; i < index; i++)
 368:       {
 369:     nx = m[0] * xpoints[i] + m[2] * ypoints[i] + m[4];
 370:     ny = m[1] * xpoints[i] + m[3] * ypoints[i] + m[5];
 371:     xpoints[i] = (float) nx;
 372:     ypoints[i] = (float) ny;
 373:       }
 374:   }
 375: 
 376:   /**
 377:    * Creates a transformed version of the path.
 378:    * @param xform the transform to apply
 379:    * @return a new transformed GeneralPath
 380:    */
 381:   public Shape createTransformedShape(AffineTransform xform)
 382:   {
 383:     GeneralPath p = new GeneralPath(this);
 384:     p.transform(xform);
 385:     return p;
 386:   }
 387: 
 388:   /**
 389:    * Returns the path&#x2019;s bounding box.
 390:    */
 391:   public Rectangle getBounds()
 392:   {
 393:     return getBounds2D().getBounds();
 394:   }
 395: 
 396:   /**
 397:    * Returns the path&#x2019;s bounding box, in <code>float</code> precision
 398:    */
 399:   public Rectangle2D getBounds2D()
 400:   {
 401:     float x1;
 402:     float y1;
 403:     float x2;
 404:     float y2;
 405: 
 406:     if (index > 0)
 407:       {
 408:     x1 = x2 = xpoints[0];
 409:     y1 = y2 = ypoints[0];
 410:       }
 411:     else
 412:       x1 = x2 = y1 = y2 = 0.0f;
 413: 
 414:     for (int i = 0; i < index; i++)
 415:       {
 416:     x1 = Math.min(xpoints[i], x1);
 417:     y1 = Math.min(ypoints[i], y1);
 418:     x2 = Math.max(xpoints[i], x2);
 419:     y2 = Math.max(ypoints[i], y2);
 420:       }
 421:     return (new Rectangle2D.Float(x1, y1, x2 - x1, y2 - y1));
 422:   }
 423: 
 424:   /**
 425:    * Evaluates if a point is within the GeneralPath,
 426:    * The NON_ZERO winding rule is used, regardless of the
 427:    * set winding rule.
 428:    * @param x x coordinate of the point to evaluate
 429:    * @param y y coordinate of the point to evaluate
 430:    * @return true if the point is within the path, false otherwise
 431:    */
 432:   public boolean contains(double x, double y)
 433:   {
 434:     return (getWindingNumber(x, y) != 0);
 435:   }
 436: 
 437:   /**
 438:    * Evaluates if a Point2D is within the GeneralPath,
 439:    * The NON_ZERO winding rule is used, regardless of the
 440:    * set winding rule.
 441:    * @param p The Point2D to evaluate
 442:    * @return true if the point is within the path, false otherwise
 443:    */
 444:   public boolean contains(Point2D p)
 445:   {
 446:     return contains(p.getX(), p.getY());
 447:   }
 448: 
 449:   /**
 450:    * Evaluates if a rectangle is completely contained within the path.
 451:    * This method will return false in the cases when the box
 452:    * intersects an inner segment of the path.
 453:    * (i.e.: The method is accurate for the EVEN_ODD winding rule)
 454:    */
 455:   public boolean contains(double x, double y, double w, double h)
 456:   {
 457:     if (! getBounds2D().intersects(x, y, w, h))
 458:       return false;
 459: 
 460:     /* Does any edge intersect? */
 461:     if (getAxisIntersections(x, y, false, w) != 0 /* top */
 462:         || getAxisIntersections(x, y + h, false, w) != 0 /* bottom */
 463:         || getAxisIntersections(x + w, y, true, h) != 0 /* right */
 464:         || getAxisIntersections(x, y, true, h) != 0) /* left */
 465:       return false;
 466: 
 467:     /* No intersections, is any point inside? */
 468:     if (getWindingNumber(x, y) != 0)
 469:       return true;
 470: 
 471:     return false;
 472:   }
 473: 
 474:   /**
 475:    * Evaluates if a rectangle is completely contained within the path.
 476:    * This method will return false in the cases when the box
 477:    * intersects an inner segment of the path.
 478:    * (i.e.: The method is accurate for the EVEN_ODD winding rule)
 479:    * @param r the rectangle
 480:    * @return <code>true</code> if the rectangle is completely contained
 481:    * within the path, <code>false</code> otherwise
 482:    */
 483:   public boolean contains(Rectangle2D r)
 484:   {
 485:     return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
 486:   }
 487: 
 488:   /**
 489:    * Evaluates if a rectangle intersects the path.
 490:    * @param x x coordinate of the rectangle
 491:    * @param y y coordinate of the rectangle
 492:    * @param w width of the rectangle
 493:    * @param h height of the rectangle
 494:    * @return <code>true</code> if the rectangle intersects the path,
 495:    * <code>false</code> otherwise
 496:    */
 497:   public boolean intersects(double x, double y, double w, double h)
 498:   {
 499:     /* Does any edge intersect? */
 500:     if (getAxisIntersections(x, y, false, w) != 0 /* top */
 501:         || getAxisIntersections(x, y + h, false, w) != 0 /* bottom */
 502:         || getAxisIntersections(x + w, y, true, h) != 0 /* right */
 503:         || getAxisIntersections(x, y, true, h) != 0) /* left */
 504:       return true;
 505: 
 506:     /* No intersections, is any point inside? */
 507:     if (getWindingNumber(x, y) != 0)
 508:       return true;
 509: 
 510:     return false;
 511:   }
 512: 
 513:   /**
 514:    * Evaluates if a Rectangle2D intersects the path.
 515:    * @param r The rectangle
 516:    * @return <code>true</code> if the rectangle intersects the path,
 517:    * <code>false</code> otherwise
 518:    */
 519:   public boolean intersects(Rectangle2D r)
 520:   {
 521:     return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
 522:   }
 523: 
 524:   /**
 525:    * A PathIterator that iterates over the segments of a GeneralPath.
 526:    *
 527:    * @author Sascha Brawer (brawer@dandelis.ch)
 528:    */
 529:   private static class GeneralPathIterator implements PathIterator
 530:   {
 531:     /**
 532:      * The number of coordinate values for each segment type.
 533:      */
 534:     private static final int[] NUM_COORDS = { 
 535:                                             /* 0: SEG_MOVETO */ 1, 
 536:                                             /* 1: SEG_LINETO */ 1, 
 537:                                             /* 2: SEG_QUADTO */ 2, 
 538:                                             /* 3: SEG_CUBICTO */ 3, 
 539:                                             /* 4: SEG_CLOSE */ 0};
 540: 
 541:     /**
 542:      * The GeneralPath whose segments are being iterated.
 543:      * This is package-private to avoid an accessor method.
 544:      */
 545:     final GeneralPath path;
 546: 
 547:     /**
 548:      * The affine transformation used to transform coordinates.
 549:      */
 550:     private final AffineTransform transform;
 551: 
 552:     /**
 553:      * The current position of the iterator.
 554:      */
 555:     private int pos;
 556: 
 557:     /**
 558:      * Constructs a new iterator for enumerating the segments of a
 559:      * GeneralPath.
 560:      *
 561:      * @param path the path to enumerate
 562:      * @param transform an affine transformation for projecting the returned
 563:      * points, or <code>null</code> to return the original points
 564:      * without any mapping.
 565:      */
 566:     GeneralPathIterator(GeneralPath path, AffineTransform transform)
 567:     {
 568:       this.path = path;
 569:       this.transform = transform;
 570:     }
 571: 
 572:     /**
 573:      * Returns the current winding rule of the GeneralPath.
 574:      */
 575:     public int getWindingRule()
 576:     {
 577:       return path.rule;
 578:     }
 579: 
 580:     /**
 581:      * Determines whether the iterator has reached the last segment in
 582:      * the path.
 583:      */
 584:     public boolean isDone()
 585:     {
 586:       return pos >= path.index;
 587:     }
 588: 
 589:     /**
 590:      * Advances the iterator position by one segment.
 591:      */
 592:     public void next()
 593:     {
 594:       int seg;
 595: 
 596:       /*
 597:        * Increment pos by the number of coordinate pairs.
 598:        */
 599:       seg = path.types[pos];
 600:       if (seg == SEG_CLOSE)
 601:     pos++;
 602:       else
 603:     pos += NUM_COORDS[seg];
 604:     }
 605: 
 606:     /**
 607:      * Returns the current segment in float coordinates.
 608:      */
 609:     public int currentSegment(float[] coords)
 610:     {
 611:       int seg;
 612:       int numCoords;
 613: 
 614:       seg = path.types[pos];
 615:       numCoords = NUM_COORDS[seg];
 616:       if (numCoords > 0)
 617:         {
 618:       for (int i = 0; i < numCoords; i++)
 619:         {
 620:           coords[i << 1] = path.xpoints[pos + i];
 621:           coords[(i << 1) + 1] = path.ypoints[pos + i];
 622:         }
 623: 
 624:       if (transform != null)
 625:         transform.transform( /* src */
 626:         coords, /* srcOffset */
 627:         0, /* dest */ coords, /* destOffset */
 628:         0, /* numPoints */ numCoords);
 629:         }
 630:       return seg;
 631:     }
 632: 
 633:     /**
 634:      * Returns the current segment in double coordinates.
 635:      */
 636:     public int currentSegment(double[] coords)
 637:     {
 638:       int seg;
 639:       int numCoords;
 640: 
 641:       seg = path.types[pos];
 642:       numCoords = NUM_COORDS[seg];
 643:       if (numCoords > 0)
 644:         {
 645:       for (int i = 0; i < numCoords; i++)
 646:         {
 647:           coords[i << 1] = (double) path.xpoints[pos + i];
 648:           coords[(i << 1) + 1] = (double) path.ypoints[pos + i];
 649:         }
 650:       if (transform != null)
 651:         transform.transform( /* src */
 652:         coords, /* srcOffset */
 653:         0, /* dest */ coords, /* destOffset */
 654:         0, /* numPoints */ numCoords);
 655:         }
 656:       return seg;
 657:     }
 658:   }
 659: 
 660:   /**
 661:    * Creates a PathIterator for iterating along the segments of the path.
 662:    *
 663:    * @param at an affine transformation for projecting the returned
 664:    * points, or <code>null</code> to let the created iterator return
 665:    * the original points without any mapping.
 666:    */
 667:   public PathIterator getPathIterator(AffineTransform at)
 668:   {
 669:     return new GeneralPathIterator(this, at);
 670:   }
 671: 
 672:   /**
 673:    * Creates a new FlatteningPathIterator for the path
 674:    */
 675:   public PathIterator getPathIterator(AffineTransform at, double flatness)
 676:   {
 677:     return new FlatteningPathIterator(getPathIterator(at), flatness);
 678:   }
 679: 
 680:   /**
 681:    * Creates a new shape of the same run-time type with the same contents 
 682:    * as this one.
 683:    *
 684:    * @return the clone
 685:    *
 686:    * @exception OutOfMemoryError If there is not enough memory available.
 687:    *
 688:    * @since 1.2
 689:    */
 690:   public Object clone()
 691:   {
 692:     // This class is final; no need to use super.clone().
 693:     return new GeneralPath(this);
 694:   }
 695: 
 696:   /**
 697:    * Helper method - ensure the size of the data arrays,
 698:    * otherwise, reallocate new ones twice the size
 699:    */
 700:   private void ensureSize(int size)
 701:   {
 702:     if (subpath < 0)
 703:       throw new IllegalPathStateException("need initial moveto");
 704:     if (size <= xpoints.length)
 705:       return;
 706:     byte[] b = new byte[types.length << 1];
 707:     System.arraycopy(types, 0, b, 0, index);
 708:     types = b;
 709:     float[] f = new float[xpoints.length << 1];
 710:     System.arraycopy(xpoints, 0, f, 0, index);
 711:     xpoints = f;
 712:     f = new float[ypoints.length << 1];
 713:     System.arraycopy(ypoints, 0, f, 0, index);
 714:     ypoints = f;
 715:   }
 716: 
 717:   /**
 718:    * Helper method - Get the total number of intersections from (x,y) along 
 719:    * a given axis, within a given distance.
 720:    */
 721:   private int getAxisIntersections(double x, double y, boolean useYaxis,
 722:                                    double distance)
 723:   {
 724:     return (evaluateCrossings(x, y, false, useYaxis, distance));
 725:   }
 726: 
 727:   /**
 728:    * Helper method - returns the winding number of a point.
 729:    */
 730:   private int getWindingNumber(double x, double y)
 731:   {
 732:     /* Evaluate the crossings from x,y to infinity on the y axis (arbitrary 
 733:        choice). Note that we don't actually use Double.INFINITY, since that's 
 734:        slower, and may cause problems. */
 735:     return (evaluateCrossings(x, y, true, true, BIG_VALUE));
 736:   }
 737: 
 738:   /**
 739:    * Helper method - evaluates the number of intersections on an axis from 
 740:    * the point (x,y) to the point (x,y+distance) or (x+distance,y).
 741:    * @param x x coordinate.
 742:    * @param y y coordinate.
 743:    * @param neg True if opposite-directed intersections should cancel, 
 744:    * false to sum all intersections.
 745:    * @param useYaxis Use the Y axis, false uses the X axis.
 746:    * @param distance Interval from (x,y) on the selected axis to find 
 747:    * intersections.
 748:    */
 749:   private int evaluateCrossings(double x, double y, boolean neg,
 750:                                 boolean useYaxis, double distance)
 751:   {
 752:     float cx = 0.0f;
 753:     float cy = 0.0f;
 754:     float firstx = 0.0f;
 755:     float firsty = 0.0f;
 756: 
 757:     int negative = (neg) ? -1 : 1;
 758:     double x0;
 759:     double x1;
 760:     double x2;
 761:     double x3;
 762:     double y0;
 763:     double y1;
 764:     double y2;
 765:     double y3;
 766:     double[] r = new double[4];
 767:     int nRoots;
 768:     double epsilon = 0.0;
 769:     int pos = 0;
 770:     int windingNumber = 0;
 771:     boolean pathStarted = false;
 772: 
 773:     if (index == 0)
 774:       return (0);
 775:     if (useYaxis)
 776:       {
 777:     float[] swap1;
 778:     swap1 = ypoints;
 779:     ypoints = xpoints;
 780:     xpoints = swap1;
 781:     double swap2;
 782:     swap2 = y;
 783:     y = x;
 784:     x = swap2;
 785:       }
 786: 
 787:     /* Get a value which is hopefully small but not insignificant relative
 788:      the path. */
 789:     epsilon = ypoints[0] * 1E-7;
 790: 
 791:     if(epsilon == 0) 
 792:       epsilon = 1E-7;
 793: 
 794:     pos = 0;
 795:     while (pos < index)
 796:       {
 797:     switch (types[pos])
 798:       {
 799:       case PathIterator.SEG_MOVETO:
 800:         if (pathStarted) // close old path
 801:           {
 802:         x0 = cx;
 803:         y0 = cy;
 804:         x1 = firstx;
 805:         y1 = firsty;
 806: 
 807:         if (y0 == 0.0)
 808:           y0 -= epsilon;
 809:         if (y1 == 0.0)
 810:           y1 -= epsilon;
 811:         if (Line2D.linesIntersect(x0, y0, x1, y1, 
 812:                       epsilon, 0.0, distance, 0.0))
 813:           windingNumber += (y1 < y0) ? 1 : negative;
 814: 
 815:         cx = firstx;
 816:         cy = firsty;
 817:           }
 818:         cx = firstx = xpoints[pos] - (float) x;
 819:         cy = firsty = ypoints[pos++] - (float) y;
 820:         pathStarted = true;
 821:         break;
 822:       case PathIterator.SEG_CLOSE:
 823:         x0 = cx;
 824:         y0 = cy;
 825:         x1 = firstx;
 826:         y1 = firsty;
 827: 
 828:         if (y0 == 0.0)
 829:           y0 -= epsilon;
 830:         if (y1 == 0.0)
 831:           y1 -= epsilon;
 832:         if (Line2D.linesIntersect(x0, y0, x1, y1, 
 833:                       epsilon, 0.0, distance, 0.0))
 834:           windingNumber += (y1 < y0) ? 1 : negative;
 835: 
 836:         cx = firstx;
 837:         cy = firsty;
 838:         pos++;
 839:         pathStarted = false;
 840:         break;
 841:       case PathIterator.SEG_LINETO:
 842:         x0 = cx;
 843:         y0 = cy;
 844:         x1 = xpoints[pos] - (float) x;
 845:         y1 = ypoints[pos++] - (float) y;
 846: 
 847:         if (y0 == 0.0)
 848:           y0 -= epsilon;
 849:         if (y1 == 0.0)
 850:           y1 -= epsilon;
 851:         if (Line2D.linesIntersect(x0, y0, x1, y1, 
 852:                       epsilon, 0.0, distance, 0.0))
 853:           windingNumber += (y1 < y0) ? 1 : negative;
 854: 
 855:         cx = xpoints[pos - 1] - (float) x;
 856:         cy = ypoints[pos - 1] - (float) y;
 857:         break;
 858:       case PathIterator.SEG_QUADTO:
 859:         x0 = cx;
 860:         y0 = cy;
 861:         x1 = xpoints[pos] - x;
 862:         y1 = ypoints[pos++] - y;
 863:         x2 = xpoints[pos] - x;
 864:         y2 = ypoints[pos++] - y;
 865: 
 866:         /* check if curve may intersect X+ axis. */
 867:         if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0)
 868:             && (y0 * y1 <= 0 || y1 * y2 <= 0))
 869:           {
 870:         if (y0 == 0.0)
 871:           y0 -= epsilon;
 872:         if (y2 == 0.0)
 873:           y2 -= epsilon;
 874: 
 875:         r[0] = y0;
 876:         r[1] = 2 * (y1 - y0);
 877:         r[2] = (y2 - 2 * y1 + y0);
 878: 
 879:         /* degenerate roots (=tangent points) do not
 880:            contribute to the winding number. */
 881:         if ((nRoots = QuadCurve2D.solveQuadratic(r)) == 2)
 882:           for (int i = 0; i < nRoots; i++)
 883:             {
 884:               float t = (float) r[i];
 885:               if (t > 0.0f && t < 1.0f)
 886:                 {
 887:               double crossing = t * t * (x2 - 2 * x1 + x0)
 888:                                 + 2 * t * (x1 - x0) + x0;
 889:               if (crossing >= 0.0 && crossing <= distance)
 890:                 windingNumber += (2 * t * (y2 - 2 * y1 + y0)
 891:                                + 2 * (y1 - y0) < 0) ? 1 : negative;
 892:                 }
 893:             }
 894:           }
 895: 
 896:         cx = xpoints[pos - 1] - (float) x;
 897:         cy = ypoints[pos - 1] - (float) y;
 898:         break;
 899:       case PathIterator.SEG_CUBICTO:
 900:         x0 = cx;
 901:         y0 = cy;
 902:         x1 = xpoints[pos] - x;
 903:         y1 = ypoints[pos++] - y;
 904:         x2 = xpoints[pos] - x;
 905:         y2 = ypoints[pos++] - y;
 906:         x3 = xpoints[pos] - x;
 907:         y3 = ypoints[pos++] - y;
 908: 
 909:         /* check if curve may intersect X+ axis. */
 910:         if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0 || x3 > 0.0)
 911:             && (y0 * y1 <= 0 || y1 * y2 <= 0 || y2 * y3 <= 0))
 912:           {
 913:         if (y0 == 0.0)
 914:           y0 -= epsilon;
 915:         if (y3 == 0.0)
 916:           y3 -= epsilon;
 917: 
 918:         r[0] = y0;
 919:         r[1] = 3 * (y1 - y0);
 920:         r[2] = 3 * (y2 + y0 - 2 * y1);
 921:         r[3] = y3 - 3 * y2 + 3 * y1 - y0;
 922: 
 923:         if ((nRoots = CubicCurve2D.solveCubic(r)) != 0)
 924:           for (int i = 0; i < nRoots; i++)
 925:             {
 926:               float t = (float) r[i];
 927:               if (t > 0.0 && t < 1.0)
 928:                 {
 929:               double crossing = -(t * t * t) * (x0 - 3 * x1
 930:                                 + 3 * x2 - x3)
 931:                                 + 3 * t * t * (x0 - 2 * x1 + x2)
 932:                                 + 3 * t * (x1 - x0) + x0;
 933:               if (crossing >= 0 && crossing <= distance)
 934:                 windingNumber += (3 * t * t * (y3 + 3 * y1
 935:                                  - 3 * y2 - y0)
 936:                                  + 6 * t * (y0 - 2 * y1 + y2)
 937:                                + 3 * (y1 - y0) < 0) ? 1 : negative;
 938:                 }
 939:             }
 940:           }
 941: 
 942:         cx = xpoints[pos - 1] - (float) x;
 943:         cy = ypoints[pos - 1] - (float) y;
 944:         break;
 945:       }
 946:       }
 947: 
 948:     // swap coordinates back
 949:     if (useYaxis)
 950:       {
 951:     float[] swap;
 952:     swap = ypoints;
 953:     ypoints = xpoints;
 954:     xpoints = swap;
 955:       }
 956:     return (windingNumber);
 957:   }
 958: } // class GeneralPath