Source for java.awt.geom.Area

   1: /* Area.java -- represents a shape built by constructive area geometry
   2:    Copyright (C) 2002, 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: package java.awt.geom;
  39: 
  40: import java.awt.Rectangle;
  41: import java.awt.Shape;
  42: import java.util.Vector;
  43: 
  44: 
  45: /**
  46:  * The Area class represents any area for the purpose of
  47:  * Constructive Area Geometry (CAG) manipulations. CAG manipulations
  48:  * work as an area-wise form of boolean logic, where the basic operations are:
  49:  * <P><li>Add (in boolean algebra: A <B>or</B> B)<BR>
  50:  * <li>Subtract (in boolean algebra: A <B>and</B> (<B>not</B> B) )<BR>
  51:  * <li>Intersect (in boolean algebra: A <B>and</B> B)<BR>
  52:  * <li>Exclusive Or <BR>
  53:  * <img src="doc-files/Area-1.png" width="342" height="302"
  54:  * alt="Illustration of CAG operations" /><BR>
  55:  * Above is an illustration of the CAG operations on two ring shapes.<P>
  56:  *
  57:  * The contains and intersects() methods are also more accurate than the
  58:  * specification of #Shape requires.<P>
  59:  *
  60:  * Please note that constructing an Area can be slow
  61:  * (Self-intersection resolving is proportional to the square of
  62:  * the number of segments).<P>
  63:  * @see #add(Area)
  64:  * @see #subtract(Area)
  65:  * @see #intersect(Area)
  66:  * @see #exclusiveOr(Area)
  67:  *
  68:  * @author Sven de Marothy (sven@physto.se)
  69:  *
  70:  * @since 1.2
  71:  * @status Works, but could be faster and more reliable.
  72:  */
  73: public class Area implements Shape, Cloneable
  74: {
  75:   /**
  76:    * General numerical precision
  77:    */
  78:   private static final double EPSILON = 1E-11;
  79: 
  80:   /**
  81:    * recursive subdivision epsilon - (see getRecursionDepth)
  82:    */
  83:   private static final double RS_EPSILON = 1E-13;
  84: 
  85:   /**
  86:    * Snap distance - points within this distance are considered equal
  87:    */
  88:   private static final double PE_EPSILON = 1E-11;
  89: 
  90:   /**
  91:    * Segment vectors containing solid areas and holes
  92:    * This is package-private to avoid an accessor method.
  93:    */
  94:   Vector solids;
  95: 
  96:   /**
  97:    * Segment vectors containing solid areas and holes
  98:    * This is package-private to avoid an accessor method.
  99:    */
 100:   Vector holes;
 101: 
 102:   /**
 103:    * Vector (temporary) storing curve-curve intersections
 104:    */
 105:   private Vector cc_intersections;
 106: 
 107:   /**
 108:    * Winding rule WIND_NON_ZERO used, after construction,
 109:    * this is irrelevant.
 110:    */
 111:   private int windingRule;
 112: 
 113:   /**
 114:    * Constructs an empty Area
 115:    */
 116:   public Area()
 117:   {
 118:     solids = new Vector();
 119:     holes = new Vector();
 120:   }
 121: 
 122:   /**
 123:    * Constructs an Area from any given Shape. <P>
 124:    *
 125:    * If the Shape is self-intersecting, the created Area will consist
 126:    * of non-self-intersecting subpaths, and any inner paths which
 127:    * are found redundant in accordance with the Shape's winding rule
 128:    * will not be included.
 129:    * 
 130:    * @param s  the shape (<code>null</code> not permitted).
 131:    * 
 132:    * @throws NullPointerException if <code>s</code> is <code>null</code>.
 133:    */
 134:   public Area(Shape s)
 135:   {
 136:     this();
 137: 
 138:     Vector p = makeSegment(s);
 139: 
 140:     // empty path
 141:     if (p == null)
 142:       return;
 143: 
 144:     // delete empty paths
 145:     for (int i = 0; i < p.size(); i++)
 146:       if (((Segment) p.elementAt(i)).getSignedArea() == 0.0)
 147:     p.remove(i--);
 148: 
 149:     /*
 150:      * Resolve self intersecting paths into non-intersecting
 151:      * solids and holes.
 152:      * Algorithm is as follows:
 153:      * 1: Create nodes at all self intersections
 154:      * 2: Put all segments into a list
 155:      * 3: Grab a segment, follow it, change direction at each node,
 156:      *    removing segments from the list in the process
 157:      * 4: Repeat (3) until no segments remain in the list
 158:      * 5: Remove redundant paths and sort into solids and holes
 159:      */
 160:     Vector paths = new Vector();
 161:     Segment v;
 162: 
 163:     for (int i = 0; i < p.size(); i++)
 164:       {
 165:     Segment path = (Segment) p.elementAt(i);
 166:     createNodesSelf(path);
 167:       }
 168: 
 169:     if (p.size() > 1)
 170:       {
 171:     for (int i = 0; i < p.size() - 1; i++)
 172:       for (int j = i + 1; j < p.size(); j++)
 173:         {
 174:           Segment path1 = (Segment) p.elementAt(i);
 175:           Segment path2 = (Segment) p.elementAt(j);
 176:           createNodes(path1, path2);
 177:         }
 178:       }
 179: 
 180:     // we have intersecting points.
 181:     Vector segments = new Vector();
 182: 
 183:     for (int i = 0; i < p.size(); i++)
 184:       {
 185:     Segment path = v = (Segment) p.elementAt(i);
 186:     do
 187:       {
 188:         segments.add(v);
 189:         v = v.next;
 190:       }
 191:     while (v != path);
 192:       }
 193: 
 194:     paths = weilerAtherton(segments);
 195:     deleteRedundantPaths(paths);
 196:   }
 197: 
 198:   /**
 199:    * Performs an add (union) operation on this area with another Area.<BR>
 200:    * @param area - the area to be unioned with this one
 201:    */
 202:   public void add(Area area)
 203:   {
 204:     if (equals(area))
 205:       return;
 206:     if (area.isEmpty())
 207:       return;
 208: 
 209:     Area B = (Area) area.clone();
 210: 
 211:     Vector pathA = new Vector();
 212:     Vector pathB = new Vector();
 213:     pathA.addAll(solids);
 214:     pathA.addAll(holes);
 215:     pathB.addAll(B.solids);
 216:     pathB.addAll(B.holes);
 217: 
 218:     int nNodes = 0;
 219: 
 220:     for (int i = 0; i < pathA.size(); i++)
 221:       {
 222:     Segment a = (Segment) pathA.elementAt(i);
 223:     for (int j = 0; j < pathB.size(); j++)
 224:       {
 225:         Segment b = (Segment) pathB.elementAt(j);
 226:         nNodes += createNodes(a, b);
 227:       }
 228:       }
 229: 
 230:     Vector paths = new Vector();
 231:     Segment v;
 232: 
 233:     // we have intersecting points.
 234:     Vector segments = new Vector();
 235: 
 236:     // In a union operation, we keep all
 237:     // segments of A oustide B and all B outside A
 238:     for (int i = 0; i < pathA.size(); i++)
 239:       {
 240:     v = (Segment) pathA.elementAt(i);
 241:     Segment path = v;
 242:     do
 243:       {
 244:         if (v.isSegmentOutside(area))
 245:           segments.add(v);
 246:         v = v.next;
 247:       }
 248:     while (v != path);
 249:       }
 250: 
 251:     for (int i = 0; i < pathB.size(); i++)
 252:       {
 253:     v = (Segment) pathB.elementAt(i);
 254:     Segment path = v;
 255:     do
 256:       {
 257:         if (v.isSegmentOutside(this))
 258:           segments.add(v);
 259:         v = v.next;
 260:       }
 261:     while (v != path);
 262:       }
 263: 
 264:     paths = weilerAtherton(segments);
 265:     deleteRedundantPaths(paths);
 266:   }
 267: 
 268:   /**
 269:    * Performs a subtraction operation on this Area.<BR>
 270:    * @param area the area to be subtracted from this area.
 271:    * @throws NullPointerException if <code>area</code> is <code>null</code>.
 272:    */
 273:   public void subtract(Area area)
 274:   {
 275:     if (isEmpty() || area.isEmpty())
 276:       return;
 277: 
 278:     if (equals(area))
 279:       {
 280:     reset();
 281:     return;
 282:       }
 283: 
 284:     Vector pathA = new Vector();
 285:     Area B = (Area) area.clone();
 286:     pathA.addAll(solids);
 287:     pathA.addAll(holes);
 288: 
 289:     // reverse the directions of B paths.
 290:     setDirection(B.holes, true);
 291:     setDirection(B.solids, false);
 292: 
 293:     Vector pathB = new Vector();
 294:     pathB.addAll(B.solids);
 295:     pathB.addAll(B.holes);
 296: 
 297:     int nNodes = 0;
 298: 
 299:     // create nodes
 300:     for (int i = 0; i < pathA.size(); i++)
 301:       {
 302:     Segment a = (Segment) pathA.elementAt(i);
 303:     for (int j = 0; j < pathB.size(); j++)
 304:       {
 305:         Segment b = (Segment) pathB.elementAt(j);
 306:         nNodes += createNodes(a, b);
 307:       }
 308:       }
 309: 
 310:     Vector paths = new Vector();
 311: 
 312:     // we have intersecting points.
 313:     Vector segments = new Vector();
 314: 
 315:     // In a subtraction operation, we keep all
 316:     // segments of A oustide B and all B within A
 317:     // We outsideness-test only one segment in each path
 318:     // and the segments before and after any node
 319:     for (int i = 0; i < pathA.size(); i++)
 320:       {
 321:     Segment v = (Segment) pathA.elementAt(i);
 322:     Segment path = v;
 323:     if (v.isSegmentOutside(area) && v.node == null)
 324:       segments.add(v);
 325:     boolean node = false;
 326:     do
 327:       {
 328:         if ((v.node != null || node))
 329:           {
 330:         node = (v.node != null);
 331:         if (v.isSegmentOutside(area))
 332:           segments.add(v);
 333:           }
 334:         v = v.next;
 335:       }
 336:     while (v != path);
 337:       }
 338: 
 339:     for (int i = 0; i < pathB.size(); i++)
 340:       {
 341:     Segment v = (Segment) pathB.elementAt(i);
 342:     Segment path = v;
 343:     if (! v.isSegmentOutside(this) && v.node == null)
 344:       segments.add(v);
 345:     v = v.next;
 346:     boolean node = false;
 347:     do
 348:       {
 349:         if ((v.node != null || node))
 350:           {
 351:         node = (v.node != null);
 352:         if (! v.isSegmentOutside(this))
 353:           segments.add(v);
 354:           }
 355:         v = v.next;
 356:       }
 357:     while (v != path);
 358:       }
 359: 
 360:     paths = weilerAtherton(segments);
 361:     deleteRedundantPaths(paths);
 362:   }
 363: 
 364:   /**
 365:    * Performs an intersection operation on this Area.<BR>
 366:    * @param area - the area to be intersected with this area.
 367:    * @throws NullPointerException if <code>area</code> is <code>null</code>.
 368:    */
 369:   public void intersect(Area area)
 370:   {
 371:     if (isEmpty() || area.isEmpty())
 372:       {
 373:     reset();
 374:     return;
 375:       }
 376:     if (equals(area))
 377:       return;
 378: 
 379:     Vector pathA = new Vector();
 380:     Area B = (Area) area.clone();
 381:     pathA.addAll(solids);
 382:     pathA.addAll(holes);
 383: 
 384:     Vector pathB = new Vector();
 385:     pathB.addAll(B.solids);
 386:     pathB.addAll(B.holes);
 387: 
 388:     int nNodes = 0;
 389: 
 390:     // create nodes
 391:     for (int i = 0; i < pathA.size(); i++)
 392:       {
 393:     Segment a = (Segment) pathA.elementAt(i);
 394:     for (int j = 0; j < pathB.size(); j++)
 395:       {
 396:         Segment b = (Segment) pathB.elementAt(j);
 397:         nNodes += createNodes(a, b);
 398:       }
 399:       }
 400: 
 401:     Vector paths = new Vector();
 402: 
 403:     // we have intersecting points.
 404:     Vector segments = new Vector();
 405: 
 406:     // In an intersection operation, we keep all
 407:     // segments of A within B and all B within A
 408:     // (The rest must be redundant)
 409:     // We outsideness-test only one segment in each path
 410:     // and the segments before and after any node
 411:     for (int i = 0; i < pathA.size(); i++)
 412:       {
 413:     Segment v = (Segment) pathA.elementAt(i);
 414:     Segment path = v;
 415:     if (! v.isSegmentOutside(area) && v.node == null)
 416:       segments.add(v);
 417:     boolean node = false;
 418:     do
 419:       {
 420:         if ((v.node != null || node))
 421:           {
 422:         node = (v.node != null);
 423:         if (! v.isSegmentOutside(area))
 424:           segments.add(v);
 425:           }
 426:         v = v.next;
 427:       }
 428:     while (v != path);
 429:       }
 430: 
 431:     for (int i = 0; i < pathB.size(); i++)
 432:       {
 433:     Segment v = (Segment) pathB.elementAt(i);
 434:     Segment path = v;
 435:     if (! v.isSegmentOutside(this) && v.node == null)
 436:       segments.add(v);
 437:     v = v.next;
 438:     boolean node = false;
 439:     do
 440:       {
 441:         if ((v.node != null || node))
 442:           {
 443:         node = (v.node != null);
 444:         if (! v.isSegmentOutside(this))
 445:           segments.add(v);
 446:           }
 447:         v = v.next;
 448:       }
 449:     while (v != path);
 450:       }
 451: 
 452:     paths = weilerAtherton(segments);
 453:     deleteRedundantPaths(paths);
 454:   }
 455: 
 456:   /**
 457:    * Performs an exclusive-or operation on this Area.<BR>
 458:    * @param area - the area to be XORed with this area.
 459:    * @throws NullPointerException if <code>area</code> is <code>null</code>.
 460:    */
 461:   public void exclusiveOr(Area area)
 462:   {
 463:     if (area.isEmpty())
 464:       return;
 465: 
 466:     if (isEmpty())
 467:       {
 468:     Area B = (Area) area.clone();
 469:     solids = B.solids;
 470:     holes = B.holes;
 471:     return;
 472:       }
 473:     if (equals(area))
 474:       {
 475:     reset();
 476:     return;
 477:       }
 478: 
 479:     Vector pathA = new Vector();
 480: 
 481:     Area B = (Area) area.clone();
 482:     Vector pathB = new Vector();
 483:     pathA.addAll(solids);
 484:     pathA.addAll(holes);
 485: 
 486:     // reverse the directions of B paths.
 487:     setDirection(B.holes, true);
 488:     setDirection(B.solids, false);
 489:     pathB.addAll(B.solids);
 490:     pathB.addAll(B.holes);
 491: 
 492:     int nNodes = 0;
 493: 
 494:     for (int i = 0; i < pathA.size(); i++)
 495:       {
 496:     Segment a = (Segment) pathA.elementAt(i);
 497:     for (int j = 0; j < pathB.size(); j++)
 498:       {
 499:         Segment b = (Segment) pathB.elementAt(j);
 500:         nNodes += createNodes(a, b);
 501:       }
 502:       }
 503: 
 504:     Vector paths = new Vector();
 505:     Segment v;
 506: 
 507:     // we have intersecting points.
 508:     Vector segments = new Vector();
 509: 
 510:     // In an XOR operation, we operate on all segments
 511:     for (int i = 0; i < pathA.size(); i++)
 512:       {
 513:     v = (Segment) pathA.elementAt(i);
 514:     Segment path = v;
 515:     do
 516:       {
 517:         segments.add(v);
 518:         v = v.next;
 519:       }
 520:     while (v != path);
 521:       }
 522: 
 523:     for (int i = 0; i < pathB.size(); i++)
 524:       {
 525:     v = (Segment) pathB.elementAt(i);
 526:     Segment path = v;
 527:     do
 528:       {
 529:         segments.add(v);
 530:         v = v.next;
 531:       }
 532:     while (v != path);
 533:       }
 534: 
 535:     paths = weilerAtherton(segments);
 536:     deleteRedundantPaths(paths);
 537:   }
 538: 
 539:   /**
 540:    * Clears the Area object, creating an empty area.
 541:    */
 542:   public void reset()
 543:   {
 544:     solids = new Vector();
 545:     holes = new Vector();
 546:   }
 547: 
 548:   /**
 549:    * Returns whether this area encloses any area.
 550:    * @return true if the object encloses any area.
 551:    */
 552:   public boolean isEmpty()
 553:   {
 554:     if (solids.size() == 0)
 555:       return true;
 556: 
 557:     double totalArea = 0;
 558:     for (int i = 0; i < solids.size(); i++)
 559:       totalArea += Math.abs(((Segment) solids.elementAt(i)).getSignedArea());
 560:     for (int i = 0; i < holes.size(); i++)
 561:       totalArea -= Math.abs(((Segment) holes.elementAt(i)).getSignedArea());
 562:     if (totalArea <= EPSILON)
 563:       return true;
 564: 
 565:     return false;
 566:   }
 567: 
 568:   /**
 569:    * Determines whether the Area consists entirely of line segments
 570:    * @return true if the Area lines-only, false otherwise
 571:    */
 572:   public boolean isPolygonal()
 573:   {
 574:     for (int i = 0; i < holes.size(); i++)
 575:       if (! ((Segment) holes.elementAt(i)).isPolygonal())
 576:     return false;
 577:     for (int i = 0; i < solids.size(); i++)
 578:       if (! ((Segment) solids.elementAt(i)).isPolygonal())
 579:     return false;
 580:     return true;
 581:   }
 582: 
 583:   /**
 584:    * Determines if the Area is rectangular.<P>
 585:    *
 586:    * This is strictly qualified. An area is considered rectangular if:<BR>
 587:    * <li>It consists of a single polygonal path.<BR>
 588:    * <li>It is oriented parallel/perpendicular to the xy axis<BR>
 589:    * <li>It must be exactly rectangular, i.e. small errors induced by
 590:    * transformations may cause a false result, although the area is
 591:    * visibly rectangular.<P>
 592:    * @return true if the above criteria are met, false otherwise
 593:    */
 594:   public boolean isRectangular()
 595:   {
 596:     if (isEmpty())
 597:       return true;
 598: 
 599:     if (holes.size() != 0 || solids.size() != 1)
 600:       return false;
 601: 
 602:     Segment path = (Segment) solids.elementAt(0);
 603:     if (! path.isPolygonal())
 604:       return false;
 605: 
 606:     int nCorners = 0;
 607:     Segment s = path;
 608:     do
 609:       {
 610:     Segment s2 = s.next;
 611:     double d1 = (s.P2.getX() - s.P1.getX())*(s2.P2.getX() - s2.P1.getX())/
 612:         ((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2)));
 613:     double d2 = (s.P2.getY() - s.P1.getY())*(s2.P2.getY() - s2.P1.getY())/ 
 614:         ((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2)));
 615:     double dotproduct = d1 + d2;
 616: 
 617:     // For some reason, only rectangles on the XY axis count.
 618:     if (d1 != 0 && d2 != 0)
 619:       return false;
 620: 
 621:     if (Math.abs(dotproduct) == 0) // 90 degree angle
 622:       nCorners++;
 623:     else if ((Math.abs(1.0 - dotproduct) > 0)) // 0 degree angle?
 624:       return false; // if not, return false
 625: 
 626:     s = s.next;
 627:       }
 628:     while (s != path);
 629: 
 630:     return nCorners == 4;
 631:   }
 632: 
 633:   /**
 634:    * Returns whether the Area consists of more than one simple
 635:    * (non self-intersecting) subpath.
 636:    *
 637:    * @return true if the Area consists of none or one simple subpath,
 638:    * false otherwise.
 639:    */
 640:   public boolean isSingular()
 641:   {
 642:     return (holes.size() == 0 && solids.size() <= 1);
 643:   }
 644: 
 645:   /**
 646:    * Returns the bounding box of the Area.<P> Unlike the CubicCurve2D and
 647:    * QuadraticCurve2D classes, this method will return the tightest possible
 648:    * bounding box, evaluating the extreme points of each curved segment.<P>
 649:    * @return the bounding box
 650:    */
 651:   public Rectangle2D getBounds2D()
 652:   {
 653:     if (solids.size() == 0)
 654:       return new Rectangle2D.Double(0.0, 0.0, 0.0, 0.0);
 655: 
 656:     double xmin;
 657:     double xmax;
 658:     double ymin;
 659:     double ymax;
 660:     xmin = xmax = ((Segment) solids.elementAt(0)).P1.getX();
 661:     ymin = ymax = ((Segment) solids.elementAt(0)).P1.getY();
 662: 
 663:     for (int path = 0; path < solids.size(); path++)
 664:       {
 665:     Rectangle2D r = ((Segment) solids.elementAt(path)).getPathBounds();
 666:     xmin = Math.min(r.getMinX(), xmin);
 667:     ymin = Math.min(r.getMinY(), ymin);
 668:     xmax = Math.max(r.getMaxX(), xmax);
 669:     ymax = Math.max(r.getMaxY(), ymax);
 670:       }
 671: 
 672:     return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
 673:   }
 674: 
 675:   /**
 676:    * Returns the bounds of this object in Rectangle format.
 677:    * Please note that this may lead to loss of precision.
 678:    * 
 679:    * @return The bounds.
 680:    * @see #getBounds2D()
 681:    */
 682:   public Rectangle getBounds()
 683:   {
 684:     return getBounds2D().getBounds();
 685:   }
 686: 
 687:   /**
 688:    * Create a new area of the same run-time type with the same contents as
 689:    * this one.
 690:    *
 691:    * @return the clone
 692:    */
 693:   public Object clone()
 694:   {
 695:     try
 696:       {
 697:     Area clone = new Area();
 698:     for (int i = 0; i < solids.size(); i++)
 699:       clone.solids.add(((Segment) solids.elementAt(i)).cloneSegmentList());
 700:     for (int i = 0; i < holes.size(); i++)
 701:       clone.holes.add(((Segment) holes.elementAt(i)).cloneSegmentList());
 702:     return clone;
 703:       }
 704:     catch (CloneNotSupportedException e)
 705:       {
 706:     throw (Error) new InternalError().initCause(e); // Impossible
 707:       }
 708:   }
 709: 
 710:   /**
 711:    * Compares two Areas.
 712:    * 
 713:    * @param area  the area to compare against this area (<code>null</code>
 714:    *              permitted).
 715:    * @return <code>true</code> if the areas are equal, and <code>false</code>
 716:    *         otherwise.
 717:    */
 718:   public boolean equals(Area area)
 719:   {
 720:     if (area == null)
 721:       return false;
 722: 
 723:     if (! getBounds2D().equals(area.getBounds2D()))
 724:       return false;
 725: 
 726:     if (solids.size() != area.solids.size()
 727:         || holes.size() != area.holes.size())
 728:       return false;
 729: 
 730:     Vector pathA = new Vector();
 731:     pathA.addAll(solids);
 732:     pathA.addAll(holes);
 733:     Vector pathB = new Vector();
 734:     pathB.addAll(area.solids);
 735:     pathB.addAll(area.holes);
 736: 
 737:     int nPaths = pathA.size();
 738:     boolean[][] match = new boolean[2][nPaths];
 739: 
 740:     for (int i = 0; i < nPaths; i++)
 741:       {
 742:     for (int j = 0; j < nPaths; j++)
 743:       {
 744:         Segment p1 = (Segment) pathA.elementAt(i);
 745:         Segment p2 = (Segment) pathB.elementAt(j);
 746:         if (! match[0][i] && ! match[1][j])
 747:           if (p1.pathEquals(p2))
 748:         match[0][i] = match[1][j] = true;
 749:       }
 750:       }
 751: 
 752:     boolean result = true;
 753:     for (int i = 0; i < nPaths; i++)
 754:       result = result && match[0][i] && match[1][i];
 755:     return result;
 756:   }
 757: 
 758:   /**
 759:    * Transforms this area by the AffineTransform at.
 760:    * 
 761:    * @param at  the transform.
 762:    */
 763:   public void transform(AffineTransform at)
 764:   {
 765:     for (int i = 0; i < solids.size(); i++)
 766:       ((Segment) solids.elementAt(i)).transformSegmentList(at);
 767:     for (int i = 0; i < holes.size(); i++)
 768:       ((Segment) holes.elementAt(i)).transformSegmentList(at);
 769: 
 770:     // Note that the orientation is not invariant under inversion
 771:     if ((at.getType() & AffineTransform.TYPE_FLIP) != 0)
 772:       {
 773:     setDirection(holes, false);
 774:     setDirection(solids, true);
 775:       }
 776:   }
 777: 
 778:   /**
 779:    * Returns a new Area equal to this one, transformed
 780:    * by the AffineTransform at.
 781:    * @param at  the transform.
 782:    * @return the transformed area
 783:    * @throws NullPointerException if <code>at</code> is <code>null</code>.
 784:    */
 785:   public Area createTransformedArea(AffineTransform at)
 786:   {
 787:     Area a = (Area) clone();
 788:     a.transform(at);
 789:     return a;
 790:   }
 791: 
 792:   /**
 793:    * Determines if the point (x,y) is contained within this Area.
 794:    *
 795:    * @param x the x-coordinate of the point.
 796:    * @param y the y-coordinate of the point.
 797:    * @return true if the point is contained, false otherwise.
 798:    */
 799:   public boolean contains(double x, double y)
 800:   {
 801:     int n = 0;
 802:     for (int i = 0; i < solids.size(); i++)
 803:       if (((Segment) solids.elementAt(i)).contains(x, y))
 804:     n++;
 805: 
 806:     for (int i = 0; i < holes.size(); i++)
 807:       if (((Segment) holes.elementAt(i)).contains(x, y))
 808:     n--;
 809: 
 810:     return (n != 0);
 811:   }
 812: 
 813:   /**
 814:    * Determines if the Point2D p is contained within this Area.
 815:    *
 816:    * @param p the point.
 817:    * @return <code>true</code> if the point is contained, <code>false</code> 
 818:    *         otherwise.
 819:    * @throws NullPointerException if <code>p</code> is <code>null</code>.
 820:    */
 821:   public boolean contains(Point2D p)
 822:   {
 823:     return contains(p.getX(), p.getY());
 824:   }
 825: 
 826:   /**
 827:    * Determines if the rectangle specified by (x,y) as the upper-left
 828:    * and with width w and height h is completely contained within this Area,
 829:    * returns false otherwise.<P>
 830:    *
 831:    * This method should always produce the correct results, unlike for other
 832:    * classes in geom.
 833:    * 
 834:    * @param x the x-coordinate of the rectangle.
 835:    * @param y the y-coordinate of the rectangle.
 836:    * @param w the width of the the rectangle.
 837:    * @param h the height of the rectangle.
 838:    * @return <code>true</code> if the rectangle is considered contained
 839:    */
 840:   public boolean contains(double x, double y, double w, double h)
 841:   {
 842:     LineSegment[] l = new LineSegment[4];
 843:     l[0] = new LineSegment(x, y, x + w, y);
 844:     l[1] = new LineSegment(x, y + h, x + w, y + h);
 845:     l[2] = new LineSegment(x, y, x, y + h);
 846:     l[3] = new LineSegment(x + w, y, x + w, y + h);
 847: 
 848:     // Since every segment in the area must a contour
 849:     // between inside/outside segments, ANY intersection
 850:     // will mean the rectangle is not entirely contained.
 851:     for (int i = 0; i < 4; i++)
 852:       {
 853:     for (int path = 0; path < solids.size(); path++)
 854:       {
 855:         Segment v;
 856:         Segment start;
 857:         start = v = (Segment) solids.elementAt(path);
 858:         do
 859:           {
 860:         if (l[i].hasIntersections(v))
 861:           return false;
 862:         v = v.next;
 863:           }
 864:         while (v != start);
 865:       }
 866:     for (int path = 0; path < holes.size(); path++)
 867:       {
 868:         Segment v;
 869:         Segment start;
 870:         start = v = (Segment) holes.elementAt(path);
 871:         do
 872:           {
 873:         if (l[i].hasIntersections(v))
 874:           return false;
 875:         v = v.next;
 876:           }
 877:         while (v != start);
 878:       }
 879:       }
 880: 
 881:     // Is any point inside?
 882:     if (! contains(x, y))
 883:       return false;
 884: 
 885:     // Final hoop: Is the rectangle non-intersecting and inside, 
 886:     // but encloses a hole?
 887:     Rectangle2D r = new Rectangle2D.Double(x, y, w, h);
 888:     for (int path = 0; path < holes.size(); path++)
 889:       if (! ((Segment) holes.elementAt(path)).isSegmentOutside(r))
 890:         return false;
 891: 
 892:     return true;
 893:   }
 894: 
 895:   /**
 896:    * Determines if the Rectangle2D specified by r is completely contained
 897:    * within this Area, returns false otherwise.<P>
 898:    *
 899:    * This method should always produce the correct results, unlike for other
 900:    * classes in geom.
 901:    * 
 902:    * @param r the rectangle.
 903:    * @return <code>true</code> if the rectangle is considered contained
 904:    * 
 905:    * @throws NullPointerException if <code>r</code> is <code>null</code>.
 906:    */
 907:   public boolean contains(Rectangle2D r)
 908:   {
 909:     return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
 910:   }
 911: 
 912:   /**
 913:    * Determines if the rectangle specified by (x,y) as the upper-left
 914:    * and with width w and height h intersects any part of this Area.
 915:    * 
 916:    * @param x  the x-coordinate for the rectangle.
 917:    * @param y  the y-coordinate for the rectangle.
 918:    * @param w  the width of the rectangle.
 919:    * @param h  the height of the rectangle.
 920:    * @return <code>true</code> if the rectangle intersects the area, 
 921:    *         <code>false</code> otherwise.
 922:    */
 923:   public boolean intersects(double x, double y, double w, double h)
 924:   {
 925:     if (solids.size() == 0)
 926:       return false;
 927: 
 928:     LineSegment[] l = new LineSegment[4];
 929:     l[0] = new LineSegment(x, y, x + w, y);
 930:     l[1] = new LineSegment(x, y + h, x + w, y + h);
 931:     l[2] = new LineSegment(x, y, x, y + h);
 932:     l[3] = new LineSegment(x + w, y, x + w, y + h);
 933: 
 934:     // Return true on any intersection
 935:     for (int i = 0; i < 4; i++)
 936:       {
 937:     for (int path = 0; path < solids.size(); path++)
 938:       {
 939:         Segment v;
 940:         Segment start;
 941:         start = v = (Segment) solids.elementAt(path);
 942:         do
 943:           {
 944:         if (l[i].hasIntersections(v))
 945:           return true;
 946:         v = v.next;
 947:           }
 948:         while (v != start);
 949:       }
 950:     for (int path = 0; path < holes.size(); path++)
 951:       {
 952:         Segment v;
 953:         Segment start;
 954:         start = v = (Segment) holes.elementAt(path);
 955:         do
 956:           {
 957:         if (l[i].hasIntersections(v))
 958:           return true;
 959:         v = v.next;
 960:           }
 961:         while (v != start);
 962:       }
 963:       }
 964: 
 965:     // Non-intersecting, Is any point inside?
 966:     if (contains(x + w * 0.5, y + h * 0.5))
 967:       return true;
 968: 
 969:     // What if the rectangle encloses the whole shape?
 970:     Point2D p = ((Segment) solids.elementAt(0)).getMidPoint();
 971:     if ((new Rectangle2D.Double(x, y, w, h)).contains(p))
 972:       return true;
 973:     return false;
 974:   }
 975: 
 976:   /**
 977:    * Determines if the Rectangle2D specified by r intersects any
 978:    * part of this Area.
 979:    * @param r  the rectangle to test intersection with (<code>null</code>
 980:    *           not permitted).
 981:    * @return <code>true</code> if the rectangle intersects the area, 
 982:    *         <code>false</code> otherwise.
 983:    * @throws NullPointerException if <code>r</code> is <code>null</code>.
 984:    */
 985:   public boolean intersects(Rectangle2D r)
 986:   {
 987:     return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
 988:   }
 989: 
 990:   /**
 991:    * Returns a PathIterator object defining the contour of this Area,
 992:    * transformed by at.
 993:    * 
 994:    * @param at  the transform.
 995:    * @return A path iterator.
 996:    */
 997:   public PathIterator getPathIterator(AffineTransform at)
 998:   {
 999:     return (new AreaIterator(at));
1000:   }
1001: 
1002:   /**
1003:    * Returns a flattened PathIterator object defining the contour of this
1004:    * Area, transformed by at and with a defined flatness.
1005:    * 
1006:    * @param at  the transform.
1007:    * @param flatness the flatness.
1008:    * @return A path iterator.
1009:    */
1010:   public PathIterator getPathIterator(AffineTransform at, double flatness)
1011:   {
1012:     return new FlatteningPathIterator(getPathIterator(at), flatness);
1013:   }
1014: 
1015:   //---------------------------------------------------------------------
1016:   // Non-public methods and classes 
1017: 
1018:   /**
1019:    * Private pathiterator object.
1020:    */
1021:   private class AreaIterator implements PathIterator
1022:   {
1023:     private Vector segments;
1024:     private int index;
1025:     private AffineTransform at;
1026: 
1027:     // Simple compound type for segments
1028:     class IteratorSegment
1029:     {
1030:       int type;
1031:       double[] coords;
1032: 
1033:       IteratorSegment()
1034:       {
1035:     coords = new double[6];
1036:       }
1037:     }
1038: 
1039:     /**
1040:      * The contructor here does most of the work,
1041:      * creates a vector of IteratorSegments, which can
1042:      * readily be returned
1043:      */
1044:     public AreaIterator(AffineTransform at)
1045:     {
1046:       this.at = at;
1047:       index = 0;
1048:       segments = new Vector();
1049:       Vector allpaths = new Vector();
1050:       allpaths.addAll(solids);
1051:       allpaths.addAll(holes);
1052: 
1053:       for (int i = 0; i < allpaths.size(); i++)
1054:         {
1055:       Segment v = (Segment) allpaths.elementAt(i);
1056:       Segment start = v;
1057: 
1058:       IteratorSegment is = new IteratorSegment();
1059:       is.type = SEG_MOVETO;
1060:       is.coords[0] = start.P1.getX();
1061:       is.coords[1] = start.P1.getY();
1062:       segments.add(is);
1063: 
1064:       do
1065:         {
1066:           is = new IteratorSegment();
1067:           is.type = v.pathIteratorFormat(is.coords);
1068:           segments.add(is);
1069:           v = v.next;
1070:         }
1071:       while (v != start);
1072: 
1073:       is = new IteratorSegment();
1074:       is.type = SEG_CLOSE;
1075:       segments.add(is);
1076:         }
1077:     }
1078: 
1079:     public int currentSegment(double[] coords)
1080:     {
1081:       IteratorSegment s = (IteratorSegment) segments.elementAt(index);
1082:       if (at != null)
1083:     at.transform(s.coords, 0, coords, 0, 3);
1084:       else
1085:     for (int i = 0; i < 6; i++)
1086:       coords[i] = s.coords[i];
1087:       return (s.type);
1088:     }
1089: 
1090:     public int currentSegment(float[] coords)
1091:     {
1092:       IteratorSegment s = (IteratorSegment) segments.elementAt(index);
1093:       double[] d = new double[6];
1094:       if (at != null)
1095:         {
1096:       at.transform(s.coords, 0, d, 0, 3);
1097:       for (int i = 0; i < 6; i++)
1098:         coords[i] = (float) d[i];
1099:         }
1100:       else
1101:     for (int i = 0; i < 6; i++)
1102:       coords[i] = (float) s.coords[i];
1103:       return (s.type);
1104:     }
1105: 
1106:     // Note that the winding rule should not matter here,
1107:     // EVEN_ODD is chosen because it renders faster.
1108:     public int getWindingRule()
1109:     {
1110:       return (PathIterator.WIND_EVEN_ODD);
1111:     }
1112: 
1113:     public boolean isDone()
1114:     {
1115:       return (index >= segments.size());
1116:     }
1117: 
1118:     public void next()
1119:     {
1120:       index++;
1121:     }
1122:   }
1123: 
1124:   /**
1125:    * Performs the fundamental task of the Weiler-Atherton algorithm,
1126:    * traverse a list of segments, for each segment:
1127:    * Follow it, removing segments from the list and switching paths
1128:    * at each node. Do so until the starting segment is reached.
1129:    *
1130:    * Returns a Vector of the resulting paths.
1131:    */
1132:   private Vector weilerAtherton(Vector segments)
1133:   {
1134:     Vector paths = new Vector();
1135:     while (segments.size() > 0)
1136:       {
1137:     // Iterate over the path
1138:     Segment start = (Segment) segments.elementAt(0);
1139:     Segment s = start;
1140:     do
1141:       {
1142:         segments.remove(s);
1143:         if (s.node != null)
1144:           { // switch over
1145:         s.next = s.node;
1146:         s.node = null;
1147:           }
1148:         s = s.next; // continue
1149:       }
1150:     while (s != start);
1151: 
1152:     paths.add(start);
1153:       }
1154:     return paths;
1155:   }
1156: 
1157:   /**
1158:    * A small wrapper class to store intersection points
1159:    */
1160:   private class Intersection
1161:   {
1162:     Point2D p; // the 2D point of intersection
1163:     double ta; // the parametric value on a
1164:     double tb; // the parametric value on b
1165:     Segment seg; // segment placeholder for node setting
1166: 
1167:     public Intersection(Point2D p, double ta, double tb)
1168:     {
1169:       this.p = p;
1170:       this.ta = ta;
1171:       this.tb = tb;
1172:     }
1173:   }
1174: 
1175:   /**
1176:    * Returns the recursion depth necessary to approximate the
1177:    * curve by line segments within the error RS_EPSILON.
1178:    *
1179:    * This is done with Wang's formula:
1180:    * L0 = max{0<=i<=N-2}(|xi - 2xi+1 + xi+2|,|yi - 2yi+1 + yi+2|)
1181:    * r0 = log4(sqrt(2)*N*(N-1)*L0/8e)
1182:    * Where e is the maximum distance error (RS_EPSILON)
1183:    */
1184:   private int getRecursionDepth(CubicSegment curve)
1185:   {
1186:     double x0 = curve.P1.getX();
1187:     double y0 = curve.P1.getY();
1188: 
1189:     double x1 = curve.cp1.getX();
1190:     double y1 = curve.cp1.getY();
1191: 
1192:     double x2 = curve.cp2.getX();
1193:     double y2 = curve.cp2.getY();
1194: 
1195:     double x3 = curve.P2.getX();
1196:     double y3 = curve.P2.getY();
1197: 
1198:     double L0 = Math.max(Math.max(Math.abs(x0 - 2 * x1 + x2),
1199:                                   Math.abs(x1 - 2 * x2 + x3)),
1200:                          Math.max(Math.abs(y0 - 2 * y1 + y2),
1201:                                   Math.abs(y1 - 2 * y2 + y3)));
1202: 
1203:     double f = Math.sqrt(2) * 6.0 * L0 / (8.0 * RS_EPSILON);
1204: 
1205:     int r0 = (int) Math.ceil(Math.log(f) / Math.log(4.0));
1206:     return (r0);
1207:   }
1208: 
1209:   /**
1210:    * Performs recursive subdivision:
1211:    * @param c1 - curve 1
1212:    * @param c2 - curve 2
1213:    * @param depth1 - recursion depth of curve 1
1214:    * @param depth2 - recursion depth of curve 2
1215:    * @param t1 - global parametric value of the first curve's starting point
1216:    * @param t2 - global parametric value of the second curve's starting point
1217:    * @param w1 - global parametric length of curve 1
1218:    * @param w2 - global parametric length of curve 2
1219:    *
1220:    * The final four parameters are for keeping track of the parametric
1221:    * value of the curve. For a full curve t = 0, w = 1, w is halved with
1222:    * each subdivision.
1223:    */
1224:   private void recursiveSubdivide(CubicCurve2D c1, CubicCurve2D c2,
1225:                                   int depth1, int depth2, double t1,
1226:                                   double t2, double w1, double w2)
1227:   {
1228:     boolean flat1 = depth1 <= 0;
1229:     boolean flat2 = depth2 <= 0;
1230: 
1231:     if (flat1 && flat2)
1232:       {
1233:     double xlk = c1.getP2().getX() - c1.getP1().getX();
1234:     double ylk = c1.getP2().getY() - c1.getP1().getY();
1235: 
1236:     double xnm = c2.getP2().getX() - c2.getP1().getX();
1237:     double ynm = c2.getP2().getY() - c2.getP1().getY();
1238: 
1239:     double xmk = c2.getP1().getX() - c1.getP1().getX();
1240:     double ymk = c2.getP1().getY() - c1.getP1().getY();
1241:     double det = xnm * ylk - ynm * xlk;
1242: 
1243:     if (det + 1.0 == 1.0)
1244:       return;
1245: 
1246:     double detinv = 1.0 / det;
1247:     double s = (xnm * ymk - ynm * xmk) * detinv;
1248:     double t = (xlk * ymk - ylk * xmk) * detinv;
1249:     if ((s < 0.0) || (s > 1.0) || (t < 0.0) || (t > 1.0))
1250:       return;
1251: 
1252:     double[] temp = new double[2];
1253:     temp[0] = t1 + s * w1;
1254:     temp[1] = t2 + t * w1;
1255:     cc_intersections.add(temp);
1256:     return;
1257:       }
1258: 
1259:     CubicCurve2D.Double c11 = new CubicCurve2D.Double();
1260:     CubicCurve2D.Double c12 = new CubicCurve2D.Double();
1261:     CubicCurve2D.Double c21 = new CubicCurve2D.Double();
1262:     CubicCurve2D.Double c22 = new CubicCurve2D.Double();
1263: 
1264:     if (! flat1 && ! flat2)
1265:       {
1266:     depth1--;
1267:     depth2--;
1268:     w1 = w1 * 0.5;
1269:     w2 = w2 * 0.5;
1270:     c1.subdivide(c11, c12);
1271:     c2.subdivide(c21, c22);
1272:     if (c11.getBounds2D().intersects(c21.getBounds2D()))
1273:       recursiveSubdivide(c11, c21, depth1, depth2, t1, t2, w1, w2);
1274:     if (c11.getBounds2D().intersects(c22.getBounds2D()))
1275:       recursiveSubdivide(c11, c22, depth1, depth2, t1, t2 + w2, w1, w2);
1276:     if (c12.getBounds2D().intersects(c21.getBounds2D()))
1277:       recursiveSubdivide(c12, c21, depth1, depth2, t1 + w1, t2, w1, w2);
1278:     if (c12.getBounds2D().intersects(c22.getBounds2D()))
1279:       recursiveSubdivide(c12, c22, depth1, depth2, t1 + w1, t2 + w2, w1, w2);
1280:     return;
1281:       }
1282: 
1283:     if (! flat1)
1284:       {
1285:     depth1--;
1286:     c1.subdivide(c11, c12);
1287:     w1 = w1 * 0.5;
1288:     if (c11.getBounds2D().intersects(c2.getBounds2D()))
1289:       recursiveSubdivide(c11, c2, depth1, depth2, t1, t2, w1, w2);
1290:     if (c12.getBounds2D().intersects(c2.getBounds2D()))
1291:       recursiveSubdivide(c12, c2, depth1, depth2, t1 + w1, t2, w1, w2);
1292:     return;
1293:       }
1294: 
1295:     depth2--;
1296:     c2.subdivide(c21, c22);
1297:     w2 = w2 * 0.5;
1298:     if (c1.getBounds2D().intersects(c21.getBounds2D()))
1299:       recursiveSubdivide(c1, c21, depth1, depth2, t1, t2, w1, w2);
1300:     if (c1.getBounds2D().intersects(c22.getBounds2D()))
1301:       recursiveSubdivide(c1, c22, depth1, depth2, t1, t2 + w2, w1, w2);
1302:   }
1303: 
1304:   /**
1305:    * Returns a set of interesections between two Cubic segments
1306:    * Or null if no intersections were found.
1307:    *
1308:    * The method used to find the intersection is recursive midpoint
1309:    * subdivision. Outline description:
1310:    *
1311:    * 1) Check if the bounding boxes of the curves intersect,
1312:    * 2) If so, divide the curves in the middle and test the bounding
1313:    * boxes again,
1314:    * 3) Repeat until a maximum recursion depth has been reached, where
1315:    * the intersecting curves can be approximated by line segments.
1316:    *
1317:    * This is a reasonably accurate method, although the recursion depth
1318:    * is typically around 20, the bounding-box tests allow for significant
1319:    * pruning of the subdivision tree.
1320:    * 
1321:    * This is package-private to avoid an accessor method.
1322:    */
1323:   Intersection[] cubicCubicIntersect(CubicSegment curve1, CubicSegment curve2)
1324:   {
1325:     Rectangle2D r1 = curve1.getBounds();
1326:     Rectangle2D r2 = curve2.getBounds();
1327: 
1328:     if (! r1.intersects(r2))
1329:       return null;
1330: 
1331:     cc_intersections = new Vector();
1332:     recursiveSubdivide(curve1.getCubicCurve2D(), curve2.getCubicCurve2D(),
1333:                        getRecursionDepth(curve1), getRecursionDepth(curve2),
1334:                        0.0, 0.0, 1.0, 1.0);
1335: 
1336:     if (cc_intersections.size() == 0)
1337:       return null;
1338: 
1339:     Intersection[] results = new Intersection[cc_intersections.size()];
1340:     for (int i = 0; i < cc_intersections.size(); i++)
1341:       {
1342:     double[] temp = (double[]) cc_intersections.elementAt(i);
1343:     results[i] = new Intersection(curve1.evaluatePoint(temp[0]), temp[0],
1344:                                   temp[1]);
1345:       }
1346:     cc_intersections = null;
1347:     return (results);
1348:   }
1349: 
1350:   /**
1351:    * Returns the intersections between a line and a quadratic bezier
1352:    * Or null if no intersections are found1
1353:    * This is done through combining the line's equation with the
1354:    * parametric form of the Bezier and solving the resulting quadratic.
1355:    * This is package-private to avoid an accessor method.
1356:    */
1357:   Intersection[] lineQuadIntersect(LineSegment l, QuadSegment c)
1358:   {
1359:     double[] y = new double[3];
1360:     double[] x = new double[3];
1361:     double[] r = new double[3];
1362:     int nRoots;
1363:     double x0 = c.P1.getX();
1364:     double y0 = c.P1.getY();
1365:     double x1 = c.cp.getX();
1366:     double y1 = c.cp.getY();
1367:     double x2 = c.P2.getX();
1368:     double y2 = c.P2.getY();
1369: 
1370:     double lx0 = l.P1.getX();
1371:     double ly0 = l.P1.getY();
1372:     double lx1 = l.P2.getX();
1373:     double ly1 = l.P2.getY();
1374:     double dx = lx1 - lx0;
1375:     double dy = ly1 - ly0;
1376: 
1377:     // form r(t) = y(t) - x(t) for the bezier
1378:     y[0] = y0;
1379:     y[1] = 2 * (y1 - y0);
1380:     y[2] = (y2 - 2 * y1 + y0);
1381: 
1382:     x[0] = x0;
1383:     x[1] = 2 * (x1 - x0);
1384:     x[2] = (x2 - 2 * x1 + x0);
1385: 
1386:     // a point, not a line
1387:     if (dy == 0 && dx == 0)
1388:       return null;
1389: 
1390:     // line on y axis
1391:     if (dx == 0 || (dy / dx) > 1.0)
1392:       {
1393:     double k = dx / dy;
1394:     x[0] -= lx0;
1395:     y[0] -= ly0;
1396:     y[0] *= k;
1397:     y[1] *= k;
1398:     y[2] *= k;
1399:       }
1400:     else
1401:       {
1402:     double k = dy / dx;
1403:     x[0] -= lx0;
1404:     y[0] -= ly0;
1405:     x[0] *= k;
1406:     x[1] *= k;
1407:     x[2] *= k;
1408:       }
1409: 
1410:     for (int i = 0; i < 3; i++)
1411:       r[i] = y[i] - x[i];
1412: 
1413:     if ((nRoots = QuadCurve2D.solveQuadratic(r)) > 0)
1414:       {
1415:     Intersection[] temp = new Intersection[nRoots];
1416:     int intersections = 0;
1417:     for (int i = 0; i < nRoots; i++)
1418:       {
1419:         double t = r[i];
1420:         if (t >= 0.0 && t <= 1.0)
1421:           {
1422:         Point2D p = c.evaluatePoint(t);
1423: 
1424:         // if the line is on an axis, snap the point to that axis.
1425:         if (dx == 0)
1426:           p.setLocation(lx0, p.getY());
1427:         if (dy == 0)
1428:           p.setLocation(p.getX(), ly0);
1429: 
1430:         if (p.getX() <= Math.max(lx0, lx1)
1431:             && p.getX() >= Math.min(lx0, lx1)
1432:             && p.getY() <= Math.max(ly0, ly1)
1433:             && p.getY() >= Math.min(ly0, ly1))
1434:           {
1435:             double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1);
1436:             temp[i] = new Intersection(p, lineparameter, t);
1437:             intersections++;
1438:           }
1439:           }
1440:         else
1441:           temp[i] = null;
1442:       }
1443:     if (intersections == 0)
1444:       return null;
1445: 
1446:     Intersection[] rValues = new Intersection[intersections];
1447: 
1448:     for (int i = 0; i < nRoots; i++)
1449:       if (temp[i] != null)
1450:         rValues[--intersections] = temp[i];
1451:     return (rValues);
1452:       }
1453:     return null;
1454:   }
1455: 
1456:   /**
1457:    * Returns the intersections between a line and a cubic segment
1458:    * This is done through combining the line's equation with the
1459:    * parametric form of the Bezier and solving the resulting quadratic.
1460:    * This is package-private to avoid an accessor method. 
1461:    */
1462:   Intersection[] lineCubicIntersect(LineSegment l, CubicSegment c)
1463:   {
1464:     double[] y = new double[4];
1465:     double[] x = new double[4];
1466:     double[] r = new double[4];
1467:     int nRoots;
1468:     double x0 = c.P1.getX();
1469:     double y0 = c.P1.getY();
1470:     double x1 = c.cp1.getX();
1471:     double y1 = c.cp1.getY();
1472:     double x2 = c.cp2.getX();
1473:     double y2 = c.cp2.getY();
1474:     double x3 = c.P2.getX();
1475:     double y3 = c.P2.getY();
1476: 
1477:     double lx0 = l.P1.getX();
1478:     double ly0 = l.P1.getY();
1479:     double lx1 = l.P2.getX();
1480:     double ly1 = l.P2.getY();
1481:     double dx = lx1 - lx0;
1482:     double dy = ly1 - ly0;
1483: 
1484:     // form r(t) = y(t) - x(t) for the bezier
1485:     y[0] = y0;
1486:     y[1] = 3 * (y1 - y0);
1487:     y[2] = 3 * (y2 + y0 - 2 * y1);
1488:     y[3] = y3 - 3 * y2 + 3 * y1 - y0;
1489: 
1490:     x[0] = x0;
1491:     x[1] = 3 * (x1 - x0);
1492:     x[2] = 3 * (x2 + x0 - 2 * x1);
1493:     x[3] = x3 - 3 * x2 + 3 * x1 - x0;
1494: 
1495:     // a point, not a line
1496:     if (dy == 0 && dx == 0)
1497:       return null;
1498: 
1499:     // line on y axis
1500:     if (dx == 0 || (dy / dx) > 1.0)
1501:       {
1502:     double k = dx / dy;
1503:     x[0] -= lx0;
1504:     y[0] -= ly0;
1505:     y[0] *= k;
1506:     y[1] *= k;
1507:     y[2] *= k;
1508:     y[3] *= k;
1509:       }
1510:     else
1511:       {
1512:     double k = dy / dx;
1513:     x[0] -= lx0;
1514:     y[0] -= ly0;
1515:     x[0] *= k;
1516:     x[1] *= k;
1517:     x[2] *= k;
1518:     x[3] *= k;
1519:       }
1520:     for (int i = 0; i < 4; i++)
1521:       r[i] = y[i] - x[i];
1522: 
1523:     if ((nRoots = CubicCurve2D.solveCubic(r)) > 0)
1524:       {
1525:     Intersection[] temp = new Intersection[nRoots];
1526:     int intersections = 0;
1527:     for (int i = 0; i < nRoots; i++)
1528:       {
1529:         double t = r[i];
1530:         if (t >= 0.0 && t <= 1.0)
1531:           {
1532:         // if the line is on an axis, snap the point to that axis.
1533:         Point2D p = c.evaluatePoint(t);
1534:         if (dx == 0)
1535:           p.setLocation(lx0, p.getY());
1536:         if (dy == 0)
1537:           p.setLocation(p.getX(), ly0);
1538: 
1539:         if (p.getX() <= Math.max(lx0, lx1)
1540:             && p.getX() >= Math.min(lx0, lx1)
1541:             && p.getY() <= Math.max(ly0, ly1)
1542:             && p.getY() >= Math.min(ly0, ly1))
1543:           {
1544:             double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1);
1545:             temp[i] = new Intersection(p, lineparameter, t);
1546:             intersections++;
1547:           }
1548:           }
1549:         else
1550:           temp[i] = null;
1551:       }
1552: 
1553:     if (intersections == 0)
1554:       return null;
1555: 
1556:     Intersection[] rValues = new Intersection[intersections];
1557:     for (int i = 0; i < nRoots; i++)
1558:       if (temp[i] != null)
1559:         rValues[--intersections] = temp[i];
1560:     return (rValues);
1561:       }
1562:     return null;
1563:   }
1564: 
1565:   /**
1566:    * Returns the intersection between two lines, or null if there is no
1567:    * intersection.
1568:    * This is package-private to avoid an accessor method.
1569:    */
1570:   Intersection linesIntersect(LineSegment a, LineSegment b)
1571:   {
1572:     Point2D P1 = a.P1;
1573:     Point2D P2 = a.P2;
1574:     Point2D P3 = b.P1;
1575:     Point2D P4 = b.P2;
1576: 
1577:     if (! Line2D.linesIntersect(P1.getX(), P1.getY(), P2.getX(), P2.getY(),
1578:                                 P3.getX(), P3.getY(), P4.getX(), P4.getY()))
1579:       return null;
1580: 
1581:     double x1 = P1.getX();
1582:     double y1 = P1.getY();
1583:     double rx = P2.getX() - x1;
1584:     double ry = P2.getY() - y1;
1585: 
1586:     double x2 = P3.getX();
1587:     double y2 = P3.getY();
1588:     double sx = P4.getX() - x2;
1589:     double sy = P4.getY() - y2;
1590: 
1591:     double determinant = sx * ry - sy * rx;
1592:     double nom = (sx * (y2 - y1) + sy * (x1 - x2));
1593: 
1594:     // Parallel lines don't intersect. At least we pretend they don't.
1595:     if (Math.abs(determinant) < EPSILON)
1596:       return null;
1597: 
1598:     nom = nom / determinant;
1599: 
1600:     if (nom == 0.0)
1601:       return null;
1602:     if (nom == 1.0)
1603:       return null;
1604: 
1605:     Point2D p = new Point2D.Double(x1 + nom * rx, y1 + nom * ry);
1606: 
1607:     return new Intersection(p, p.distance(P1) / P1.distance(P2),
1608:                             p.distance(P3) / P3.distance(P4));
1609:   }
1610: 
1611:   /**
1612:    * Determines if two points are equal, within an error margin
1613:    * 'snap distance'
1614:    * This is package-private to avoid an accessor method.
1615:    */
1616:   boolean pointEquals(Point2D a, Point2D b)
1617:   {
1618:     return (a.equals(b) || a.distance(b) < PE_EPSILON);
1619:   }
1620: 
1621:   /**
1622:    * Helper method
1623:    * Turns a shape into a Vector of Segments
1624:    */
1625:   private Vector makeSegment(Shape s)
1626:   {
1627:     Vector paths = new Vector();
1628:     PathIterator pi = s.getPathIterator(null);
1629:     double[] coords = new double[6];
1630:     Segment subpath = null;
1631:     Segment current = null;
1632:     double cx;
1633:     double cy;
1634:     double subpathx;
1635:     double subpathy;
1636:     cx = cy = subpathx = subpathy = 0.0;
1637: 
1638:     this.windingRule = pi.getWindingRule();
1639: 
1640:     while (! pi.isDone())
1641:       {
1642:     Segment v;
1643:     switch (pi.currentSegment(coords))
1644:       {
1645:       case PathIterator.SEG_MOVETO:
1646:         if (subpath != null)
1647:           { // close existing open path
1648:         current.next = new LineSegment(cx, cy, subpathx, subpathy);
1649:         current = current.next;
1650:         current.next = subpath;
1651:           }
1652:         subpath = null;
1653:         subpathx = cx = coords[0];
1654:         subpathy = cy = coords[1];
1655:         break;
1656: 
1657:       // replace 'close' with a line-to.
1658:       case PathIterator.SEG_CLOSE:
1659:         if (subpath != null && (subpathx != cx || subpathy != cy))
1660:           {
1661:         current.next = new LineSegment(cx, cy, subpathx, subpathy);
1662:         current = current.next;
1663:         current.next = subpath;
1664:         cx = subpathx;
1665:         cy = subpathy;
1666:         subpath = null;
1667:           }
1668:         else if (subpath != null)
1669:           {
1670:         current.next = subpath;
1671:         subpath = null;
1672:           }
1673:         break;
1674:       case PathIterator.SEG_LINETO:
1675:         if (cx != coords[0] || cy != coords[1])
1676:           {
1677:         v = new LineSegment(cx, cy, coords[0], coords[1]);
1678:         if (subpath == null)
1679:           {
1680:             subpath = current = v;
1681:             paths.add(subpath);
1682:           }
1683:         else
1684:           {
1685:             current.next = v;
1686:             current = current.next;
1687:           }
1688:         cx = coords[0];
1689:         cy = coords[1];
1690:           }
1691:         break;
1692:       case PathIterator.SEG_QUADTO:
1693:         v = new QuadSegment(cx, cy, coords[0], coords[1], coords[2],
1694:                             coords[3]);
1695:         if (subpath == null)
1696:           {
1697:         subpath = current = v;
1698:         paths.add(subpath);
1699:           }
1700:         else
1701:           {
1702:         current.next = v;
1703:         current = current.next;
1704:           }
1705:         cx = coords[2];
1706:         cy = coords[3];
1707:         break;
1708:       case PathIterator.SEG_CUBICTO:
1709:         v = new CubicSegment(cx, cy, coords[0], coords[1], coords[2],
1710:                              coords[3], coords[4], coords[5]);
1711:         if (subpath == null)
1712:           {
1713:         subpath = current = v;
1714:         paths.add(subpath);
1715:           }
1716:         else
1717:           {
1718:         current.next = v;
1719:         current = current.next;
1720:           }
1721: 
1722:         // check if the cubic is self-intersecting
1723:         double[] lpts = ((CubicSegment) v).getLoop();
1724:         if (lpts != null)
1725:           {
1726:         // if it is, break off the loop into its own path.
1727:         v.subdivideInsert(lpts[0]);
1728:         v.next.subdivideInsert((lpts[1] - lpts[0]) / (1.0 - lpts[0]));
1729: 
1730:         CubicSegment loop = (CubicSegment) v.next;
1731:         v.next = loop.next;
1732:         loop.next = loop;
1733: 
1734:         v.P2 = v.next.P1 = loop.P2 = loop.P1; // snap points
1735:         paths.add(loop);
1736:         current = v.next;
1737:           }
1738: 
1739:         cx = coords[4];
1740:         cy = coords[5];
1741:         break;
1742:       }
1743:     pi.next();
1744:       }
1745: 
1746:     if (subpath != null)
1747:       { // close any open path
1748:     if (subpathx != cx || subpathy != cy)
1749:       {
1750:         current.next = new LineSegment(cx, cy, subpathx, subpathy);
1751:         current = current.next;
1752:         current.next = subpath;
1753:       }
1754:     else
1755:       current.next = subpath;
1756:       }
1757: 
1758:     if (paths.size() == 0)
1759:       return (null);
1760: 
1761:     return (paths);
1762:   }
1763: 
1764:   /**
1765:    * Find the intersections of two separate closed paths,
1766:    * A and B, split the segments at the intersection points,
1767:    * and create nodes pointing from one to the other
1768:    */
1769:   private int createNodes(Segment A, Segment B)
1770:   {
1771:     int nNodes = 0;
1772: 
1773:     Segment a = A;
1774:     Segment b = B;
1775: 
1776:     do
1777:       {
1778:     do
1779:       {
1780:         nNodes += a.splitIntersections(b);
1781:         b = b.next;
1782:       }
1783:     while (b != B);
1784: 
1785:     a = a.next; // move to the next segment
1786:       }
1787:     while (a != A); // until one wrap.
1788: 
1789:     return (nNodes);
1790:   }
1791: 
1792:   /**
1793:    * Find the intersections of a path with itself.
1794:    * Splits the segments at the intersection points,
1795:    * and create nodes pointing from one to the other.
1796:    */
1797:   private int createNodesSelf(Segment A)
1798:   {
1799:     int nNodes = 0;
1800:     Segment a = A;
1801: 
1802:     if (A.next == A)
1803:       return 0;
1804: 
1805:     do
1806:       {
1807:     Segment b = a.next;
1808:     do
1809:       {
1810:         if (b != a) // necessary
1811:           nNodes += a.splitIntersections(b);
1812:         b = b.next;
1813:       }
1814:     while (b != A);
1815:     a = a.next; // move to the next segment
1816:       }
1817:     while (a != A); // until one wrap.
1818: 
1819:     return (nNodes);
1820:   }
1821: 
1822:   /**
1823:    * Deletes paths which are redundant from a list, (i.e. solid areas within
1824:    * solid areas) Clears any nodes. Sorts the remaining paths into solids
1825:    * and holes, sets their orientation and sets the solids and holes lists.
1826:    */
1827:   private void deleteRedundantPaths(Vector paths)
1828:   {
1829:     int npaths = paths.size();
1830: 
1831:     int[][] contains = new int[npaths][npaths];
1832:     int[][] windingNumbers = new int[npaths][2];
1833:     int neg;
1834:     Rectangle2D[] bb = new Rectangle2D[npaths]; // path bounding boxes
1835: 
1836:     neg = ((windingRule == PathIterator.WIND_NON_ZERO) ? -1 : 1);
1837: 
1838:     for (int i = 0; i < npaths; i++)
1839:       bb[i] = ((Segment) paths.elementAt(i)).getPathBounds();
1840: 
1841:     // Find which path contains which, assign winding numbers
1842:     for (int i = 0; i < npaths; i++)
1843:       {
1844:     Segment pathA = (Segment) paths.elementAt(i);
1845:     pathA.nullNodes(); // remove any now-redundant nodes, in case.
1846:     int windingA = pathA.hasClockwiseOrientation() ? 1 : neg;
1847: 
1848:     for (int j = 0; j < npaths; j++)
1849:       if (i != j)
1850:         {
1851:           Segment pathB = (Segment) paths.elementAt(j);
1852: 
1853:           // A contains B
1854:           if (bb[i].intersects(bb[j]))
1855:             {
1856:           Segment s = pathB.next;
1857:           while (s.P1.getY() == s.P2.getY() && s != pathB)
1858:             s = s.next;
1859:           Point2D p = s.getMidPoint();
1860:           if (pathA.contains(p.getX(), p.getY()))
1861:             contains[i][j] = windingA;
1862:             }
1863:           else
1864:         // A does not contain B
1865:         contains[i][j] = 0;
1866:         }
1867:       else
1868:         contains[i][j] = windingA; // i == j
1869:       }
1870: 
1871:     for (int i = 0; i < npaths; i++)
1872:       {
1873:     windingNumbers[i][0] = 0;
1874:     for (int j = 0; j < npaths; j++)
1875:       windingNumbers[i][0] += contains[j][i];
1876:     windingNumbers[i][1] = contains[i][i];
1877:       }
1878: 
1879:     Vector solids = new Vector();
1880:     Vector holes = new Vector();
1881: 
1882:     if (windingRule == PathIterator.WIND_NON_ZERO)
1883:       {
1884:     for (int i = 0; i < npaths; i++)
1885:       {
1886:         if (windingNumbers[i][0] == 0)
1887:           holes.add(paths.elementAt(i));
1888:         else if (windingNumbers[i][0] - windingNumbers[i][1] == 0
1889:                  && Math.abs(windingNumbers[i][0]) == 1)
1890:           solids.add(paths.elementAt(i));
1891:       }
1892:       }
1893:     else
1894:       {
1895:     windingRule = PathIterator.WIND_NON_ZERO;
1896:     for (int i = 0; i < npaths; i++)
1897:       {
1898:         if ((windingNumbers[i][0] & 1) == 0)
1899:           holes.add(paths.elementAt(i));
1900:         else if ((windingNumbers[i][0] & 1) == 1)
1901:           solids.add(paths.elementAt(i));
1902:       }
1903:       }
1904: 
1905:     setDirection(holes, false);
1906:     setDirection(solids, true);
1907:     this.holes = holes;
1908:     this.solids = solids;
1909:   }
1910: 
1911:   /**
1912:    * Sets the winding direction of a Vector of paths
1913:    * @param clockwise gives the direction,
1914:    * true = clockwise, false = counter-clockwise
1915:    */
1916:   private void setDirection(Vector paths, boolean clockwise)
1917:   {
1918:     Segment v;
1919:     for (int i = 0; i < paths.size(); i++)
1920:       {
1921:     v = (Segment) paths.elementAt(i);
1922:     if (clockwise != v.hasClockwiseOrientation())
1923:       v.reverseAll();
1924:       }
1925:   }
1926: 
1927:   /**
1928:    * Class representing a linked-list of vertices forming a closed polygon,
1929:    * convex or concave, without holes.
1930:    */
1931:   private abstract class Segment implements Cloneable
1932:   {
1933:     // segment type, PathIterator segment types are used.
1934:     Point2D P1;
1935:     Point2D P2;
1936:     Segment next;
1937:     Segment node;
1938: 
1939:     Segment()
1940:     {
1941:       P1 = P2 = null;
1942:       node = next = null;
1943:     }
1944: 
1945:     /**
1946:      * Reverses the direction of a single segment
1947:      */
1948:     abstract void reverseCoords();
1949: 
1950:     /**
1951:      * Returns the segment's midpoint
1952:      */
1953:     abstract Point2D getMidPoint();
1954: 
1955:     /**
1956:      * Returns the bounding box of this segment
1957:      */
1958:     abstract Rectangle2D getBounds();
1959: 
1960:     /**
1961:      * Transforms a single segment
1962:      */
1963:     abstract void transform(AffineTransform at);
1964: 
1965:     /**
1966:      * Returns the PathIterator type of a segment
1967:      */
1968:     abstract int getType();
1969: 
1970:     /**
1971:      */
1972:     abstract int splitIntersections(Segment b);
1973: 
1974:     /**
1975:      * Returns the PathIterator coords of a segment
1976:      */
1977:     abstract int pathIteratorFormat(double[] coords);
1978: 
1979:     /**
1980:      * Returns the number of intersections on the positive X axis,
1981:      * with the origin at (x,y), used for contains()-testing
1982:      *
1983:      * (Although that could be done by the line-intersect methods,
1984:      * a dedicated method is better to guarantee consitent handling
1985:      * of endpoint-special-cases)
1986:      */
1987:     abstract int rayCrossing(double x, double y);
1988: 
1989:     /**
1990:      * Subdivides the segment at parametric value t, inserting
1991:      * the new segment into the linked list after this,
1992:      * such that this becomes [0,t] and this.next becomes [t,1]
1993:      */
1994:     abstract void subdivideInsert(double t);
1995: 
1996:     /**
1997:      * Returns twice the area of a curve, relative the P1-P2 line
1998:      * Used for area calculations.
1999:      */
2000:     abstract double curveArea();
2001: 
2002:     /**
2003:      * Compare two segments.
2004:      */
2005:     abstract boolean equals(Segment b);
2006: 
2007:     /**
2008:      * Determines if this path of segments contains the point (x,y)
2009:      */
2010:     boolean contains(double x, double y)
2011:     {
2012:       Segment v = this;
2013:       int crossings = 0;
2014:       do
2015:         {
2016:       int n = v.rayCrossing(x, y);
2017:       crossings += n;
2018:       v = v.next;
2019:         }
2020:       while (v != this);
2021:       return ((crossings & 1) == 1);
2022:     }
2023: 
2024:     /**
2025:      * Nulls all nodes of the path. Clean up any 'hairs'.
2026:      */
2027:     void nullNodes()
2028:     {
2029:       Segment v = this;
2030:       do
2031:         {
2032:       v.node = null;
2033:       v = v.next;
2034:         }
2035:       while (v != this);
2036:     }
2037: 
2038:     /**
2039:      * Transforms each segment in the closed path
2040:      */
2041:     void transformSegmentList(AffineTransform at)
2042:     {
2043:       Segment v = this;
2044:       do
2045:         {
2046:       v.transform(at);
2047:       v = v.next;
2048:         }
2049:       while (v != this);
2050:     }
2051: 
2052:     /**
2053:      * Determines the winding direction of the path
2054:      * By the sign of the area.
2055:      */
2056:     boolean hasClockwiseOrientation()
2057:     {
2058:       return (getSignedArea() > 0.0);
2059:     }
2060: 
2061:     /**
2062:      * Returns the bounds of this path
2063:      */
2064:     public Rectangle2D getPathBounds()
2065:     {
2066:       double xmin;
2067:       double xmax;
2068:       double ymin;
2069:       double ymax;
2070:       xmin = xmax = P1.getX();
2071:       ymin = ymax = P1.getY();
2072: 
2073:       Segment v = this;
2074:       do
2075:         {
2076:       Rectangle2D r = v.getBounds();
2077:       xmin = Math.min(r.getMinX(), xmin);
2078:       ymin = Math.min(r.getMinY(), ymin);
2079:       xmax = Math.max(r.getMaxX(), xmax);
2080:       ymax = Math.max(r.getMaxY(), ymax);
2081:       v = v.next;
2082:         }
2083:       while (v != this);
2084: 
2085:       return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
2086:     }
2087: 
2088:     /**
2089:      * Calculates twice the signed area of the path;
2090:      */
2091:     double getSignedArea()
2092:     {
2093:       Segment s;
2094:       double area = 0.0;
2095: 
2096:       s = this;
2097:       do
2098:         {
2099:       area += s.curveArea();
2100: 
2101:       area += s.P1.getX() * s.next.P1.getY()
2102:       - s.P1.getY() * s.next.P1.getX();
2103:       s = s.next;
2104:         }
2105:       while (s != this);
2106: 
2107:       return area;
2108:     }
2109: 
2110:     /**
2111:      * Reverses the orientation of the whole polygon
2112:      */
2113:     void reverseAll()
2114:     {
2115:       reverseCoords();
2116:       Segment v = next;
2117:       Segment former = this;
2118:       while (v != this)
2119:         {
2120:       v.reverseCoords();
2121:       Segment vnext = v.next;
2122:       v.next = former;
2123:       former = v;
2124:       v = vnext;
2125:         }
2126:       next = former;
2127:     }
2128: 
2129:     /**
2130:      * Inserts a Segment after this one
2131:      */
2132:     void insert(Segment v)
2133:     {
2134:       Segment n = next;
2135:       next = v;
2136:       v.next = n;
2137:     }
2138: 
2139:     /**
2140:      * Returns if this segment path is polygonal
2141:      */
2142:     boolean isPolygonal()
2143:     {
2144:       Segment v = this;
2145:       do
2146:         {
2147:       if (! (v instanceof LineSegment))
2148:         return false;
2149:       v = v.next;
2150:         }
2151:       while (v != this);
2152:       return true;
2153:     }
2154: 
2155:     /**
2156:      * Clones this path
2157:      */
2158:     Segment cloneSegmentList() throws CloneNotSupportedException
2159:     {
2160:       Vector list = new Vector();
2161:       Segment v = next;
2162: 
2163:       while (v != this)
2164:         {
2165:       list.add(v);
2166:       v = v.next;
2167:         }
2168: 
2169:       Segment clone = (Segment) this.clone();
2170:       v = clone;
2171:       for (int i = 0; i < list.size(); i++)
2172:         {
2173:       clone.next = (Segment) ((Segment) list.elementAt(i)).clone();
2174:       clone = clone.next;
2175:         }
2176:       clone.next = v;
2177:       return v;
2178:     }
2179: 
2180:     /**
2181:      * Creates a node between this segment and segment b
2182:      * at the given intersection
2183:      * @return the number of nodes created (0 or 1)
2184:      */
2185:     int createNode(Segment b, Intersection i)
2186:     {
2187:       Point2D p = i.p;
2188:       if ((pointEquals(P1, p) || pointEquals(P2, p))
2189:           && (pointEquals(b.P1, p) || pointEquals(b.P2, p)))
2190:     return 0;
2191: 
2192:       subdivideInsert(i.ta);
2193:       b.subdivideInsert(i.tb);
2194: 
2195:       // snap points
2196:       b.P2 = b.next.P1 = P2 = next.P1 = i.p;
2197: 
2198:       node = b.next;
2199:       b.node = next;
2200:       return 1;
2201:     }
2202: 
2203:     /**
2204:      * Creates multiple nodes from a list of intersections,
2205:      * This must be done in the order of ascending parameters,
2206:      * and the parameters must be recalculated in accordance
2207:      * with each split.
2208:      * @return the number of nodes created
2209:      */
2210:     protected int createNodes(Segment b, Intersection[] x)
2211:     {
2212:       Vector v = new Vector();
2213:       for (int i = 0; i < x.length; i++)
2214:         {
2215:       Point2D p = x[i].p;
2216:       if (! ((pointEquals(P1, p) || pointEquals(P2, p))
2217:           && (pointEquals(b.P1, p) || pointEquals(b.P2, p))))
2218:         v.add(x[i]);
2219:         }
2220: 
2221:       int nNodes = v.size();
2222:       Intersection[] A = new Intersection[nNodes];
2223:       Intersection[] B = new Intersection[nNodes];
2224:       for (int i = 0; i < nNodes; i++)
2225:     A[i] = B[i] = (Intersection) v.elementAt(i);
2226: 
2227:       // Create two lists sorted by the parameter
2228:       // Bubble sort, OK I suppose, since the number of intersections
2229:       // cannot be larger than 9 (cubic-cubic worst case) anyway
2230:       for (int i = 0; i < nNodes - 1; i++)
2231:         {
2232:       for (int j = i + 1; j < nNodes; j++)
2233:         {
2234:           if (A[i].ta > A[j].ta)
2235:             {
2236:           Intersection swap = A[i];
2237:           A[i] = A[j];
2238:           A[j] = swap;
2239:             }
2240:           if (B[i].tb > B[j].tb)
2241:             {
2242:           Intersection swap = B[i];
2243:           B[i] = B[j];
2244:           B[j] = swap;
2245:             }
2246:         }
2247:         }
2248:       // subdivide a
2249:       Segment s = this;
2250:       for (int i = 0; i < nNodes; i++)
2251:         {
2252:       s.subdivideInsert(A[i].ta);
2253: 
2254:       // renormalize the parameters
2255:       for (int j = i + 1; j < nNodes; j++)
2256:         A[j].ta = (A[j].ta - A[i].ta) / (1.0 - A[i].ta);
2257: 
2258:       A[i].seg = s;
2259:       s = s.next;
2260:         }
2261: 
2262:       // subdivide b, set nodes
2263:       s = b;
2264:       for (int i = 0; i < nNodes; i++)
2265:         {
2266:       s.subdivideInsert(B[i].tb);
2267: 
2268:       for (int j = i + 1; j < nNodes; j++)
2269:         B[j].tb = (B[j].tb - B[i].tb) / (1.0 - B[i].tb);
2270: 
2271:       // set nodes
2272:       B[i].seg.node = s.next; // node a -> b 
2273:       s.node = B[i].seg.next; // node b -> a 
2274: 
2275:       // snap points
2276:       B[i].seg.P2 = B[i].seg.next.P1 = s.P2 = s.next.P1 = B[i].p;
2277:       s = s.next;
2278:         }
2279:       return nNodes;
2280:     }
2281: 
2282:     /**
2283:      * Determines if two paths are equal.
2284:      * Colinear line segments are ignored in the comparison.
2285:      */
2286:     boolean pathEquals(Segment B)
2287:     {
2288:       if (! getPathBounds().equals(B.getPathBounds()))
2289:     return false;
2290: 
2291:       Segment startA = getTopLeft();
2292:       Segment startB = B.getTopLeft();
2293:       Segment a = startA;
2294:       Segment b = startB;
2295:       do
2296:         {
2297:       if (! a.equals(b))
2298:         return false;
2299: 
2300:       if (a instanceof LineSegment)
2301:         a = ((LineSegment) a).lastCoLinear();
2302:       if (b instanceof LineSegment)
2303:         b = ((LineSegment) b).lastCoLinear();
2304: 
2305:       a = a.next;
2306:       b = b.next;
2307:         }
2308:       while (a != startA && b != startB);
2309:       return true;
2310:     }
2311: 
2312:     /**
2313:      * Return the segment with the top-leftmost first point
2314:      */
2315:     Segment getTopLeft()
2316:     {
2317:       Segment v = this;
2318:       Segment tl = this;
2319:       do
2320:         {
2321:       if (v.P1.getY() < tl.P1.getY())
2322:         tl = v;
2323:       else if (v.P1.getY() == tl.P1.getY())
2324:         {
2325:           if (v.P1.getX() < tl.P1.getX())
2326:         tl = v;
2327:         }
2328:       v = v.next;
2329:         }
2330:       while (v != this);
2331:       return tl;
2332:     }
2333: 
2334:     /**
2335:      * Returns if the path has a segment outside a shape
2336:      */
2337:     boolean isSegmentOutside(Shape shape)
2338:     {
2339:       return ! shape.contains(getMidPoint());
2340:     }
2341:   } // class Segment
2342: 
2343:   private class LineSegment extends Segment
2344:   {
2345:     public LineSegment(double x1, double y1, double x2, double y2)
2346:     {
2347:       super();
2348:       P1 = new Point2D.Double(x1, y1);
2349:       P2 = new Point2D.Double(x2, y2);
2350:     }
2351: 
2352:     public LineSegment(Point2D p1, Point2D p2)
2353:     {
2354:       super();
2355:       P1 = (Point2D) p1.clone();
2356:       P2 = (Point2D) p2.clone();
2357:     }
2358: 
2359:     /**
2360:      * Clones this segment
2361:      */
2362:     public Object clone()
2363:     {
2364:       return new LineSegment(P1, P2);
2365:     }
2366: 
2367:     /**
2368:      * Transforms the segment
2369:      */
2370:     void transform(AffineTransform at)
2371:     {
2372:       P1 = at.transform(P1, null);
2373:       P2 = at.transform(P2, null);
2374:     }
2375: 
2376:     /**
2377:      * Swap start and end points
2378:      */
2379:     void reverseCoords()
2380:     {
2381:       Point2D p = P1;
2382:       P1 = P2;
2383:       P2 = p;
2384:     }
2385: 
2386:     /**
2387:      * Returns the segment's midpoint
2388:      */
2389:     Point2D getMidPoint()
2390:     {
2391:       return (new Point2D.Double(0.5 * (P1.getX() + P2.getX()),
2392:                                  0.5 * (P1.getY() + P2.getY())));
2393:     }
2394: 
2395:     /**
2396:      * Returns twice the area of a curve, relative the P1-P2 line
2397:      * Obviously, a line does not enclose any area besides the line
2398:      */
2399:     double curveArea()
2400:     {
2401:       return 0;
2402:     }
2403: 
2404:     /**
2405:      * Returns the PathIterator type of a segment
2406:      */
2407:     int getType()
2408:     {
2409:       return (PathIterator.SEG_LINETO);
2410:     }
2411: 
2412:     /**
2413:      * Subdivides the segment at parametric value t, inserting
2414:      * the new segment into the linked list after this,
2415:      * such that this becomes [0,t] and this.next becomes [t,1]
2416:      */
2417:     void subdivideInsert(double t)
2418:     {
2419:       Point2D p = new Point2D.Double((P2.getX() - P1.getX()) * t + P1.getX(),
2420:                                      (P2.getY() - P1.getY()) * t + P1.getY());
2421:       insert(new LineSegment(p, P2));
2422:       P2 = p;
2423:       next.node = node;
2424:       node = null;
2425:     }
2426: 
2427:     /**
2428:      * Determines if two line segments are strictly colinear
2429:      */
2430:     boolean isCoLinear(LineSegment b)
2431:     {
2432:       double x1 = P1.getX();
2433:       double y1 = P1.getY();
2434:       double x2 = P2.getX();
2435:       double y2 = P2.getY();
2436:       double x3 = b.P1.getX();
2437:       double y3 = b.P1.getY();
2438:       double x4 = b.P2.getX();
2439:       double y4 = b.P2.getY();
2440: 
2441:       if ((y1 - y3) * (x4 - x3) - (x1 - x3) * (y4 - y3) != 0.0)
2442:     return false;
2443: 
2444:       return ((x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3) == 0.0);
2445:     }
2446: 
2447:     /**
2448:      * Return the last segment colinear with this one.
2449:      * Used in comparing paths.
2450:      */
2451:     Segment lastCoLinear()
2452:     {
2453:       Segment prev = this;
2454:       Segment v = next;
2455: 
2456:       while (v instanceof LineSegment)
2457:         {
2458:       if (isCoLinear((LineSegment) v))
2459:         {
2460:           prev = v;
2461:           v = v.next;
2462:         }
2463:       else
2464:         return prev;
2465:         }
2466:       return prev;
2467:     }
2468: 
2469:     /**
2470:      * Compare two segments.
2471:      * We must take into account that the lines may be broken into colinear
2472:      * subsegments and ignore them.
2473:      */
2474:     boolean equals(Segment b)
2475:     {
2476:       if (! (b instanceof LineSegment))
2477:     return false;
2478:       Point2D p1 = P1;
2479:       Point2D p3 = b.P1;
2480: 
2481:       if (! p1.equals(p3))
2482:     return false;
2483: 
2484:       Point2D p2 = lastCoLinear().P2;
2485:       Point2D p4 = ((LineSegment) b).lastCoLinear().P2;
2486:       return (p2.equals(p4));
2487:     }
2488: 
2489:     /**
2490:      * Returns a line segment
2491:      */
2492:     int pathIteratorFormat(double[] coords)
2493:     {
2494:       coords[0] = P2.getX();
2495:       coords[1] = P2.getY();
2496:       return (PathIterator.SEG_LINETO);
2497:     }
2498: 
2499:     /**
2500:      * Returns if the line has intersections.
2501:      */
2502:     boolean hasIntersections(Segment b)
2503:     {
2504:       if (b instanceof LineSegment)
2505:     return (linesIntersect(this, (LineSegment) b) != null);
2506: 
2507:       if (b instanceof QuadSegment)
2508:     return (lineQuadIntersect(this, (QuadSegment) b) != null);
2509: 
2510:       if (b instanceof CubicSegment)
2511:     return (lineCubicIntersect(this, (CubicSegment) b) != null);
2512: 
2513:       return false;
2514:     }
2515: 
2516:     /**
2517:      * Splits intersections into nodes,
2518:      * This one handles line-line, line-quadratic, line-cubic
2519:      */
2520:     int splitIntersections(Segment b)
2521:     {
2522:       if (b instanceof LineSegment)
2523:         {
2524:       Intersection i = linesIntersect(this, (LineSegment) b);
2525: 
2526:       if (i == null)
2527:         return 0;
2528: 
2529:       return createNode(b, i);
2530:         }
2531: 
2532:       Intersection[] x = null;
2533: 
2534:       if (b instanceof QuadSegment)
2535:     x = lineQuadIntersect(this, (QuadSegment) b);
2536: 
2537:       if (b instanceof CubicSegment)
2538:     x = lineCubicIntersect(this, (CubicSegment) b);
2539: 
2540:       if (x == null)
2541:     return 0;
2542: 
2543:       if (x.length == 1)
2544:     return createNode(b, (Intersection) x[0]);
2545: 
2546:       return createNodes(b, x);
2547:     }
2548: 
2549:     /**
2550:      * Returns the bounding box of this segment
2551:      */
2552:     Rectangle2D getBounds()
2553:     {
2554:       return (new Rectangle2D.Double(Math.min(P1.getX(), P2.getX()),
2555:                                      Math.min(P1.getY(), P2.getY()),
2556:                                      Math.abs(P1.getX() - P2.getX()),
2557:                                      Math.abs(P1.getY() - P2.getY())));
2558:     }
2559: 
2560:     /**
2561:      * Returns the number of intersections on the positive X axis,
2562:      * with the origin at (x,y), used for contains()-testing
2563:      */
2564:     int rayCrossing(double x, double y)
2565:     {
2566:       double x0 = P1.getX() - x;
2567:       double y0 = P1.getY() - y;
2568:       double x1 = P2.getX() - x;
2569:       double y1 = P2.getY() - y;
2570: 
2571:       if (y0 * y1 > 0)
2572:     return 0;
2573: 
2574:       if (x0 < 0 && x1 < 0)
2575:     return 0;
2576: 
2577:       if (y0 == 0.0)
2578:     y0 -= EPSILON;
2579: 
2580:       if (y1 == 0.0)
2581:     y1 -= EPSILON;
2582: 
2583:       if (Line2D.linesIntersect(x0, y0, x1, y1, 
2584:                 EPSILON, 0.0, Double.MAX_VALUE, 0.0))
2585:     return 1;
2586:       return 0;
2587:     }
2588:   } // class LineSegment
2589: 
2590:   /**
2591:    * Quadratic Bezier curve segment
2592:    *
2593:    * Note: Most peers don't support quadratics directly, so it might make
2594:    * sense to represent them as cubics internally and just be done with it.
2595:    * I think we should be peer-agnostic, however, and stay faithful to the
2596:    * input geometry types as far as possible.
2597:    */
2598:   private class QuadSegment extends Segment
2599:   {
2600:     Point2D cp; // control point
2601: 
2602:     /**
2603:      * Constructor, takes the coordinates of the start, control,
2604:      * and end point, respectively.
2605:      */
2606:     QuadSegment(double x1, double y1, double cx, double cy, double x2,
2607:                 double y2)
2608:     {
2609:       super();
2610:       P1 = new Point2D.Double(x1, y1);
2611:       P2 = new Point2D.Double(x2, y2);
2612:       cp = new Point2D.Double(cx, cy);
2613:     }
2614: 
2615:     /**
2616:      * Clones this segment
2617:      */
2618:     public Object clone()
2619:     {
2620:       return new QuadSegment(P1.getX(), P1.getY(), cp.getX(), cp.getY(),
2621:                              P2.getX(), P2.getY());
2622:     }
2623: 
2624:     /**
2625:      * Returns twice the area of a curve, relative the P1-P2 line
2626:      *
2627:      * The area formula can be derived by using Green's formula in the
2628:      * plane on the parametric form of the bezier.
2629:      */
2630:     double curveArea()
2631:     {
2632:       double x0 = P1.getX();
2633:       double y0 = P1.getY();
2634:       double x1 = cp.getX();
2635:       double y1 = cp.getY();
2636:       double x2 = P2.getX();
2637:       double y2 = P2.getY();
2638: 
2639:       double P = (y2 - 2 * y1 + y0);
2640:       double Q = 2 * (y1 - y0);
2641: 
2642:       double A = (x2 - 2 * x1 + x0);
2643:       double B = 2 * (x1 - x0);
2644: 
2645:       double area = (B * P - A * Q) / 3.0;
2646:       return (area);
2647:     }
2648: 
2649:     /**
2650:      * Compare two segments.
2651:      */
2652:     boolean equals(Segment b)
2653:     {
2654:       if (! (b instanceof QuadSegment))
2655:     return false;
2656: 
2657:       return (P1.equals(b.P1) && cp.equals(((QuadSegment) b).cp)
2658:              && P2.equals(b.P2));
2659:     }
2660: 
2661:     /**
2662:      * Returns a Point2D corresponding to the parametric value t
2663:      * of the curve
2664:      */
2665:     Point2D evaluatePoint(double t)
2666:     {
2667:       double x0 = P1.getX();
2668:       double y0 = P1.getY();
2669:       double x1 = cp.getX();
2670:       double y1 = cp.getY();
2671:       double x2 = P2.getX();
2672:       double y2 = P2.getY();
2673: 
2674:       return new Point2D.Double(t * t * (x2 - 2 * x1 + x0) + 2 * t * (x1 - x0)
2675:                                 + x0,
2676:                                 t * t * (y2 - 2 * y1 + y0) + 2 * t * (y1 - y0)
2677:                                 + y0);
2678:     }
2679: 
2680:     /**
2681:      * Returns the bounding box of this segment
2682:      */
2683:     Rectangle2D getBounds()
2684:     {
2685:       double x0 = P1.getX();
2686:       double y0 = P1.getY();
2687:       double x1 = cp.getX();
2688:       double y1 = cp.getY();
2689:       double x2 = P2.getX();
2690:       double y2 = P2.getY();
2691:       double r0;
2692:       double r1;
2693: 
2694:       double xmax = Math.max(x0, x2);
2695:       double ymax = Math.max(y0, y2);
2696:       double xmin = Math.min(x0, x2);
2697:       double ymin = Math.min(y0, y2);
2698: 
2699:       r0 = 2 * (y1 - y0);
2700:       r1 = 2 * (y2 - 2 * y1 + y0);
2701:       if (r1 != 0.0)
2702:         {
2703:       double t = -r0 / r1;
2704:       if (t > 0.0 && t < 1.0)
2705:         {
2706:           double y = evaluatePoint(t).getY();
2707:           ymax = Math.max(y, ymax);
2708:           ymin = Math.min(y, ymin);
2709:         }
2710:         }
2711:       r0 = 2 * (x1 - x0);
2712:       r1 = 2 * (x2 - 2 * x1 + x0);
2713:       if (r1 != 0.0)
2714:         {
2715:       double t = -r0 / r1;
2716:       if (t > 0.0 && t < 1.0)
2717:         {
2718:           double x = evaluatePoint(t).getY();
2719:           xmax = Math.max(x, xmax);
2720:           xmin = Math.min(x, xmin);
2721:         }
2722:         }
2723: 
2724:       return (new Rectangle2D.Double(xmin, ymin, xmax - xmin, ymax - ymin));
2725:     }
2726: 
2727:     /**
2728:      * Returns a cubic segment corresponding to this curve
2729:      */
2730:     CubicSegment getCubicSegment()
2731:     {
2732:       double x1 = P1.getX() + 2.0 * (cp.getX() - P1.getX()) / 3.0;
2733:       double y1 = P1.getY() + 2.0 * (cp.getY() - P1.getY()) / 3.0;
2734:       double x2 = cp.getX() + (P2.getX() - cp.getX()) / 3.0;
2735:       double y2 = cp.getY() + (P2.getY() - cp.getY()) / 3.0;
2736: 
2737:       return new CubicSegment(P1.getX(), P1.getY(), x1, y1, x2, y2, P2.getX(),
2738:                               P2.getY());
2739:     }
2740: 
2741:     /**
2742:      * Returns the segment's midpoint
2743:      */
2744:     Point2D getMidPoint()
2745:     {
2746:       return evaluatePoint(0.5);
2747:     }
2748: 
2749:     /**
2750:      * Returns the PathIterator type of a segment
2751:      */
2752:     int getType()
2753:     {
2754:       return (PathIterator.SEG_QUADTO);
2755:     }
2756: 
2757:     /**
2758:      * Returns the PathIterator coords of a segment
2759:      */
2760:     int pathIteratorFormat(double[] coords)
2761:     {
2762:       coords[0] = cp.getX();
2763:       coords[1] = cp.getY();
2764:       coords[2] = P2.getX();
2765:       coords[3] = P2.getY();
2766:       return (PathIterator.SEG_QUADTO);
2767:     }
2768: 
2769:     /**
2770:      * Returns the number of intersections on the positive X axis,
2771:      * with the origin at (x,y), used for contains()-testing
2772:      */
2773:     int rayCrossing(double x, double y)
2774:     {
2775:       double x0 = P1.getX() - x;
2776:       double y0 = P1.getY() - y;
2777:       double x1 = cp.getX() - x;
2778:       double y1 = cp.getY() - y;
2779:       double x2 = P2.getX() - x;
2780:       double y2 = P2.getY() - y;
2781:       double[] r = new double[3];
2782:       int nRoots;
2783:       int nCrossings = 0;
2784: 
2785:       /* check if curve may intersect X+ axis. */
2786:       if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0) && (y0 * y1 <= 0 || y1 * y2 <= 0))
2787:         {
2788:       if (y0 == 0.0)
2789:         y0 -= EPSILON;
2790:       if (y2 == 0.0)
2791:         y2 -= EPSILON;
2792: 
2793:       r[0] = y0;
2794:       r[1] = 2 * (y1 - y0);
2795:       r[2] = (y2 - 2 * y1 + y0);
2796: 
2797:       nRoots = QuadCurve2D.solveQuadratic(r);
2798:       for (int i = 0; i < nRoots; i++)
2799:         if (r[i] > 0.0f && r[i] < 1.0f)
2800:           {
2801:         double t = r[i];
2802:         if (t * t * (x2 - 2 * x1 + x0) + 2 * t * (x1 - x0) + x0 > 0.0)
2803:           nCrossings++;
2804:           }
2805:         }
2806:       return nCrossings;
2807:     }
2808: 
2809:     /**
2810:      * Swap start and end points
2811:      */
2812:     void reverseCoords()
2813:     {
2814:       Point2D temp = P1;
2815:       P1 = P2;
2816:       P2 = temp;
2817:     }
2818: 
2819:     /**
2820:      * Splits intersections into nodes,
2821:      * This one handles quadratic-quadratic only,
2822:      * Quadratic-line is passed on to the LineSegment class,
2823:      * Quadratic-cubic is passed on to the CubicSegment class
2824:      */
2825:     int splitIntersections(Segment b)
2826:     {
2827:       if (b instanceof LineSegment)
2828:     return (b.splitIntersections(this));
2829: 
2830:       if (b instanceof CubicSegment)
2831:     return (b.splitIntersections(this));
2832: 
2833:       if (b instanceof QuadSegment)
2834:         {
2835:       // Use the cubic-cubic intersection routine for quads as well,
2836:       // Since a quadratic can be exactly described as a cubic, this
2837:       // should not be a problem; 
2838:       // The recursion depth will be the same in any case.
2839:       Intersection[] x = cubicCubicIntersect(getCubicSegment(),
2840:                                              ((QuadSegment) b)
2841:                                              .getCubicSegment());
2842:       if (x == null)
2843:         return 0;
2844: 
2845:       if (x.length == 1)
2846:         return createNode(b, (Intersection) x[0]);
2847: 
2848:       return createNodes(b, x);
2849:         }
2850:       return 0;
2851:     }
2852: 
2853:     /**
2854:      * Subdivides the segment at parametric value t, inserting
2855:      * the new segment into the linked list after this,
2856:      * such that this becomes [0,t] and this.next becomes [t,1]
2857:      */
2858:     void subdivideInsert(double t)
2859:     {
2860:       double x0 = P1.getX();
2861:       double y0 = P1.getY();
2862:       double x1 = cp.getX();
2863:       double y1 = cp.getY();
2864:       double x2 = P2.getX();
2865:       double y2 = P2.getY();
2866: 
2867:       double p10x = x0 + t * (x1 - x0);
2868:       double p10y = y0 + t * (y1 - y0);
2869:       double p11x = x1 + t * (x2 - x1);
2870:       double p11y = y1 + t * (y2 - y1);
2871:       double p20x = p10x + t * (p11x - p10x);
2872:       double p20y = p10y + t * (p11y - p10y);
2873: 
2874:       insert(new QuadSegment(p20x, p20y, p11x, p11y, x2, y2));
2875:       P2 = next.P1;
2876:       cp.setLocation(p10x, p10y);
2877: 
2878:       next.node = node;
2879:       node = null;
2880:     }
2881: 
2882:     /**
2883:      * Transforms the segment
2884:      */
2885:     void transform(AffineTransform at)
2886:     {
2887:       P1 = at.transform(P1, null);
2888:       P2 = at.transform(P2, null);
2889:       cp = at.transform(cp, null);
2890:     }
2891:   } // class QuadSegment
2892: 
2893:   /**
2894:    * Cubic Bezier curve segment
2895:    */
2896:   private class CubicSegment extends Segment
2897:   {
2898:     Point2D cp1; // control points
2899:     Point2D cp2; // control points
2900: 
2901:     /**
2902:      * Constructor - takes coordinates of the starting point,
2903:      * first control point, second control point and end point,
2904:      * respecively.
2905:      */
2906:     public CubicSegment(double x1, double y1, double c1x, double c1y,
2907:                         double c2x, double c2y, double x2, double y2)
2908:     {
2909:       super();
2910:       P1 = new Point2D.Double(x1, y1);
2911:       P2 = new Point2D.Double(x2, y2);
2912:       cp1 = new Point2D.Double(c1x, c1y);
2913:       cp2 = new Point2D.Double(c2x, c2y);
2914:     }
2915: 
2916:     /**
2917:      * Clones this segment
2918:      */
2919:     public Object clone()
2920:     {
2921:       return new CubicSegment(P1.getX(), P1.getY(), cp1.getX(), cp1.getY(),
2922:                               cp2.getX(), cp2.getY(), P2.getX(), P2.getY());
2923:     }
2924: 
2925:     /**
2926:      * Returns twice the area of a curve, relative the P1-P2 line
2927:      *
2928:      * The area formula can be derived by using Green's formula in the
2929:      * plane on the parametric form of the bezier.
2930:      */
2931:     double curveArea()
2932:     {
2933:       double x0 = P1.getX();
2934:       double y0 = P1.getY();
2935:       double x1 = cp1.getX();
2936:       double y1 = cp1.getY();
2937:       double x2 = cp2.getX();
2938:       double y2 = cp2.getY();
2939:       double x3 = P2.getX();
2940:       double y3 = P2.getY();
2941: 
2942:       double P = y3 - 3 * y2 + 3 * y1 - y0;
2943:       double Q = 3 * (y2 + y0 - 2 * y1);
2944:       double R = 3 * (y1 - y0);
2945: 
2946:       double A = x3 - 3 * x2 + 3 * x1 - x0;
2947:       double B = 3 * (x2 + x0 - 2 * x1);
2948:       double C = 3 * (x1 - x0);
2949: 
2950:       double area = (B * P - A * Q) / 5.0 + (C * P - A * R) / 2.0
2951:                     + (C * Q - B * R) / 3.0;
2952: 
2953:       return (area);
2954:     }
2955: 
2956:     /**
2957:      * Compare two segments.
2958:      */
2959:     boolean equals(Segment b)
2960:     {
2961:       if (! (b instanceof CubicSegment))
2962:     return false;
2963: 
2964:       return (P1.equals(b.P1) && cp1.equals(((CubicSegment) b).cp1)
2965:              && cp2.equals(((CubicSegment) b).cp2) && P2.equals(b.P2));
2966:     }
2967: 
2968:     /**
2969:      * Returns a Point2D corresponding to the parametric value t
2970:      * of the curve
2971:      */
2972:     Point2D evaluatePoint(double t)
2973:     {
2974:       double x0 = P1.getX();
2975:       double y0 = P1.getY();
2976:       double x1 = cp1.getX();
2977:       double y1 = cp1.getY();
2978:       double x2 = cp2.getX();
2979:       double y2 = cp2.getY();
2980:       double x3 = P2.getX();
2981:       double y3 = P2.getY();
2982: 
2983:       return new Point2D.Double(-(t * t * t) * (x0 - 3 * x1 + 3 * x2 - x3)
2984:                                 + 3 * t * t * (x0 - 2 * x1 + x2)
2985:                                 + 3 * t * (x1 - x0) + x0,
2986:                                 -(t * t * t) * (y0 - 3 * y1 + 3 * y2 - y3)
2987:                                 + 3 * t * t * (y0 - 2 * y1 + y2)
2988:                                 + 3 * t * (y1 - y0) + y0);
2989:     }
2990: 
2991:     /**
2992:      * Returns the bounding box of this segment
2993:      */
2994:     Rectangle2D getBounds()
2995:     {
2996:       double x0 = P1.getX();
2997:       double y0 = P1.getY();
2998:       double x1 = cp1.getX();
2999:       double y1 = cp1.getY();
3000:       double x2 = cp2.getX();
3001:       double y2 = cp2.getY();
3002:       double x3 = P2.getX();
3003:       double y3 = P2.getY();
3004:       double[] r = new double[3];
3005: 
3006:       double xmax = Math.max(x0, x3);
3007:       double ymax = Math.max(y0, y3);
3008:       double xmin = Math.min(x0, x3);
3009:       double ymin = Math.min(y0, y3);
3010: 
3011:       r[0] = 3 * (y1 - y0);
3012:       r[1] = 6.0 * (y2 + y0 - 2 * y1);
3013:       r[2] = 3.0 * (y3 - 3 * y2 + 3 * y1 - y0);
3014: 
3015:       int n = QuadCurve2D.solveQuadratic(r);
3016:       for (int i = 0; i < n; i++)
3017:         {
3018:       double t = r[i];
3019:       if (t > 0 && t < 1.0)
3020:         {
3021:           double y = evaluatePoint(t).getY();
3022:           ymax = Math.max(y, ymax);
3023:           ymin = Math.min(y, ymin);
3024:         }
3025:         }
3026: 
3027:       r[0] = 3 * (x1 - x0);
3028:       r[1] = 6.0 * (x2 + x0 - 2 * x1);
3029:       r[2] = 3.0 * (x3 - 3 * x2 + 3 * x1 - x0);
3030:       n = QuadCurve2D.solveQuadratic(r);
3031:       for (int i = 0; i < n; i++)
3032:         {
3033:       double t = r[i];
3034:       if (t > 0 && t < 1.0)
3035:         {
3036:           double x = evaluatePoint(t).getX();
3037:           xmax = Math.max(x, xmax);
3038:           xmin = Math.min(x, xmin);
3039:         }
3040:         }
3041:       return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
3042:     }
3043: 
3044:     /**
3045:      * Returns a CubicCurve2D object corresponding to this segment.
3046:      */
3047:     CubicCurve2D getCubicCurve2D()
3048:     {
3049:       return new CubicCurve2D.Double(P1.getX(), P1.getY(), cp1.getX(),
3050:                                      cp1.getY(), cp2.getX(), cp2.getY(),
3051:                                      P2.getX(), P2.getY());
3052:     }
3053: 
3054:     /**
3055:      * Returns the parametric points of self-intersection if the cubic
3056:      * is self-intersecting, null otherwise.
3057:      */
3058:     double[] getLoop()
3059:     {
3060:       double x0 = P1.getX();
3061:       double y0 = P1.getY();
3062:       double x1 = cp1.getX();
3063:       double y1 = cp1.getY();
3064:       double x2 = cp2.getX();
3065:       double y2 = cp2.getY();
3066:       double x3 = P2.getX();
3067:       double y3 = P2.getY();
3068:       double[] r = new double[4];
3069:       double k;
3070:       double R;
3071:       double T;
3072:       double A;
3073:       double B;
3074:       double[] results = new double[2];
3075: 
3076:       R = x3 - 3 * x2 + 3 * x1 - x0;
3077:       T = y3 - 3 * y2 + 3 * y1 - y0;
3078: 
3079:       // A qudratic
3080:       if (R == 0.0 && T == 0.0)
3081:     return null;
3082: 
3083:       // true cubic
3084:       if (R != 0.0 && T != 0.0)
3085:         {
3086:       A = 3 * (x2 + x0 - 2 * x1) / R;
3087:       B = 3 * (x1 - x0) / R;
3088: 
3089:       double P = 3 * (y2 + y0 - 2 * y1) / T;
3090:       double Q = 3 * (y1 - y0) / T;
3091: 
3092:       if (A == P || Q == B)
3093:         return null;
3094: 
3095:       k = (Q - B) / (A - P);
3096:         }
3097:       else
3098:         {
3099:       if (R == 0.0)
3100:         {
3101:           // quadratic in x
3102:           k = -(3 * (x1 - x0)) / (3 * (x2 + x0 - 2 * x1));
3103:           A = 3 * (y2 + y0 - 2 * y1) / T;
3104:           B = 3 * (y1 - y0) / T;
3105:         }
3106:       else
3107:         {
3108:           // quadratic in y
3109:           k = -(3 * (y1 - y0)) / (3 * (y2 + y0 - 2 * y1));
3110:           A = 3 * (x2 + x0 - 2 * x1) / R;
3111:           B = 3 * (x1 - x0) / R;
3112:         }
3113:         }
3114: 
3115:       r[0] = -k * k * k - A * k * k - B * k;
3116:       r[1] = 3 * k * k + 2 * k * A + 2 * B;
3117:       r[2] = -3 * k;
3118:       r[3] = 2;
3119: 
3120:       int n = CubicCurve2D.solveCubic(r);
3121:       if (n != 3)
3122:     return null;
3123: 
3124:       // sort r
3125:       double t;
3126:       for (int i = 0; i < 2; i++)
3127:     for (int j = i + 1; j < 3; j++)
3128:       if (r[j] < r[i])
3129:         {
3130:           t = r[i];
3131:           r[i] = r[j];
3132:           r[j] = t;
3133:         }
3134: 
3135:       if (Math.abs(r[0] + r[2] - k) < 1E-13)
3136:     if (r[0] >= 0.0 && r[0] <= 1.0 && r[2] >= 0.0 && r[2] <= 1.0)
3137:       if (evaluatePoint(r[0]).distance(evaluatePoint(r[2])) < PE_EPSILON * 10)
3138:         { // we snap the points anyway
3139:           results[0] = r[0];
3140:           results[1] = r[2];
3141:           return (results);
3142:         }
3143:       return null;
3144:     }
3145: 
3146:     /**
3147:      * Returns the segment's midpoint
3148:      */
3149:     Point2D getMidPoint()
3150:     {
3151:       return evaluatePoint(0.5);
3152:     }
3153: 
3154:     /**
3155:      * Returns the PathIterator type of a segment
3156:      */
3157:     int getType()
3158:     {
3159:       return (PathIterator.SEG_CUBICTO);
3160:     }
3161: 
3162:     /**
3163:      * Returns the PathIterator coords of a segment
3164:      */
3165:     int pathIteratorFormat(double[] coords)
3166:     {
3167:       coords[0] = cp1.getX();
3168:       coords[1] = cp1.getY();
3169:       coords[2] = cp2.getX();
3170:       coords[3] = cp2.getY();
3171:       coords[4] = P2.getX();
3172:       coords[5] = P2.getY();
3173:       return (PathIterator.SEG_CUBICTO);
3174:     }
3175: 
3176:     /**
3177:      * Returns the number of intersections on the positive X axis,
3178:      * with the origin at (x,y), used for contains()-testing
3179:      */
3180:     int rayCrossing(double x, double y)
3181:     {
3182:       double x0 = P1.getX() - x;
3183:       double y0 = P1.getY() - y;
3184:       double x1 = cp1.getX() - x;
3185:       double y1 = cp1.getY() - y;
3186:       double x2 = cp2.getX() - x;
3187:       double y2 = cp2.getY() - y;
3188:       double x3 = P2.getX() - x;
3189:       double y3 = P2.getY() - y;
3190:       double[] r = new double[4];
3191:       int nRoots;
3192:       int nCrossings = 0;
3193: 
3194:       /* check if curve may intersect X+ axis. */
3195:       if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0 || x3 > 0.0)
3196:           && (y0 * y1 <= 0 || y1 * y2 <= 0 || y2 * y3 <= 0))
3197:         {
3198:       if (y0 == 0.0)
3199:         y0 -= EPSILON;
3200:       if (y3 == 0.0)
3201:         y3 -= EPSILON;
3202: 
3203:       r[0] = y0;
3204:       r[1] = 3 * (y1 - y0);
3205:       r[2] = 3 * (y2 + y0 - 2 * y1);
3206:       r[3] = y3 - 3 * y2 + 3 * y1 - y0;
3207: 
3208:       if ((nRoots = CubicCurve2D.solveCubic(r)) > 0)
3209:         for (int i = 0; i < nRoots; i++)
3210:           {
3211:         if (r[i] > 0.0 && r[i] < 1.0)
3212:           {
3213:             double t = r[i];
3214:             if (-(t * t * t) * (x0 - 3 * x1 + 3 * x2 - x3)
3215:                 + 3 * t * t * (x0 - 2 * x1 + x2) + 3 * t * (x1 - x0)
3216:                 + x0 > 0.0)
3217:               nCrossings++;
3218:           }
3219:           }
3220:         }
3221:       return nCrossings;
3222:     }
3223: 
3224:     /**
3225:      * Swap start and end points
3226:      */
3227:     void reverseCoords()
3228:     {
3229:       Point2D p = P1;
3230:       P1 = P2;
3231:       P2 = p;
3232:       p = cp1; // swap control points
3233:       cp1 = cp2;
3234:       cp2 = p;
3235:     }
3236: 
3237:     /**
3238:      * Splits intersections into nodes,
3239:      * This one handles cubic-cubic and cubic-quadratic intersections
3240:      */
3241:     int splitIntersections(Segment b)
3242:     {
3243:       if (b instanceof LineSegment)
3244:     return (b.splitIntersections(this));
3245: 
3246:       Intersection[] x = null;
3247: 
3248:       if (b instanceof QuadSegment)
3249:     x = cubicCubicIntersect(this, ((QuadSegment) b).getCubicSegment());
3250: 
3251:       if (b instanceof CubicSegment)
3252:     x = cubicCubicIntersect(this, (CubicSegment) b);
3253: 
3254:       if (x == null)
3255:     return 0;
3256: 
3257:       if (x.length == 1)
3258:     return createNode(b, x[0]);
3259: 
3260:       return createNodes(b, x);
3261:     }
3262: 
3263:     /**
3264:      * Subdivides the segment at parametric value t, inserting
3265:      * the new segment into the linked list after this,
3266:      * such that this becomes [0,t] and this.next becomes [t,1]
3267:      */
3268:     void subdivideInsert(double t)
3269:     {
3270:       CubicSegment s = (CubicSegment) clone();
3271:       double p1x = (s.cp1.getX() - s.P1.getX()) * t + s.P1.getX();
3272:       double p1y = (s.cp1.getY() - s.P1.getY()) * t + s.P1.getY();
3273: 
3274:       double px = (s.cp2.getX() - s.cp1.getX()) * t + s.cp1.getX();
3275:       double py = (s.cp2.getY() - s.cp1.getY()) * t + s.cp1.getY();
3276: 
3277:       s.cp2.setLocation((s.P2.getX() - s.cp2.getX()) * t + s.cp2.getX(),
3278:                         (s.P2.getY() - s.cp2.getY()) * t + s.cp2.getY());
3279: 
3280:       s.cp1.setLocation((s.cp2.getX() - px) * t + px,
3281:                         (s.cp2.getY() - py) * t + py);
3282: 
3283:       double p2x = (px - p1x) * t + p1x;
3284:       double p2y = (py - p1y) * t + p1y;
3285: 
3286:       double p3x = (s.cp1.getX() - p2x) * t + p2x;
3287:       double p3y = (s.cp1.getY() - p2y) * t + p2y;
3288:       s.P1.setLocation(p3x, p3y);
3289: 
3290:       // insert new curve
3291:       insert(s);
3292: 
3293:       // set this curve
3294:       cp1.setLocation(p1x, p1y);
3295:       cp2.setLocation(p2x, p2y);
3296:       P2 = s.P1;
3297:       next.node = node;
3298:       node = null;
3299:     }
3300: 
3301:     /**
3302:      * Transforms the segment
3303:      */
3304:     void transform(AffineTransform at)
3305:     {
3306:       P1 = at.transform(P1, null);
3307:       P2 = at.transform(P2, null);
3308:       cp1 = at.transform(cp1, null);
3309:       cp2 = at.transform(cp2, null);
3310:     }
3311:   } // class CubicSegment
3312: } // class Area