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