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