Source for java.awt.geom.GeneralPath

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