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