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