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