1 /* Area.java -- represents a shape built by constructive area geometry
2 Copyright (C) 2002, 2004 Free Software Foundation
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
38 package java
.awt
.geom
;
40 import java
.awt
.Rectangle
;
41 import java
.awt
.Shape
;
42 import java
.util
.Vector
;
46 * The Area class represents any area for the purpose of
47 * Constructive Area Geometry (CAG) manipulations. CAG manipulations
48 * work as an area-wise form of boolean logic, where the basic operations are:
49 * <P><li>Add (in boolean algebra: A <B>or</B> B)<BR>
50 * <li>Subtract (in boolean algebra: A <B>and</B> (<B>not</B> B) )<BR>
51 * <li>Intersect (in boolean algebra: A <B>and</B> B)<BR>
52 * <li>Exclusive Or <BR>
53 * <img src="doc-files/Area-1.png" width="342" height="302"
54 * alt="Illustration of CAG operations" /><BR>
55 * Above is an illustration of the CAG operations on two ring shapes.<P>
57 * The contains and intersects() methods are also more accurate than the
58 * specification of #Shape requires.<P>
60 * Please note that constructing an Area can be slow
61 * (Self-intersection resolving is proportional to the square of
62 * the number of segments).<P>
64 * @see #subtract(Area)
65 * @see #intersect(Area)
66 * @see #exclusiveOr(Area)
68 * @author Sven de Marothy (sven@physto.se)
71 * @status Works, but could be faster and more reliable.
73 public class Area
implements Shape
, Cloneable
76 * General numerical precision
78 private static final double EPSILON
= 1E-11;
81 * recursive subdivision epsilon - (see getRecursionDepth)
83 private static final double RS_EPSILON
= 1E-13;
86 * Snap distance - points within this distance are considered equal
88 private static final double PE_EPSILON
= 1E-11;
91 * Segment vectors containing solid areas and holes
93 private Vector solids
;
96 * Segment vectors containing solid areas and holes
101 * Vector (temporary) storing curve-curve intersections
103 private Vector cc_intersections
;
106 * Winding rule WIND_NON_ZERO used, after construction,
107 * this is irrelevant.
109 private int windingRule
;
112 * Constructs an empty Area
116 solids
= new Vector();
117 holes
= new Vector();
121 * Constructs an Area from any given Shape. <P>
123 * If the Shape is self-intersecting, the created Area will consist
124 * of non-self-intersecting subpaths, and any inner paths which
125 * are found redundant in accordance with the Shape's winding rule
126 * will not be included.
128 * @param s the shape (<code>null</code> not permitted).
130 * @throws NullPointerException if <code>s</code> is <code>null</code>.
136 Vector p
= makeSegment(s
);
142 // delete empty paths
143 for (int i
= 0; i
< p
.size(); i
++)
144 if (((Segment
) p
.elementAt(i
)).getSignedArea() == 0.0)
148 * Resolve self intersecting paths into non-intersecting
150 * Algorithm is as follows:
151 * 1: Create nodes at all self intersections
152 * 2: Put all segments into a list
153 * 3: Grab a segment, follow it, change direction at each node,
154 * removing segments from the list in the process
155 * 4: Repeat (3) until no segments remain in the list
156 * 5: Remove redundant paths and sort into solids and holes
158 Vector paths
= new Vector();
161 for (int i
= 0; i
< p
.size(); i
++)
163 Segment path
= (Segment
) p
.elementAt(i
);
164 createNodesSelf(path
);
169 for (int i
= 0; i
< p
.size() - 1; i
++)
170 for (int j
= i
+ 1; j
< p
.size(); j
++)
172 Segment path1
= (Segment
) p
.elementAt(i
);
173 Segment path2
= (Segment
) p
.elementAt(j
);
174 createNodes(path1
, path2
);
178 // we have intersecting points.
179 Vector segments
= new Vector();
181 for (int i
= 0; i
< p
.size(); i
++)
183 Segment path
= v
= (Segment
) p
.elementAt(i
);
192 paths
= weilerAtherton(segments
);
193 deleteRedundantPaths(paths
);
197 * Performs an add (union) operation on this area with another Area.<BR>
198 * @param area - the area to be unioned with this one
200 public void add(Area area
)
207 Area B
= (Area
) area
.clone();
209 Vector pathA
= new Vector();
210 Vector pathB
= new Vector();
211 pathA
.addAll(solids
);
213 pathB
.addAll(B
.solids
);
214 pathB
.addAll(B
.holes
);
218 for (int i
= 0; i
< pathA
.size(); i
++)
220 Segment a
= (Segment
) pathA
.elementAt(i
);
221 for (int j
= 0; j
< pathB
.size(); j
++)
223 Segment b
= (Segment
) pathB
.elementAt(j
);
224 nNodes
+= createNodes(a
, b
);
228 Vector paths
= new Vector();
231 // we have intersecting points.
232 Vector segments
= new Vector();
234 // In a union operation, we keep all
235 // segments of A oustide B and all B outside A
236 for (int i
= 0; i
< pathA
.size(); i
++)
238 v
= (Segment
) pathA
.elementAt(i
);
242 if (v
.isSegmentOutside(area
))
249 for (int i
= 0; i
< pathB
.size(); i
++)
251 v
= (Segment
) pathB
.elementAt(i
);
255 if (v
.isSegmentOutside(this))
262 paths
= weilerAtherton(segments
);
263 deleteRedundantPaths(paths
);
267 * Performs a subtraction operation on this Area.<BR>
268 * @param area the area to be subtracted from this area.
269 * @throws NullPointerException if <code>area</code> is <code>null</code>.
271 public void subtract(Area area
)
273 if (isEmpty() || area
.isEmpty())
282 Vector pathA
= new Vector();
283 Area B
= (Area
) area
.clone();
284 pathA
.addAll(solids
);
287 // reverse the directions of B paths.
288 setDirection(B
.holes
, true);
289 setDirection(B
.solids
, false);
291 Vector pathB
= new Vector();
292 pathB
.addAll(B
.solids
);
293 pathB
.addAll(B
.holes
);
298 for (int i
= 0; i
< pathA
.size(); i
++)
300 Segment a
= (Segment
) pathA
.elementAt(i
);
301 for (int j
= 0; j
< pathB
.size(); j
++)
303 Segment b
= (Segment
) pathB
.elementAt(j
);
304 nNodes
+= createNodes(a
, b
);
308 Vector paths
= new Vector();
310 // we have intersecting points.
311 Vector segments
= new Vector();
313 // In a subtraction operation, we keep all
314 // segments of A oustide B and all B within A
315 // We outsideness-test only one segment in each path
316 // and the segments before and after any node
317 for (int i
= 0; i
< pathA
.size(); i
++)
319 Segment v
= (Segment
) pathA
.elementAt(i
);
321 if (v
.isSegmentOutside(area
) && v
.node
== null)
323 boolean node
= false;
326 if ((v
.node
!= null || node
))
328 node
= (v
.node
!= null);
329 if (v
.isSegmentOutside(area
))
337 for (int i
= 0; i
< pathB
.size(); i
++)
339 Segment v
= (Segment
) pathB
.elementAt(i
);
341 if (! v
.isSegmentOutside(this) && v
.node
== null)
344 boolean node
= false;
347 if ((v
.node
!= null || node
))
349 node
= (v
.node
!= null);
350 if (! v
.isSegmentOutside(this))
358 paths
= weilerAtherton(segments
);
359 deleteRedundantPaths(paths
);
363 * Performs an intersection operation on this Area.<BR>
364 * @param area - the area to be intersected with this area.
365 * @throws NullPointerException if <code>area</code> is <code>null</code>.
367 public void intersect(Area area
)
369 if (isEmpty() || area
.isEmpty())
377 Vector pathA
= new Vector();
378 Area B
= (Area
) area
.clone();
379 pathA
.addAll(solids
);
382 Vector pathB
= new Vector();
383 pathB
.addAll(B
.solids
);
384 pathB
.addAll(B
.holes
);
389 for (int i
= 0; i
< pathA
.size(); i
++)
391 Segment a
= (Segment
) pathA
.elementAt(i
);
392 for (int j
= 0; j
< pathB
.size(); j
++)
394 Segment b
= (Segment
) pathB
.elementAt(j
);
395 nNodes
+= createNodes(a
, b
);
399 Vector paths
= new Vector();
401 // we have intersecting points.
402 Vector segments
= new Vector();
404 // In an intersection operation, we keep all
405 // segments of A within B and all B within A
406 // (The rest must be redundant)
407 // We outsideness-test only one segment in each path
408 // and the segments before and after any node
409 for (int i
= 0; i
< pathA
.size(); i
++)
411 Segment v
= (Segment
) pathA
.elementAt(i
);
413 if (! v
.isSegmentOutside(area
) && v
.node
== null)
415 boolean node
= false;
418 if ((v
.node
!= null || node
))
420 node
= (v
.node
!= null);
421 if (! v
.isSegmentOutside(area
))
429 for (int i
= 0; i
< pathB
.size(); i
++)
431 Segment v
= (Segment
) pathB
.elementAt(i
);
433 if (! v
.isSegmentOutside(this) && v
.node
== null)
436 boolean node
= false;
439 if ((v
.node
!= null || node
))
441 node
= (v
.node
!= null);
442 if (! v
.isSegmentOutside(this))
450 paths
= weilerAtherton(segments
);
451 deleteRedundantPaths(paths
);
455 * Performs an exclusive-or operation on this Area.<BR>
456 * @param area - the area to be XORed with this area.
457 * @throws NullPointerException if <code>area</code> is <code>null</code>.
459 public void exclusiveOr(Area area
)
466 Area B
= (Area
) area
.clone();
477 Vector pathA
= new Vector();
479 Area B
= (Area
) area
.clone();
480 Vector pathB
= new Vector();
481 pathA
.addAll(solids
);
484 // reverse the directions of B paths.
485 setDirection(B
.holes
, true);
486 setDirection(B
.solids
, false);
487 pathB
.addAll(B
.solids
);
488 pathB
.addAll(B
.holes
);
492 for (int i
= 0; i
< pathA
.size(); i
++)
494 Segment a
= (Segment
) pathA
.elementAt(i
);
495 for (int j
= 0; j
< pathB
.size(); j
++)
497 Segment b
= (Segment
) pathB
.elementAt(j
);
498 nNodes
+= createNodes(a
, b
);
502 Vector paths
= new Vector();
505 // we have intersecting points.
506 Vector segments
= new Vector();
508 // In an XOR operation, we operate on all segments
509 for (int i
= 0; i
< pathA
.size(); i
++)
511 v
= (Segment
) pathA
.elementAt(i
);
521 for (int i
= 0; i
< pathB
.size(); i
++)
523 v
= (Segment
) pathB
.elementAt(i
);
533 paths
= weilerAtherton(segments
);
534 deleteRedundantPaths(paths
);
538 * Clears the Area object, creating an empty area.
542 solids
= new Vector();
543 holes
= new Vector();
547 * Returns whether this area encloses any area.
548 * @return true if the object encloses any area.
550 public boolean isEmpty()
552 if (solids
.size() == 0)
555 double totalArea
= 0;
556 for (int i
= 0; i
< solids
.size(); i
++)
557 totalArea
+= Math
.abs(((Segment
) solids
.elementAt(i
)).getSignedArea());
558 for (int i
= 0; i
< holes
.size(); i
++)
559 totalArea
-= Math
.abs(((Segment
) holes
.elementAt(i
)).getSignedArea());
560 if (totalArea
<= EPSILON
)
567 * Determines whether the Area consists entirely of line segments
568 * @return true if the Area lines-only, false otherwise
570 public boolean isPolygonal()
572 for (int i
= 0; i
< holes
.size(); i
++)
573 if (! ((Segment
) holes
.elementAt(i
)).isPolygonal())
575 for (int i
= 0; i
< solids
.size(); i
++)
576 if (! ((Segment
) solids
.elementAt(i
)).isPolygonal())
582 * Determines if the Area is rectangular.<P>
584 * This is strictly qualified. An area is considered rectangular if:<BR>
585 * <li>It consists of a single polygonal path.<BR>
586 * <li>It is oriented parallel/perpendicular to the xy axis<BR>
587 * <li>It must be exactly rectangular, i.e. small errors induced by
588 * transformations may cause a false result, although the area is
589 * visibly rectangular.<P>
590 * @return true if the above criteria are met, false otherwise
592 public boolean isRectangular()
597 if (holes
.size() != 0 || solids
.size() != 1)
600 Segment path
= (Segment
) solids
.elementAt(0);
601 if (! path
.isPolygonal())
609 double d1
= (s
.P2
.getX() - s
.P1
.getX())*(s2
.P2
.getX() - s2
.P1
.getX())/
610 ((s
.P1
.distance(s
.P2
)) * (s2
.P1
.distance(s2
.P2
)));
611 double d2
= (s
.P2
.getY() - s
.P1
.getY())*(s2
.P2
.getY() - s2
.P1
.getY())/
612 ((s
.P1
.distance(s
.P2
)) * (s2
.P1
.distance(s2
.P2
)));
613 double dotproduct
= d1
+ d2
;
615 // For some reason, only rectangles on the XY axis count.
616 if (d1
!= 0 && d2
!= 0)
619 if (Math
.abs(dotproduct
) == 0) // 90 degree angle
621 else if ((Math
.abs(1.0 - dotproduct
) > 0)) // 0 degree angle?
622 return false; // if not, return false
628 return nCorners
== 4;
632 * Returns whether the Area consists of more than one simple
633 * (non self-intersecting) subpath.
635 * @return true if the Area consists of none or one simple subpath,
638 public boolean isSingular()
640 return (holes
.size() == 0 && solids
.size() <= 1);
644 * Returns the bounding box of the Area.<P> Unlike the CubicCurve2D and
645 * QuadraticCurve2D classes, this method will return the tightest possible
646 * bounding box, evaluating the extreme points of each curved segment.<P>
647 * @return the bounding box
649 public Rectangle2D
getBounds2D()
651 if (solids
.size() == 0)
652 return new Rectangle2D
.Double(0.0, 0.0, 0.0, 0.0);
658 xmin
= xmax
= ((Segment
) solids
.elementAt(0)).P1
.getX();
659 ymin
= ymax
= ((Segment
) solids
.elementAt(0)).P1
.getY();
661 for (int path
= 0; path
< solids
.size(); path
++)
663 Rectangle2D r
= ((Segment
) solids
.elementAt(path
)).getPathBounds();
664 xmin
= Math
.min(r
.getMinX(), xmin
);
665 ymin
= Math
.min(r
.getMinY(), ymin
);
666 xmax
= Math
.max(r
.getMaxX(), xmax
);
667 ymax
= Math
.max(r
.getMaxY(), ymax
);
670 return (new Rectangle2D
.Double(xmin
, ymin
, (xmax
- xmin
), (ymax
- ymin
)));
674 * Returns the bounds of this object in Rectangle format.
675 * Please note that this may lead to loss of precision.
677 * @return The bounds.
678 * @see #getBounds2D()
680 public Rectangle
getBounds()
682 return getBounds2D().getBounds();
686 * Create a new area of the same run-time type with the same contents as
691 public Object
clone()
695 Area clone
= new Area();
696 for (int i
= 0; i
< solids
.size(); i
++)
697 clone
.solids
.add(((Segment
) solids
.elementAt(i
)).cloneSegmentList());
698 for (int i
= 0; i
< holes
.size(); i
++)
699 clone
.holes
.add(((Segment
) holes
.elementAt(i
)).cloneSegmentList());
702 catch (CloneNotSupportedException e
)
704 throw (Error
) new InternalError().initCause(e
); // Impossible
709 * Compares two Areas.
711 * @param area the area to compare against this area (<code>null</code>
713 * @return <code>true</code> if the areas are equal, and <code>false</code>
716 public boolean equals(Area area
)
721 if (! getBounds2D().equals(area
.getBounds2D()))
724 if (solids
.size() != area
.solids
.size()
725 || holes
.size() != area
.holes
.size())
728 Vector pathA
= new Vector();
729 pathA
.addAll(solids
);
731 Vector pathB
= new Vector();
732 pathB
.addAll(area
.solids
);
733 pathB
.addAll(area
.holes
);
735 int nPaths
= pathA
.size();
736 boolean[][] match
= new boolean[2][nPaths
];
738 for (int i
= 0; i
< nPaths
; i
++)
740 for (int j
= 0; j
< nPaths
; j
++)
742 Segment p1
= (Segment
) pathA
.elementAt(i
);
743 Segment p2
= (Segment
) pathB
.elementAt(j
);
744 if (! match
[0][i
] && ! match
[1][j
])
745 if (p1
.pathEquals(p2
))
746 match
[0][i
] = match
[1][j
] = true;
750 boolean result
= true;
751 for (int i
= 0; i
< nPaths
; i
++)
752 result
= result
&& match
[0][i
] && match
[1][i
];
757 * Transforms this area by the AffineTransform at.
759 * @param at the transform.
761 public void transform(AffineTransform at
)
763 for (int i
= 0; i
< solids
.size(); i
++)
764 ((Segment
) solids
.elementAt(i
)).transformSegmentList(at
);
765 for (int i
= 0; i
< holes
.size(); i
++)
766 ((Segment
) holes
.elementAt(i
)).transformSegmentList(at
);
768 // Note that the orientation is not invariant under inversion
769 if ((at
.getType() & AffineTransform
.TYPE_FLIP
) != 0)
771 setDirection(holes
, false);
772 setDirection(solids
, true);
777 * Returns a new Area equal to this one, transformed
778 * by the AffineTransform at.
779 * @param at the transform.
780 * @return the transformed area
781 * @throws NullPointerException if <code>at</code> is <code>null</code>.
783 public Area
createTransformedArea(AffineTransform at
)
785 Area a
= (Area
) clone();
791 * Determines if the point (x,y) is contained within this Area.
793 * @param x the x-coordinate of the point.
794 * @param y the y-coordinate of the point.
795 * @return true if the point is contained, false otherwise.
797 public boolean contains(double x
, double y
)
800 for (int i
= 0; i
< solids
.size(); i
++)
801 if (((Segment
) solids
.elementAt(i
)).contains(x
, y
))
804 for (int i
= 0; i
< holes
.size(); i
++)
805 if (((Segment
) holes
.elementAt(i
)).contains(x
, y
))
812 * Determines if the Point2D p is contained within this Area.
814 * @param p the point.
815 * @return <code>true</code> if the point is contained, <code>false</code>
817 * @throws NullPointerException if <code>p</code> is <code>null</code>.
819 public boolean contains(Point2D p
)
821 return contains(p
.getX(), p
.getY());
825 * Determines if the rectangle specified by (x,y) as the upper-left
826 * and with width w and height h is completely contained within this Area,
827 * returns false otherwise.<P>
829 * This method should always produce the correct results, unlike for other
832 * @param x the x-coordinate of the rectangle.
833 * @param y the y-coordinate of the rectangle.
834 * @param w the width of the the rectangle.
835 * @param h the height of the rectangle.
836 * @return <code>true</code> if the rectangle is considered contained
838 public boolean contains(double x
, double y
, double w
, double h
)
840 LineSegment
[] l
= new LineSegment
[4];
841 l
[0] = new LineSegment(x
, y
, x
+ w
, y
);
842 l
[1] = new LineSegment(x
, y
+ h
, x
+ w
, y
+ h
);
843 l
[2] = new LineSegment(x
, y
, x
, y
+ h
);
844 l
[3] = new LineSegment(x
+ w
, y
, x
+ w
, y
+ h
);
846 // Since every segment in the area must a contour
847 // between inside/outside segments, ANY intersection
848 // will mean the rectangle is not entirely contained.
849 for (int i
= 0; i
< 4; i
++)
851 for (int path
= 0; path
< solids
.size(); path
++)
855 start
= v
= (Segment
) solids
.elementAt(path
);
858 if (l
[i
].hasIntersections(v
))
864 for (int path
= 0; path
< holes
.size(); path
++)
868 start
= v
= (Segment
) holes
.elementAt(path
);
871 if (l
[i
].hasIntersections(v
))
879 // Is any point inside?
880 if (! contains(x
, y
))
883 // Final hoop: Is the rectangle non-intersecting and inside,
884 // but encloses a hole?
885 Rectangle2D r
= new Rectangle2D
.Double(x
, y
, w
, h
);
886 for (int path
= 0; path
< holes
.size(); path
++)
887 if (! ((Segment
) holes
.elementAt(path
)).isSegmentOutside(r
))
894 * Determines if the Rectangle2D specified by r is completely contained
895 * within this Area, returns false otherwise.<P>
897 * This method should always produce the correct results, unlike for other
900 * @param r the rectangle.
901 * @return <code>true</code> if the rectangle is considered contained
903 * @throws NullPointerException if <code>r</code> is <code>null</code>.
905 public boolean contains(Rectangle2D r
)
907 return contains(r
.getX(), r
.getY(), r
.getWidth(), r
.getHeight());
911 * Determines if the rectangle specified by (x,y) as the upper-left
912 * and with width w and height h intersects any part of this Area.
914 * @param x the x-coordinate for the rectangle.
915 * @param y the y-coordinate for the rectangle.
916 * @param w the width of the rectangle.
917 * @param h the height of the rectangle.
918 * @return <code>true</code> if the rectangle intersects the area,
919 * <code>false</code> otherwise.
921 public boolean intersects(double x
, double y
, double w
, double h
)
923 if (solids
.size() == 0)
926 LineSegment
[] l
= new LineSegment
[4];
927 l
[0] = new LineSegment(x
, y
, x
+ w
, y
);
928 l
[1] = new LineSegment(x
, y
+ h
, x
+ w
, y
+ h
);
929 l
[2] = new LineSegment(x
, y
, x
, y
+ h
);
930 l
[3] = new LineSegment(x
+ w
, y
, x
+ w
, y
+ h
);
932 // Return true on any intersection
933 for (int i
= 0; i
< 4; i
++)
935 for (int path
= 0; path
< solids
.size(); path
++)
939 start
= v
= (Segment
) solids
.elementAt(path
);
942 if (l
[i
].hasIntersections(v
))
948 for (int path
= 0; path
< holes
.size(); path
++)
952 start
= v
= (Segment
) holes
.elementAt(path
);
955 if (l
[i
].hasIntersections(v
))
963 // Non-intersecting, Is any point inside?
964 if (contains(x
+ w
* 0.5, y
+ h
* 0.5))
967 // What if the rectangle encloses the whole shape?
968 Point2D p
= ((Segment
) solids
.elementAt(0)).getMidPoint();
969 if ((new Rectangle2D
.Double(x
, y
, w
, h
)).contains(p
))
975 * Determines if the Rectangle2D specified by r intersects any
977 * @param r the rectangle to test intersection with (<code>null</code>
979 * @return <code>true</code> if the rectangle intersects the area,
980 * <code>false</code> otherwise.
981 * @throws NullPointerException if <code>r</code> is <code>null</code>.
983 public boolean intersects(Rectangle2D r
)
985 return intersects(r
.getX(), r
.getY(), r
.getWidth(), r
.getHeight());
989 * Returns a PathIterator object defining the contour of this Area,
992 * @param at the transform.
993 * @return A path iterator.
995 public PathIterator
getPathIterator(AffineTransform at
)
997 return (new AreaIterator(at
));
1001 * Returns a flattened PathIterator object defining the contour of this
1002 * Area, transformed by at and with a defined flatness.
1004 * @param at the transform.
1005 * @param flatness the flatness.
1006 * @return A path iterator.
1008 public PathIterator
getPathIterator(AffineTransform at
, double flatness
)
1010 return new FlatteningPathIterator(getPathIterator(at
), flatness
);
1013 //---------------------------------------------------------------------
1014 // Non-public methods and classes
1017 * Private pathiterator object.
1019 private class AreaIterator
implements PathIterator
1021 private Vector segments
;
1023 private AffineTransform at
;
1025 // Simple compound type for segments
1026 class IteratorSegment
1033 coords
= new double[6];
1038 * The contructor here does most of the work,
1039 * creates a vector of IteratorSegments, which can
1040 * readily be returned
1042 public AreaIterator(AffineTransform at
)
1046 segments
= new Vector();
1047 Vector allpaths
= new Vector();
1048 allpaths
.addAll(solids
);
1049 allpaths
.addAll(holes
);
1051 for (int i
= 0; i
< allpaths
.size(); i
++)
1053 Segment v
= (Segment
) allpaths
.elementAt(i
);
1056 IteratorSegment is
= new IteratorSegment();
1057 is
.type
= SEG_MOVETO
;
1058 is
.coords
[0] = start
.P1
.getX();
1059 is
.coords
[1] = start
.P1
.getY();
1064 is
= new IteratorSegment();
1065 is
.type
= v
.pathIteratorFormat(is
.coords
);
1071 is
= new IteratorSegment();
1072 is
.type
= SEG_CLOSE
;
1077 public int currentSegment(double[] coords
)
1079 IteratorSegment s
= (IteratorSegment
) segments
.elementAt(index
);
1081 at
.transform(s
.coords
, 0, coords
, 0, 3);
1083 for (int i
= 0; i
< 6; i
++)
1084 coords
[i
] = s
.coords
[i
];
1088 public int currentSegment(float[] coords
)
1090 IteratorSegment s
= (IteratorSegment
) segments
.elementAt(index
);
1091 double[] d
= new double[6];
1094 at
.transform(s
.coords
, 0, d
, 0, 3);
1095 for (int i
= 0; i
< 6; i
++)
1096 coords
[i
] = (float) d
[i
];
1099 for (int i
= 0; i
< 6; i
++)
1100 coords
[i
] = (float) s
.coords
[i
];
1104 // Note that the winding rule should not matter here,
1105 // EVEN_ODD is chosen because it renders faster.
1106 public int getWindingRule()
1108 return (PathIterator
.WIND_EVEN_ODD
);
1111 public boolean isDone()
1113 return (index
>= segments
.size());
1123 * Performs the fundamental task of the Weiler-Atherton algorithm,
1124 * traverse a list of segments, for each segment:
1125 * Follow it, removing segments from the list and switching paths
1126 * at each node. Do so until the starting segment is reached.
1128 * Returns a Vector of the resulting paths.
1130 private Vector
weilerAtherton(Vector segments
)
1132 Vector paths
= new Vector();
1133 while (segments
.size() > 0)
1135 // Iterate over the path
1136 Segment start
= (Segment
) segments
.elementAt(0);
1146 s
= s
.next
; // continue
1156 * A small wrapper class to store intersection points
1158 private class Intersection
1160 Point2D p
; // the 2D point of intersection
1161 double ta
; // the parametric value on a
1162 double tb
; // the parametric value on b
1163 Segment seg
; // segment placeholder for node setting
1165 public Intersection(Point2D p
, double ta
, double tb
)
1174 * Returns the recursion depth necessary to approximate the
1175 * curve by line segments within the error RS_EPSILON.
1177 * This is done with Wang's formula:
1178 * L0 = max{0<=i<=N-2}(|xi - 2xi+1 + xi+2|,|yi - 2yi+1 + yi+2|)
1179 * r0 = log4(sqrt(2)*N*(N-1)*L0/8e)
1180 * Where e is the maximum distance error (RS_EPSILON)
1182 private int getRecursionDepth(CubicSegment curve
)
1184 double x0
= curve
.P1
.getX();
1185 double y0
= curve
.P1
.getY();
1187 double x1
= curve
.cp1
.getX();
1188 double y1
= curve
.cp1
.getY();
1190 double x2
= curve
.cp2
.getX();
1191 double y2
= curve
.cp2
.getY();
1193 double x3
= curve
.P2
.getX();
1194 double y3
= curve
.P2
.getY();
1196 double L0
= Math
.max(Math
.max(Math
.abs(x0
- 2 * x1
+ x2
),
1197 Math
.abs(x1
- 2 * x2
+ x3
)),
1198 Math
.max(Math
.abs(y0
- 2 * y1
+ y2
),
1199 Math
.abs(y1
- 2 * y2
+ y3
)));
1201 double f
= Math
.sqrt(2) * 6.0 * L0
/ (8.0 * RS_EPSILON
);
1203 int r0
= (int) Math
.ceil(Math
.log(f
) / Math
.log(4.0));
1208 * Performs recursive subdivision:
1209 * @param c1 - curve 1
1210 * @param c2 - curve 2
1211 * @param depth1 - recursion depth of curve 1
1212 * @param depth2 - recursion depth of curve 2
1213 * @param t1 - global parametric value of the first curve's starting point
1214 * @param t2 - global parametric value of the second curve's starting point
1215 * @param w1 - global parametric length of curve 1
1216 * @param c1 - global parametric length of curve 2
1218 * The final four parameters are for keeping track of the parametric
1219 * value of the curve. For a full curve t = 0, w = 1, w is halved with
1222 private void recursiveSubdivide(CubicCurve2D c1
, CubicCurve2D c2
,
1223 int depth1
, int depth2
, double t1
,
1224 double t2
, double w1
, double w2
)
1226 boolean flat1
= depth1
<= 0;
1227 boolean flat2
= depth2
<= 0;
1231 double xlk
= c1
.getP2().getX() - c1
.getP1().getX();
1232 double ylk
= c1
.getP2().getY() - c1
.getP1().getY();
1234 double xnm
= c2
.getP2().getX() - c2
.getP1().getX();
1235 double ynm
= c2
.getP2().getY() - c2
.getP1().getY();
1237 double xmk
= c2
.getP1().getX() - c1
.getP1().getX();
1238 double ymk
= c2
.getP1().getY() - c1
.getP1().getY();
1239 double det
= xnm
* ylk
- ynm
* xlk
;
1241 if (det
+ 1.0 == 1.0)
1244 double detinv
= 1.0 / det
;
1245 double s
= (xnm
* ymk
- ynm
* xmk
) * detinv
;
1246 double t
= (xlk
* ymk
- ylk
* xmk
) * detinv
;
1247 if ((s
< 0.0) || (s
> 1.0) || (t
< 0.0) || (t
> 1.0))
1250 double[] temp
= new double[2];
1251 temp
[0] = t1
+ s
* w1
;
1252 temp
[1] = t2
+ t
* w1
;
1253 cc_intersections
.add(temp
);
1257 CubicCurve2D
.Double c11
= new CubicCurve2D
.Double();
1258 CubicCurve2D
.Double c12
= new CubicCurve2D
.Double();
1259 CubicCurve2D
.Double c21
= new CubicCurve2D
.Double();
1260 CubicCurve2D
.Double c22
= new CubicCurve2D
.Double();
1262 if (! flat1
&& ! flat2
)
1268 c1
.subdivide(c11
, c12
);
1269 c2
.subdivide(c21
, c22
);
1270 if (c11
.getBounds2D().intersects(c21
.getBounds2D()))
1271 recursiveSubdivide(c11
, c21
, depth1
, depth2
, t1
, t2
, w1
, w2
);
1272 if (c11
.getBounds2D().intersects(c22
.getBounds2D()))
1273 recursiveSubdivide(c11
, c22
, depth1
, depth2
, t1
, t2
+ w2
, w1
, w2
);
1274 if (c12
.getBounds2D().intersects(c21
.getBounds2D()))
1275 recursiveSubdivide(c12
, c21
, depth1
, depth2
, t1
+ w1
, t2
, w1
, w2
);
1276 if (c12
.getBounds2D().intersects(c22
.getBounds2D()))
1277 recursiveSubdivide(c12
, c22
, depth1
, depth2
, t1
+ w1
, t2
+ w2
, w1
, w2
);
1284 c1
.subdivide(c11
, c12
);
1286 if (c11
.getBounds2D().intersects(c2
.getBounds2D()))
1287 recursiveSubdivide(c11
, c2
, depth1
, depth2
, t1
, t2
, w1
, w2
);
1288 if (c12
.getBounds2D().intersects(c2
.getBounds2D()))
1289 recursiveSubdivide(c12
, c2
, depth1
, depth2
, t1
+ w1
, t2
, w1
, w2
);
1294 c2
.subdivide(c21
, c22
);
1296 if (c1
.getBounds2D().intersects(c21
.getBounds2D()))
1297 recursiveSubdivide(c1
, c21
, depth1
, depth2
, t1
, t2
, w1
, w2
);
1298 if (c1
.getBounds2D().intersects(c22
.getBounds2D()))
1299 recursiveSubdivide(c1
, c22
, depth1
, depth2
, t1
, t2
+ w2
, w1
, w2
);
1303 * Returns a set of interesections between two Cubic segments
1304 * Or null if no intersections were found.
1306 * The method used to find the intersection is recursive midpoint
1307 * subdivision. Outline description:
1309 * 1) Check if the bounding boxes of the curves intersect,
1310 * 2) If so, divide the curves in the middle and test the bounding
1312 * 3) Repeat until a maximum recursion depth has been reached, where
1313 * the intersecting curves can be approximated by line segments.
1315 * This is a reasonably accurate method, although the recursion depth
1316 * is typically around 20, the bounding-box tests allow for significant
1317 * pruning of the subdivision tree.
1319 private Intersection
[] cubicCubicIntersect(CubicSegment curve1
,
1320 CubicSegment curve2
)
1322 Rectangle2D r1
= curve1
.getBounds();
1323 Rectangle2D r2
= curve2
.getBounds();
1325 if (! r1
.intersects(r2
))
1328 cc_intersections
= new Vector();
1329 recursiveSubdivide(curve1
.getCubicCurve2D(), curve2
.getCubicCurve2D(),
1330 getRecursionDepth(curve1
), getRecursionDepth(curve2
),
1331 0.0, 0.0, 1.0, 1.0);
1333 if (cc_intersections
.size() == 0)
1336 Intersection
[] results
= new Intersection
[cc_intersections
.size()];
1337 for (int i
= 0; i
< cc_intersections
.size(); i
++)
1339 double[] temp
= (double[]) cc_intersections
.elementAt(i
);
1340 results
[i
] = new Intersection(curve1
.evaluatePoint(temp
[0]), temp
[0],
1343 cc_intersections
= null;
1348 * Returns the intersections between a line and a quadratic bezier
1349 * Or null if no intersections are found1
1350 * This is done through combining the line's equation with the
1351 * parametric form of the Bezier and solving the resulting quadratic.
1353 private Intersection
[] lineQuadIntersect(LineSegment l
, QuadSegment c
)
1355 double[] y
= new double[3];
1356 double[] x
= new double[3];
1357 double[] r
= new double[3];
1359 double x0
= c
.P1
.getX();
1360 double y0
= c
.P1
.getY();
1361 double x1
= c
.cp
.getX();
1362 double y1
= c
.cp
.getY();
1363 double x2
= c
.P2
.getX();
1364 double y2
= c
.P2
.getY();
1366 double lx0
= l
.P1
.getX();
1367 double ly0
= l
.P1
.getY();
1368 double lx1
= l
.P2
.getX();
1369 double ly1
= l
.P2
.getY();
1370 double dx
= lx1
- lx0
;
1371 double dy
= ly1
- ly0
;
1373 // form r(t) = y(t) - x(t) for the bezier
1375 y
[1] = 2 * (y1
- y0
);
1376 y
[2] = (y2
- 2 * y1
+ y0
);
1379 x
[1] = 2 * (x1
- x0
);
1380 x
[2] = (x2
- 2 * x1
+ x0
);
1382 // a point, not a line
1383 if (dy
== 0 && dx
== 0)
1387 if (dx
== 0 || (dy
/ dx
) > 1.0)
1406 for (int i
= 0; i
< 3; i
++)
1409 if ((nRoots
= QuadCurve2D
.solveQuadratic(r
)) > 0)
1411 Intersection
[] temp
= new Intersection
[nRoots
];
1412 int intersections
= 0;
1413 for (int i
= 0; i
< nRoots
; i
++)
1416 if (t
>= 0.0 && t
<= 1.0)
1418 Point2D p
= c
.evaluatePoint(t
);
1420 // if the line is on an axis, snap the point to that axis.
1422 p
.setLocation(lx0
, p
.getY());
1424 p
.setLocation(p
.getX(), ly0
);
1426 if (p
.getX() <= Math
.max(lx0
, lx1
)
1427 && p
.getX() >= Math
.min(lx0
, lx1
)
1428 && p
.getY() <= Math
.max(ly0
, ly1
)
1429 && p
.getY() >= Math
.min(ly0
, ly1
))
1431 double lineparameter
= p
.distance(l
.P1
) / l
.P2
.distance(l
.P1
);
1432 temp
[i
] = new Intersection(p
, lineparameter
, t
);
1439 if (intersections
== 0)
1442 Intersection
[] rValues
= new Intersection
[intersections
];
1444 for (int i
= 0; i
< nRoots
; i
++)
1445 if (temp
[i
] != null)
1446 rValues
[--intersections
] = temp
[i
];
1453 * Returns the intersections between a line and a cubic segment
1454 * This is done through combining the line's equation with the
1455 * parametric form of the Bezier and solving the resulting quadratic.
1457 private Intersection
[] lineCubicIntersect(LineSegment l
, CubicSegment c
)
1459 double[] y
= new double[4];
1460 double[] x
= new double[4];
1461 double[] r
= new double[4];
1463 double x0
= c
.P1
.getX();
1464 double y0
= c
.P1
.getY();
1465 double x1
= c
.cp1
.getX();
1466 double y1
= c
.cp1
.getY();
1467 double x2
= c
.cp2
.getX();
1468 double y2
= c
.cp2
.getY();
1469 double x3
= c
.P2
.getX();
1470 double y3
= c
.P2
.getY();
1472 double lx0
= l
.P1
.getX();
1473 double ly0
= l
.P1
.getY();
1474 double lx1
= l
.P2
.getX();
1475 double ly1
= l
.P2
.getY();
1476 double dx
= lx1
- lx0
;
1477 double dy
= ly1
- ly0
;
1479 // form r(t) = y(t) - x(t) for the bezier
1481 y
[1] = 3 * (y1
- y0
);
1482 y
[2] = 3 * (y2
+ y0
- 2 * y1
);
1483 y
[3] = y3
- 3 * y2
+ 3 * y1
- y0
;
1486 x
[1] = 3 * (x1
- x0
);
1487 x
[2] = 3 * (x2
+ x0
- 2 * x1
);
1488 x
[3] = x3
- 3 * x2
+ 3 * x1
- x0
;
1490 // a point, not a line
1491 if (dy
== 0 && dx
== 0)
1495 if (dx
== 0 || (dy
/ dx
) > 1.0)
1515 for (int i
= 0; i
< 4; i
++)
1518 if ((nRoots
= CubicCurve2D
.solveCubic(r
)) > 0)
1520 Intersection
[] temp
= new Intersection
[nRoots
];
1521 int intersections
= 0;
1522 for (int i
= 0; i
< nRoots
; i
++)
1525 if (t
>= 0.0 && t
<= 1.0)
1527 // if the line is on an axis, snap the point to that axis.
1528 Point2D p
= c
.evaluatePoint(t
);
1530 p
.setLocation(lx0
, p
.getY());
1532 p
.setLocation(p
.getX(), ly0
);
1534 if (p
.getX() <= Math
.max(lx0
, lx1
)
1535 && p
.getX() >= Math
.min(lx0
, lx1
)
1536 && p
.getY() <= Math
.max(ly0
, ly1
)
1537 && p
.getY() >= Math
.min(ly0
, ly1
))
1539 double lineparameter
= p
.distance(l
.P1
) / l
.P2
.distance(l
.P1
);
1540 temp
[i
] = new Intersection(p
, lineparameter
, t
);
1548 if (intersections
== 0)
1551 Intersection
[] rValues
= new Intersection
[intersections
];
1552 for (int i
= 0; i
< nRoots
; i
++)
1553 if (temp
[i
] != null)
1554 rValues
[--intersections
] = temp
[i
];
1561 * Returns the intersection between two lines, or null if there is no
1564 private Intersection
linesIntersect(LineSegment a
, LineSegment b
)
1571 if (! Line2D
.linesIntersect(P1
.getX(), P1
.getY(), P2
.getX(), P2
.getY(),
1572 P3
.getX(), P3
.getY(), P4
.getX(), P4
.getY()))
1575 double x1
= P1
.getX();
1576 double y1
= P1
.getY();
1577 double rx
= P2
.getX() - x1
;
1578 double ry
= P2
.getY() - y1
;
1580 double x2
= P3
.getX();
1581 double y2
= P3
.getY();
1582 double sx
= P4
.getX() - x2
;
1583 double sy
= P4
.getY() - y2
;
1585 double determinant
= sx
* ry
- sy
* rx
;
1586 double nom
= (sx
* (y2
- y1
) + sy
* (x1
- x2
));
1588 // Parallel lines don't intersect. At least we pretend they don't.
1589 if (Math
.abs(determinant
) < EPSILON
)
1592 nom
= nom
/ determinant
;
1599 Point2D p
= new Point2D
.Double(x1
+ nom
* rx
, y1
+ nom
* ry
);
1601 return new Intersection(p
, p
.distance(P1
) / P1
.distance(P2
),
1602 p
.distance(P3
) / P3
.distance(P4
));
1606 * Determines if two points are equal, within an error margin
1609 private boolean pointEquals(Point2D a
, Point2D b
)
1611 return (a
.equals(b
) || a
.distance(b
) < PE_EPSILON
);
1616 * Turns a shape into a Vector of Segments
1618 private Vector
makeSegment(Shape s
)
1620 Vector paths
= new Vector();
1621 PathIterator pi
= s
.getPathIterator(null);
1622 double[] coords
= new double[6];
1623 Segment subpath
= null;
1624 Segment current
= null;
1629 cx
= cy
= subpathx
= subpathy
= 0.0;
1631 this.windingRule
= pi
.getWindingRule();
1633 while (! pi
.isDone())
1636 switch (pi
.currentSegment(coords
))
1638 case PathIterator
.SEG_MOVETO
:
1639 if (subpath
!= null)
1640 { // close existing open path
1641 current
.next
= new LineSegment(cx
, cy
, subpathx
, subpathy
);
1642 current
= current
.next
;
1643 current
.next
= subpath
;
1646 subpathx
= cx
= coords
[0];
1647 subpathy
= cy
= coords
[1];
1650 // replace 'close' with a line-to.
1651 case PathIterator
.SEG_CLOSE
:
1652 if (subpath
!= null && (subpathx
!= cx
|| subpathy
!= cy
))
1654 current
.next
= new LineSegment(cx
, cy
, subpathx
, subpathy
);
1655 current
= current
.next
;
1656 current
.next
= subpath
;
1661 else if (subpath
!= null)
1663 current
.next
= subpath
;
1667 case PathIterator
.SEG_LINETO
:
1668 if (cx
!= coords
[0] || cy
!= coords
[1])
1670 v
= new LineSegment(cx
, cy
, coords
[0], coords
[1]);
1671 if (subpath
== null)
1673 subpath
= current
= v
;
1679 current
= current
.next
;
1685 case PathIterator
.SEG_QUADTO
:
1686 v
= new QuadSegment(cx
, cy
, coords
[0], coords
[1], coords
[2],
1688 if (subpath
== null)
1690 subpath
= current
= v
;
1696 current
= current
.next
;
1701 case PathIterator
.SEG_CUBICTO
:
1702 v
= new CubicSegment(cx
, cy
, coords
[0], coords
[1], coords
[2],
1703 coords
[3], coords
[4], coords
[5]);
1704 if (subpath
== null)
1706 subpath
= current
= v
;
1712 current
= current
.next
;
1715 // check if the cubic is self-intersecting
1716 double[] lpts
= ((CubicSegment
) v
).getLoop();
1719 // if it is, break off the loop into its own path.
1720 v
.subdivideInsert(lpts
[0]);
1721 v
.next
.subdivideInsert((lpts
[1] - lpts
[0]) / (1.0 - lpts
[0]));
1723 CubicSegment loop
= (CubicSegment
) v
.next
;
1727 v
.P2
= v
.next
.P1
= loop
.P2
= loop
.P1
; // snap points
1739 if (subpath
!= null)
1740 { // close any open path
1741 if (subpathx
!= cx
|| subpathy
!= cy
)
1743 current
.next
= new LineSegment(cx
, cy
, subpathx
, subpathy
);
1744 current
= current
.next
;
1745 current
.next
= subpath
;
1748 current
.next
= subpath
;
1751 if (paths
.size() == 0)
1758 * Find the intersections of two separate closed paths,
1759 * A and B, split the segments at the intersection points,
1760 * and create nodes pointing from one to the other
1762 private int createNodes(Segment A
, Segment B
)
1773 nNodes
+= a
.splitIntersections(b
);
1778 a
= a
.next
; // move to the next segment
1780 while (a
!= A
); // until one wrap.
1786 * Find the intersections of a path with itself.
1787 * Splits the segments at the intersection points,
1788 * and create nodes pointing from one to the other.
1790 private int createNodesSelf(Segment A
)
1803 if (b
!= a
) // necessary
1804 nNodes
+= a
.splitIntersections(b
);
1808 a
= a
.next
; // move to the next segment
1810 while (a
!= A
); // until one wrap.
1816 * Deletes paths which are redundant from a list, (i.e. solid areas within
1817 * solid areas) Clears any nodes. Sorts the remaining paths into solids
1818 * and holes, sets their orientation and sets the solids and holes lists.
1820 private void deleteRedundantPaths(Vector paths
)
1822 int npaths
= paths
.size();
1824 int[][] contains
= new int[npaths
][npaths
];
1825 int[][] windingNumbers
= new int[npaths
][2];
1827 Rectangle2D
[] bb
= new Rectangle2D
[npaths
]; // path bounding boxes
1829 neg
= ((windingRule
== PathIterator
.WIND_NON_ZERO
) ?
-1 : 1);
1831 for (int i
= 0; i
< npaths
; i
++)
1832 bb
[i
] = ((Segment
) paths
.elementAt(i
)).getPathBounds();
1834 // Find which path contains which, assign winding numbers
1835 for (int i
= 0; i
< npaths
; i
++)
1837 Segment pathA
= (Segment
) paths
.elementAt(i
);
1838 pathA
.nullNodes(); // remove any now-redundant nodes, in case.
1839 int windingA
= pathA
.hasClockwiseOrientation() ?
1 : neg
;
1841 for (int j
= 0; j
< npaths
; j
++)
1844 Segment pathB
= (Segment
) paths
.elementAt(j
);
1847 if (bb
[i
].intersects(bb
[j
]))
1849 Segment s
= pathB
.next
;
1850 while (s
.P1
.getY() == s
.P2
.getY() && s
!= pathB
)
1852 Point2D p
= s
.getMidPoint();
1853 if (pathA
.contains(p
.getX(), p
.getY()))
1854 contains
[i
][j
] = windingA
;
1857 // A does not contain B
1861 contains
[i
][j
] = windingA
; // i == j
1864 for (int i
= 0; i
< npaths
; i
++)
1866 windingNumbers
[i
][0] = 0;
1867 for (int j
= 0; j
< npaths
; j
++)
1868 windingNumbers
[i
][0] += contains
[j
][i
];
1869 windingNumbers
[i
][1] = contains
[i
][i
];
1872 Vector solids
= new Vector();
1873 Vector holes
= new Vector();
1875 if (windingRule
== PathIterator
.WIND_NON_ZERO
)
1877 for (int i
= 0; i
< npaths
; i
++)
1879 if (windingNumbers
[i
][0] == 0)
1880 holes
.add(paths
.elementAt(i
));
1881 else if (windingNumbers
[i
][0] - windingNumbers
[i
][1] == 0
1882 && Math
.abs(windingNumbers
[i
][0]) == 1)
1883 solids
.add(paths
.elementAt(i
));
1888 windingRule
= PathIterator
.WIND_NON_ZERO
;
1889 for (int i
= 0; i
< npaths
; i
++)
1891 if ((windingNumbers
[i
][0] & 1) == 0)
1892 holes
.add(paths
.elementAt(i
));
1893 else if ((windingNumbers
[i
][0] & 1) == 1)
1894 solids
.add(paths
.elementAt(i
));
1898 setDirection(holes
, false);
1899 setDirection(solids
, true);
1901 this.solids
= solids
;
1905 * Sets the winding direction of a Vector of paths
1906 * @param clockwise gives the direction,
1907 * true = clockwise, false = counter-clockwise
1909 private void setDirection(Vector paths
, boolean clockwise
)
1912 for (int i
= 0; i
< paths
.size(); i
++)
1914 v
= (Segment
) paths
.elementAt(i
);
1915 if (clockwise
!= v
.hasClockwiseOrientation())
1921 * Class representing a linked-list of vertices forming a closed polygon,
1922 * convex or concave, without holes.
1924 private abstract class Segment
implements Cloneable
1926 // segment type, PathIterator segment types are used.
1939 * Reverses the direction of a single segment
1941 abstract void reverseCoords();
1944 * Returns the segment's midpoint
1946 abstract Point2D
getMidPoint();
1949 * Returns the bounding box of this segment
1951 abstract Rectangle2D
getBounds();
1954 * Transforms a single segment
1956 abstract void transform(AffineTransform at
);
1959 * Returns the PathIterator type of a segment
1961 abstract int getType();
1965 abstract int splitIntersections(Segment b
);
1968 * Returns the PathIterator coords of a segment
1970 abstract int pathIteratorFormat(double[] coords
);
1973 * Returns the number of intersections on the positive X axis,
1974 * with the origin at (x,y), used for contains()-testing
1976 * (Although that could be done by the line-intersect methods,
1977 * a dedicated method is better to guarantee consitent handling
1978 * of endpoint-special-cases)
1980 abstract int rayCrossing(double x
, double y
);
1983 * Subdivides the segment at parametric value t, inserting
1984 * the new segment into the linked list after this,
1985 * such that this becomes [0,t] and this.next becomes [t,1]
1987 abstract void subdivideInsert(double t
);
1990 * Returns twice the area of a curve, relative the P1-P2 line
1991 * Used for area calculations.
1993 abstract double curveArea();
1996 * Compare two segments.
1998 abstract boolean equals(Segment b
);
2001 * Determines if this path of segments contains the point (x,y)
2003 boolean contains(double x
, double y
)
2009 int n
= v
.rayCrossing(x
, y
);
2014 return ((crossings
& 1) == 1);
2018 * Nulls all nodes of the path. Clean up any 'hairs'.
2032 * Transforms each segment in the closed path
2034 void transformSegmentList(AffineTransform at
)
2046 * Determines the winding direction of the path
2047 * By the sign of the area.
2049 boolean hasClockwiseOrientation()
2051 return (getSignedArea() > 0.0);
2055 * Returns the bounds of this path
2057 public Rectangle2D
getPathBounds()
2063 xmin
= xmax
= P1
.getX();
2064 ymin
= ymax
= P1
.getY();
2069 Rectangle2D r
= v
.getBounds();
2070 xmin
= Math
.min(r
.getMinX(), xmin
);
2071 ymin
= Math
.min(r
.getMinY(), ymin
);
2072 xmax
= Math
.max(r
.getMaxX(), xmax
);
2073 ymax
= Math
.max(r
.getMaxY(), ymax
);
2078 return (new Rectangle2D
.Double(xmin
, ymin
, (xmax
- xmin
), (ymax
- ymin
)));
2082 * Calculates twice the signed area of the path;
2084 double getSignedArea()
2092 area
+= s
.curveArea();
2094 area
+= s
.P1
.getX() * s
.next
.P1
.getY()
2095 - s
.P1
.getY() * s
.next
.P1
.getX();
2104 * Reverses the orientation of the whole polygon
2110 Segment former
= this;
2114 Segment vnext
= v
.next
;
2123 * Inserts a Segment after this one
2125 void insert(Segment v
)
2133 * Returns if this segment path is polygonal
2135 boolean isPolygonal()
2140 if (! (v
instanceof LineSegment
))
2151 Segment
cloneSegmentList() throws CloneNotSupportedException
2153 Vector list
= new Vector();
2162 Segment clone
= (Segment
) this.clone();
2164 for (int i
= 0; i
< list
.size(); i
++)
2166 clone
.next
= (Segment
) ((Segment
) list
.elementAt(i
)).clone();
2174 * Creates a node between this segment and segment b
2175 * at the given intersection
2176 * @return the number of nodes created (0 or 1)
2178 int createNode(Segment b
, Intersection i
)
2181 if ((pointEquals(P1
, p
) || pointEquals(P2
, p
))
2182 && (pointEquals(b
.P1
, p
) || pointEquals(b
.P2
, p
)))
2185 subdivideInsert(i
.ta
);
2186 b
.subdivideInsert(i
.tb
);
2189 b
.P2
= b
.next
.P1
= P2
= next
.P1
= i
.p
;
2197 * Creates multiple nodes from a list of intersections,
2198 * This must be done in the order of ascending parameters,
2199 * and the parameters must be recalculated in accordance
2201 * @return the number of nodes created
2203 protected int createNodes(Segment b
, Intersection
[] x
)
2205 Vector v
= new Vector();
2206 for (int i
= 0; i
< x
.length
; i
++)
2209 if (! ((pointEquals(P1
, p
) || pointEquals(P2
, p
))
2210 && (pointEquals(b
.P1
, p
) || pointEquals(b
.P2
, p
))))
2214 int nNodes
= v
.size();
2215 Intersection
[] A
= new Intersection
[nNodes
];
2216 Intersection
[] B
= new Intersection
[nNodes
];
2217 for (int i
= 0; i
< nNodes
; i
++)
2218 A
[i
] = B
[i
] = (Intersection
) v
.elementAt(i
);
2220 // Create two lists sorted by the parameter
2221 // Bubble sort, OK I suppose, since the number of intersections
2222 // cannot be larger than 9 (cubic-cubic worst case) anyway
2223 for (int i
= 0; i
< nNodes
- 1; i
++)
2225 for (int j
= i
+ 1; j
< nNodes
; j
++)
2227 if (A
[i
].ta
> A
[j
].ta
)
2229 Intersection swap
= A
[i
];
2233 if (B
[i
].tb
> B
[j
].tb
)
2235 Intersection swap
= B
[i
];
2243 for (int i
= 0; i
< nNodes
; i
++)
2245 s
.subdivideInsert(A
[i
].ta
);
2247 // renormalize the parameters
2248 for (int j
= i
+ 1; j
< nNodes
; j
++)
2249 A
[j
].ta
= (A
[j
].ta
- A
[i
].ta
) / (1.0 - A
[i
].ta
);
2255 // subdivide b, set nodes
2257 for (int i
= 0; i
< nNodes
; i
++)
2259 s
.subdivideInsert(B
[i
].tb
);
2261 for (int j
= i
+ 1; j
< nNodes
; j
++)
2262 B
[j
].tb
= (B
[j
].tb
- B
[i
].tb
) / (1.0 - B
[i
].tb
);
2265 B
[i
].seg
.node
= s
.next
; // node a -> b
2266 s
.node
= B
[i
].seg
.next
; // node b -> a
2269 B
[i
].seg
.P2
= B
[i
].seg
.next
.P1
= s
.P2
= s
.next
.P1
= B
[i
].p
;
2276 * Determines if two paths are equal.
2277 * Colinear line segments are ignored in the comparison.
2279 boolean pathEquals(Segment B
)
2281 if (! getPathBounds().equals(B
.getPathBounds()))
2284 Segment startA
= getTopLeft();
2285 Segment startB
= B
.getTopLeft();
2293 if (a
instanceof LineSegment
)
2294 a
= ((LineSegment
) a
).lastCoLinear();
2295 if (b
instanceof LineSegment
)
2296 b
= ((LineSegment
) b
).lastCoLinear();
2301 while (a
!= startA
&& b
!= startB
);
2306 * Return the segment with the top-leftmost first point
2308 Segment
getTopLeft()
2314 if (v
.P1
.getY() < tl
.P1
.getY())
2316 else if (v
.P1
.getY() == tl
.P1
.getY())
2318 if (v
.P1
.getX() < tl
.P1
.getX())
2328 * Returns if the path has a segment outside a shape
2330 boolean isSegmentOutside(Shape shape
)
2332 return ! shape
.contains(getMidPoint());
2336 private class LineSegment
extends Segment
2338 public LineSegment(double x1
, double y1
, double x2
, double y2
)
2341 P1
= new Point2D
.Double(x1
, y1
);
2342 P2
= new Point2D
.Double(x2
, y2
);
2345 public LineSegment(Point2D p1
, Point2D p2
)
2348 P1
= (Point2D
) p1
.clone();
2349 P2
= (Point2D
) p2
.clone();
2353 * Clones this segment
2355 public Object
clone()
2357 return new LineSegment(P1
, P2
);
2361 * Transforms the segment
2363 void transform(AffineTransform at
)
2365 P1
= at
.transform(P1
, null);
2366 P2
= at
.transform(P2
, null);
2370 * Swap start and end points
2372 void reverseCoords()
2380 * Returns the segment's midpoint
2382 Point2D
getMidPoint()
2384 return (new Point2D
.Double(0.5 * (P1
.getX() + P2
.getX()),
2385 0.5 * (P1
.getY() + P2
.getY())));
2389 * Returns twice the area of a curve, relative the P1-P2 line
2390 * Obviously, a line does not enclose any area besides the line
2398 * Returns the PathIterator type of a segment
2402 return (PathIterator
.SEG_LINETO
);
2406 * Subdivides the segment at parametric value t, inserting
2407 * the new segment into the linked list after this,
2408 * such that this becomes [0,t] and this.next becomes [t,1]
2410 void subdivideInsert(double t
)
2412 Point2D p
= new Point2D
.Double((P2
.getX() - P1
.getX()) * t
+ P1
.getX(),
2413 (P2
.getY() - P1
.getY()) * t
+ P1
.getY());
2414 insert(new LineSegment(p
, P2
));
2421 * Determines if two line segments are strictly colinear
2423 boolean isCoLinear(LineSegment b
)
2425 double x1
= P1
.getX();
2426 double y1
= P1
.getY();
2427 double x2
= P2
.getX();
2428 double y2
= P2
.getY();
2429 double x3
= b
.P1
.getX();
2430 double y3
= b
.P1
.getY();
2431 double x4
= b
.P2
.getX();
2432 double y4
= b
.P2
.getY();
2434 if ((y1
- y3
) * (x4
- x3
) - (x1
- x3
) * (y4
- y3
) != 0.0)
2437 return ((x2
- x1
) * (y4
- y3
) - (y2
- y1
) * (x4
- x3
) == 0.0);
2441 * Return the last segment colinear with this one.
2442 * Used in comparing paths.
2444 Segment
lastCoLinear()
2446 Segment prev
= this;
2449 while (v
instanceof LineSegment
)
2451 if (isCoLinear((LineSegment
) v
))
2463 * Compare two segments.
2464 * We must take into account that the lines may be broken into colinear
2465 * subsegments and ignore them.
2467 boolean equals(Segment b
)
2469 if (! (b
instanceof LineSegment
))
2474 if (! p1
.equals(p3
))
2477 Point2D p2
= lastCoLinear().P2
;
2478 Point2D p4
= ((LineSegment
) b
).lastCoLinear().P2
;
2479 return (p2
.equals(p4
));
2483 * Returns a line segment
2485 int pathIteratorFormat(double[] coords
)
2487 coords
[0] = P2
.getX();
2488 coords
[1] = P2
.getY();
2489 return (PathIterator
.SEG_LINETO
);
2493 * Returns if the line has intersections.
2495 boolean hasIntersections(Segment b
)
2497 if (b
instanceof LineSegment
)
2498 return (linesIntersect(this, (LineSegment
) b
) != null);
2500 if (b
instanceof QuadSegment
)
2501 return (lineQuadIntersect(this, (QuadSegment
) b
) != null);
2503 if (b
instanceof CubicSegment
)
2504 return (lineCubicIntersect(this, (CubicSegment
) b
) != null);
2510 * Splits intersections into nodes,
2511 * This one handles line-line, line-quadratic, line-cubic
2513 int splitIntersections(Segment b
)
2515 if (b
instanceof LineSegment
)
2517 Intersection i
= linesIntersect(this, (LineSegment
) b
);
2522 return createNode(b
, i
);
2525 Intersection
[] x
= null;
2527 if (b
instanceof QuadSegment
)
2528 x
= lineQuadIntersect(this, (QuadSegment
) b
);
2530 if (b
instanceof CubicSegment
)
2531 x
= lineCubicIntersect(this, (CubicSegment
) b
);
2537 return createNode(b
, (Intersection
) x
[0]);
2539 return createNodes(b
, x
);
2543 * Returns the bounding box of this segment
2545 Rectangle2D
getBounds()
2547 return (new Rectangle2D
.Double(Math
.min(P1
.getX(), P2
.getX()),
2548 Math
.min(P1
.getY(), P2
.getY()),
2549 Math
.abs(P1
.getX() - P2
.getX()),
2550 Math
.abs(P1
.getY() - P2
.getY())));
2554 * Returns the number of intersections on the positive X axis,
2555 * with the origin at (x,y), used for contains()-testing
2557 int rayCrossing(double x
, double y
)
2559 double x0
= P1
.getX() - x
;
2560 double y0
= P1
.getY() - y
;
2561 double x1
= P2
.getX() - x
;
2562 double y1
= P2
.getY() - y
;
2567 if (x0
< 0 && x1
< 0)
2576 if (Line2D
.linesIntersect(x0
, y0
, x1
, y1
,
2577 EPSILON
, 0.0, Double
.MAX_VALUE
, 0.0))
2581 } // class LineSegment
2584 * Quadratic Bezier curve segment
2586 * Note: Most peers don't support quadratics directly, so it might make
2587 * sense to represent them as cubics internally and just be done with it.
2588 * I think we should be peer-agnostic, however, and stay faithful to the
2589 * input geometry types as far as possible.
2591 private class QuadSegment
extends Segment
2593 Point2D cp
; // control point
2596 * Constructor, takes the coordinates of the start, control,
2597 * and end point, respectively.
2599 QuadSegment(double x1
, double y1
, double cx
, double cy
, double x2
,
2603 P1
= new Point2D
.Double(x1
, y1
);
2604 P2
= new Point2D
.Double(x2
, y2
);
2605 cp
= new Point2D
.Double(cx
, cy
);
2609 * Clones this segment
2611 public Object
clone()
2613 return new QuadSegment(P1
.getX(), P1
.getY(), cp
.getX(), cp
.getY(),
2614 P2
.getX(), P2
.getY());
2618 * Returns twice the area of a curve, relative the P1-P2 line
2620 * The area formula can be derived by using Green's formula in the
2621 * plane on the parametric form of the bezier.
2625 double x0
= P1
.getX();
2626 double y0
= P1
.getY();
2627 double x1
= cp
.getX();
2628 double y1
= cp
.getY();
2629 double x2
= P2
.getX();
2630 double y2
= P2
.getY();
2632 double P
= (y2
- 2 * y1
+ y0
);
2633 double Q
= 2 * (y1
- y0
);
2635 double A
= (x2
- 2 * x1
+ x0
);
2636 double B
= 2 * (x1
- x0
);
2638 double area
= (B
* P
- A
* Q
) / 3.0;
2643 * Compare two segments.
2645 boolean equals(Segment b
)
2647 if (! (b
instanceof QuadSegment
))
2650 return (P1
.equals(b
.P1
) && cp
.equals(((QuadSegment
) b
).cp
)
2651 && P2
.equals(b
.P2
));
2655 * Returns a Point2D corresponding to the parametric value t
2658 Point2D
evaluatePoint(double t
)
2660 double x0
= P1
.getX();
2661 double y0
= P1
.getY();
2662 double x1
= cp
.getX();
2663 double y1
= cp
.getY();
2664 double x2
= P2
.getX();
2665 double y2
= P2
.getY();
2667 return new Point2D
.Double(t
* t
* (x2
- 2 * x1
+ x0
) + 2 * t
* (x1
- x0
)
2669 t
* t
* (y2
- 2 * y1
+ y0
) + 2 * t
* (y1
- y0
)
2674 * Returns the bounding box of this segment
2676 Rectangle2D
getBounds()
2678 double x0
= P1
.getX();
2679 double y0
= P1
.getY();
2680 double x1
= cp
.getX();
2681 double y1
= cp
.getY();
2682 double x2
= P2
.getX();
2683 double y2
= P2
.getY();
2687 double xmax
= Math
.max(x0
, x2
);
2688 double ymax
= Math
.max(y0
, y2
);
2689 double xmin
= Math
.min(x0
, x2
);
2690 double ymin
= Math
.min(y0
, y2
);
2693 r1
= 2 * (y2
- 2 * y1
+ y0
);
2696 double t
= -r0
/ r1
;
2697 if (t
> 0.0 && t
< 1.0)
2699 double y
= evaluatePoint(t
).getY();
2700 ymax
= Math
.max(y
, ymax
);
2701 ymin
= Math
.min(y
, ymin
);
2705 r1
= 2 * (x2
- 2 * x1
+ x0
);
2708 double t
= -r0
/ r1
;
2709 if (t
> 0.0 && t
< 1.0)
2711 double x
= evaluatePoint(t
).getY();
2712 xmax
= Math
.max(x
, xmax
);
2713 xmin
= Math
.min(x
, xmin
);
2717 return (new Rectangle2D
.Double(xmin
, ymin
, xmax
- xmin
, ymax
- ymin
));
2721 * Returns a cubic segment corresponding to this curve
2723 CubicSegment
getCubicSegment()
2725 double x1
= P1
.getX() + 2.0 * (cp
.getX() - P1
.getX()) / 3.0;
2726 double y1
= P1
.getY() + 2.0 * (cp
.getY() - P1
.getY()) / 3.0;
2727 double x2
= cp
.getX() + (P2
.getX() - cp
.getX()) / 3.0;
2728 double y2
= cp
.getY() + (P2
.getY() - cp
.getY()) / 3.0;
2730 return new CubicSegment(P1
.getX(), P1
.getY(), x1
, y1
, x2
, y2
, P2
.getX(),
2735 * Returns the segment's midpoint
2737 Point2D
getMidPoint()
2739 return evaluatePoint(0.5);
2743 * Returns the PathIterator type of a segment
2747 return (PathIterator
.SEG_QUADTO
);
2751 * Returns the PathIterator coords of a segment
2753 int pathIteratorFormat(double[] coords
)
2755 coords
[0] = cp
.getX();
2756 coords
[1] = cp
.getY();
2757 coords
[2] = P2
.getX();
2758 coords
[3] = P2
.getY();
2759 return (PathIterator
.SEG_QUADTO
);
2763 * Returns the number of intersections on the positive X axis,
2764 * with the origin at (x,y), used for contains()-testing
2766 int rayCrossing(double x
, double y
)
2768 double x0
= P1
.getX() - x
;
2769 double y0
= P1
.getY() - y
;
2770 double x1
= cp
.getX() - x
;
2771 double y1
= cp
.getY() - y
;
2772 double x2
= P2
.getX() - x
;
2773 double y2
= P2
.getY() - y
;
2774 double[] r
= new double[3];
2778 /* check if curve may intersect X+ axis. */
2779 if ((x0
> 0.0 || x1
> 0.0 || x2
> 0.0) && (y0
* y1
<= 0 || y1
* y2
<= 0))
2787 r
[1] = 2 * (y1
- y0
);
2788 r
[2] = (y2
- 2 * y1
+ y0
);
2790 nRoots
= QuadCurve2D
.solveQuadratic(r
);
2791 for (int i
= 0; i
< nRoots
; i
++)
2792 if (r
[i
] > 0.0f
&& r
[i
] < 1.0f
)
2795 if (t
* t
* (x2
- 2 * x1
+ x0
) + 2 * t
* (x1
- x0
) + x0
> 0.0)
2803 * Swap start and end points
2805 void reverseCoords()
2813 * Splits intersections into nodes,
2814 * This one handles quadratic-quadratic only,
2815 * Quadratic-line is passed on to the LineSegment class,
2816 * Quadratic-cubic is passed on to the CubicSegment class
2818 int splitIntersections(Segment b
)
2820 if (b
instanceof LineSegment
)
2821 return (b
.splitIntersections(this));
2823 if (b
instanceof CubicSegment
)
2824 return (b
.splitIntersections(this));
2826 if (b
instanceof QuadSegment
)
2828 // Use the cubic-cubic intersection routine for quads as well,
2829 // Since a quadratic can be exactly described as a cubic, this
2830 // should not be a problem;
2831 // The recursion depth will be the same in any case.
2832 Intersection
[] x
= cubicCubicIntersect(getCubicSegment(),
2834 .getCubicSegment());
2839 return createNode(b
, (Intersection
) x
[0]);
2841 return createNodes(b
, x
);
2847 * Subdivides the segment at parametric value t, inserting
2848 * the new segment into the linked list after this,
2849 * such that this becomes [0,t] and this.next becomes [t,1]
2851 void subdivideInsert(double t
)
2853 double x0
= P1
.getX();
2854 double y0
= P1
.getY();
2855 double x1
= cp
.getX();
2856 double y1
= cp
.getY();
2857 double x2
= P2
.getX();
2858 double y2
= P2
.getY();
2860 double p10x
= x0
+ t
* (x1
- x0
);
2861 double p10y
= y0
+ t
* (y1
- y0
);
2862 double p11x
= x1
+ t
* (x2
- x1
);
2863 double p11y
= y1
+ t
* (y2
- y1
);
2864 double p20x
= p10x
+ t
* (p11x
- p10x
);
2865 double p20y
= p10y
+ t
* (p11y
- p10y
);
2867 insert(new QuadSegment(p20x
, p20y
, p11x
, p11y
, x2
, y2
));
2869 cp
.setLocation(p10x
, p10y
);
2876 * Transforms the segment
2878 void transform(AffineTransform at
)
2880 P1
= at
.transform(P1
, null);
2881 P2
= at
.transform(P2
, null);
2882 cp
= at
.transform(cp
, null);
2884 } // class QuadSegment
2887 * Cubic Bezier curve segment
2889 private class CubicSegment
extends Segment
2891 Point2D cp1
; // control points
2892 Point2D cp2
; // control points
2895 * Constructor - takes coordinates of the starting point,
2896 * first control point, second control point and end point,
2899 public CubicSegment(double x1
, double y1
, double c1x
, double c1y
,
2900 double c2x
, double c2y
, double x2
, double y2
)
2903 P1
= new Point2D
.Double(x1
, y1
);
2904 P2
= new Point2D
.Double(x2
, y2
);
2905 cp1
= new Point2D
.Double(c1x
, c1y
);
2906 cp2
= new Point2D
.Double(c2x
, c2y
);
2910 * Clones this segment
2912 public Object
clone()
2914 return new CubicSegment(P1
.getX(), P1
.getY(), cp1
.getX(), cp1
.getY(),
2915 cp2
.getX(), cp2
.getY(), P2
.getX(), P2
.getY());
2919 * Returns twice the area of a curve, relative the P1-P2 line
2921 * The area formula can be derived by using Green's formula in the
2922 * plane on the parametric form of the bezier.
2926 double x0
= P1
.getX();
2927 double y0
= P1
.getY();
2928 double x1
= cp1
.getX();
2929 double y1
= cp1
.getY();
2930 double x2
= cp2
.getX();
2931 double y2
= cp2
.getY();
2932 double x3
= P2
.getX();
2933 double y3
= P2
.getY();
2935 double P
= y3
- 3 * y2
+ 3 * y1
- y0
;
2936 double Q
= 3 * (y2
+ y0
- 2 * y1
);
2937 double R
= 3 * (y1
- y0
);
2939 double A
= x3
- 3 * x2
+ 3 * x1
- x0
;
2940 double B
= 3 * (x2
+ x0
- 2 * x1
);
2941 double C
= 3 * (x1
- x0
);
2943 double area
= (B
* P
- A
* Q
) / 5.0 + (C
* P
- A
* R
) / 2.0
2944 + (C
* Q
- B
* R
) / 3.0;
2950 * Compare two segments.
2952 boolean equals(Segment b
)
2954 if (! (b
instanceof CubicSegment
))
2957 return (P1
.equals(b
.P1
) && cp1
.equals(((CubicSegment
) b
).cp1
)
2958 && cp2
.equals(((CubicSegment
) b
).cp2
) && P2
.equals(b
.P2
));
2962 * Returns a Point2D corresponding to the parametric value t
2965 Point2D
evaluatePoint(double t
)
2967 double x0
= P1
.getX();
2968 double y0
= P1
.getY();
2969 double x1
= cp1
.getX();
2970 double y1
= cp1
.getY();
2971 double x2
= cp2
.getX();
2972 double y2
= cp2
.getY();
2973 double x3
= P2
.getX();
2974 double y3
= P2
.getY();
2976 return new Point2D
.Double(-(t
* t
* t
) * (x0
- 3 * x1
+ 3 * x2
- x3
)
2977 + 3 * t
* t
* (x0
- 2 * x1
+ x2
)
2978 + 3 * t
* (x1
- x0
) + x0
,
2979 -(t
* t
* t
) * (y0
- 3 * y1
+ 3 * y2
- y3
)
2980 + 3 * t
* t
* (y0
- 2 * y1
+ y2
)
2981 + 3 * t
* (y1
- y0
) + y0
);
2985 * Returns the bounding box of this segment
2987 Rectangle2D
getBounds()
2989 double x0
= P1
.getX();
2990 double y0
= P1
.getY();
2991 double x1
= cp1
.getX();
2992 double y1
= cp1
.getY();
2993 double x2
= cp2
.getX();
2994 double y2
= cp2
.getY();
2995 double x3
= P2
.getX();
2996 double y3
= P2
.getY();
2997 double[] r
= new double[3];
2999 double xmax
= Math
.max(x0
, x3
);
3000 double ymax
= Math
.max(y0
, y3
);
3001 double xmin
= Math
.min(x0
, x3
);
3002 double ymin
= Math
.min(y0
, y3
);
3004 r
[0] = 3 * (y1
- y0
);
3005 r
[1] = 6.0 * (y2
+ y0
- 2 * y1
);
3006 r
[2] = 3.0 * (y3
- 3 * y2
+ 3 * y1
- y0
);
3008 int n
= QuadCurve2D
.solveQuadratic(r
);
3009 for (int i
= 0; i
< n
; i
++)
3012 if (t
> 0 && t
< 1.0)
3014 double y
= evaluatePoint(t
).getY();
3015 ymax
= Math
.max(y
, ymax
);
3016 ymin
= Math
.min(y
, ymin
);
3020 r
[0] = 3 * (x1
- x0
);
3021 r
[1] = 6.0 * (x2
+ x0
- 2 * x1
);
3022 r
[2] = 3.0 * (x3
- 3 * x2
+ 3 * x1
- x0
);
3023 n
= QuadCurve2D
.solveQuadratic(r
);
3024 for (int i
= 0; i
< n
; i
++)
3027 if (t
> 0 && t
< 1.0)
3029 double x
= evaluatePoint(t
).getX();
3030 xmax
= Math
.max(x
, xmax
);
3031 xmin
= Math
.min(x
, xmin
);
3034 return (new Rectangle2D
.Double(xmin
, ymin
, (xmax
- xmin
), (ymax
- ymin
)));
3038 * Returns a CubicCurve2D object corresponding to this segment.
3040 CubicCurve2D
getCubicCurve2D()
3042 return new CubicCurve2D
.Double(P1
.getX(), P1
.getY(), cp1
.getX(),
3043 cp1
.getY(), cp2
.getX(), cp2
.getY(),
3044 P2
.getX(), P2
.getY());
3048 * Returns the parametric points of self-intersection if the cubic
3049 * is self-intersecting, null otherwise.
3053 double x0
= P1
.getX();
3054 double y0
= P1
.getY();
3055 double x1
= cp1
.getX();
3056 double y1
= cp1
.getY();
3057 double x2
= cp2
.getX();
3058 double y2
= cp2
.getY();
3059 double x3
= P2
.getX();
3060 double y3
= P2
.getY();
3061 double[] r
= new double[4];
3067 double[] results
= new double[2];
3069 R
= x3
- 3 * x2
+ 3 * x1
- x0
;
3070 T
= y3
- 3 * y2
+ 3 * y1
- y0
;
3073 if (R
== 0.0 && T
== 0.0)
3077 if (R
!= 0.0 && T
!= 0.0)
3079 A
= 3 * (x2
+ x0
- 2 * x1
) / R
;
3080 B
= 3 * (x1
- x0
) / R
;
3082 double P
= 3 * (y2
+ y0
- 2 * y1
) / T
;
3083 double Q
= 3 * (y1
- y0
) / T
;
3085 if (A
== P
|| Q
== B
)
3088 k
= (Q
- B
) / (A
- P
);
3095 k
= -(3 * (x1
- x0
)) / (3 * (x2
+ x0
- 2 * x1
));
3096 A
= 3 * (y2
+ y0
- 2 * y1
) / T
;
3097 B
= 3 * (y1
- y0
) / T
;
3102 k
= -(3 * (y1
- y0
)) / (3 * (y2
+ y0
- 2 * y1
));
3103 A
= 3 * (x2
+ x0
- 2 * x1
) / R
;
3104 B
= 3 * (x1
- x0
) / R
;
3108 r
[0] = -k
* k
* k
- A
* k
* k
- B
* k
;
3109 r
[1] = 3 * k
* k
+ 2 * k
* A
+ 2 * B
;
3113 int n
= CubicCurve2D
.solveCubic(r
);
3119 for (int i
= 0; i
< 2; i
++)
3120 for (int j
= i
+ 1; j
< 3; j
++)
3128 if (Math
.abs(r
[0] + r
[2] - k
) < 1E-13)
3129 if (r
[0] >= 0.0 && r
[0] <= 1.0 && r
[2] >= 0.0 && r
[2] <= 1.0)
3130 if (evaluatePoint(r
[0]).distance(evaluatePoint(r
[2])) < PE_EPSILON
* 10)
3131 { // we snap the points anyway
3140 * Returns the segment's midpoint
3142 Point2D
getMidPoint()
3144 return evaluatePoint(0.5);
3148 * Returns the PathIterator type of a segment
3152 return (PathIterator
.SEG_CUBICTO
);
3156 * Returns the PathIterator coords of a segment
3158 int pathIteratorFormat(double[] coords
)
3160 coords
[0] = cp1
.getX();
3161 coords
[1] = cp1
.getY();
3162 coords
[2] = cp2
.getX();
3163 coords
[3] = cp2
.getY();
3164 coords
[4] = P2
.getX();
3165 coords
[5] = P2
.getY();
3166 return (PathIterator
.SEG_CUBICTO
);
3170 * Returns the number of intersections on the positive X axis,
3171 * with the origin at (x,y), used for contains()-testing
3173 int rayCrossing(double x
, double y
)
3175 double x0
= P1
.getX() - x
;
3176 double y0
= P1
.getY() - y
;
3177 double x1
= cp1
.getX() - x
;
3178 double y1
= cp1
.getY() - y
;
3179 double x2
= cp2
.getX() - x
;
3180 double y2
= cp2
.getY() - y
;
3181 double x3
= P2
.getX() - x
;
3182 double y3
= P2
.getY() - y
;
3183 double[] r
= new double[4];
3187 /* check if curve may intersect X+ axis. */
3188 if ((x0
> 0.0 || x1
> 0.0 || x2
> 0.0 || x3
> 0.0)
3189 && (y0
* y1
<= 0 || y1
* y2
<= 0 || y2
* y3
<= 0))
3197 r
[1] = 3 * (y1
- y0
);
3198 r
[2] = 3 * (y2
+ y0
- 2 * y1
);
3199 r
[3] = y3
- 3 * y2
+ 3 * y1
- y0
;
3201 if ((nRoots
= CubicCurve2D
.solveCubic(r
)) > 0)
3202 for (int i
= 0; i
< nRoots
; i
++)
3204 if (r
[i
] > 0.0 && r
[i
] < 1.0)
3207 if (-(t
* t
* t
) * (x0
- 3 * x1
+ 3 * x2
- x3
)
3208 + 3 * t
* t
* (x0
- 2 * x1
+ x2
) + 3 * t
* (x1
- x0
)
3218 * Swap start and end points
3220 void reverseCoords()
3225 p
= cp1
; // swap control points
3231 * Splits intersections into nodes,
3232 * This one handles cubic-cubic and cubic-quadratic intersections
3234 int splitIntersections(Segment b
)
3236 if (b
instanceof LineSegment
)
3237 return (b
.splitIntersections(this));
3239 Intersection
[] x
= null;
3241 if (b
instanceof QuadSegment
)
3242 x
= cubicCubicIntersect(this, ((QuadSegment
) b
).getCubicSegment());
3244 if (b
instanceof CubicSegment
)
3245 x
= cubicCubicIntersect(this, (CubicSegment
) b
);
3251 return createNode(b
, x
[0]);
3253 return createNodes(b
, x
);
3257 * Subdivides the segment at parametric value t, inserting
3258 * the new segment into the linked list after this,
3259 * such that this becomes [0,t] and this.next becomes [t,1]
3261 void subdivideInsert(double t
)
3263 CubicSegment s
= (CubicSegment
) clone();
3264 double p1x
= (s
.cp1
.getX() - s
.P1
.getX()) * t
+ s
.P1
.getX();
3265 double p1y
= (s
.cp1
.getY() - s
.P1
.getY()) * t
+ s
.P1
.getY();
3267 double px
= (s
.cp2
.getX() - s
.cp1
.getX()) * t
+ s
.cp1
.getX();
3268 double py
= (s
.cp2
.getY() - s
.cp1
.getY()) * t
+ s
.cp1
.getY();
3270 s
.cp2
.setLocation((s
.P2
.getX() - s
.cp2
.getX()) * t
+ s
.cp2
.getX(),
3271 (s
.P2
.getY() - s
.cp2
.getY()) * t
+ s
.cp2
.getY());
3273 s
.cp1
.setLocation((s
.cp2
.getX() - px
) * t
+ px
,
3274 (s
.cp2
.getY() - py
) * t
+ py
);
3276 double p2x
= (px
- p1x
) * t
+ p1x
;
3277 double p2y
= (py
- p1y
) * t
+ p1y
;
3279 double p3x
= (s
.cp1
.getX() - p2x
) * t
+ p2x
;
3280 double p3y
= (s
.cp1
.getY() - p2y
) * t
+ p2y
;
3281 s
.P1
.setLocation(p3x
, p3y
);
3287 cp1
.setLocation(p1x
, p1y
);
3288 cp2
.setLocation(p2x
, p2y
);
3295 * Transforms the segment
3297 void transform(AffineTransform at
)
3299 P1
= at
.transform(P1
, null);
3300 P2
= at
.transform(P2
, null);
3301 cp1
= at
.transform(cp1
, null);
3302 cp2
= at
.transform(cp2
, null);
3304 } // class CubicSegment