aboutsummaryrefslogtreecommitdiff
path: root/libjava/java/awt/geom
diff options
context:
space:
mode:
Diffstat (limited to 'libjava/java/awt/geom')
-rw-r--r--libjava/java/awt/geom/AffineTransform.java73
-rw-r--r--libjava/java/awt/geom/Arc2D.java415
-rw-r--r--libjava/java/awt/geom/Area.java3212
-rw-r--r--libjava/java/awt/geom/CubicCurve2D.java11
-rw-r--r--libjava/java/awt/geom/Ellipse2D.java225
-rw-r--r--libjava/java/awt/geom/GeneralPath.java105
-rw-r--r--libjava/java/awt/geom/Line2D.java117
-rw-r--r--libjava/java/awt/geom/PathIterator.java4
-rw-r--r--libjava/java/awt/geom/Point2D.java11
-rw-r--r--libjava/java/awt/geom/QuadCurve2D.java11
-rw-r--r--libjava/java/awt/geom/Rectangle2D.java32
-rw-r--r--libjava/java/awt/geom/RectangularShape.java2
12 files changed, 3916 insertions, 302 deletions
diff --git a/libjava/java/awt/geom/AffineTransform.java b/libjava/java/awt/geom/AffineTransform.java
index 1410d90..21eacae 100644
--- a/libjava/java/awt/geom/AffineTransform.java
+++ b/libjava/java/awt/geom/AffineTransform.java
@@ -1,5 +1,5 @@
/* AffineTransform.java -- transform coordinates between two 2-D spaces
- Copyright (C) 2000, 2001, 2002 Free Software Foundation
+ Copyright (C) 2000, 2001, 2002, 2004 Free Software Foundation
This file is part of GNU Classpath.
@@ -57,10 +57,11 @@ import java.io.Serializable;
* [ 1 ] [ 0 0 1 ] [ 1 ] [ 1 ]
* </pre>
* The bottom row of the matrix is constant, so a transform can be uniquely
- * represented (as in toString) by "[[m00, m01, m02], [m10, m11, m12]]".
+ * represented (as in {@link #toString()}) by
+ * "[[m00, m01, m02], [m10, m11, m12]]".
*
- * @author Tom Tromey <tromey@cygnus.com>
- * @author Eric Blake <ebb9@email.byu.edu>
+ * @author Tom Tromey (tromey@cygnus.com)
+ * @author Eric Blake (ebb9@email.byu.edu)
* @since 1.2
* @status partially updated to 1.4, still has some problems
*/
@@ -517,6 +518,8 @@ public class AffineTransform implements Cloneable, Serializable
* or a bit-wise combination of TYPE_TRANSLATION, the mutually exclusive
* TYPE_*_ROTATIONs, and the mutually exclusive TYPE_*_SCALEs.
*
+ * @return The type.
+ *
* @see #TYPE_IDENTITY
* @see #TYPE_TRANSLATION
* @see #TYPE_UNIFORM_SCALE
@@ -1105,9 +1108,9 @@ public class AffineTransform implements Cloneable, Serializable
* transformation, so that no result will overwrite a point that has not yet
* been evaluated.
*
- * @param src the array of source points
+ * @param srcPts the array of source points
* @param srcOff the starting offset into src
- * @param dst the array of destination points
+ * @param dstPts the array of destination points
* @param dstOff the starting offset into dst
* @param num the number of points to transform
* @throws NullPointerException if src or dst is null
@@ -1139,9 +1142,9 @@ public class AffineTransform implements Cloneable, Serializable
* transformation, so that no result will overwrite a point that has not yet
* been evaluated.
*
- * @param src the array of source points
+ * @param srcPts the array of source points
* @param srcOff the starting offset into src
- * @param dst the array of destination points
+ * @param dstPts the array of destination points
* @param dstOff the starting offset into dst
* @param num the number of points to transform
* @throws NullPointerException if src or dst is null
@@ -1171,9 +1174,9 @@ public class AffineTransform implements Cloneable, Serializable
* storing the results in another array. This will not create a destination
* array.
*
- * @param src the array of source points
+ * @param srcPts the array of source points
* @param srcOff the starting offset into src
- * @param dst the array of destination points
+ * @param dstPts the array of destination points
* @param dstOff the starting offset into dst
* @param num the number of points to transform
* @throws NullPointerException if src or dst is null
@@ -1196,9 +1199,9 @@ public class AffineTransform implements Cloneable, Serializable
* storing the results in another array. This will not create a destination
* array.
*
- * @param src the array of source points
+ * @param srcPts the array of source points
* @param srcOff the starting offset into src
- * @param dst the array of destination points
+ * @param dstPts the array of destination points
* @param dstOff the starting offset into dst
* @param num the number of points to transform
* @throws NullPointerException if src or dst is null
@@ -1231,17 +1234,7 @@ public class AffineTransform implements Cloneable, Serializable
public Point2D inverseTransform(Point2D src, Point2D dst)
throws NoninvertibleTransformException
{
- double det = getDeterminant();
- if (det == 0)
- throw new NoninvertibleTransformException("couldn't invert transform");
- if (dst == null)
- dst = new Point2D.Double();
- double x = src.getX();
- double y = src.getY();
- double nx = (m11 * x + -m10 * y) / det - m02;
- double ny = (m01 * x + -m00 * y) / det - m12;
- dst.setLocation(nx, ny);
- return dst;
+ return createInverse().transform(src, dst);
}
/**
@@ -1251,9 +1244,9 @@ public class AffineTransform implements Cloneable, Serializable
* transformation, so that no result will overwrite a point that has not yet
* been evaluated.
*
- * @param src the array of source points
+ * @param srcPts the array of source points
* @param srcOff the starting offset into src
- * @param dst the array of destination points
+ * @param dstPts the array of destination points
* @param dstOff the starting offset into dst
* @param num the number of points to transform
* @throws NullPointerException if src or dst is null
@@ -1265,23 +1258,7 @@ public class AffineTransform implements Cloneable, Serializable
double[] dstPts, int dstOff, int num)
throws NoninvertibleTransformException
{
- double det = getDeterminant();
- if (det == 0)
- throw new NoninvertibleTransformException("couldn't invert transform");
- if (srcPts == dstPts && dstOff > srcOff
- && num > 1 && srcOff + 2 * num > dstOff)
- {
- double[] d = new double[2 * num];
- System.arraycopy(srcPts, srcOff, d, 0, 2 * num);
- srcPts = d;
- }
- while (--num >= 0)
- {
- double x = srcPts[srcOff++];
- double y = srcPts[srcOff++];
- dstPts[dstOff++] = (m11 * x + -m10 * y) / det - m02;
- dstPts[dstOff++] = (m01 * x + -m00 * y) / det - m12;
- }
+ createInverse().transform(srcPts, srcOff, dstPts, dstOff, num);
}
/**
@@ -1322,9 +1299,9 @@ public class AffineTransform implements Cloneable, Serializable
* [ y' ] [ m10 m11 ] [ y ] = [ m10 * x + m11 * y ]
* </pre>
*
- * @param src the array of source points
+ * @param srcPts the array of source points
* @param srcOff the starting offset into src
- * @param dst the array of destination points
+ * @param dstPts the array of destination points
* @param dstOff the starting offset into dst
* @param num the number of points to transform
* @throws NullPointerException if src or dst is null
@@ -1356,12 +1333,14 @@ public class AffineTransform implements Cloneable, Serializable
* which only stores points in float precision.
*
* @param src the shape source to transform
- * @return the shape, transformed by this
- * @throws NullPointerException if src is null
+ * @return the shape, transformed by this, <code>null</code> if src is
+ * <code>null</code>.
* @see GeneralPath#transform(AffineTransform)
*/
public Shape createTransformedShape(Shape src)
{
+ if(src == null)
+ return null;
GeneralPath p = new GeneralPath(src);
p.transform(this);
return p;
@@ -1445,7 +1424,7 @@ public class AffineTransform implements Cloneable, Serializable
* Compares two transforms for equality. This returns true if they have the
* same matrix values.
*
- * @param o the transform to compare
+ * @param obj the transform to compare
* @return true if it is equal
*/
public boolean equals(Object obj)
diff --git a/libjava/java/awt/geom/Arc2D.java b/libjava/java/awt/geom/Arc2D.java
index 64d8165..5ce3b08 100644
--- a/libjava/java/awt/geom/Arc2D.java
+++ b/libjava/java/awt/geom/Arc2D.java
@@ -1,5 +1,5 @@
/* Arc2D.java -- represents an arc in 2-D space
- Copyright (C) 2002, 2003 Free Software Foundation
+ Copyright (C) 2002, 2003, 2004 Free Software Foundation
This file is part of GNU Classpath.
@@ -35,11 +35,11 @@ this exception to your version of the library, but you are not
obligated to do so. If you do not wish to do so, delete this
exception statement from your version. */
-
package java.awt.geom;
import java.util.NoSuchElementException;
+
/**
* This class represents all arcs (segments of an ellipse in 2-D space). The
* arcs are defined by starting angle and extent (arc length) in degrees, as
@@ -51,8 +51,8 @@ import java.util.NoSuchElementException;
* first 360 degrees. Storage is up to the subclasses.
*
* @author Eric Blake (ebb9@email.byu.edu)
+ * @author Sven de Marothy (sven@physto.se)
* @since 1.2
- * @status updated to 1.4, but still missing functionality
*/
public abstract class Arc2D extends RectangularShape
{
@@ -154,8 +154,8 @@ public abstract class Arc2D extends RectangularShape
* extent sweeps counterclockwise (from the positive x-axis to the negative
* y-axis).
*
- * @param x the new x coordinate of the lower left of the bounding box
- * @param y the new y coordinate of the lower left of the bounding box
+ * @param x the new x coordinate of the upper left of the bounding box
+ * @param y the new y coordinate of the upper left of the bounding box
* @param w the new width of the bounding box
* @param h the new height of the bounding box
* @param start the start angle, in degrees
@@ -171,7 +171,7 @@ public abstract class Arc2D extends RectangularShape
* extent sweeps counterclockwise (from the positive x-axis to the negative
* y-axis).
*
- * @param p the lower left point of the bounding box
+ * @param p the upper left point of the bounding box
* @param d the dimensions of the bounding box
* @param start the start angle, in degrees
* @param extent the arc extent, in degrees
@@ -179,11 +179,10 @@ public abstract class Arc2D extends RectangularShape
* @throws IllegalArgumentException if type is invalid
* @throws NullPointerException if p or d is null
*/
- public void setArc(Point2D p, Dimension2D d,
- double start, double extent, int type)
+ public void setArc(Point2D p, Dimension2D d, double start, double extent,
+ int type)
{
- setArc(p.getX(), p.getY(), d.getWidth(), d.getHeight(),
- start, extent, type);
+ setArc(p.getX(), p.getY(), d.getWidth(), d.getHeight(), start, extent, type);
}
/**
@@ -200,8 +199,7 @@ public abstract class Arc2D extends RectangularShape
*/
public void setArc(Rectangle2D r, double start, double extent, int type)
{
- setArc(r.getX(), r.getY(), r.getWidth(), r.getHeight(),
- start, extent, type);
+ setArc(r.getX(), r.getY(), r.getWidth(), r.getHeight(), start, extent, type);
}
/**
@@ -212,8 +210,8 @@ public abstract class Arc2D extends RectangularShape
*/
public void setArc(Arc2D a)
{
- setArc(a.getX(), a.getY(), a.getWidth(), a.getHeight(),
- a.getAngleStart(), a.getAngleExtent(), a.getArcType());
+ setArc(a.getX(), a.getY(), a.getWidth(), a.getHeight(), a.getAngleStart(),
+ a.getAngleExtent(), a.getArcType());
}
/**
@@ -230,8 +228,8 @@ public abstract class Arc2D extends RectangularShape
* @param type one of {@link #OPEN}, {@link #CHORD}, or {@link #PIE}
* @throws IllegalArgumentException if type is invalid
*/
- public void setArcByCenter(double x, double y, double r,
- double start, double extent, int type)
+ public void setArcByCenter(double x, double y, double r, double start,
+ double extent, int type)
{
setArc(x - r, y - r, r + r, r + r, start, extent, type);
}
@@ -252,8 +250,50 @@ public abstract class Arc2D extends RectangularShape
*/
public void setArcByTangent(Point2D p1, Point2D p2, Point2D p3, double r)
{
- // XXX Implement.
- throw new Error("not implemented");
+ if ((p2.getX() - p1.getX()) * (p3.getY() - p1.getY())
+ - (p3.getX() - p1.getX()) * (p2.getY() - p1.getY()) > 0)
+ {
+ Point2D p = p3;
+ p3 = p1;
+ p1 = p;
+ }
+
+ // normalized tangent vectors
+ double dx1 = (p1.getX() - p2.getX()) / p1.distance(p2);
+ double dy1 = (p1.getY() - p2.getY()) / p1.distance(p2);
+ double dx2 = (p2.getX() - p3.getX()) / p3.distance(p2);
+ double dy2 = (p2.getY() - p3.getY()) / p3.distance(p2);
+ double theta1 = Math.atan2(dx1, dy1);
+ double theta2 = Math.atan2(dx2, dy2);
+
+ double dx = r * Math.cos(theta2) - r * Math.cos(theta1);
+ double dy = -r * Math.sin(theta2) + r * Math.sin(theta1);
+
+ if (theta1 < 0)
+ theta1 += 2 * Math.PI;
+ if (theta2 < 0)
+ theta2 += 2 * Math.PI;
+ if (theta2 < theta1)
+ theta2 += 2 * Math.PI;
+
+ // Vectors of the lines, not normalized, note we change
+ // the direction of line 2.
+ dx1 = p1.getX() - p2.getX();
+ dy1 = p1.getY() - p2.getY();
+ dx2 = p3.getX() - p2.getX();
+ dy2 = p3.getY() - p2.getY();
+
+ // Calculate the tangent point to the second line
+ double t2 = -(dx1 * dy - dy1 * dx) / (dx2 * dy1 - dx1 * dy2);
+ double x2 = t2 * (p3.getX() - p2.getX()) + p2.getX();
+ double y2 = t2 * (p3.getY() - p2.getY()) + p2.getY();
+
+ // calculate the center point
+ double x = x2 - r * Math.cos(theta2);
+ double y = y2 + r * Math.sin(theta2);
+
+ setArc(x - r, y - r, 2 * r, 2 * r, Math.toDegrees(theta1),
+ Math.toDegrees(theta2 - theta1), getArcType());
}
/**
@@ -287,7 +327,7 @@ public abstract class Arc2D extends RectangularShape
// Normalize.
double x = p.getX() - (getX() + getWidth() / 2);
double y = p.getY() - (getY() + getHeight() / 2);
- setAngleStart(Math.toDegrees(Math.atan2(y, x)));
+ setAngleStart(Math.toDegrees(Math.atan2(-y, x)));
}
/**
@@ -312,8 +352,8 @@ public abstract class Arc2D extends RectangularShape
y1 = y1 - (my + mh / 2);
x2 = x2 - (mx + mw / 2);
y2 = y2 - (my + mh / 2);
- double start = Math.toDegrees(Math.atan2(y1, x1));
- double extent = Math.toDegrees(Math.atan2(y2, x2)) - start;
+ double start = Math.toDegrees(Math.atan2(-y1, x1));
+ double extent = Math.toDegrees(Math.atan2(-y2, x2)) - start;
if (extent < 0)
extent += 360;
setAngleStart(start);
@@ -413,8 +453,8 @@ public abstract class Arc2D extends RectangularShape
* @param h the height
* @return the rectangle for use in getBounds2D
*/
- protected abstract Rectangle2D makeBounds(double x, double y,
- double w, double h);
+ protected abstract Rectangle2D makeBounds(double x, double y, double w,
+ double h);
/**
* Tests if the given angle, in degrees, is included in the arc.
@@ -426,27 +466,44 @@ public abstract class Arc2D extends RectangularShape
public boolean containsAngle(double a)
{
double start = getAngleStart();
- double end = start + getAngleExtent();
+ double extent = getAngleExtent();
+ double end = start + extent;
+
+ if (extent == 0)
+ return false;
+
+ if (extent >= 360 || extent <= -360)
+ return true;
+
+ if (extent < 0)
+ {
+ end = start;
+ start += extent;
+ }
start %= 360;
- if (start < 0)
+ while (start < 0)
start += 360;
end %= 360;
- if (end < 0)
+ while (end < start)
end += 360;
a %= 360;
- if (a < 0)
+ while (a < start)
a += 360;
- return a >= start && a <= end;
+ return a >= start && a < end; // starting angle included, ending angle not
}
/**
* Determines if the arc contains the given point. If the bounding box
* is empty, then this will return false.
*
+ * The area considered 'inside' an arc of type OPEN is the same as the
+ * area inside an equivalent filled CHORD-type arc. The area considered
+ * 'inside' a CHORD-type arc is the same as the filled area.
+ *
* @param x the x coordinate to test
* @param y the y coordinate to test
* @return true if the point is inside the arc
@@ -455,15 +512,50 @@ public abstract class Arc2D extends RectangularShape
{
double w = getWidth();
double h = getHeight();
- if (w <= 0 || h <= 0)
+ double extent = getAngleExtent();
+ if (w <= 0 || h <= 0 || extent == 0)
return false;
- // XXX Finish implementing.
- throw new Error("not implemented");
+
+ double mx = getX() + w / 2;
+ double my = getY() + h / 2;
+ double dx = (x - mx) * 2 / w;
+ double dy = (y - my) * 2 / h;
+ if ((dx * dx + dy * dy) >= 1.0)
+ return false;
+
+ double angle = Math.toDegrees(Math.atan2(-dy, dx));
+ if (getArcType() == PIE)
+ return containsAngle(angle);
+
+ double a1 = Math.toRadians(getAngleStart());
+ double a2 = Math.toRadians(getAngleStart() + extent);
+ double x1 = mx + getWidth() * Math.cos(a1) / 2;
+ double y1 = my - getHeight() * Math.sin(a1) / 2;
+ double x2 = mx + getWidth() * Math.cos(a2) / 2;
+ double y2 = my - getHeight() * Math.sin(a2) / 2;
+ double sgn = ((x2 - x1) * (my - y1) - (mx - x1) * (y2 - y1)) * ((x2 - x1) * (y
+ - y1) - (x - x1) * (y2 - y1));
+
+ if (Math.abs(extent) > 180)
+ {
+ if (containsAngle(angle))
+ return true;
+ return sgn > 0;
+ }
+ else
+ {
+ if (! containsAngle(angle))
+ return false;
+ return sgn < 0;
+ }
}
/**
* Tests if a given rectangle intersects the area of the arc.
*
+ * For a definition of the 'inside' area, see the contains() method.
+ * @see #contains(double, double)
+ *
* @param x the x coordinate of the rectangle
* @param y the y coordinate of the rectangle
* @param w the width of the rectangle
@@ -472,12 +564,94 @@ public abstract class Arc2D extends RectangularShape
*/
public boolean intersects(double x, double y, double w, double h)
{
- double mw = getWidth();
- double mh = getHeight();
- if (mw <= 0 || mh <= 0 || w <= 0 || h <= 0)
+ double extent = getAngleExtent();
+ if (extent == 0)
return false;
- // XXX Finish implementing.
- throw new Error("not implemented");
+
+ if (contains(x, y) || contains(x, y + h) || contains(x + w, y)
+ || contains(x + w, y + h))
+ return true;
+
+ Rectangle2D rect = new Rectangle2D.Double(x, y, w, h);
+
+ double a = getWidth() / 2.0;
+ double b = getHeight() / 2.0;
+
+ double mx = getX() + a;
+ double my = getY() + b;
+ double x1 = mx + a * Math.cos(Math.toRadians(getAngleStart()));
+ double y1 = my - b * Math.sin(Math.toRadians(getAngleStart()));
+ double x2 = mx + a * Math.cos(Math.toRadians(getAngleStart() + extent));
+ double y2 = my - b * Math.sin(Math.toRadians(getAngleStart() + extent));
+
+ if (getArcType() != CHORD)
+ {
+ // check intersections against the pie radii
+ if (rect.intersectsLine(mx, my, x1, y1))
+ return true;
+ if (rect.intersectsLine(mx, my, x2, y2))
+ return true;
+ }
+ else// check the chord
+ if (rect.intersectsLine(x1, y1, x2, y2))
+ return true;
+
+ // Check the Arc segment against the four edges
+ double dx;
+
+ // Check the Arc segment against the four edges
+ double dy;
+ dy = y - my;
+ dx = a * Math.sqrt(1 - ((dy * dy) / (b * b)));
+ if (! java.lang.Double.isNaN(dx))
+ {
+ if (mx + dx >= x && mx + dx <= x + w
+ && containsAngle(Math.toDegrees(Math.atan2(-dy, dx))))
+ return true;
+ if (mx - dx >= x && mx - dx <= x + w
+ && containsAngle(Math.toDegrees(Math.atan2(-dy, -dx))))
+ return true;
+ }
+ dy = (y + h) - my;
+ dx = a * Math.sqrt(1 - ((dy * dy) / (b * b)));
+ if (! java.lang.Double.isNaN(dx))
+ {
+ if (mx + dx >= x && mx + dx <= x + w
+ && containsAngle(Math.toDegrees(Math.atan2(-dy, dx))))
+ return true;
+ if (mx - dx >= x && mx - dx <= x + w
+ && containsAngle(Math.toDegrees(Math.atan2(-dy, -dx))))
+ return true;
+ }
+ dx = x - mx;
+ dy = b * Math.sqrt(1 - ((dx * dx) / (a * a)));
+ if (! java.lang.Double.isNaN(dy))
+ {
+ if (my + dy >= y && my + dy <= y + h
+ && containsAngle(Math.toDegrees(Math.atan2(-dy, dx))))
+ return true;
+ if (my - dy >= y && my - dy <= y + h
+ && containsAngle(Math.toDegrees(Math.atan2(dy, dx))))
+ return true;
+ }
+
+ dx = (x + w) - mx;
+ dy = b * Math.sqrt(1 - ((dx * dx) / (a * a)));
+ if (! java.lang.Double.isNaN(dy))
+ {
+ if (my + dy >= y && my + dy <= y + h
+ && containsAngle(Math.toDegrees(Math.atan2(-dy, dx))))
+ return true;
+ if (my - dy >= y && my - dy <= y + h
+ && containsAngle(Math.toDegrees(Math.atan2(dy, dx))))
+ return true;
+ }
+
+ // Check whether the arc is contained within the box
+ if (rect.contains(mx, my))
+ return true;
+
+ return false;
}
/**
@@ -491,12 +665,37 @@ public abstract class Arc2D extends RectangularShape
*/
public boolean contains(double x, double y, double w, double h)
{
- double mw = getWidth();
- double mh = getHeight();
- if (mw <= 0 || mh <= 0 || w <= 0 || h <= 0)
+ double extent = getAngleExtent();
+ if (extent == 0)
+ return false;
+
+ if (! (contains(x, y) && contains(x, y + h) && contains(x + w, y)
+ && contains(x + w, y + h)))
+ return false;
+
+ Rectangle2D rect = new Rectangle2D.Double(x, y, w, h);
+
+ double a = getWidth() / 2.0;
+ double b = getHeight() / 2.0;
+
+ double mx = getX() + a;
+ double my = getY() + b;
+ double x1 = mx + a * Math.cos(Math.toRadians(getAngleStart()));
+ double y1 = my - b * Math.sin(Math.toRadians(getAngleStart()));
+ double x2 = mx + a * Math.cos(Math.toRadians(getAngleStart() + extent));
+ double y2 = my - b * Math.sin(Math.toRadians(getAngleStart() + extent));
+ if (getArcType() != CHORD)
+ {
+ // check intersections against the pie radii
+ if (rect.intersectsLine(mx, my, x1, y1))
+ return false;
+
+ if (rect.intersectsLine(mx, my, x2, y2))
+ return false;
+ }
+ else if (rect.intersectsLine(x1, y1, x2, y2))
return false;
- // XXX Finish implementing.
- throw new Error("not implemented");
+ return true;
}
/**
@@ -567,29 +766,37 @@ public abstract class Arc2D extends RectangularShape
* @param a the arc
* @param xform the transform
*/
- ArcIterator(Arc2D a, AffineTransform xform)
+ public ArcIterator(Arc2D a, AffineTransform xform)
{
this.xform = xform;
x = a.getX();
y = a.getY();
w = a.getWidth();
h = a.getHeight();
- start = a.getAngleStart() * (Math.PI / 180);
- extent = a.getAngleExtent() * (Math.PI / 180);
+ double start = a.getAngleStart() * (Math.PI / 180);
+ double extent = a.getAngleExtent() * (Math.PI / 180);
+
+ if (extent < 0)
+ {
+ extent = -extent;
+ start = 2 * Math.PI - extent + start;
+ }
+ this.start = start;
+ this.extent = extent;
+
type = a.type;
- double e = extent < 0 ? -extent : extent;
if (w < 0 || h < 0)
- limit = -1;
- else if (e == 0)
- limit = type;
- else if (e <= Math.PI / 2.0)
- limit = type + 1;
- else if (e <= Math.PI)
- limit = type + 2;
- else if (e <= 3.0 * (Math.PI / 2.0))
- limit = type + 3;
+ limit = -1;
+ else if (extent == 0)
+ limit = type;
+ else if (extent <= Math.PI / 2.0)
+ limit = type + 1;
+ else if (extent <= Math.PI)
+ limit = type + 2;
+ else if (extent <= 3.0 * (Math.PI / 2.0))
+ limit = type + 3;
else
- limit = type + 4;
+ limit = type + 4;
}
/**
@@ -598,7 +805,7 @@ public abstract class Arc2D extends RectangularShape
* @param e the ellipse
* @param xform the transform
*/
- ArcIterator(Ellipse2D e, AffineTransform xform)
+ public ArcIterator(Ellipse2D e, AffineTransform xform)
{
this.xform = xform;
x = e.getX();
@@ -606,7 +813,7 @@ public abstract class Arc2D extends RectangularShape
w = e.getWidth();
h = e.getHeight();
start = 0;
- extent = -2 * Math.PI;
+ extent = 2 * Math.PI;
type = CHORD;
limit = (w < 0 || h < 0) ? -1 : 5;
}
@@ -650,9 +857,9 @@ public abstract class Arc2D extends RectangularShape
public int currentSegment(float[] coords)
{
double[] double_coords = new double[6];
- int code = currentSegment (double_coords);
+ int code = currentSegment(double_coords);
for (int i = 0; i < 6; ++i)
- coords[i] = (float) double_coords[i];
+ coords[i] = (float) double_coords[i];
return code;
}
@@ -666,48 +873,38 @@ public abstract class Arc2D extends RectangularShape
*/
public int currentSegment(double[] coords)
{
- double rx = w/2;
- double ry = h/2;
+ double rx = w / 2;
+ double ry = h / 2;
double xmid = x + rx;
double ymid = y + ry;
-
+
if (current > limit)
- throw new NoSuchElementException("arc iterator out of bounds");
+ throw new NoSuchElementException("arc iterator out of bounds");
if (current == 0)
{
- coords[0] = xmid + rx * Math.cos(start);
- coords[1] = ymid - ry * Math.sin(start);
- if (xform != null)
- xform.transform(coords, 0, coords, 0, 1);
- return SEG_MOVETO;
+ coords[0] = xmid + rx * Math.cos(start);
+ coords[1] = ymid - ry * Math.sin(start);
+ if (xform != null)
+ xform.transform(coords, 0, coords, 0, 1);
+ return SEG_MOVETO;
}
if (type != OPEN && current == limit)
- return SEG_CLOSE;
+ return SEG_CLOSE;
- if ((current == limit - 1) &&
- (type == PIE) || (type == CHORD))
+ if ((current == limit - 1) && (type == PIE))
{
- if (type == PIE)
- {
- coords[0] = xmid;
- coords[1] = ymid;
- }
- else if (type == CHORD)
- {
- coords[0] = xmid + rx * Math.cos(start);
- coords[1] = ymid - ry * Math.sin(start);
- }
- if (xform != null)
- xform.transform(coords, 0, coords, 0, 1);
- return SEG_LINETO;
+ coords[0] = xmid;
+ coords[1] = ymid;
+ if (xform != null)
+ xform.transform(coords, 0, coords, 0, 1);
+ return SEG_LINETO;
}
// note that this produces a cubic approximation of the arc segment,
// not a true ellipsoid. there's no ellipsoid path segment code,
// unfortunately. the cubic approximation looks about right, though.
-
double kappa = (Math.sqrt(2.0) - 1.0) * (4.0 / 3.0);
double quad = (Math.PI / 2.0);
@@ -717,14 +914,14 @@ public abstract class Arc2D extends RectangularShape
double x0 = xmid + rx * Math.cos(curr_begin);
double y0 = ymid - ry * Math.sin(curr_begin);
-
+
double x1 = xmid + rx * Math.cos(curr_begin + curr_extent);
double y1 = ymid - ry * Math.sin(curr_begin + curr_extent);
- AffineTransform trans = new AffineTransform ();
- double [] cvec = new double[2];
- double len = kappa * portion_of_a_quadrant;
- double angle = curr_begin;
+ AffineTransform trans = new AffineTransform();
+ double[] cvec = new double[2];
+ double len = kappa * portion_of_a_quadrant;
+ double angle = curr_begin;
// in a hypothetical "first quadrant" setting, our first control
// vector would be sticking up, from [1,0] to [1,kappa].
@@ -733,31 +930,29 @@ public abstract class Arc2D extends RectangularShape
// from what one would consider "normal" first quadrant rules, so we
// will *subtract* the y value of this control vector from our first
// point.
-
cvec[0] = 0;
cvec[1] = len;
- trans.scale (rx, ry);
- trans.rotate (angle);
+ trans.scale(rx, ry);
+ trans.rotate(angle);
trans.transform(cvec, 0, cvec, 0, 1);
coords[0] = x0 + cvec[0];
coords[1] = y0 - cvec[1];
// control vector #2 would, ideally, be sticking out and to the
// right, in a first quadrant arc segment. again, subtraction of y.
-
cvec[0] = 0;
cvec[1] = -len;
- trans.rotate (curr_extent);
+ trans.rotate(curr_extent);
trans.transform(cvec, 0, cvec, 0, 1);
coords[2] = x1 + cvec[0];
coords[3] = y1 - cvec[1];
-
+
// end point
coords[4] = x1;
coords[5] = y1;
if (xform != null)
- xform.transform(coords, 0, coords, 0, 3);
+ xform.transform(coords, 0, coords, 0, 3);
return SEG_CUBICTO;
}
@@ -820,8 +1015,8 @@ public abstract class Arc2D extends RectangularShape
* @param type the arc type: {@link #OPEN}, {@link #CHORD}, or {@link #PIE}
* @throws IllegalArgumentException if type is invalid
*/
- public Double(double x, double y, double w, double h,
- double start, double extent, int type)
+ public Double(double x, double y, double w, double h, double start,
+ double extent, int type)
{
super(type);
this.x = x;
@@ -831,7 +1026,7 @@ public abstract class Arc2D extends RectangularShape
this.start = start;
this.extent = extent;
}
-
+
/**
* Create a new arc with the given dimensions.
*
@@ -935,8 +1130,8 @@ public abstract class Arc2D extends RectangularShape
* @param type the arc type: {@link #OPEN}, {@link #CHORD}, or {@link #PIE}
* @throws IllegalArgumentException if type is invalid
*/
- public void setArc(double x, double y, double w, double h,
- double start, double extent, int type)
+ public void setArc(double x, double y, double w, double h, double start,
+ double extent, int type)
{
this.x = x;
this.y = y;
@@ -960,7 +1155,7 @@ public abstract class Arc2D extends RectangularShape
/**
* Sets the extent angle of the arc.
*
- * @param start the new extent angle
+ * @param extent the new extent angle
*/
public void setAngleExtent(double extent)
{
@@ -1039,8 +1234,8 @@ public abstract class Arc2D extends RectangularShape
* @param type the arc type: {@link #OPEN}, {@link #CHORD}, or {@link #PIE}
* @throws IllegalArgumentException if type is invalid
*/
- public Float(float x, float y, float w, float h,
- float start, float extent, int type)
+ public Float(float x, float y, float w, float h, float start,
+ float extent, int type)
{
super(type);
this.x = x;
@@ -1050,7 +1245,7 @@ public abstract class Arc2D extends RectangularShape
this.start = start;
this.extent = extent;
}
-
+
/**
* Create a new arc with the given dimensions.
*
@@ -1069,7 +1264,7 @@ public abstract class Arc2D extends RectangularShape
width = (float) r.getWidth();
height = (float) r.getHeight();
this.start = start;
- this.extent = extent;
+ this.extent = (float) extent;
}
/**
@@ -1154,8 +1349,8 @@ public abstract class Arc2D extends RectangularShape
* @param type the arc type: {@link #OPEN}, {@link #CHORD}, or {@link #PIE}
* @throws IllegalArgumentException if type is invalid
*/
- public void setArc(double x, double y, double w, double h,
- double start, double extent, int type)
+ public void setArc(double x, double y, double w, double h, double start,
+ double extent, int type)
{
this.x = (float) x;
this.y = (float) y;
@@ -1179,7 +1374,7 @@ public abstract class Arc2D extends RectangularShape
/**
* Sets the extent angle of the arc.
*
- * @param start the new extent angle
+ * @param extent the new extent angle
*/
public void setAngleExtent(double extent)
{
diff --git a/libjava/java/awt/geom/Area.java b/libjava/java/awt/geom/Area.java
index 85bc642..9b1b9d3 100644
--- a/libjava/java/awt/geom/Area.java
+++ b/libjava/java/awt/geom/Area.java
@@ -1,5 +1,5 @@
/* Area.java -- represents a shape built by constructive area geometry
- Copyright (C) 2002 Free Software Foundation
+ Copyright (C) 2002, 2004 Free Software Foundation
This file is part of GNU Classpath.
@@ -35,74 +35,648 @@ this exception to your version of the library, but you are not
obligated to do so. If you do not wish to do so, delete this
exception statement from your version. */
-
package java.awt.geom;
import java.awt.Rectangle;
import java.awt.Shape;
+import java.util.Vector;
+
/**
- * STUBS ONLY
- * XXX Implement and document.
+ * The Area class represents any area for the purpose of
+ * Constructive Area Geometry (CAG) manipulations. CAG manipulations
+ * work as an area-wise form of boolean logic, where the basic operations are:
+ * <P><li>Add (in boolean algebra: A <B>or</B> B)<BR>
+ * <li>Subtract (in boolean algebra: A <B>and</B> (<B>not</B> B) )<BR>
+ * <li>Intersect (in boolean algebra: A <B>and</B> B)<BR>
+ * <li>Exclusive Or <BR>
+ * <img src="doc-files/Area-1.png" width="342" height="302"
+ * alt="Illustration of CAG operations" /><BR>
+ * Above is an illustration of the CAG operations on two ring shapes.<P>
+ *
+ * The contains and intersects() methods are also more accurate than the
+ * specification of #Shape requires.<P>
+ *
+ * Please note that constructing an Area can be slow
+ * (Self-intersection resolving is proportional to the square of
+ * the number of segments).<P>
+ * @see #add(Area)
+ * @see #subtract(Area)
+ * @see #intersect(Area)
+ * @see #exclusiveOr(Area)
+ *
+ * @author Sven de Marothy (sven@physto.se)
+ *
+ * @since 1.2
+ * @status Works, but could be faster and more reliable.
*/
public class Area implements Shape, Cloneable
{
+ /**
+ * General numerical precision
+ */
+ private static final double EPSILON = 1E-11;
+
+ /**
+ * recursive subdivision epsilon - (see getRecursionDepth)
+ */
+ private static final double RS_EPSILON = 1E-13;
+
+ /**
+ * Snap distance - points within this distance are considered equal
+ */
+ private static final double PE_EPSILON = 1E-11;
+
+ /**
+ * Segment vectors containing solid areas and holes
+ */
+ private Vector solids;
+
+ /**
+ * Segment vectors containing solid areas and holes
+ */
+ private Vector holes;
+
+ /**
+ * Vector (temporary) storing curve-curve intersections
+ */
+ private Vector cc_intersections;
+
+ /**
+ * Winding rule WIND_NON_ZERO used, after construction,
+ * this is irrelevant.
+ */
+ private int windingRule;
+
+ /**
+ * Constructs an empty Area
+ */
public Area()
{
+ solids = new Vector();
+ holes = new Vector();
}
+
+ /**
+ * Constructs an Area from any given Shape. <P>
+ *
+ * If the Shape is self-intersecting, the created Area will consist
+ * of non-self-intersecting subpaths, and any inner paths which
+ * are found redundant in accordance with the Shape's winding rule
+ * will not be included.
+ *
+ * @param s the shape (<code>null</code> not permitted).
+ *
+ * @throws NullPointerException if <code>s</code> is <code>null</code>.
+ */
public Area(Shape s)
{
+ this();
+
+ Vector p = makeSegment(s);
+
+ // empty path
+ if (p == null)
+ return;
+
+ // delete empty paths
+ for (int i = 0; i < p.size(); i++)
+ if (((Segment) p.elementAt(i)).getSignedArea() == 0.0)
+ p.remove(i--);
+
+ /*
+ * Resolve self intersecting paths into non-intersecting
+ * solids and holes.
+ * Algorithm is as follows:
+ * 1: Create nodes at all self intersections
+ * 2: Put all segments into a list
+ * 3: Grab a segment, follow it, change direction at each node,
+ * removing segments from the list in the process
+ * 4: Repeat (3) until no segments remain in the list
+ * 5: Remove redundant paths and sort into solids and holes
+ */
+ Vector paths = new Vector();
+ Segment v;
+
+ for (int i = 0; i < p.size(); i++)
+ {
+ Segment path = (Segment) p.elementAt(i);
+ createNodesSelf(path);
+ }
+
+ if (p.size() > 1)
+ {
+ for (int i = 0; i < p.size() - 1; i++)
+ for (int j = i + 1; j < p.size(); j++)
+ {
+ Segment path1 = (Segment) p.elementAt(i);
+ Segment path2 = (Segment) p.elementAt(j);
+ createNodes(path1, path2);
+ }
+ }
+
+ // we have intersecting points.
+ Vector segments = new Vector();
+
+ for (int i = 0; i < p.size(); i++)
+ {
+ Segment path = v = (Segment) p.elementAt(i);
+ do
+ {
+ segments.add(v);
+ v = v.next;
+ }
+ while (v != path);
+ }
+
+ paths = weilerAtherton(segments);
+ deleteRedundantPaths(paths);
}
- public void add(Area a)
+
+ /**
+ * Performs an add (union) operation on this area with another Area.<BR>
+ * @param area - the area to be unioned with this one
+ */
+ public void add(Area area)
{
- // XXX Implement.
- throw new Error("not implemented");
+ if (equals(area))
+ return;
+ if (area.isEmpty())
+ return;
+
+ Area B = (Area) area.clone();
+
+ Vector pathA = new Vector();
+ Vector pathB = new Vector();
+ pathA.addAll(solids);
+ pathA.addAll(holes);
+ pathB.addAll(B.solids);
+ pathB.addAll(B.holes);
+
+ int nNodes = 0;
+
+ for (int i = 0; i < pathA.size(); i++)
+ {
+ Segment a = (Segment) pathA.elementAt(i);
+ for (int j = 0; j < pathB.size(); j++)
+ {
+ Segment b = (Segment) pathB.elementAt(j);
+ nNodes += createNodes(a, b);
+ }
+ }
+
+ Vector paths = new Vector();
+ Segment v;
+
+ // we have intersecting points.
+ Vector segments = new Vector();
+
+ // In a union operation, we keep all
+ // segments of A oustide B and all B outside A
+ for (int i = 0; i < pathA.size(); i++)
+ {
+ v = (Segment) pathA.elementAt(i);
+ Segment path = v;
+ do
+ {
+ if (v.isSegmentOutside(area))
+ segments.add(v);
+ v = v.next;
+ }
+ while (v != path);
+ }
+
+ for (int i = 0; i < pathB.size(); i++)
+ {
+ v = (Segment) pathB.elementAt(i);
+ Segment path = v;
+ do
+ {
+ if (v.isSegmentOutside(this))
+ segments.add(v);
+ v = v.next;
+ }
+ while (v != path);
+ }
+
+ paths = weilerAtherton(segments);
+ deleteRedundantPaths(paths);
}
- public void subtract(Area a)
+
+ /**
+ * Performs a subtraction operation on this Area.<BR>
+ * @param area the area to be subtracted from this area.
+ * @throws NullPointerException if <code>area</code> is <code>null</code>.
+ */
+ public void subtract(Area area)
{
- // XXX Implement.
- throw new Error("not implemented");
+ if (isEmpty() || area.isEmpty())
+ return;
+
+ if (equals(area))
+ {
+ reset();
+ return;
+ }
+
+ Vector pathA = new Vector();
+ Area B = (Area) area.clone();
+ pathA.addAll(solids);
+ pathA.addAll(holes);
+
+ // reverse the directions of B paths.
+ setDirection(B.holes, true);
+ setDirection(B.solids, false);
+
+ Vector pathB = new Vector();
+ pathB.addAll(B.solids);
+ pathB.addAll(B.holes);
+
+ int nNodes = 0;
+
+ // create nodes
+ for (int i = 0; i < pathA.size(); i++)
+ {
+ Segment a = (Segment) pathA.elementAt(i);
+ for (int j = 0; j < pathB.size(); j++)
+ {
+ Segment b = (Segment) pathB.elementAt(j);
+ nNodes += createNodes(a, b);
+ }
+ }
+
+ Vector paths = new Vector();
+
+ // we have intersecting points.
+ Vector segments = new Vector();
+
+ // In a subtraction operation, we keep all
+ // segments of A oustide B and all B within A
+ // We outsideness-test only one segment in each path
+ // and the segments before and after any node
+ for (int i = 0; i < pathA.size(); i++)
+ {
+ Segment v = (Segment) pathA.elementAt(i);
+ Segment path = v;
+ if (v.isSegmentOutside(area) && v.node == null)
+ segments.add(v);
+ boolean node = false;
+ do
+ {
+ if ((v.node != null || node))
+ {
+ node = (v.node != null);
+ if (v.isSegmentOutside(area))
+ segments.add(v);
+ }
+ v = v.next;
+ }
+ while (v != path);
+ }
+
+ for (int i = 0; i < pathB.size(); i++)
+ {
+ Segment v = (Segment) pathB.elementAt(i);
+ Segment path = v;
+ if (! v.isSegmentOutside(this) && v.node == null)
+ segments.add(v);
+ v = v.next;
+ boolean node = false;
+ do
+ {
+ if ((v.node != null || node))
+ {
+ node = (v.node != null);
+ if (! v.isSegmentOutside(this))
+ segments.add(v);
+ }
+ v = v.next;
+ }
+ while (v != path);
+ }
+
+ paths = weilerAtherton(segments);
+ deleteRedundantPaths(paths);
}
- public void intersect(Area a)
+
+ /**
+ * Performs an intersection operation on this Area.<BR>
+ * @param area - the area to be intersected with this area.
+ * @throws NullPointerException if <code>area</code> is <code>null</code>.
+ */
+ public void intersect(Area area)
{
- // XXX Implement.
- throw new Error("not implemented");
+ if (isEmpty() || area.isEmpty())
+ {
+ reset();
+ return;
+ }
+ if (equals(area))
+ return;
+
+ Vector pathA = new Vector();
+ Area B = (Area) area.clone();
+ pathA.addAll(solids);
+ pathA.addAll(holes);
+
+ Vector pathB = new Vector();
+ pathB.addAll(B.solids);
+ pathB.addAll(B.holes);
+
+ int nNodes = 0;
+
+ // create nodes
+ for (int i = 0; i < pathA.size(); i++)
+ {
+ Segment a = (Segment) pathA.elementAt(i);
+ for (int j = 0; j < pathB.size(); j++)
+ {
+ Segment b = (Segment) pathB.elementAt(j);
+ nNodes += createNodes(a, b);
+ }
+ }
+
+ Vector paths = new Vector();
+
+ // we have intersecting points.
+ Vector segments = new Vector();
+
+ // In an intersection operation, we keep all
+ // segments of A within B and all B within A
+ // (The rest must be redundant)
+ // We outsideness-test only one segment in each path
+ // and the segments before and after any node
+ for (int i = 0; i < pathA.size(); i++)
+ {
+ Segment v = (Segment) pathA.elementAt(i);
+ Segment path = v;
+ if (! v.isSegmentOutside(area) && v.node == null)
+ segments.add(v);
+ boolean node = false;
+ do
+ {
+ if ((v.node != null || node))
+ {
+ node = (v.node != null);
+ if (! v.isSegmentOutside(area))
+ segments.add(v);
+ }
+ v = v.next;
+ }
+ while (v != path);
+ }
+
+ for (int i = 0; i < pathB.size(); i++)
+ {
+ Segment v = (Segment) pathB.elementAt(i);
+ Segment path = v;
+ if (! v.isSegmentOutside(this) && v.node == null)
+ segments.add(v);
+ v = v.next;
+ boolean node = false;
+ do
+ {
+ if ((v.node != null || node))
+ {
+ node = (v.node != null);
+ if (! v.isSegmentOutside(this))
+ segments.add(v);
+ }
+ v = v.next;
+ }
+ while (v != path);
+ }
+
+ paths = weilerAtherton(segments);
+ deleteRedundantPaths(paths);
}
- public void exclusiveOr(Area a)
+
+ /**
+ * Performs an exclusive-or operation on this Area.<BR>
+ * @param area - the area to be XORed with this area.
+ * @throws NullPointerException if <code>area</code> is <code>null</code>.
+ */
+ public void exclusiveOr(Area area)
{
- // XXX Implement.
- throw new Error("not implemented");
+ if (area.isEmpty())
+ return;
+
+ if (isEmpty())
+ {
+ Area B = (Area) area.clone();
+ solids = B.solids;
+ holes = B.holes;
+ return;
+ }
+ if (equals(area))
+ {
+ reset();
+ return;
+ }
+
+ Vector pathA = new Vector();
+
+ Area B = (Area) area.clone();
+ Vector pathB = new Vector();
+ pathA.addAll(solids);
+ pathA.addAll(holes);
+
+ // reverse the directions of B paths.
+ setDirection(B.holes, true);
+ setDirection(B.solids, false);
+ pathB.addAll(B.solids);
+ pathB.addAll(B.holes);
+
+ int nNodes = 0;
+
+ for (int i = 0; i < pathA.size(); i++)
+ {
+ Segment a = (Segment) pathA.elementAt(i);
+ for (int j = 0; j < pathB.size(); j++)
+ {
+ Segment b = (Segment) pathB.elementAt(j);
+ nNodes += createNodes(a, b);
+ }
+ }
+
+ Vector paths = new Vector();
+ Segment v;
+
+ // we have intersecting points.
+ Vector segments = new Vector();
+
+ // In an XOR operation, we operate on all segments
+ for (int i = 0; i < pathA.size(); i++)
+ {
+ v = (Segment) pathA.elementAt(i);
+ Segment path = v;
+ do
+ {
+ segments.add(v);
+ v = v.next;
+ }
+ while (v != path);
+ }
+
+ for (int i = 0; i < pathB.size(); i++)
+ {
+ v = (Segment) pathB.elementAt(i);
+ Segment path = v;
+ do
+ {
+ segments.add(v);
+ v = v.next;
+ }
+ while (v != path);
+ }
+
+ paths = weilerAtherton(segments);
+ deleteRedundantPaths(paths);
}
+
+ /**
+ * Clears the Area object, creating an empty area.
+ */
public void reset()
{
- // XXX Implement.
- throw new Error("not implemented");
+ solids = new Vector();
+ holes = new Vector();
}
+
+ /**
+ * Returns whether this area encloses any area.
+ * @return true if the object encloses any area.
+ */
public boolean isEmpty()
{
- // XXX Implement.
- throw new Error("not implemented");
+ if (solids.size() == 0)
+ return true;
+
+ double totalArea = 0;
+ for (int i = 0; i < solids.size(); i++)
+ totalArea += Math.abs(((Segment) solids.elementAt(i)).getSignedArea());
+ for (int i = 0; i < holes.size(); i++)
+ totalArea -= Math.abs(((Segment) holes.elementAt(i)).getSignedArea());
+ if (totalArea <= EPSILON)
+ return true;
+
+ return false;
}
+
+ /**
+ * Determines whether the Area consists entirely of line segments
+ * @return true if the Area lines-only, false otherwise
+ */
public boolean isPolygonal()
{
- // XXX Implement.
- throw new Error("not implemented");
+ for (int i = 0; i < holes.size(); i++)
+ if (! ((Segment) holes.elementAt(i)).isPolygonal())
+ return false;
+ for (int i = 0; i < solids.size(); i++)
+ if (! ((Segment) solids.elementAt(i)).isPolygonal())
+ return false;
+ return true;
}
+
+ /**
+ * Determines if the Area is rectangular.<P>
+ *
+ * This is strictly qualified. An area is considered rectangular if:<BR>
+ * <li>It consists of a single polygonal path.<BR>
+ * <li>It is oriented parallel/perpendicular to the xy axis<BR>
+ * <li>It must be exactly rectangular, i.e. small errors induced by
+ * transformations may cause a false result, although the area is
+ * visibly rectangular.<P>
+ * @return true if the above criteria are met, false otherwise
+ */
public boolean isRectangular()
{
- // XXX Implement.
- throw new Error("not implemented");
+ if (isEmpty())
+ return true;
+
+ if (holes.size() != 0 || solids.size() != 1)
+ return false;
+
+ Segment path = (Segment) solids.elementAt(0);
+ if (! path.isPolygonal())
+ return false;
+
+ int nCorners = 0;
+ Segment s = path;
+ do
+ {
+ Segment s2 = s.next;
+ double d1 = (s.P2.getX() - s.P1.getX())*(s2.P2.getX() - s2.P1.getX())/
+ ((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2)));
+ double d2 = (s.P2.getY() - s.P1.getY())*(s2.P2.getY() - s2.P1.getY())/
+ ((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2)));
+ double dotproduct = d1 + d2;
+
+ // For some reason, only rectangles on the XY axis count.
+ if (d1 != 0 && d2 != 0)
+ return false;
+
+ if (Math.abs(dotproduct) == 0) // 90 degree angle
+ nCorners++;
+ else if ((Math.abs(1.0 - dotproduct) > 0)) // 0 degree angle?
+ return false; // if not, return false
+
+ s = s.next;
+ }
+ while (s != path);
+
+ return nCorners == 4;
}
+
+ /**
+ * Returns whether the Area consists of more than one simple
+ * (non self-intersecting) subpath.
+ *
+ * @return true if the Area consists of none or one simple subpath,
+ * false otherwise.
+ */
public boolean isSingular()
{
- // XXX Implement.
- throw new Error("not implemented");
+ return (holes.size() == 0 && solids.size() <= 1);
}
+
+ /**
+ * Returns the bounding box of the Area.<P> Unlike the CubicCurve2D and
+ * QuadraticCurve2D classes, this method will return the tightest possible
+ * bounding box, evaluating the extreme points of each curved segment.<P>
+ * @return the bounding box
+ */
public Rectangle2D getBounds2D()
{
- // XXX Implement.
- throw new Error("not implemented");
+ if (solids.size() == 0)
+ return new Rectangle2D.Double(0.0, 0.0, 0.0, 0.0);
+
+ double xmin;
+ double xmax;
+ double ymin;
+ double ymax;
+ xmin = xmax = ((Segment) solids.elementAt(0)).P1.getX();
+ ymin = ymax = ((Segment) solids.elementAt(0)).P1.getY();
+
+ for (int path = 0; path < solids.size(); path++)
+ {
+ Rectangle2D r = ((Segment) solids.elementAt(path)).getPathBounds();
+ xmin = Math.min(r.getMinX(), xmin);
+ ymin = Math.min(r.getMinY(), ymin);
+ xmax = Math.max(r.getMaxX(), xmax);
+ ymax = Math.max(r.getMaxY(), ymax);
+ }
+
+ return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
}
+
+ /**
+ * Returns the bounds of this object in Rectangle format.
+ * Please note that this may lead to loss of precision.
+ *
+ * @return The bounds.
+ * @see #getBounds2D()
+ */
public Rectangle getBounds()
{
return getBounds2D().getBounds();
@@ -118,66 +692,2618 @@ public class Area implements Shape, Cloneable
{
try
{
- return super.clone();
+ Area clone = new Area();
+ for (int i = 0; i < solids.size(); i++)
+ clone.solids.add(((Segment) solids.elementAt(i)).cloneSegmentList());
+ for (int i = 0; i < holes.size(); i++)
+ clone.holes.add(((Segment) holes.elementAt(i)).cloneSegmentList());
+ return clone;
}
catch (CloneNotSupportedException e)
{
- throw (Error) new InternalError().initCause(e); // Impossible
+ throw (Error) new InternalError().initCause(e); // Impossible
}
}
- public boolean equals(Area a)
+ /**
+ * Compares two Areas.
+ *
+ * @param area the area to compare against this area (<code>null</code>
+ * permitted).
+ * @return <code>true</code> if the areas are equal, and <code>false</code>
+ * otherwise.
+ */
+ public boolean equals(Area area)
{
- // XXX Implement.
- throw new Error("not implemented");
+ if (area == null)
+ return false;
+
+ if (! getBounds2D().equals(area.getBounds2D()))
+ return false;
+
+ if (solids.size() != area.solids.size()
+ || holes.size() != area.holes.size())
+ return false;
+
+ Vector pathA = new Vector();
+ pathA.addAll(solids);
+ pathA.addAll(holes);
+ Vector pathB = new Vector();
+ pathB.addAll(area.solids);
+ pathB.addAll(area.holes);
+
+ int nPaths = pathA.size();
+ boolean[][] match = new boolean[2][nPaths];
+
+ for (int i = 0; i < nPaths; i++)
+ {
+ for (int j = 0; j < nPaths; j++)
+ {
+ Segment p1 = (Segment) pathA.elementAt(i);
+ Segment p2 = (Segment) pathB.elementAt(j);
+ if (! match[0][i] && ! match[1][j])
+ if (p1.pathEquals(p2))
+ match[0][i] = match[1][j] = true;
+ }
+ }
+
+ boolean result = true;
+ for (int i = 0; i < nPaths; i++)
+ result = result && match[0][i] && match[1][i];
+ return result;
}
+ /**
+ * Transforms this area by the AffineTransform at.
+ *
+ * @param at the transform.
+ */
public void transform(AffineTransform at)
{
- // XXX Implement.
- throw new Error("not implemented");
+ for (int i = 0; i < solids.size(); i++)
+ ((Segment) solids.elementAt(i)).transformSegmentList(at);
+ for (int i = 0; i < holes.size(); i++)
+ ((Segment) holes.elementAt(i)).transformSegmentList(at);
+
+ // Note that the orientation is not invariant under inversion
+ if ((at.getType() & AffineTransform.TYPE_FLIP) != 0)
+ {
+ setDirection(holes, false);
+ setDirection(solids, true);
+ }
}
+
+ /**
+ * Returns a new Area equal to this one, transformed
+ * by the AffineTransform at.
+ * @param at the transform.
+ * @return the transformed area
+ * @throws NullPointerException if <code>at</code> is <code>null</code>.
+ */
public Area createTransformedArea(AffineTransform at)
{
Area a = (Area) clone();
a.transform(at);
return a;
}
+
+ /**
+ * Determines if the point (x,y) is contained within this Area.
+ *
+ * @param x the x-coordinate of the point.
+ * @param y the y-coordinate of the point.
+ * @return true if the point is contained, false otherwise.
+ */
public boolean contains(double x, double y)
{
- // XXX Implement.
- throw new Error("not implemented");
+ int n = 0;
+ for (int i = 0; i < solids.size(); i++)
+ if (((Segment) solids.elementAt(i)).contains(x, y))
+ n++;
+
+ for (int i = 0; i < holes.size(); i++)
+ if (((Segment) holes.elementAt(i)).contains(x, y))
+ n--;
+
+ return (n != 0);
}
+
+ /**
+ * Determines if the Point2D p is contained within this Area.
+ *
+ * @param p the point.
+ * @return <code>true</code> if the point is contained, <code>false</code>
+ * otherwise.
+ * @throws NullPointerException if <code>p</code> is <code>null</code>.
+ */
public boolean contains(Point2D p)
{
return contains(p.getX(), p.getY());
}
+
+ /**
+ * Determines if the rectangle specified by (x,y) as the upper-left
+ * and with width w and height h is completely contained within this Area,
+ * returns false otherwise.<P>
+ *
+ * This method should always produce the correct results, unlike for other
+ * classes in geom.
+ *
+ * @param x the x-coordinate of the rectangle.
+ * @param y the y-coordinate of the rectangle.
+ * @param w the width of the the rectangle.
+ * @param h the height of the rectangle.
+ * @return <code>true</code> if the rectangle is considered contained
+ */
public boolean contains(double x, double y, double w, double h)
{
- // XXX Implement.
- throw new Error("not implemented");
+ LineSegment[] l = new LineSegment[4];
+ l[0] = new LineSegment(x, y, x + w, y);
+ l[1] = new LineSegment(x, y + h, x + w, y + h);
+ l[2] = new LineSegment(x, y, x, y + h);
+ l[3] = new LineSegment(x + w, y, x + w, y + h);
+
+ // Since every segment in the area must a contour
+ // between inside/outside segments, ANY intersection
+ // will mean the rectangle is not entirely contained.
+ for (int i = 0; i < 4; i++)
+ {
+ for (int path = 0; path < solids.size(); path++)
+ {
+ Segment v;
+ Segment start;
+ start = v = (Segment) solids.elementAt(path);
+ do
+ {
+ if (l[i].hasIntersections(v))
+ return false;
+ v = v.next;
+ }
+ while (v != start);
+ }
+ for (int path = 0; path < holes.size(); path++)
+ {
+ Segment v;
+ Segment start;
+ start = v = (Segment) holes.elementAt(path);
+ do
+ {
+ if (l[i].hasIntersections(v))
+ return false;
+ v = v.next;
+ }
+ while (v != start);
+ }
+ }
+
+ // Is any point inside?
+ if (! contains(x, y))
+ return false;
+
+ // Final hoop: Is the rectangle non-intersecting and inside,
+ // but encloses a hole?
+ Rectangle2D r = new Rectangle2D.Double(x, y, w, h);
+ for (int path = 0; path < holes.size(); path++)
+ if (! ((Segment) holes.elementAt(path)).isSegmentOutside(r))
+ return false;
+
+ return true;
}
+
+ /**
+ * Determines if the Rectangle2D specified by r is completely contained
+ * within this Area, returns false otherwise.<P>
+ *
+ * This method should always produce the correct results, unlike for other
+ * classes in geom.
+ *
+ * @param r the rectangle.
+ * @return <code>true</code> if the rectangle is considered contained
+ *
+ * @throws NullPointerException if <code>r</code> is <code>null</code>.
+ */
public boolean contains(Rectangle2D r)
{
return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
}
+ /**
+ * Determines if the rectangle specified by (x,y) as the upper-left
+ * and with width w and height h intersects any part of this Area.
+ *
+ * @param x the x-coordinate for the rectangle.
+ * @param y the y-coordinate for the rectangle.
+ * @param w the width of the rectangle.
+ * @param h the height of the rectangle.
+ * @return <code>true</code> if the rectangle intersects the area,
+ * <code>false</code> otherwise.
+ */
public boolean intersects(double x, double y, double w, double h)
{
- // XXX Implement.
- throw new Error("not implemented");
+ if (solids.size() == 0)
+ return false;
+
+ LineSegment[] l = new LineSegment[4];
+ l[0] = new LineSegment(x, y, x + w, y);
+ l[1] = new LineSegment(x, y + h, x + w, y + h);
+ l[2] = new LineSegment(x, y, x, y + h);
+ l[3] = new LineSegment(x + w, y, x + w, y + h);
+
+ // Return true on any intersection
+ for (int i = 0; i < 4; i++)
+ {
+ for (int path = 0; path < solids.size(); path++)
+ {
+ Segment v;
+ Segment start;
+ start = v = (Segment) solids.elementAt(path);
+ do
+ {
+ if (l[i].hasIntersections(v))
+ return true;
+ v = v.next;
+ }
+ while (v != start);
+ }
+ for (int path = 0; path < holes.size(); path++)
+ {
+ Segment v;
+ Segment start;
+ start = v = (Segment) holes.elementAt(path);
+ do
+ {
+ if (l[i].hasIntersections(v))
+ return true;
+ v = v.next;
+ }
+ while (v != start);
+ }
+ }
+
+ // Non-intersecting, Is any point inside?
+ if (contains(x + w * 0.5, y + h * 0.5))
+ return true;
+
+ // What if the rectangle encloses the whole shape?
+ Point2D p = ((Segment) solids.elementAt(0)).getMidPoint();
+ if ((new Rectangle2D.Double(x, y, w, h)).contains(p))
+ return true;
+ return false;
}
+
+ /**
+ * Determines if the Rectangle2D specified by r intersects any
+ * part of this Area.
+ * @param r the rectangle to test intersection with (<code>null</code>
+ * not permitted).
+ * @return <code>true</code> if the rectangle intersects the area,
+ * <code>false</code> otherwise.
+ * @throws NullPointerException if <code>r</code> is <code>null</code>.
+ */
public boolean intersects(Rectangle2D r)
{
return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
}
+
+ /**
+ * Returns a PathIterator object defining the contour of this Area,
+ * transformed by at.
+ *
+ * @param at the transform.
+ * @return A path iterator.
+ */
public PathIterator getPathIterator(AffineTransform at)
{
- // XXX Implement.
- throw new Error("not implemented");
+ return (new AreaIterator(at));
}
+
+ /**
+ * Returns a flattened PathIterator object defining the contour of this
+ * Area, transformed by at and with a defined flatness.
+ *
+ * @param at the transform.
+ * @param flatness the flatness.
+ * @return A path iterator.
+ */
public PathIterator getPathIterator(AffineTransform at, double flatness)
{
return new FlatteningPathIterator(getPathIterator(at), flatness);
}
+
+ //---------------------------------------------------------------------
+ // Non-public methods and classes
+
+ /**
+ * Private pathiterator object.
+ */
+ private class AreaIterator implements PathIterator
+ {
+ private Vector segments;
+ private int index;
+ private AffineTransform at;
+
+ // Simple compound type for segments
+ class IteratorSegment
+ {
+ int type;
+ double[] coords;
+
+ IteratorSegment()
+ {
+ coords = new double[6];
+ }
+ }
+
+ /**
+ * The contructor here does most of the work,
+ * creates a vector of IteratorSegments, which can
+ * readily be returned
+ */
+ public AreaIterator(AffineTransform at)
+ {
+ this.at = at;
+ index = 0;
+ segments = new Vector();
+ Vector allpaths = new Vector();
+ allpaths.addAll(solids);
+ allpaths.addAll(holes);
+
+ for (int i = 0; i < allpaths.size(); i++)
+ {
+ Segment v = (Segment) allpaths.elementAt(i);
+ Segment start = v;
+
+ IteratorSegment is = new IteratorSegment();
+ is.type = SEG_MOVETO;
+ is.coords[0] = start.P1.getX();
+ is.coords[1] = start.P1.getY();
+ segments.add(is);
+
+ do
+ {
+ is = new IteratorSegment();
+ is.type = v.pathIteratorFormat(is.coords);
+ segments.add(is);
+ v = v.next;
+ }
+ while (v != start);
+
+ is = new IteratorSegment();
+ is.type = SEG_CLOSE;
+ segments.add(is);
+ }
+ }
+
+ public int currentSegment(double[] coords)
+ {
+ IteratorSegment s = (IteratorSegment) segments.elementAt(index);
+ if (at != null)
+ at.transform(s.coords, 0, coords, 0, 3);
+ else
+ for (int i = 0; i < 6; i++)
+ coords[i] = s.coords[i];
+ return (s.type);
+ }
+
+ public int currentSegment(float[] coords)
+ {
+ IteratorSegment s = (IteratorSegment) segments.elementAt(index);
+ double[] d = new double[6];
+ if (at != null)
+ {
+ at.transform(s.coords, 0, d, 0, 3);
+ for (int i = 0; i < 6; i++)
+ coords[i] = (float) d[i];
+ }
+ else
+ for (int i = 0; i < 6; i++)
+ coords[i] = (float) s.coords[i];
+ return (s.type);
+ }
+
+ // Note that the winding rule should not matter here,
+ // EVEN_ODD is chosen because it renders faster.
+ public int getWindingRule()
+ {
+ return (PathIterator.WIND_EVEN_ODD);
+ }
+
+ public boolean isDone()
+ {
+ return (index >= segments.size());
+ }
+
+ public void next()
+ {
+ index++;
+ }
+ }
+
+ /**
+ * Performs the fundamental task of the Weiler-Atherton algorithm,
+ * traverse a list of segments, for each segment:
+ * Follow it, removing segments from the list and switching paths
+ * at each node. Do so until the starting segment is reached.
+ *
+ * Returns a Vector of the resulting paths.
+ */
+ private Vector weilerAtherton(Vector segments)
+ {
+ Vector paths = new Vector();
+ while (segments.size() > 0)
+ {
+ // Iterate over the path
+ Segment start = (Segment) segments.elementAt(0);
+ Segment s = start;
+ do
+ {
+ segments.remove(s);
+ if (s.node != null)
+ { // switch over
+ s.next = s.node;
+ s.node = null;
+ }
+ s = s.next; // continue
+ }
+ while (s != start);
+
+ paths.add(start);
+ }
+ return paths;
+ }
+
+ /**
+ * A small wrapper class to store intersection points
+ */
+ private class Intersection
+ {
+ Point2D p; // the 2D point of intersection
+ double ta; // the parametric value on a
+ double tb; // the parametric value on b
+ Segment seg; // segment placeholder for node setting
+
+ public Intersection(Point2D p, double ta, double tb)
+ {
+ this.p = p;
+ this.ta = ta;
+ this.tb = tb;
+ }
+ }
+
+ /**
+ * Returns the recursion depth necessary to approximate the
+ * curve by line segments within the error RS_EPSILON.
+ *
+ * This is done with Wang's formula:
+ * L0 = max{0<=i<=N-2}(|xi - 2xi+1 + xi+2|,|yi - 2yi+1 + yi+2|)
+ * r0 = log4(sqrt(2)*N*(N-1)*L0/8e)
+ * Where e is the maximum distance error (RS_EPSILON)
+ */
+ private int getRecursionDepth(CubicSegment curve)
+ {
+ double x0 = curve.P1.getX();
+ double y0 = curve.P1.getY();
+
+ double x1 = curve.cp1.getX();
+ double y1 = curve.cp1.getY();
+
+ double x2 = curve.cp2.getX();
+ double y2 = curve.cp2.getY();
+
+ double x3 = curve.P2.getX();
+ double y3 = curve.P2.getY();
+
+ double L0 = Math.max(Math.max(Math.abs(x0 - 2 * x1 + x2),
+ Math.abs(x1 - 2 * x2 + x3)),
+ Math.max(Math.abs(y0 - 2 * y1 + y2),
+ Math.abs(y1 - 2 * y2 + y3)));
+
+ double f = Math.sqrt(2) * 6.0 * L0 / (8.0 * RS_EPSILON);
+
+ int r0 = (int) Math.ceil(Math.log(f) / Math.log(4.0));
+ return (r0);
+ }
+
+ /**
+ * Performs recursive subdivision:
+ * @param c1 - curve 1
+ * @param c2 - curve 2
+ * @param depth1 - recursion depth of curve 1
+ * @param depth2 - recursion depth of curve 2
+ * @param t1 - global parametric value of the first curve's starting point
+ * @param t2 - global parametric value of the second curve's starting point
+ * @param w1 - global parametric length of curve 1
+ * @param c1 - global parametric length of curve 2
+ *
+ * The final four parameters are for keeping track of the parametric
+ * value of the curve. For a full curve t = 0, w = 1, w is halved with
+ * each subdivision.
+ */
+ private void recursiveSubdivide(CubicCurve2D c1, CubicCurve2D c2,
+ int depth1, int depth2, double t1,
+ double t2, double w1, double w2)
+ {
+ boolean flat1 = depth1 <= 0;
+ boolean flat2 = depth2 <= 0;
+
+ if (flat1 && flat2)
+ {
+ double xlk = c1.getP2().getX() - c1.getP1().getX();
+ double ylk = c1.getP2().getY() - c1.getP1().getY();
+
+ double xnm = c2.getP2().getX() - c2.getP1().getX();
+ double ynm = c2.getP2().getY() - c2.getP1().getY();
+
+ double xmk = c2.getP1().getX() - c1.getP1().getX();
+ double ymk = c2.getP1().getY() - c1.getP1().getY();
+ double det = xnm * ylk - ynm * xlk;
+
+ if (det + 1.0 == 1.0)
+ return;
+
+ double detinv = 1.0 / det;
+ double s = (xnm * ymk - ynm * xmk) * detinv;
+ double t = (xlk * ymk - ylk * xmk) * detinv;
+ if ((s < 0.0) || (s > 1.0) || (t < 0.0) || (t > 1.0))
+ return;
+
+ double[] temp = new double[2];
+ temp[0] = t1 + s * w1;
+ temp[1] = t2 + t * w1;
+ cc_intersections.add(temp);
+ return;
+ }
+
+ CubicCurve2D.Double c11 = new CubicCurve2D.Double();
+ CubicCurve2D.Double c12 = new CubicCurve2D.Double();
+ CubicCurve2D.Double c21 = new CubicCurve2D.Double();
+ CubicCurve2D.Double c22 = new CubicCurve2D.Double();
+
+ if (! flat1 && ! flat2)
+ {
+ depth1--;
+ depth2--;
+ w1 = w1 * 0.5;
+ w2 = w2 * 0.5;
+ c1.subdivide(c11, c12);
+ c2.subdivide(c21, c22);
+ if (c11.getBounds2D().intersects(c21.getBounds2D()))
+ recursiveSubdivide(c11, c21, depth1, depth2, t1, t2, w1, w2);
+ if (c11.getBounds2D().intersects(c22.getBounds2D()))
+ recursiveSubdivide(c11, c22, depth1, depth2, t1, t2 + w2, w1, w2);
+ if (c12.getBounds2D().intersects(c21.getBounds2D()))
+ recursiveSubdivide(c12, c21, depth1, depth2, t1 + w1, t2, w1, w2);
+ if (c12.getBounds2D().intersects(c22.getBounds2D()))
+ recursiveSubdivide(c12, c22, depth1, depth2, t1 + w1, t2 + w2, w1, w2);
+ return;
+ }
+
+ if (! flat1)
+ {
+ depth1--;
+ c1.subdivide(c11, c12);
+ w1 = w1 * 0.5;
+ if (c11.getBounds2D().intersects(c2.getBounds2D()))
+ recursiveSubdivide(c11, c2, depth1, depth2, t1, t2, w1, w2);
+ if (c12.getBounds2D().intersects(c2.getBounds2D()))
+ recursiveSubdivide(c12, c2, depth1, depth2, t1 + w1, t2, w1, w2);
+ return;
+ }
+
+ depth2--;
+ c2.subdivide(c21, c22);
+ w2 = w2 * 0.5;
+ if (c1.getBounds2D().intersects(c21.getBounds2D()))
+ recursiveSubdivide(c1, c21, depth1, depth2, t1, t2, w1, w2);
+ if (c1.getBounds2D().intersects(c22.getBounds2D()))
+ recursiveSubdivide(c1, c22, depth1, depth2, t1, t2 + w2, w1, w2);
+ }
+
+ /**
+ * Returns a set of interesections between two Cubic segments
+ * Or null if no intersections were found.
+ *
+ * The method used to find the intersection is recursive midpoint
+ * subdivision. Outline description:
+ *
+ * 1) Check if the bounding boxes of the curves intersect,
+ * 2) If so, divide the curves in the middle and test the bounding
+ * boxes again,
+ * 3) Repeat until a maximum recursion depth has been reached, where
+ * the intersecting curves can be approximated by line segments.
+ *
+ * This is a reasonably accurate method, although the recursion depth
+ * is typically around 20, the bounding-box tests allow for significant
+ * pruning of the subdivision tree.
+ */
+ private Intersection[] cubicCubicIntersect(CubicSegment curve1,
+ CubicSegment curve2)
+ {
+ Rectangle2D r1 = curve1.getBounds();
+ Rectangle2D r2 = curve2.getBounds();
+
+ if (! r1.intersects(r2))
+ return null;
+
+ cc_intersections = new Vector();
+ recursiveSubdivide(curve1.getCubicCurve2D(), curve2.getCubicCurve2D(),
+ getRecursionDepth(curve1), getRecursionDepth(curve2),
+ 0.0, 0.0, 1.0, 1.0);
+
+ if (cc_intersections.size() == 0)
+ return null;
+
+ Intersection[] results = new Intersection[cc_intersections.size()];
+ for (int i = 0; i < cc_intersections.size(); i++)
+ {
+ double[] temp = (double[]) cc_intersections.elementAt(i);
+ results[i] = new Intersection(curve1.evaluatePoint(temp[0]), temp[0],
+ temp[1]);
+ }
+ cc_intersections = null;
+ return (results);
+ }
+
+ /**
+ * Returns the intersections between a line and a quadratic bezier
+ * Or null if no intersections are found1
+ * This is done through combining the line's equation with the
+ * parametric form of the Bezier and solving the resulting quadratic.
+ */
+ private Intersection[] lineQuadIntersect(LineSegment l, QuadSegment c)
+ {
+ double[] y = new double[3];
+ double[] x = new double[3];
+ double[] r = new double[3];
+ int nRoots;
+ double x0 = c.P1.getX();
+ double y0 = c.P1.getY();
+ double x1 = c.cp.getX();
+ double y1 = c.cp.getY();
+ double x2 = c.P2.getX();
+ double y2 = c.P2.getY();
+
+ double lx0 = l.P1.getX();
+ double ly0 = l.P1.getY();
+ double lx1 = l.P2.getX();
+ double ly1 = l.P2.getY();
+ double dx = lx1 - lx0;
+ double dy = ly1 - ly0;
+
+ // form r(t) = y(t) - x(t) for the bezier
+ y[0] = y0;
+ y[1] = 2 * (y1 - y0);
+ y[2] = (y2 - 2 * y1 + y0);
+
+ x[0] = x0;
+ x[1] = 2 * (x1 - x0);
+ x[2] = (x2 - 2 * x1 + x0);
+
+ // a point, not a line
+ if (dy == 0 && dx == 0)
+ return null;
+
+ // line on y axis
+ if (dx == 0 || (dy / dx) > 1.0)
+ {
+ double k = dx / dy;
+ x[0] -= lx0;
+ y[0] -= ly0;
+ y[0] *= k;
+ y[1] *= k;
+ y[2] *= k;
+ }
+ else
+ {
+ double k = dy / dx;
+ x[0] -= lx0;
+ y[0] -= ly0;
+ x[0] *= k;
+ x[1] *= k;
+ x[2] *= k;
+ }
+
+ for (int i = 0; i < 3; i++)
+ r[i] = y[i] - x[i];
+
+ if ((nRoots = QuadCurve2D.solveQuadratic(r)) > 0)
+ {
+ Intersection[] temp = new Intersection[nRoots];
+ int intersections = 0;
+ for (int i = 0; i < nRoots; i++)
+ {
+ double t = r[i];
+ if (t >= 0.0 && t <= 1.0)
+ {
+ Point2D p = c.evaluatePoint(t);
+
+ // if the line is on an axis, snap the point to that axis.
+ if (dx == 0)
+ p.setLocation(lx0, p.getY());
+ if (dy == 0)
+ p.setLocation(p.getX(), ly0);
+
+ if (p.getX() <= Math.max(lx0, lx1)
+ && p.getX() >= Math.min(lx0, lx1)
+ && p.getY() <= Math.max(ly0, ly1)
+ && p.getY() >= Math.min(ly0, ly1))
+ {
+ double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1);
+ temp[i] = new Intersection(p, lineparameter, t);
+ intersections++;
+ }
+ }
+ else
+ temp[i] = null;
+ }
+ if (intersections == 0)
+ return null;
+
+ Intersection[] rValues = new Intersection[intersections];
+
+ for (int i = 0; i < nRoots; i++)
+ if (temp[i] != null)
+ rValues[--intersections] = temp[i];
+ return (rValues);
+ }
+ return null;
+ }
+
+ /**
+ * Returns the intersections between a line and a cubic segment
+ * This is done through combining the line's equation with the
+ * parametric form of the Bezier and solving the resulting quadratic.
+ */
+ private Intersection[] lineCubicIntersect(LineSegment l, CubicSegment c)
+ {
+ double[] y = new double[4];
+ double[] x = new double[4];
+ double[] r = new double[4];
+ int nRoots;
+ double x0 = c.P1.getX();
+ double y0 = c.P1.getY();
+ double x1 = c.cp1.getX();
+ double y1 = c.cp1.getY();
+ double x2 = c.cp2.getX();
+ double y2 = c.cp2.getY();
+ double x3 = c.P2.getX();
+ double y3 = c.P2.getY();
+
+ double lx0 = l.P1.getX();
+ double ly0 = l.P1.getY();
+ double lx1 = l.P2.getX();
+ double ly1 = l.P2.getY();
+ double dx = lx1 - lx0;
+ double dy = ly1 - ly0;
+
+ // form r(t) = y(t) - x(t) for the bezier
+ y[0] = y0;
+ y[1] = 3 * (y1 - y0);
+ y[2] = 3 * (y2 + y0 - 2 * y1);
+ y[3] = y3 - 3 * y2 + 3 * y1 - y0;
+
+ x[0] = x0;
+ x[1] = 3 * (x1 - x0);
+ x[2] = 3 * (x2 + x0 - 2 * x1);
+ x[3] = x3 - 3 * x2 + 3 * x1 - x0;
+
+ // a point, not a line
+ if (dy == 0 && dx == 0)
+ return null;
+
+ // line on y axis
+ if (dx == 0 || (dy / dx) > 1.0)
+ {
+ double k = dx / dy;
+ x[0] -= lx0;
+ y[0] -= ly0;
+ y[0] *= k;
+ y[1] *= k;
+ y[2] *= k;
+ y[3] *= k;
+ }
+ else
+ {
+ double k = dy / dx;
+ x[0] -= lx0;
+ y[0] -= ly0;
+ x[0] *= k;
+ x[1] *= k;
+ x[2] *= k;
+ x[3] *= k;
+ }
+ for (int i = 0; i < 4; i++)
+ r[i] = y[i] - x[i];
+
+ if ((nRoots = CubicCurve2D.solveCubic(r)) > 0)
+ {
+ Intersection[] temp = new Intersection[nRoots];
+ int intersections = 0;
+ for (int i = 0; i < nRoots; i++)
+ {
+ double t = r[i];
+ if (t >= 0.0 && t <= 1.0)
+ {
+ // if the line is on an axis, snap the point to that axis.
+ Point2D p = c.evaluatePoint(t);
+ if (dx == 0)
+ p.setLocation(lx0, p.getY());
+ if (dy == 0)
+ p.setLocation(p.getX(), ly0);
+
+ if (p.getX() <= Math.max(lx0, lx1)
+ && p.getX() >= Math.min(lx0, lx1)
+ && p.getY() <= Math.max(ly0, ly1)
+ && p.getY() >= Math.min(ly0, ly1))
+ {
+ double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1);
+ temp[i] = new Intersection(p, lineparameter, t);
+ intersections++;
+ }
+ }
+ else
+ temp[i] = null;
+ }
+
+ if (intersections == 0)
+ return null;
+
+ Intersection[] rValues = new Intersection[intersections];
+ for (int i = 0; i < nRoots; i++)
+ if (temp[i] != null)
+ rValues[--intersections] = temp[i];
+ return (rValues);
+ }
+ return null;
+ }
+
+ /**
+ * Returns the intersection between two lines, or null if there is no
+ * intersection.
+ */
+ private Intersection linesIntersect(LineSegment a, LineSegment b)
+ {
+ Point2D P1 = a.P1;
+ Point2D P2 = a.P2;
+ Point2D P3 = b.P1;
+ Point2D P4 = b.P2;
+
+ if (! Line2D.linesIntersect(P1.getX(), P1.getY(), P2.getX(), P2.getY(),
+ P3.getX(), P3.getY(), P4.getX(), P4.getY()))
+ return null;
+
+ double x1 = P1.getX();
+ double y1 = P1.getY();
+ double rx = P2.getX() - x1;
+ double ry = P2.getY() - y1;
+
+ double x2 = P3.getX();
+ double y2 = P3.getY();
+ double sx = P4.getX() - x2;
+ double sy = P4.getY() - y2;
+
+ double determinant = sx * ry - sy * rx;
+ double nom = (sx * (y2 - y1) + sy * (x1 - x2));
+
+ // Parallel lines don't intersect. At least we pretend they don't.
+ if (Math.abs(determinant) < EPSILON)
+ return null;
+
+ nom = nom / determinant;
+
+ if (nom == 0.0)
+ return null;
+ if (nom == 1.0)
+ return null;
+
+ Point2D p = new Point2D.Double(x1 + nom * rx, y1 + nom * ry);
+
+ return new Intersection(p, p.distance(P1) / P1.distance(P2),
+ p.distance(P3) / P3.distance(P4));
+ }
+
+ /**
+ * Determines if two points are equal, within an error margin
+ * 'snap distance'
+ */
+ private boolean pointEquals(Point2D a, Point2D b)
+ {
+ return (a.equals(b) || a.distance(b) < PE_EPSILON);
+ }
+
+ /**
+ * Helper method
+ * Turns a shape into a Vector of Segments
+ */
+ private Vector makeSegment(Shape s)
+ {
+ Vector paths = new Vector();
+ PathIterator pi = s.getPathIterator(null);
+ double[] coords = new double[6];
+ Segment subpath = null;
+ Segment current = null;
+ double cx;
+ double cy;
+ double subpathx;
+ double subpathy;
+ cx = cy = subpathx = subpathy = 0.0;
+
+ this.windingRule = pi.getWindingRule();
+
+ while (! pi.isDone())
+ {
+ Segment v;
+ switch (pi.currentSegment(coords))
+ {
+ case PathIterator.SEG_MOVETO:
+ if (subpath != null)
+ { // close existing open path
+ current.next = new LineSegment(cx, cy, subpathx, subpathy);
+ current = current.next;
+ current.next = subpath;
+ }
+ subpath = null;
+ subpathx = cx = coords[0];
+ subpathy = cy = coords[1];
+ break;
+
+ // replace 'close' with a line-to.
+ case PathIterator.SEG_CLOSE:
+ if (subpath != null && (subpathx != cx || subpathy != cy))
+ {
+ current.next = new LineSegment(cx, cy, subpathx, subpathy);
+ current = current.next;
+ current.next = subpath;
+ cx = subpathx;
+ cy = subpathy;
+ subpath = null;
+ }
+ else if (subpath != null)
+ {
+ current.next = subpath;
+ subpath = null;
+ }
+ break;
+ case PathIterator.SEG_LINETO:
+ if (cx != coords[0] || cy != coords[1])
+ {
+ v = new LineSegment(cx, cy, coords[0], coords[1]);
+ if (subpath == null)
+ {
+ subpath = current = v;
+ paths.add(subpath);
+ }
+ else
+ {
+ current.next = v;
+ current = current.next;
+ }
+ cx = coords[0];
+ cy = coords[1];
+ }
+ break;
+ case PathIterator.SEG_QUADTO:
+ v = new QuadSegment(cx, cy, coords[0], coords[1], coords[2],
+ coords[3]);
+ if (subpath == null)
+ {
+ subpath = current = v;
+ paths.add(subpath);
+ }
+ else
+ {
+ current.next = v;
+ current = current.next;
+ }
+ cx = coords[2];
+ cy = coords[3];
+ break;
+ case PathIterator.SEG_CUBICTO:
+ v = new CubicSegment(cx, cy, coords[0], coords[1], coords[2],
+ coords[3], coords[4], coords[5]);
+ if (subpath == null)
+ {
+ subpath = current = v;
+ paths.add(subpath);
+ }
+ else
+ {
+ current.next = v;
+ current = current.next;
+ }
+
+ // check if the cubic is self-intersecting
+ double[] lpts = ((CubicSegment) v).getLoop();
+ if (lpts != null)
+ {
+ // if it is, break off the loop into its own path.
+ v.subdivideInsert(lpts[0]);
+ v.next.subdivideInsert((lpts[1] - lpts[0]) / (1.0 - lpts[0]));
+
+ CubicSegment loop = (CubicSegment) v.next;
+ v.next = loop.next;
+ loop.next = loop;
+
+ v.P2 = v.next.P1 = loop.P2 = loop.P1; // snap points
+ paths.add(loop);
+ current = v.next;
+ }
+
+ cx = coords[4];
+ cy = coords[5];
+ break;
+ }
+ pi.next();
+ }
+
+ if (subpath != null)
+ { // close any open path
+ if (subpathx != cx || subpathy != cy)
+ {
+ current.next = new LineSegment(cx, cy, subpathx, subpathy);
+ current = current.next;
+ current.next = subpath;
+ }
+ else
+ current.next = subpath;
+ }
+
+ if (paths.size() == 0)
+ return (null);
+
+ return (paths);
+ }
+
+ /**
+ * Find the intersections of two separate closed paths,
+ * A and B, split the segments at the intersection points,
+ * and create nodes pointing from one to the other
+ */
+ private int createNodes(Segment A, Segment B)
+ {
+ int nNodes = 0;
+
+ Segment a = A;
+ Segment b = B;
+
+ do
+ {
+ do
+ {
+ nNodes += a.splitIntersections(b);
+ b = b.next;
+ }
+ while (b != B);
+
+ a = a.next; // move to the next segment
+ }
+ while (a != A); // until one wrap.
+
+ return (nNodes);
+ }
+
+ /**
+ * Find the intersections of a path with itself.
+ * Splits the segments at the intersection points,
+ * and create nodes pointing from one to the other.
+ */
+ private int createNodesSelf(Segment A)
+ {
+ int nNodes = 0;
+ Segment a = A;
+
+ if (A.next == A)
+ return 0;
+
+ do
+ {
+ Segment b = a.next;
+ do
+ {
+ if (b != a) // necessary
+ nNodes += a.splitIntersections(b);
+ b = b.next;
+ }
+ while (b != A);
+ a = a.next; // move to the next segment
+ }
+ while (a != A); // until one wrap.
+
+ return (nNodes);
+ }
+
+ /**
+ * Deletes paths which are redundant from a list, (i.e. solid areas within
+ * solid areas) Clears any nodes. Sorts the remaining paths into solids
+ * and holes, sets their orientation and sets the solids and holes lists.
+ */
+ private void deleteRedundantPaths(Vector paths)
+ {
+ int npaths = paths.size();
+
+ int[][] contains = new int[npaths][npaths];
+ int[][] windingNumbers = new int[npaths][2];
+ int neg;
+ Rectangle2D[] bb = new Rectangle2D[npaths]; // path bounding boxes
+
+ neg = ((windingRule == PathIterator.WIND_NON_ZERO) ? -1 : 1);
+
+ for (int i = 0; i < npaths; i++)
+ bb[i] = ((Segment) paths.elementAt(i)).getPathBounds();
+
+ // Find which path contains which, assign winding numbers
+ for (int i = 0; i < npaths; i++)
+ {
+ Segment pathA = (Segment) paths.elementAt(i);
+ pathA.nullNodes(); // remove any now-redundant nodes, in case.
+ int windingA = pathA.hasClockwiseOrientation() ? 1 : neg;
+
+ for (int j = 0; j < npaths; j++)
+ if (i != j)
+ {
+ Segment pathB = (Segment) paths.elementAt(j);
+
+ // A contains B
+ if (bb[i].intersects(bb[j]))
+ {
+ Segment s = pathB.next;
+ while (s.P1.getY() == s.P2.getY() && s != pathB)
+ s = s.next;
+ Point2D p = s.getMidPoint();
+ if (pathA.contains(p.getX(), p.getY()))
+ contains[i][j] = windingA;
+ }
+ else
+ // A does not contain B
+ contains[i][j] = 0;
+ }
+ else
+ contains[i][j] = windingA; // i == j
+ }
+
+ for (int i = 0; i < npaths; i++)
+ {
+ windingNumbers[i][0] = 0;
+ for (int j = 0; j < npaths; j++)
+ windingNumbers[i][0] += contains[j][i];
+ windingNumbers[i][1] = contains[i][i];
+ }
+
+ Vector solids = new Vector();
+ Vector holes = new Vector();
+
+ if (windingRule == PathIterator.WIND_NON_ZERO)
+ {
+ for (int i = 0; i < npaths; i++)
+ {
+ if (windingNumbers[i][0] == 0)
+ holes.add(paths.elementAt(i));
+ else if (windingNumbers[i][0] - windingNumbers[i][1] == 0
+ && Math.abs(windingNumbers[i][0]) == 1)
+ solids.add(paths.elementAt(i));
+ }
+ }
+ else
+ {
+ windingRule = PathIterator.WIND_NON_ZERO;
+ for (int i = 0; i < npaths; i++)
+ {
+ if ((windingNumbers[i][0] & 1) == 0)
+ holes.add(paths.elementAt(i));
+ else if ((windingNumbers[i][0] & 1) == 1)
+ solids.add(paths.elementAt(i));
+ }
+ }
+
+ setDirection(holes, false);
+ setDirection(solids, true);
+ this.holes = holes;
+ this.solids = solids;
+ }
+
+ /**
+ * Sets the winding direction of a Vector of paths
+ * @param clockwise gives the direction,
+ * true = clockwise, false = counter-clockwise
+ */
+ private void setDirection(Vector paths, boolean clockwise)
+ {
+ Segment v;
+ for (int i = 0; i < paths.size(); i++)
+ {
+ v = (Segment) paths.elementAt(i);
+ if (clockwise != v.hasClockwiseOrientation())
+ v.reverseAll();
+ }
+ }
+
+ /**
+ * Class representing a linked-list of vertices forming a closed polygon,
+ * convex or concave, without holes.
+ */
+ private abstract class Segment implements Cloneable
+ {
+ // segment type, PathIterator segment types are used.
+ Point2D P1;
+ Point2D P2;
+ Segment next;
+ Segment node;
+
+ Segment()
+ {
+ P1 = P2 = null;
+ node = next = null;
+ }
+
+ /**
+ * Reverses the direction of a single segment
+ */
+ abstract void reverseCoords();
+
+ /**
+ * Returns the segment's midpoint
+ */
+ abstract Point2D getMidPoint();
+
+ /**
+ * Returns the bounding box of this segment
+ */
+ abstract Rectangle2D getBounds();
+
+ /**
+ * Transforms a single segment
+ */
+ abstract void transform(AffineTransform at);
+
+ /**
+ * Returns the PathIterator type of a segment
+ */
+ abstract int getType();
+
+ /**
+ */
+ abstract int splitIntersections(Segment b);
+
+ /**
+ * Returns the PathIterator coords of a segment
+ */
+ abstract int pathIteratorFormat(double[] coords);
+
+ /**
+ * Returns the number of intersections on the positive X axis,
+ * with the origin at (x,y), used for contains()-testing
+ *
+ * (Although that could be done by the line-intersect methods,
+ * a dedicated method is better to guarantee consitent handling
+ * of endpoint-special-cases)
+ */
+ abstract int rayCrossing(double x, double y);
+
+ /**
+ * Subdivides the segment at parametric value t, inserting
+ * the new segment into the linked list after this,
+ * such that this becomes [0,t] and this.next becomes [t,1]
+ */
+ abstract void subdivideInsert(double t);
+
+ /**
+ * Returns twice the area of a curve, relative the P1-P2 line
+ * Used for area calculations.
+ */
+ abstract double curveArea();
+
+ /**
+ * Compare two segments.
+ */
+ abstract boolean equals(Segment b);
+
+ /**
+ * Determines if this path of segments contains the point (x,y)
+ */
+ boolean contains(double x, double y)
+ {
+ Segment v = this;
+ int crossings = 0;
+ do
+ {
+ int n = v.rayCrossing(x, y);
+ crossings += n;
+ v = v.next;
+ }
+ while (v != this);
+ return ((crossings & 1) == 1);
+ }
+
+ /**
+ * Nulls all nodes of the path. Clean up any 'hairs'.
+ */
+ void nullNodes()
+ {
+ Segment v = this;
+ do
+ {
+ v.node = null;
+ v = v.next;
+ }
+ while (v != this);
+ }
+
+ /**
+ * Transforms each segment in the closed path
+ */
+ void transformSegmentList(AffineTransform at)
+ {
+ Segment v = this;
+ do
+ {
+ v.transform(at);
+ v = v.next;
+ }
+ while (v != this);
+ }
+
+ /**
+ * Determines the winding direction of the path
+ * By the sign of the area.
+ */
+ boolean hasClockwiseOrientation()
+ {
+ return (getSignedArea() > 0.0);
+ }
+
+ /**
+ * Returns the bounds of this path
+ */
+ public Rectangle2D getPathBounds()
+ {
+ double xmin;
+ double xmax;
+ double ymin;
+ double ymax;
+ xmin = xmax = P1.getX();
+ ymin = ymax = P1.getY();
+
+ Segment v = this;
+ do
+ {
+ Rectangle2D r = v.getBounds();
+ xmin = Math.min(r.getMinX(), xmin);
+ ymin = Math.min(r.getMinY(), ymin);
+ xmax = Math.max(r.getMaxX(), xmax);
+ ymax = Math.max(r.getMaxY(), ymax);
+ v = v.next;
+ }
+ while (v != this);
+
+ return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
+ }
+
+ /**
+ * Calculates twice the signed area of the path;
+ */
+ double getSignedArea()
+ {
+ Segment s;
+ double area = 0.0;
+
+ s = this;
+ do
+ {
+ area += s.curveArea();
+
+ area += s.P1.getX() * s.next.P1.getY()
+ - s.P1.getY() * s.next.P1.getX();
+ s = s.next;
+ }
+ while (s != this);
+
+ return area;
+ }
+
+ /**
+ * Reverses the orientation of the whole polygon
+ */
+ void reverseAll()
+ {
+ reverseCoords();
+ Segment v = next;
+ Segment former = this;
+ while (v != this)
+ {
+ v.reverseCoords();
+ Segment vnext = v.next;
+ v.next = former;
+ former = v;
+ v = vnext;
+ }
+ next = former;
+ }
+
+ /**
+ * Inserts a Segment after this one
+ */
+ void insert(Segment v)
+ {
+ Segment n = next;
+ next = v;
+ v.next = n;
+ }
+
+ /**
+ * Returns if this segment path is polygonal
+ */
+ boolean isPolygonal()
+ {
+ Segment v = this;
+ do
+ {
+ if (! (v instanceof LineSegment))
+ return false;
+ v = v.next;
+ }
+ while (v != this);
+ return true;
+ }
+
+ /**
+ * Clones this path
+ */
+ Segment cloneSegmentList() throws CloneNotSupportedException
+ {
+ Vector list = new Vector();
+ Segment v = next;
+
+ while (v != this)
+ {
+ list.add(v);
+ v = v.next;
+ }
+
+ Segment clone = (Segment) this.clone();
+ v = clone;
+ for (int i = 0; i < list.size(); i++)
+ {
+ clone.next = (Segment) ((Segment) list.elementAt(i)).clone();
+ clone = clone.next;
+ }
+ clone.next = v;
+ return v;
+ }
+
+ /**
+ * Creates a node between this segment and segment b
+ * at the given intersection
+ * @return the number of nodes created (0 or 1)
+ */
+ int createNode(Segment b, Intersection i)
+ {
+ Point2D p = i.p;
+ if ((pointEquals(P1, p) || pointEquals(P2, p))
+ && (pointEquals(b.P1, p) || pointEquals(b.P2, p)))
+ return 0;
+
+ subdivideInsert(i.ta);
+ b.subdivideInsert(i.tb);
+
+ // snap points
+ b.P2 = b.next.P1 = P2 = next.P1 = i.p;
+
+ node = b.next;
+ b.node = next;
+ return 1;
+ }
+
+ /**
+ * Creates multiple nodes from a list of intersections,
+ * This must be done in the order of ascending parameters,
+ * and the parameters must be recalculated in accordance
+ * with each split.
+ * @return the number of nodes created
+ */
+ protected int createNodes(Segment b, Intersection[] x)
+ {
+ Vector v = new Vector();
+ for (int i = 0; i < x.length; i++)
+ {
+ Point2D p = x[i].p;
+ if (! ((pointEquals(P1, p) || pointEquals(P2, p))
+ && (pointEquals(b.P1, p) || pointEquals(b.P2, p))))
+ v.add(x[i]);
+ }
+
+ int nNodes = v.size();
+ Intersection[] A = new Intersection[nNodes];
+ Intersection[] B = new Intersection[nNodes];
+ for (int i = 0; i < nNodes; i++)
+ A[i] = B[i] = (Intersection) v.elementAt(i);
+
+ // Create two lists sorted by the parameter
+ // Bubble sort, OK I suppose, since the number of intersections
+ // cannot be larger than 9 (cubic-cubic worst case) anyway
+ for (int i = 0; i < nNodes - 1; i++)
+ {
+ for (int j = i + 1; j < nNodes; j++)
+ {
+ if (A[i].ta > A[j].ta)
+ {
+ Intersection swap = A[i];
+ A[i] = A[j];
+ A[j] = swap;
+ }
+ if (B[i].tb > B[j].tb)
+ {
+ Intersection swap = B[i];
+ B[i] = B[j];
+ B[j] = swap;
+ }
+ }
+ }
+ // subdivide a
+ Segment s = this;
+ for (int i = 0; i < nNodes; i++)
+ {
+ s.subdivideInsert(A[i].ta);
+
+ // renormalize the parameters
+ for (int j = i + 1; j < nNodes; j++)
+ A[j].ta = (A[j].ta - A[i].ta) / (1.0 - A[i].ta);
+
+ A[i].seg = s;
+ s = s.next;
+ }
+
+ // subdivide b, set nodes
+ s = b;
+ for (int i = 0; i < nNodes; i++)
+ {
+ s.subdivideInsert(B[i].tb);
+
+ for (int j = i + 1; j < nNodes; j++)
+ B[j].tb = (B[j].tb - B[i].tb) / (1.0 - B[i].tb);
+
+ // set nodes
+ B[i].seg.node = s.next; // node a -> b
+ s.node = B[i].seg.next; // node b -> a
+
+ // snap points
+ B[i].seg.P2 = B[i].seg.next.P1 = s.P2 = s.next.P1 = B[i].p;
+ s = s.next;
+ }
+ return nNodes;
+ }
+
+ /**
+ * Determines if two paths are equal.
+ * Colinear line segments are ignored in the comparison.
+ */
+ boolean pathEquals(Segment B)
+ {
+ if (! getPathBounds().equals(B.getPathBounds()))
+ return false;
+
+ Segment startA = getTopLeft();
+ Segment startB = B.getTopLeft();
+ Segment a = startA;
+ Segment b = startB;
+ do
+ {
+ if (! a.equals(b))
+ return false;
+
+ if (a instanceof LineSegment)
+ a = ((LineSegment) a).lastCoLinear();
+ if (b instanceof LineSegment)
+ b = ((LineSegment) b).lastCoLinear();
+
+ a = a.next;
+ b = b.next;
+ }
+ while (a != startA && b != startB);
+ return true;
+ }
+
+ /**
+ * Return the segment with the top-leftmost first point
+ */
+ Segment getTopLeft()
+ {
+ Segment v = this;
+ Segment tl = this;
+ do
+ {
+ if (v.P1.getY() < tl.P1.getY())
+ tl = v;
+ else if (v.P1.getY() == tl.P1.getY())
+ {
+ if (v.P1.getX() < tl.P1.getX())
+ tl = v;
+ }
+ v = v.next;
+ }
+ while (v != this);
+ return tl;
+ }
+
+ /**
+ * Returns if the path has a segment outside a shape
+ */
+ boolean isSegmentOutside(Shape shape)
+ {
+ return ! shape.contains(getMidPoint());
+ }
+ } // class Segment
+
+ private class LineSegment extends Segment
+ {
+ public LineSegment(double x1, double y1, double x2, double y2)
+ {
+ super();
+ P1 = new Point2D.Double(x1, y1);
+ P2 = new Point2D.Double(x2, y2);
+ }
+
+ public LineSegment(Point2D p1, Point2D p2)
+ {
+ super();
+ P1 = (Point2D) p1.clone();
+ P2 = (Point2D) p2.clone();
+ }
+
+ /**
+ * Clones this segment
+ */
+ public Object clone()
+ {
+ return new LineSegment(P1, P2);
+ }
+
+ /**
+ * Transforms the segment
+ */
+ void transform(AffineTransform at)
+ {
+ P1 = at.transform(P1, null);
+ P2 = at.transform(P2, null);
+ }
+
+ /**
+ * Swap start and end points
+ */
+ void reverseCoords()
+ {
+ Point2D p = P1;
+ P1 = P2;
+ P2 = p;
+ }
+
+ /**
+ * Returns the segment's midpoint
+ */
+ Point2D getMidPoint()
+ {
+ return (new Point2D.Double(0.5 * (P1.getX() + P2.getX()),
+ 0.5 * (P1.getY() + P2.getY())));
+ }
+
+ /**
+ * Returns twice the area of a curve, relative the P1-P2 line
+ * Obviously, a line does not enclose any area besides the line
+ */
+ double curveArea()
+ {
+ return 0;
+ }
+
+ /**
+ * Returns the PathIterator type of a segment
+ */
+ int getType()
+ {
+ return (PathIterator.SEG_LINETO);
+ }
+
+ /**
+ * Subdivides the segment at parametric value t, inserting
+ * the new segment into the linked list after this,
+ * such that this becomes [0,t] and this.next becomes [t,1]
+ */
+ void subdivideInsert(double t)
+ {
+ Point2D p = new Point2D.Double((P2.getX() - P1.getX()) * t + P1.getX(),
+ (P2.getY() - P1.getY()) * t + P1.getY());
+ insert(new LineSegment(p, P2));
+ P2 = p;
+ next.node = node;
+ node = null;
+ }
+
+ /**
+ * Determines if two line segments are strictly colinear
+ */
+ boolean isCoLinear(LineSegment b)
+ {
+ double x1 = P1.getX();
+ double y1 = P1.getY();
+ double x2 = P2.getX();
+ double y2 = P2.getY();
+ double x3 = b.P1.getX();
+ double y3 = b.P1.getY();
+ double x4 = b.P2.getX();
+ double y4 = b.P2.getY();
+
+ if ((y1 - y3) * (x4 - x3) - (x1 - x3) * (y4 - y3) != 0.0)
+ return false;
+
+ return ((x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3) == 0.0);
+ }
+
+ /**
+ * Return the last segment colinear with this one.
+ * Used in comparing paths.
+ */
+ Segment lastCoLinear()
+ {
+ Segment prev = this;
+ Segment v = next;
+
+ while (v instanceof LineSegment)
+ {
+ if (isCoLinear((LineSegment) v))
+ {
+ prev = v;
+ v = v.next;
+ }
+ else
+ return prev;
+ }
+ return prev;
+ }
+
+ /**
+ * Compare two segments.
+ * We must take into account that the lines may be broken into colinear
+ * subsegments and ignore them.
+ */
+ boolean equals(Segment b)
+ {
+ if (! (b instanceof LineSegment))
+ return false;
+ Point2D p1 = P1;
+ Point2D p3 = b.P1;
+
+ if (! p1.equals(p3))
+ return false;
+
+ Point2D p2 = lastCoLinear().P2;
+ Point2D p4 = ((LineSegment) b).lastCoLinear().P2;
+ return (p2.equals(p4));
+ }
+
+ /**
+ * Returns a line segment
+ */
+ int pathIteratorFormat(double[] coords)
+ {
+ coords[0] = P2.getX();
+ coords[1] = P2.getY();
+ return (PathIterator.SEG_LINETO);
+ }
+
+ /**
+ * Returns if the line has intersections.
+ */
+ boolean hasIntersections(Segment b)
+ {
+ if (b instanceof LineSegment)
+ return (linesIntersect(this, (LineSegment) b) != null);
+
+ if (b instanceof QuadSegment)
+ return (lineQuadIntersect(this, (QuadSegment) b) != null);
+
+ if (b instanceof CubicSegment)
+ return (lineCubicIntersect(this, (CubicSegment) b) != null);
+
+ return false;
+ }
+
+ /**
+ * Splits intersections into nodes,
+ * This one handles line-line, line-quadratic, line-cubic
+ */
+ int splitIntersections(Segment b)
+ {
+ if (b instanceof LineSegment)
+ {
+ Intersection i = linesIntersect(this, (LineSegment) b);
+
+ if (i == null)
+ return 0;
+
+ return createNode(b, i);
+ }
+
+ Intersection[] x = null;
+
+ if (b instanceof QuadSegment)
+ x = lineQuadIntersect(this, (QuadSegment) b);
+
+ if (b instanceof CubicSegment)
+ x = lineCubicIntersect(this, (CubicSegment) b);
+
+ if (x == null)
+ return 0;
+
+ if (x.length == 1)
+ return createNode(b, (Intersection) x[0]);
+
+ return createNodes(b, x);
+ }
+
+ /**
+ * Returns the bounding box of this segment
+ */
+ Rectangle2D getBounds()
+ {
+ return (new Rectangle2D.Double(Math.min(P1.getX(), P2.getX()),
+ Math.min(P1.getY(), P2.getY()),
+ Math.abs(P1.getX() - P2.getX()),
+ Math.abs(P1.getY() - P2.getY())));
+ }
+
+ /**
+ * Returns the number of intersections on the positive X axis,
+ * with the origin at (x,y), used for contains()-testing
+ */
+ int rayCrossing(double x, double y)
+ {
+ double x0 = P1.getX() - x;
+ double y0 = P1.getY() - y;
+ double x1 = P2.getX() - x;
+ double y1 = P2.getY() - y;
+
+ if (y0 * y1 > 0)
+ return 0;
+
+ if (x0 < 0 && x1 < 0)
+ return 0;
+
+ if (y0 == 0.0)
+ y0 -= EPSILON;
+
+ if (y1 == 0.0)
+ y1 -= EPSILON;
+
+ if (Line2D.linesIntersect(x0, y0, x1, y1,
+ EPSILON, 0.0, Double.MAX_VALUE, 0.0))
+ return 1;
+ return 0;
+ }
+ } // class LineSegment
+
+ /**
+ * Quadratic Bezier curve segment
+ *
+ * Note: Most peers don't support quadratics directly, so it might make
+ * sense to represent them as cubics internally and just be done with it.
+ * I think we should be peer-agnostic, however, and stay faithful to the
+ * input geometry types as far as possible.
+ */
+ private class QuadSegment extends Segment
+ {
+ Point2D cp; // control point
+
+ /**
+ * Constructor, takes the coordinates of the start, control,
+ * and end point, respectively.
+ */
+ QuadSegment(double x1, double y1, double cx, double cy, double x2,
+ double y2)
+ {
+ super();
+ P1 = new Point2D.Double(x1, y1);
+ P2 = new Point2D.Double(x2, y2);
+ cp = new Point2D.Double(cx, cy);
+ }
+
+ /**
+ * Clones this segment
+ */
+ public Object clone()
+ {
+ return new QuadSegment(P1.getX(), P1.getY(), cp.getX(), cp.getY(),
+ P2.getX(), P2.getY());
+ }
+
+ /**
+ * Returns twice the area of a curve, relative the P1-P2 line
+ *
+ * The area formula can be derived by using Green's formula in the
+ * plane on the parametric form of the bezier.
+ */
+ double curveArea()
+ {
+ double x0 = P1.getX();
+ double y0 = P1.getY();
+ double x1 = cp.getX();
+ double y1 = cp.getY();
+ double x2 = P2.getX();
+ double y2 = P2.getY();
+
+ double P = (y2 - 2 * y1 + y0);
+ double Q = 2 * (y1 - y0);
+ double R = y0;
+
+ double A = (x2 - 2 * x1 + x0);
+ double B = 2 * (x1 - x0);
+ double C = x0;
+
+ double area = (B * P - A * Q) / 3.0;
+ return (area);
+ }
+
+ /**
+ * Compare two segments.
+ */
+ boolean equals(Segment b)
+ {
+ if (! (b instanceof QuadSegment))
+ return false;
+
+ return (P1.equals(b.P1) && cp.equals(((QuadSegment) b).cp)
+ && P2.equals(b.P2));
+ }
+
+ /**
+ * Returns a Point2D corresponding to the parametric value t
+ * of the curve
+ */
+ Point2D evaluatePoint(double t)
+ {
+ double x0 = P1.getX();
+ double y0 = P1.getY();
+ double x1 = cp.getX();
+ double y1 = cp.getY();
+ double x2 = P2.getX();
+ double y2 = P2.getY();
+
+ return new Point2D.Double(t * t * (x2 - 2 * x1 + x0) + 2 * t * (x1 - x0)
+ + x0,
+ t * t * (y2 - 2 * y1 + y0) + 2 * t * (y1 - y0)
+ + y0);
+ }
+
+ /**
+ * Returns the bounding box of this segment
+ */
+ Rectangle2D getBounds()
+ {
+ double x0 = P1.getX();
+ double y0 = P1.getY();
+ double x1 = cp.getX();
+ double y1 = cp.getY();
+ double x2 = P2.getX();
+ double y2 = P2.getY();
+ double r0;
+ double r1;
+
+ double xmax = Math.max(x0, x2);
+ double ymax = Math.max(y0, y2);
+ double xmin = Math.min(x0, x2);
+ double ymin = Math.min(y0, y2);
+
+ r0 = 2 * (y1 - y0);
+ r1 = 2 * (y2 - 2 * y1 + y0);
+ if (r1 != 0.0)
+ {
+ double t = -r0 / r1;
+ if (t > 0.0 && t < 1.0)
+ {
+ double y = evaluatePoint(t).getY();
+ ymax = Math.max(y, ymax);
+ ymin = Math.min(y, ymin);
+ }
+ }
+ r0 = 2 * (x1 - x0);
+ r1 = 2 * (x2 - 2 * x1 + x0);
+ if (r1 != 0.0)
+ {
+ double t = -r0 / r1;
+ if (t > 0.0 && t < 1.0)
+ {
+ double x = evaluatePoint(t).getY();
+ xmax = Math.max(x, xmax);
+ xmin = Math.min(x, xmin);
+ }
+ }
+
+ return (new Rectangle2D.Double(xmin, ymin, xmax - xmin, ymax - ymin));
+ }
+
+ /**
+ * Returns a cubic segment corresponding to this curve
+ */
+ CubicSegment getCubicSegment()
+ {
+ double x1 = P1.getX() + 2.0 * (cp.getX() - P1.getX()) / 3.0;
+ double y1 = P1.getY() + 2.0 * (cp.getY() - P1.getY()) / 3.0;
+ double x2 = cp.getX() + (P2.getX() - cp.getX()) / 3.0;
+ double y2 = cp.getY() + (P2.getY() - cp.getY()) / 3.0;
+
+ return new CubicSegment(P1.getX(), P1.getY(), x1, y1, x2, y2, P2.getX(),
+ P2.getY());
+ }
+
+ /**
+ * Returns the segment's midpoint
+ */
+ Point2D getMidPoint()
+ {
+ return evaluatePoint(0.5);
+ }
+
+ /**
+ * Returns the PathIterator type of a segment
+ */
+ int getType()
+ {
+ return (PathIterator.SEG_QUADTO);
+ }
+
+ /**
+ * Returns the PathIterator coords of a segment
+ */
+ int pathIteratorFormat(double[] coords)
+ {
+ coords[0] = cp.getX();
+ coords[1] = cp.getY();
+ coords[2] = P2.getX();
+ coords[3] = P2.getY();
+ return (PathIterator.SEG_QUADTO);
+ }
+
+ /**
+ * Returns the number of intersections on the positive X axis,
+ * with the origin at (x,y), used for contains()-testing
+ */
+ int rayCrossing(double x, double y)
+ {
+ double x0 = P1.getX() - x;
+ double y0 = P1.getY() - y;
+ double x1 = cp.getX() - x;
+ double y1 = cp.getY() - y;
+ double x2 = P2.getX() - x;
+ double y2 = P2.getY() - y;
+ double[] r = new double[3];
+ int nRoots;
+ int nCrossings = 0;
+
+ /* check if curve may intersect X+ axis. */
+ if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0) && (y0 * y1 <= 0 || y1 * y2 <= 0))
+ {
+ if (y0 == 0.0)
+ y0 -= EPSILON;
+ if (y2 == 0.0)
+ y2 -= EPSILON;
+
+ r[0] = y0;
+ r[1] = 2 * (y1 - y0);
+ r[2] = (y2 - 2 * y1 + y0);
+
+ nRoots = QuadCurve2D.solveQuadratic(r);
+ for (int i = 0; i < nRoots; i++)
+ if (r[i] > 0.0f && r[i] < 1.0f)
+ {
+ double t = r[i];
+ if (t * t * (x2 - 2 * x1 + x0) + 2 * t * (x1 - x0) + x0 > 0.0)
+ nCrossings++;
+ }
+ }
+ return nCrossings;
+ }
+
+ /**
+ * Swap start and end points
+ */
+ void reverseCoords()
+ {
+ Point2D temp = P1;
+ P1 = P2;
+ P2 = temp;
+ }
+
+ /**
+ * Splits intersections into nodes,
+ * This one handles quadratic-quadratic only,
+ * Quadratic-line is passed on to the LineSegment class,
+ * Quadratic-cubic is passed on to the CubicSegment class
+ */
+ int splitIntersections(Segment b)
+ {
+ if (b instanceof LineSegment)
+ return (b.splitIntersections(this));
+
+ if (b instanceof CubicSegment)
+ return (b.splitIntersections(this));
+
+ if (b instanceof QuadSegment)
+ {
+ // Use the cubic-cubic intersection routine for quads as well,
+ // Since a quadratic can be exactly described as a cubic, this
+ // should not be a problem;
+ // The recursion depth will be the same in any case.
+ Intersection[] x = cubicCubicIntersect(getCubicSegment(),
+ ((QuadSegment) b)
+ .getCubicSegment());
+ if (x == null)
+ return 0;
+
+ if (x.length == 1)
+ return createNode(b, (Intersection) x[0]);
+
+ return createNodes(b, x);
+ }
+ return 0;
+ }
+
+ /**
+ * Subdivides the segment at parametric value t, inserting
+ * the new segment into the linked list after this,
+ * such that this becomes [0,t] and this.next becomes [t,1]
+ */
+ void subdivideInsert(double t)
+ {
+ double x0 = P1.getX();
+ double y0 = P1.getY();
+ double x1 = cp.getX();
+ double y1 = cp.getY();
+ double x2 = P2.getX();
+ double y2 = P2.getY();
+
+ double p10x = x0 + t * (x1 - x0);
+ double p10y = y0 + t * (y1 - y0);
+ double p11x = x1 + t * (x2 - x1);
+ double p11y = y1 + t * (y2 - y1);
+ double p20x = p10x + t * (p11x - p10x);
+ double p20y = p10y + t * (p11y - p10y);
+
+ insert(new QuadSegment(p20x, p20y, p11x, p11y, x2, y2));
+ P2 = next.P1;
+ cp.setLocation(p10x, p10y);
+
+ next.node = node;
+ node = null;
+ }
+
+ /**
+ * Transforms the segment
+ */
+ void transform(AffineTransform at)
+ {
+ P1 = at.transform(P1, null);
+ P2 = at.transform(P2, null);
+ cp = at.transform(cp, null);
+ }
+ } // class QuadSegment
+
+ /**
+ * Cubic Bezier curve segment
+ */
+ private class CubicSegment extends Segment
+ {
+ Point2D cp1; // control points
+ Point2D cp2; // control points
+
+ /**
+ * Constructor - takes coordinates of the starting point,
+ * first control point, second control point and end point,
+ * respecively.
+ */
+ public CubicSegment(double x1, double y1, double c1x, double c1y,
+ double c2x, double c2y, double x2, double y2)
+ {
+ super();
+ P1 = new Point2D.Double(x1, y1);
+ P2 = new Point2D.Double(x2, y2);
+ cp1 = new Point2D.Double(c1x, c1y);
+ cp2 = new Point2D.Double(c2x, c2y);
+ }
+
+ /**
+ * Clones this segment
+ */
+ public Object clone()
+ {
+ return new CubicSegment(P1.getX(), P1.getY(), cp1.getX(), cp1.getY(),
+ cp2.getX(), cp2.getY(), P2.getX(), P2.getY());
+ }
+
+ /**
+ * Returns twice the area of a curve, relative the P1-P2 line
+ *
+ * The area formula can be derived by using Green's formula in the
+ * plane on the parametric form of the bezier.
+ */
+ double curveArea()
+ {
+ double x0 = P1.getX();
+ double y0 = P1.getY();
+ double x1 = cp1.getX();
+ double y1 = cp1.getY();
+ double x2 = cp2.getX();
+ double y2 = cp2.getY();
+ double x3 = P2.getX();
+ double y3 = P2.getY();
+
+ double P = y3 - 3 * y2 + 3 * y1 - y0;
+ double Q = 3 * (y2 + y0 - 2 * y1);
+ double R = 3 * (y1 - y0);
+ double S = y0;
+
+ double A = x3 - 3 * x2 + 3 * x1 - x0;
+ double B = 3 * (x2 + x0 - 2 * x1);
+ double C = 3 * (x1 - x0);
+ double D = x0;
+
+ double area = (B * P - A * Q) / 5.0 + (C * P - A * R) / 2.0
+ + (C * Q - B * R) / 3.0;
+
+ return (area);
+ }
+
+ /**
+ * Compare two segments.
+ */
+ boolean equals(Segment b)
+ {
+ if (! (b instanceof CubicSegment))
+ return false;
+
+ return (P1.equals(b.P1) && cp1.equals(((CubicSegment) b).cp1)
+ && cp2.equals(((CubicSegment) b).cp2) && P2.equals(b.P2));
+ }
+
+ /**
+ * Returns a Point2D corresponding to the parametric value t
+ * of the curve
+ */
+ Point2D evaluatePoint(double t)
+ {
+ double x0 = P1.getX();
+ double y0 = P1.getY();
+ double x1 = cp1.getX();
+ double y1 = cp1.getY();
+ double x2 = cp2.getX();
+ double y2 = cp2.getY();
+ double x3 = P2.getX();
+ double y3 = P2.getY();
+
+ return new Point2D.Double(-(t * t * t) * (x0 - 3 * x1 + 3 * x2 - x3)
+ + 3 * t * t * (x0 - 2 * x1 + x2)
+ + 3 * t * (x1 - x0) + x0,
+ -(t * t * t) * (y0 - 3 * y1 + 3 * y2 - y3)
+ + 3 * t * t * (y0 - 2 * y1 + y2)
+ + 3 * t * (y1 - y0) + y0);
+ }
+
+ /**
+ * Returns the bounding box of this segment
+ */
+ Rectangle2D getBounds()
+ {
+ double x0 = P1.getX();
+ double y0 = P1.getY();
+ double x1 = cp1.getX();
+ double y1 = cp1.getY();
+ double x2 = cp2.getX();
+ double y2 = cp2.getY();
+ double x3 = P2.getX();
+ double y3 = P2.getY();
+ double[] r = new double[3];
+
+ double xmax = Math.max(x0, x3);
+ double ymax = Math.max(y0, y3);
+ double xmin = Math.min(x0, x3);
+ double ymin = Math.min(y0, y3);
+
+ r[0] = 3 * (y1 - y0);
+ r[1] = 6.0 * (y2 + y0 - 2 * y1);
+ r[2] = 3.0 * (y3 - 3 * y2 + 3 * y1 - y0);
+
+ int n = QuadCurve2D.solveQuadratic(r);
+ for (int i = 0; i < n; i++)
+ {
+ double t = r[i];
+ if (t > 0 && t < 1.0)
+ {
+ double y = evaluatePoint(t).getY();
+ ymax = Math.max(y, ymax);
+ ymin = Math.min(y, ymin);
+ }
+ }
+
+ r[0] = 3 * (x1 - x0);
+ r[1] = 6.0 * (x2 + x0 - 2 * x1);
+ r[2] = 3.0 * (x3 - 3 * x2 + 3 * x1 - x0);
+ n = QuadCurve2D.solveQuadratic(r);
+ for (int i = 0; i < n; i++)
+ {
+ double t = r[i];
+ if (t > 0 && t < 1.0)
+ {
+ double x = evaluatePoint(t).getX();
+ xmax = Math.max(x, xmax);
+ xmin = Math.min(x, xmin);
+ }
+ }
+ return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin)));
+ }
+
+ /**
+ * Returns a CubicCurve2D object corresponding to this segment.
+ */
+ CubicCurve2D getCubicCurve2D()
+ {
+ return new CubicCurve2D.Double(P1.getX(), P1.getY(), cp1.getX(),
+ cp1.getY(), cp2.getX(), cp2.getY(),
+ P2.getX(), P2.getY());
+ }
+
+ /**
+ * Returns the parametric points of self-intersection if the cubic
+ * is self-intersecting, null otherwise.
+ */
+ double[] getLoop()
+ {
+ double x0 = P1.getX();
+ double y0 = P1.getY();
+ double x1 = cp1.getX();
+ double y1 = cp1.getY();
+ double x2 = cp2.getX();
+ double y2 = cp2.getY();
+ double x3 = P2.getX();
+ double y3 = P2.getY();
+ double[] r = new double[4];
+ double k;
+ double R;
+ double T;
+ double A;
+ double B;
+ double[] results = new double[2];
+
+ R = x3 - 3 * x2 + 3 * x1 - x0;
+ T = y3 - 3 * y2 + 3 * y1 - y0;
+
+ // A qudratic
+ if (R == 0.0 && T == 0.0)
+ return null;
+
+ // true cubic
+ if (R != 0.0 && T != 0.0)
+ {
+ A = 3 * (x2 + x0 - 2 * x1) / R;
+ B = 3 * (x1 - x0) / R;
+
+ double P = 3 * (y2 + y0 - 2 * y1) / T;
+ double Q = 3 * (y1 - y0) / T;
+
+ if (A == P || Q == B)
+ return null;
+
+ k = (Q - B) / (A - P);
+ }
+ else
+ {
+ if (R == 0.0)
+ {
+ // quadratic in x
+ k = -(3 * (x1 - x0)) / (3 * (x2 + x0 - 2 * x1));
+ A = 3 * (y2 + y0 - 2 * y1) / T;
+ B = 3 * (y1 - y0) / T;
+ }
+ else
+ {
+ // quadratic in y
+ k = -(3 * (y1 - y0)) / (3 * (y2 + y0 - 2 * y1));
+ A = 3 * (x2 + x0 - 2 * x1) / R;
+ B = 3 * (x1 - x0) / R;
+ }
+ }
+
+ r[0] = -k * k * k - A * k * k - B * k;
+ r[1] = 3 * k * k + 2 * k * A + 2 * B;
+ r[2] = -3 * k;
+ r[3] = 2;
+
+ int n = CubicCurve2D.solveCubic(r);
+ if (n != 3)
+ return null;
+
+ // sort r
+ double t;
+ for (int i = 0; i < 2; i++)
+ for (int j = i + 1; j < 3; j++)
+ if (r[j] < r[i])
+ {
+ t = r[i];
+ r[i] = r[j];
+ r[j] = t;
+ }
+
+ if (Math.abs(r[0] + r[2] - k) < 1E-13)
+ if (r[0] >= 0.0 && r[0] <= 1.0 && r[2] >= 0.0 && r[2] <= 1.0)
+ if (evaluatePoint(r[0]).distance(evaluatePoint(r[2])) < PE_EPSILON * 10)
+ { // we snap the points anyway
+ results[0] = r[0];
+ results[1] = r[2];
+ return (results);
+ }
+ return null;
+ }
+
+ /**
+ * Returns the segment's midpoint
+ */
+ Point2D getMidPoint()
+ {
+ return evaluatePoint(0.5);
+ }
+
+ /**
+ * Returns the PathIterator type of a segment
+ */
+ int getType()
+ {
+ return (PathIterator.SEG_CUBICTO);
+ }
+
+ /**
+ * Returns the PathIterator coords of a segment
+ */
+ int pathIteratorFormat(double[] coords)
+ {
+ coords[0] = cp1.getX();
+ coords[1] = cp1.getY();
+ coords[2] = cp2.getX();
+ coords[3] = cp2.getY();
+ coords[4] = P2.getX();
+ coords[5] = P2.getY();
+ return (PathIterator.SEG_CUBICTO);
+ }
+
+ /**
+ * Returns the number of intersections on the positive X axis,
+ * with the origin at (x,y), used for contains()-testing
+ */
+ int rayCrossing(double x, double y)
+ {
+ double x0 = P1.getX() - x;
+ double y0 = P1.getY() - y;
+ double x1 = cp1.getX() - x;
+ double y1 = cp1.getY() - y;
+ double x2 = cp2.getX() - x;
+ double y2 = cp2.getY() - y;
+ double x3 = P2.getX() - x;
+ double y3 = P2.getY() - y;
+ double[] r = new double[4];
+ int nRoots;
+ int nCrossings = 0;
+
+ /* check if curve may intersect X+ axis. */
+ if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0 || x3 > 0.0)
+ && (y0 * y1 <= 0 || y1 * y2 <= 0 || y2 * y3 <= 0))
+ {
+ if (y0 == 0.0)
+ y0 -= EPSILON;
+ if (y3 == 0.0)
+ y3 -= EPSILON;
+
+ r[0] = y0;
+ r[1] = 3 * (y1 - y0);
+ r[2] = 3 * (y2 + y0 - 2 * y1);
+ r[3] = y3 - 3 * y2 + 3 * y1 - y0;
+
+ if ((nRoots = CubicCurve2D.solveCubic(r)) > 0)
+ for (int i = 0; i < nRoots; i++)
+ {
+ if (r[i] > 0.0 && r[i] < 1.0)
+ {
+ double t = r[i];
+ if (-(t * t * t) * (x0 - 3 * x1 + 3 * x2 - x3)
+ + 3 * t * t * (x0 - 2 * x1 + x2) + 3 * t * (x1 - x0)
+ + x0 > 0.0)
+ nCrossings++;
+ }
+ }
+ }
+ return nCrossings;
+ }
+
+ /**
+ * Swap start and end points
+ */
+ void reverseCoords()
+ {
+ Point2D p = P1;
+ P1 = P2;
+ P2 = p;
+ p = cp1; // swap control points
+ cp1 = cp2;
+ cp2 = p;
+ }
+
+ /**
+ * Splits intersections into nodes,
+ * This one handles cubic-cubic and cubic-quadratic intersections
+ */
+ int splitIntersections(Segment b)
+ {
+ if (b instanceof LineSegment)
+ return (b.splitIntersections(this));
+
+ Intersection[] x = null;
+
+ if (b instanceof QuadSegment)
+ x = cubicCubicIntersect(this, ((QuadSegment) b).getCubicSegment());
+
+ if (b instanceof CubicSegment)
+ x = cubicCubicIntersect(this, (CubicSegment) b);
+
+ if (x == null)
+ return 0;
+
+ if (x.length == 1)
+ return createNode(b, x[0]);
+
+ return createNodes(b, x);
+ }
+
+ /**
+ * Subdivides the segment at parametric value t, inserting
+ * the new segment into the linked list after this,
+ * such that this becomes [0,t] and this.next becomes [t,1]
+ */
+ void subdivideInsert(double t)
+ {
+ CubicSegment s = (CubicSegment) clone();
+ double p1x = (s.cp1.getX() - s.P1.getX()) * t + s.P1.getX();
+ double p1y = (s.cp1.getY() - s.P1.getY()) * t + s.P1.getY();
+
+ double px = (s.cp2.getX() - s.cp1.getX()) * t + s.cp1.getX();
+ double py = (s.cp2.getY() - s.cp1.getY()) * t + s.cp1.getY();
+
+ s.cp2.setLocation((s.P2.getX() - s.cp2.getX()) * t + s.cp2.getX(),
+ (s.P2.getY() - s.cp2.getY()) * t + s.cp2.getY());
+
+ s.cp1.setLocation((s.cp2.getX() - px) * t + px,
+ (s.cp2.getY() - py) * t + py);
+
+ double p2x = (px - p1x) * t + p1x;
+ double p2y = (py - p1y) * t + p1y;
+
+ double p3x = (s.cp1.getX() - p2x) * t + p2x;
+ double p3y = (s.cp1.getY() - p2y) * t + p2y;
+ s.P1.setLocation(p3x, p3y);
+
+ // insert new curve
+ insert(s);
+
+ // set this curve
+ cp1.setLocation(p1x, p1y);
+ cp2.setLocation(p2x, p2y);
+ P2 = s.P1;
+ next.node = node;
+ node = null;
+ }
+
+ /**
+ * Transforms the segment
+ */
+ void transform(AffineTransform at)
+ {
+ P1 = at.transform(P1, null);
+ P2 = at.transform(P2, null);
+ cp1 = at.transform(cp1, null);
+ cp2 = at.transform(cp2, null);
+ }
+ } // class CubicSegment
} // class Area
diff --git a/libjava/java/awt/geom/CubicCurve2D.java b/libjava/java/awt/geom/CubicCurve2D.java
index 56b90e9..2037306 100644
--- a/libjava/java/awt/geom/CubicCurve2D.java
+++ b/libjava/java/awt/geom/CubicCurve2D.java
@@ -59,6 +59,7 @@ import java.util.NoSuchElementException;
public abstract class CubicCurve2D implements Shape, Cloneable
{
private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0;
+ private static final double EPSILON = 1E-10;
/**
* Constructs a new CubicCurve2D. Typical users will want to
@@ -1089,21 +1090,21 @@ public abstract class CubicCurve2D implements Shape, Cloneable
If this is not done, bad behaviour may result for points on that axis.*/
if (a0 == 0.0 || a3 == 0.0)
{
- double small = getFlatness() * (1E-10);
+ double small = getFlatness() * EPSILON;
if (a0 == 0.0)
- a0 += small;
+ a0 -= small;
if (a3 == 0.0)
- a3 += small;
+ a3 -= small;
}
if (useYaxis)
{
- if (Line2D.linesIntersect(b0, a0, b3, a3, 0.0, 0.0, distance, 0.0))
+ if (Line2D.linesIntersect(b0, a0, b3, a3, EPSILON, 0.0, distance, 0.0))
nCrossings++;
}
else
{
- if (Line2D.linesIntersect(a0, b0, a3, b3, 0.0, 0.0, 0.0, distance))
+ if (Line2D.linesIntersect(a0, b0, a3, b3, 0.0, EPSILON, 0.0, distance))
nCrossings++;
}
diff --git a/libjava/java/awt/geom/Ellipse2D.java b/libjava/java/awt/geom/Ellipse2D.java
index 223a193..bd64adf 100644
--- a/libjava/java/awt/geom/Ellipse2D.java
+++ b/libjava/java/awt/geom/Ellipse2D.java
@@ -1,5 +1,5 @@
/* Ellipse2D.java -- represents an ellipse in 2-D space
- Copyright (C) 2000, 2002 Free Software Foundation
+ Copyright (C) 2000, 2002, 2004 Free Software Foundation
This file is part of GNU Classpath.
@@ -37,58 +37,153 @@ exception statement from your version. */
package java.awt.geom;
+
/**
+ * Ellipse2D is the shape of an ellipse.
+ * <BR>
+ * <img src="doc-files/Ellipse-1.png" width="347" height="221"
+ * alt="A drawing of an ellipse" /><BR>
+ * The ellipse is defined by it's bounding box (shown in red),
+ * and is defined by the implicit curve:<BR>
+ * <blockquote>(<i>x</i>/<i>a</i>)<sup>2</sup> +
+ * (<i>y</i>/<i>b</i>)<sup>2</sup> = 1<BR><BR>
+ *
* @author Tom Tromey <tromey@cygnus.com>
* @author Eric Blake <ebb9@email.byu.edu>
+ *
* @since 1.2
- * @status still needs documentation
*/
public abstract class Ellipse2D extends RectangularShape
{
+ /**
+ * Ellipse2D is defined as abstract.
+ * Implementing classes are Ellipse2D.Float and Ellipse2D.Double.
+ */
protected Ellipse2D()
{
}
+ /**
+ * Determines if a point is contained within the ellipse. <P>
+ * @param x - x coordinate of the point.
+ * @param y - y coordinate of the point.
+ * @return true if the point is within the ellipse, false otherwise.
+ */
public boolean contains(double x, double y)
{
double rx = getWidth() / 2;
double ry = getHeight() / 2;
- double tx = (x - getCenterX()) / rx;
- double ty = (y - getCenterY()) / ry;
- return tx * tx + ty * ty <= 1.0;
+ double tx = (x - (getX() + rx)) / rx;
+ double ty = (y - (getY() + ry)) / ry;
+ return tx * tx + ty * ty < 1.0;
}
+ /**
+ * Determines if a rectangle is completely contained within the
+ * ellipse. <P>
+ * @param x - x coordinate of the upper-left corner of the rectangle
+ * @param y - y coordinate of the upper-left corner of the rectangle
+ * @param w - width of the rectangle
+ * @param h - height of the rectangle
+ * @return true if the rectangle is completely contained, false otherwise.
+ */
public boolean contains(double x, double y, double w, double h)
{
double x2 = x + w;
double y2 = y + h;
- return (contains(x, y) && contains(x, y2)
- && contains(x2, y) && contains(x2, y2));
+ return (contains(x, y) && contains(x, y2) && contains(x2, y)
+ && contains(x2, y2));
}
+ /**
+ * Returns a PathIterator object corresponding to the ellipse.<P>
+ *
+ * Note: An ellipse cannot be represented exactly in PathIterator
+ * segments, the outline is thefore approximated with cubic
+ * Bezier segments.
+ *
+ * @param at an optional transform.
+ * @return A path iterator.
+ */
public PathIterator getPathIterator(AffineTransform at)
{
// An ellipse is just a complete arc.
return new Arc2D.ArcIterator(this, at);
}
+ /**
+ * Determines if a rectangle intersects any part of the ellipse.<P>
+ * @param x - x coordinate of the upper-left corner of the rectangle
+ * @param y - y coordinate of the upper-left corner of the rectangle
+ * @param w - width of the rectangle
+ * @param h - height of the rectangle
+ * @return true if the rectangle intersects the ellipse, false otherwise.
+ */
public boolean intersects(double x, double y, double w, double h)
{
- // fixme
+ Rectangle2D r = new Rectangle2D.Double(x, y, w, h);
+ if (! r.intersects(getX(), getY(), getWidth(), getHeight()))
+ return false;
+
+ if (contains(x, y) || contains(x, y + h) || contains(x + w, y)
+ || contains(x + w, y + h))
+ return true;
+
+ Line2D l1 = new Line2D.Double(getX(), getY() + (getHeight() / 2),
+ getX() + getWidth(),
+ getY() + (getHeight() / 2));
+ Line2D l2 = new Line2D.Double(getX() + (getWidth() / 2), getY(),
+ getX() + (getWidth() / 2),
+ getY() + getHeight());
+
+ if (l1.intersects(r) || l2.intersects(r))
+ return true;
+
return false;
}
+ /**
+ * An {@link Ellipse2D} that stores its coordinates using <code>double</code>
+ * primitives.
+ */
public static class Double extends Ellipse2D
{
+ /**
+ * The height of the ellipse.
+ */
public double height;
+
+ /**
+ * The width of the ellipse.
+ */
public double width;
+
+ /**
+ * The upper-left x coordinate of the bounding-box
+ */
public double x;
+
+ /**
+ * The upper-left y coordinate of the bounding-box
+ */
public double y;
+ /**
+ * Creates a new Ellipse2D with an upper-left coordinate of (0,0)
+ * and a zero size.
+ */
public Double()
{
}
+ /**
+ * Creates a new Ellipse2D within a given rectangle
+ * using double-precision coordinates.<P>
+ * @param x - x coordinate of the upper-left of the bounding rectangle
+ * @param y - y coordinate of the upper-left of the bounding rectangle
+ * @param w - width of the ellipse
+ * @param h - height of the ellipse
+ */
public Double(double x, double y, double w, double h)
{
this.x = x;
@@ -97,36 +192,72 @@ public abstract class Ellipse2D extends RectangularShape
width = w;
}
+ /**
+ * Returns the bounding-box of the ellipse.
+ * @return The bounding box.
+ */
public Rectangle2D getBounds2D()
{
return new Rectangle2D.Double(x, y, width, height);
}
+ /**
+ * Returns the height of the ellipse.
+ * @return The height of the ellipse.
+ */
public double getHeight()
{
return height;
}
+ /**
+ * Returns the width of the ellipse.
+ * @return The width of the ellipse.
+ */
public double getWidth()
{
return width;
}
+ /**
+ * Returns x coordinate of the upper-left corner of
+ * the ellipse's bounding-box.
+ * @return The x coordinate.
+ */
public double getX()
{
return x;
}
+ /**
+ * Returns y coordinate of the upper-left corner of
+ * the ellipse's bounding-box.
+ * @return The y coordinate.
+ */
public double getY()
{
return y;
}
+ /**
+ * Returns <code>true</code> if the ellipse encloses no area, and
+ * <code>false</code> otherwise.
+ *
+ * @return A boolean.
+ */
public boolean isEmpty()
{
return height <= 0 || width <= 0;
}
+ /**
+ * Sets the geometry of the ellipse's bounding box.<P>
+ *
+ * @param x - x coordinate of the upper-left of the bounding rectangle
+ * @param y - y coordinate of the upper-left of the bounding rectangle
+ * @param w - width of the ellipse
+ * @param h - height of the ellipse
+ */
public void setFrame(double x, double y, double w, double h)
{
this.x = x;
@@ -136,17 +267,49 @@ public abstract class Ellipse2D extends RectangularShape
}
} // class Double
+ /**
+ * An {@link Ellipse2D} that stores its coordinates using <code>float</code>
+ * primitives.
+ */
public static class Float extends Ellipse2D
{
+ /**
+ * The height of the ellipse.
+ */
public float height;
+
+ /**
+ * The width of the ellipse.
+ */
public float width;
+
+ /**
+ * The upper-left x coordinate of the bounding-box
+ */
public float x;
+
+ /**
+ * The upper-left y coordinate of the bounding-box
+ */
public float y;
+ /**
+ * Creates a new Ellipse2D with an upper-left coordinate of (0,0)
+ * and a zero size.
+ */
public Float()
{
}
+ /**
+ * Creates a new Ellipse2D within a given rectangle
+ * using floating-point precision.<P>
+ * @param x - x coordinate of the upper-left of the bounding rectangle
+ * @param y - y coordinate of the upper-left of the bounding rectangle
+ * @param w - width of the ellipse
+ * @param h - height of the ellipse
+ *
+ */
public Float(float x, float y, float w, float h)
{
this.x = x;
@@ -155,36 +318,72 @@ public abstract class Ellipse2D extends RectangularShape
this.width = w;
}
+ /**
+ * Returns the bounding-box of the ellipse.
+ * @return The bounding box.
+ */
public Rectangle2D getBounds2D()
{
return new Rectangle2D.Float(x, y, width, height);
}
+ /**
+ * Returns the height of the ellipse.
+ * @return The height of the ellipse.
+ */
public double getHeight()
{
return height;
}
+ /**
+ * Returns the width of the ellipse.
+ * @return The width of the ellipse.
+ */
public double getWidth()
{
return width;
}
+ /**
+ * Returns x coordinate of the upper-left corner of
+ * the ellipse's bounding-box.
+ * @return The x coordinate.
+ */
public double getX()
{
return x;
}
+ /**
+ * Returns y coordinate of the upper-left corner of
+ * the ellipse's bounding-box.
+ * @return The y coordinate.
+ */
public double getY()
{
return y;
}
+ /**
+ * Returns <code>true</code> if the ellipse encloses no area, and
+ * <code>false</code> otherwise.
+ *
+ * @return A boolean.
+ */
public boolean isEmpty()
{
return height <= 0 || width <= 0;
}
+ /**
+ * Sets the geometry of the ellipse's bounding box.<P>
+ *
+ * @param x - x coordinate of the upper-left of the bounding rectangle
+ * @param y - y coordinate of the upper-left of the bounding rectangle
+ * @param w - width of the ellipse
+ * @param h - height of the ellipse
+ */
public void setFrame(float x, float y, float w, float h)
{
this.x = x;
@@ -193,6 +392,16 @@ public abstract class Ellipse2D extends RectangularShape
width = w;
}
+ /**
+ * Sets the geometry of the ellipse's bounding box.
+ *
+ * Note: This leads to a loss of precision.<P>
+ *
+ * @param x - x coordinate of the upper-left of the bounding rectangle
+ * @param y - y coordinate of the upper-left of the bounding rectangle
+ * @param w - width of the ellipse
+ * @param h - height of the ellipse
+ */
public void setFrame(double x, double y, double w, double h)
{
this.x = (float) x;
diff --git a/libjava/java/awt/geom/GeneralPath.java b/libjava/java/awt/geom/GeneralPath.java
index 40182ea..0dc9ede 100644
--- a/libjava/java/awt/geom/GeneralPath.java
+++ b/libjava/java/awt/geom/GeneralPath.java
@@ -1,39 +1,40 @@
/* GeneralPath.java -- represents a shape built from subpaths
Copyright (C) 2002, 2003, 2004 Free Software Foundation
- This file is part of GNU Classpath.
-
- GNU Classpath is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2, or (at your option)
- any later version.
-
- GNU Classpath is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with GNU Classpath; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
- 02111-1307 USA.
-
- Linking this library statically or dynamically with other modules is
- making a combined work based on this library. Thus, the terms and
- conditions of the GNU General Public License cover the whole
- combination.
-
- As a special exception, the copyright holders of this library give you
- permission to link this library with independent modules to produce an
- executable, regardless of the license terms of these independent
- modules, and to copy and distribute the resulting executable under
- terms of your choice, provided that you also meet, for each linked
- independent module, the terms and conditions of the license of that
- module. An independent module is a module which is not derived from
- or based on this library. If you modify this library, you may extend
- this exception to your version of the library, but you are not
- obligated to do so. If you do not wish to do so, delete this
- exception statement from your version. */
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING. If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library. Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module. An independent module is a module which is not derived from
+or based on this library. If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so. If you do not wish to do so, delete this
+exception statement from your version. */
+
package java.awt.geom;
@@ -641,7 +642,7 @@ public final class GeneralPath implements Shape, Cloneable
if (transform != null)
transform.transform( /* src */
coords, /* srcOffset */
- pos, /* dest */ coords, /* destOffset */
+ 0, /* dest */ coords, /* destOffset */
0, /* numPoints */ numCoords);
}
return seg;
@@ -777,7 +778,10 @@ public final class GeneralPath implements Shape, Cloneable
/* Get a value which is hopefully small but not insignificant relative
the path. */
- epsilon = ypoints[0] * 1E-9;
+ epsilon = ypoints[0] * 1E-7;
+
+ if(epsilon == 0)
+ epsilon = 1E-7;
pos = 0;
while (pos < index)
@@ -793,11 +797,11 @@ public final class GeneralPath implements Shape, Cloneable
y1 = firsty;
if (y0 == 0.0)
- y0 += epsilon;
+ y0 -= epsilon;
if (y1 == 0.0)
- y1 += epsilon;
- if (Line2D.linesIntersect(x0, y0, x1, y1, 0.0, 0.0, distance,
- 0.0))
+ y1 -= epsilon;
+ if (Line2D.linesIntersect(x0, y0, x1, y1,
+ epsilon, 0.0, distance, 0.0))
windingNumber += (y1 < y0) ? 1 : negative;
cx = firstx;
@@ -814,10 +818,11 @@ public final class GeneralPath implements Shape, Cloneable
y1 = firsty;
if (y0 == 0.0)
- y0 += epsilon;
+ y0 -= epsilon;
if (y1 == 0.0)
- y1 += epsilon;
- if (Line2D.linesIntersect(x0, y0, x1, y1, 0.0, 0.0, distance, 0.0))
+ y1 -= epsilon;
+ if (Line2D.linesIntersect(x0, y0, x1, y1,
+ epsilon, 0.0, distance, 0.0))
windingNumber += (y1 < y0) ? 1 : negative;
cx = firstx;
@@ -832,10 +837,11 @@ public final class GeneralPath implements Shape, Cloneable
y1 = ypoints[pos++] - (float) y;
if (y0 == 0.0)
- y0 += epsilon;
+ y0 -= epsilon;
if (y1 == 0.0)
- y1 += epsilon;
- if (Line2D.linesIntersect(x0, y0, x1, y1, 0.0, 0.0, distance, 0.0))
+ y1 -= epsilon;
+ if (Line2D.linesIntersect(x0, y0, x1, y1,
+ epsilon, 0.0, distance, 0.0))
windingNumber += (y1 < y0) ? 1 : negative;
cx = xpoints[pos - 1] - (float) x;
@@ -854,9 +860,9 @@ public final class GeneralPath implements Shape, Cloneable
&& (y0 * y1 <= 0 || y1 * y2 <= 0))
{
if (y0 == 0.0)
- y0 += epsilon;
+ y0 -= epsilon;
if (y2 == 0.0)
- y2 += epsilon;
+ y2 -= epsilon;
r[0] = y0;
r[1] = 2 * (y1 - y0);
@@ -897,9 +903,9 @@ public final class GeneralPath implements Shape, Cloneable
&& (y0 * y1 <= 0 || y1 * y2 <= 0 || y2 * y3 <= 0))
{
if (y0 == 0.0)
- y0 += epsilon;
+ y0 -= epsilon;
if (y3 == 0.0)
- y3 += epsilon;
+ y3 -= epsilon;
r[0] = y0;
r[1] = 3 * (y1 - y0);
@@ -942,3 +948,4 @@ public final class GeneralPath implements Shape, Cloneable
return (windingNumber);
}
} // class GeneralPath
+
diff --git a/libjava/java/awt/geom/Line2D.java b/libjava/java/awt/geom/Line2D.java
index 15b2eca..05eedcd 100644
--- a/libjava/java/awt/geom/Line2D.java
+++ b/libjava/java/awt/geom/Line2D.java
@@ -48,6 +48,7 @@ import java.util.NoSuchElementException;
*
* @author Tom Tromey <tromey@cygnus.com>
* @author Eric Blake <ebb9@email.byu.edu>
+ * @author David Gilbert
* @since 1.2
* @status updated to 1.4
*/
@@ -235,11 +236,57 @@ public abstract class Line2D implements Shape, Cloneable
}
/**
- * Test if the line segment (x1,y1)-&gt;(x2,y2) intersects the line segment
+ * Computes twice the (signed) area of the triangle defined by the three
+ * points. This method is used for intersection testing.
+ *
+ * @param x1 the x-coordinate of the first point.
+ * @param y1 the y-coordinate of the first point.
+ * @param x2 the x-coordinate of the second point.
+ * @param y2 the y-coordinate of the second point.
+ * @param x3 the x-coordinate of the third point.
+ * @param y3 the y-coordinate of the third point.
+ *
+ * @return Twice the area.
+ */
+ private static double area2(double x1, double y1,
+ double x2, double y2,
+ double x3, double y3)
+ {
+ return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
+ }
+
+ /**
+ * Returns <code>true</code> if (x3, y3) lies between (x1, y1) and (x2, y2),
+ * and false otherwise, This test assumes that the three points are
+ * collinear, and is used for intersection testing.
+ *
+ * @param x1 the x-coordinate of the first point.
+ * @param y1 the y-coordinate of the first point.
+ * @param x2 the x-coordinate of the second point.
+ * @param y2 the y-coordinate of the second point.
+ * @param x3 the x-coordinate of the third point.
+ * @param y3 the y-coordinate of the third point.
+ *
+ * @return A boolean.
+ */
+ private static boolean between(double x1, double y1,
+ double x2, double y2,
+ double x3, double y3)
+ {
+ if (x1 != x2) {
+ return (x1 <= x3 && x3 <= x2) || (x1 >= x3 && x3 >= x2);
+ }
+ else {
+ return (y1 <= y3 && y3 <= y2) || (y1 >= y3 && y3 >= y2);
+ }
+ }
+
+ /**
+ * Test if the line segment (x1,y1)-&gt;(x2,y2) intersects the line segment
* (x3,y3)-&gt;(x4,y4).
*
* @param x1 the first x coordinate of the first segment
- * @param y1 the first y coordinate of the first segment
+ * @param y1 the first y coordinate of the first segment
* @param x2 the second x coordinate of the first segment
* @param y2 the second y coordinate of the first segment
* @param x3 the first x coordinate of the second segment
@@ -249,16 +296,64 @@ public abstract class Line2D implements Shape, Cloneable
* @return true if the segments intersect
*/
public static boolean linesIntersect(double x1, double y1,
- double x2, double y2,
- double x3, double y3,
- double x4, double y4)
+ double x2, double y2,
+ double x3, double y3,
+ double x4, double y4)
{
- double beta = (((y1 - y3) * (x4 - x3) + (x1 - x3) * (y4 - y3))
- / ((y2 - y1) * (x4 - x3) + (x2 - x1) * (y4 - y3)));
- if (beta < 0.0 || beta > 1.0)
- return false;
- double alpha = (x1 + beta * (x2 - x1) - x3) / (x4 - x3);
- return alpha >= 0.0 && alpha <= 1.0;
+ double a1, a2, a3, a4;
+
+ // deal with special cases
+ if ((a1 = area2(x1, y1, x2, y2, x3, y3)) == 0.0)
+ {
+ // check if p3 is between p1 and p2 OR
+ // p4 is collinear also AND either between p1 and p2 OR at opposite ends
+ if (between(x1, y1, x2, y2, x3, y3))
+ {
+ return true;
+ }
+ else
+ {
+ if (area2(x1, y1, x2, y2, x4, y4) == 0.0)
+ {
+ return between(x3, y3, x4, y4, x1, y1)
+ || between (x3, y3, x4, y4, x2, y2);
+ }
+ else {
+ return false;
+ }
+ }
+ }
+ else if ((a2 = area2(x1, y1, x2, y2, x4, y4)) == 0.0)
+ {
+ // check if p4 is between p1 and p2 (we already know p3 is not
+ // collinear)
+ return between(x1, y1, x2, y2, x4, y4);
+ }
+
+ if ((a3 = area2(x3, y3, x4, y4, x1, y1)) == 0.0) {
+ // check if p1 is between p3 and p4 OR
+ // p2 is collinear also AND either between p1 and p2 OR at opposite ends
+ if (between(x3, y3, x4, y4, x1, y1)) {
+ return true;
+ }
+ else {
+ if (area2(x3, y3, x4, y4, x2, y2) == 0.0) {
+ return between(x1, y1, x2, y2, x3, y3)
+ || between (x1, y1, x2, y2, x4, y4);
+ }
+ else {
+ return false;
+ }
+ }
+ }
+ else if ((a4 = area2(x3, y3, x4, y4, x2, y2)) == 0.0) {
+ // check if p2 is between p3 and p4 (we already know p1 is not
+ // collinear)
+ return between(x3, y3, x4, y4, x2, y2);
+ }
+ else { // test for regular intersection
+ return ((a1 > 0.0) ^ (a2 > 0.0)) && ((a3 > 0.0) ^ (a4 > 0.0));
+ }
}
/**
diff --git a/libjava/java/awt/geom/PathIterator.java b/libjava/java/awt/geom/PathIterator.java
index 1fb0a46..8076b5c 100644
--- a/libjava/java/awt/geom/PathIterator.java
+++ b/libjava/java/awt/geom/PathIterator.java
@@ -46,8 +46,8 @@ package java.awt.geom;
*
* @author Tom Tromey <tromey@cygnus.com>
* @author Eric Blake <ebb9@email.byu.edu>
- * @see Shape
- * @see Stroke
+ * @see java.awt.Shape
+ * @see java.awt.Stroke
* @see FlatteningPathIterator
* @since 1.2
* @status updated to 1.4
diff --git a/libjava/java/awt/geom/Point2D.java b/libjava/java/awt/geom/Point2D.java
index 48b12f6..d27505f 100644
--- a/libjava/java/awt/geom/Point2D.java
+++ b/libjava/java/awt/geom/Point2D.java
@@ -1,5 +1,5 @@
/* Point2D.java -- generic point in 2-D space
- Copyright (C) 1999, 2000, 2002 Free Software Foundation
+ Copyright (C) 1999, 2000, 2002, 2004 Free Software Foundation
This file is part of GNU Classpath.
@@ -35,6 +35,7 @@ this exception to your version of the library, but you are not
obligated to do so. If you do not wish to do so, delete this
exception statement from your version. */
+
package java.awt.geom;
/**
@@ -42,8 +43,8 @@ package java.awt.geom;
* representation is left up to the subclass. Point includes two useful
* nested classes, for float and double storage respectively.
*
- * @author Per Bothner <bothner@cygnus.com>
- * @author Eric Blake <ebb9@email.byu.edu>
+ * @author Per Bothner (bothner@cygnus.com)
+ * @author Eric Blake (ebb9@email.byu.edu)
* @since 1.2
* @status updated to 1.4
*/
@@ -52,7 +53,7 @@ public abstract class Point2D implements Cloneable
/**
* The default constructor.
*
- * @see Point
+ * @see java.awt.Point
* @see Point2D.Float
* @see Point2D.Double
*/
@@ -120,7 +121,7 @@ public abstract class Point2D implements Cloneable
* @param y2 the y coordinate of point 2
* @return the distance from (x1,y1) to (x2,y2)
*/
- static public double distance(double x1, double y1, double x2, double y2)
+ public static double distance(double x1, double y1, double x2, double y2)
{
return Math.sqrt(distanceSq(x1, y1, x2, y2));
}
diff --git a/libjava/java/awt/geom/QuadCurve2D.java b/libjava/java/awt/geom/QuadCurve2D.java
index 0cc9eb4..0376d5a 100644
--- a/libjava/java/awt/geom/QuadCurve2D.java
+++ b/libjava/java/awt/geom/QuadCurve2D.java
@@ -59,6 +59,7 @@ import java.util.NoSuchElementException;
public abstract class QuadCurve2D implements Shape, Cloneable
{
private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0;
+ private static final double EPSILON = 1E-10;
/**
* Constructs a new QuadCurve2D. Typical users will want to
@@ -962,12 +963,12 @@ public abstract class QuadCurve2D implements Shape, Cloneable
If this is not done,bad behaviour may result for points on that axis. */
if (a0 == 0.0 || a2 == 0.0)
{
- double small = getFlatness() * (1E-10);
+ double small = getFlatness() * EPSILON;
if (a0 == 0.0)
- a0 += small;
+ a0 -= small;
if (a2 == 0.0)
- a2 += small;
+ a2 -= small;
}
r[0] = a0;
@@ -990,12 +991,12 @@ public abstract class QuadCurve2D implements Shape, Cloneable
if (useYaxis)
{
- if (Line2D.linesIntersect(b0, a0, b2, a2, 0.0, 0.0, distance, 0.0))
+ if (Line2D.linesIntersect(b0, a0, b2, a2, EPSILON, 0.0, distance, 0.0))
nCrossings++;
}
else
{
- if (Line2D.linesIntersect(a0, b0, a2, b2, 0.0, 0.0, 0.0, distance))
+ if (Line2D.linesIntersect(a0, b0, a2, b2, 0.0, EPSILON, 0.0, distance))
nCrossings++;
}
diff --git a/libjava/java/awt/geom/Rectangle2D.java b/libjava/java/awt/geom/Rectangle2D.java
index 8203ca3..bd1a37c 100644
--- a/libjava/java/awt/geom/Rectangle2D.java
+++ b/libjava/java/awt/geom/Rectangle2D.java
@@ -49,8 +49,8 @@ import java.util.NoSuchElementException;
* in methods like <code>contains</code> or <code>intersects</code> is
* undefined unless the rectangle has positive width and height.
*
- * @author Tom Tromey <tromey@cygnus.com>
- * @author Eric Blake <ebb9@email.byu.edu>
+ * @author Tom Tromey (tromey@cygnus.com)
+ * @author Eric Blake (ebb9@email.byu.edu)
* @since 1.2
* @status updated to 1.4
*/
@@ -71,14 +71,14 @@ public abstract class Rectangle2D extends RectangularShape
public static final int OUT_TOP = 2;
/**
- * The point lies right of the rectangle (p.x > r.maxX).
+ * The point lies right of the rectangle (p.x &gt; r.maxX).
*
* @see #outcode()
*/
public static final int OUT_RIGHT = 4;
/**
- * The point lies below of the rectangle (p.y > r.maxY).
+ * The point lies below of the rectangle (p.y &gt; r.maxY).
*
* @see #outcode()
*/
@@ -335,8 +335,8 @@ public abstract class Rectangle2D extends RectangularShape
* inside the rectangle, a subsequent call to <code>contains</code> may
* return false.
*
- * @param x the X coordinate of the point to add to this rectangle
- * @param y the Y coordinate of the point to add to this rectangle
+ * @param newx the X coordinate of the point to add to this rectangle
+ * @param newy the Y coordinate of the point to add to this rectangle
*/
public void add(double newx, double newy)
{
@@ -368,7 +368,7 @@ public abstract class Rectangle2D extends RectangularShape
*
* @param r the rectangle to add to this rectangle
* @throws NullPointerException if r is null
- * @see #union(Rectangle2D)
+ * @see #union(Rectangle2D, Rectangle2D, Rectangle2D)
*/
public void add(Rectangle2D r)
{
@@ -382,7 +382,7 @@ public abstract class Rectangle2D extends RectangularShape
* safe; modifications to the rectangle do not affect the results of this
* path instance.
*
- * @param transform an optional transform to apply to the iterator
+ * @param at an optional transform to apply to the iterator
* @return a new iterator over the boundary
* @since 1.2
*/
@@ -490,8 +490,8 @@ public abstract class Rectangle2D extends RectangularShape
* path instance. As the rectangle is already flat, the flatness parameter
* is ignored.
*
- * @param transform an optional transform to apply to the iterator
- * @param double the maximum distance for deviation from the real boundary
+ * @param at an optional transform to apply to the iterator
+ * @param flatness the maximum distance for deviation from the real boundary
* @return a new iterator over the boundary
* @since 1.2
*/
@@ -508,7 +508,7 @@ public abstract class Rectangle2D extends RectangularShape
* + 37 * Double.doubleToLongBits(getY())
* + 43 * Double.doubleToLongBits(getWidth())
* + 47 * Double.doubleToLongBits(getHeight());
- * return (int) ((l >> 32) ^ l);
+ * return (int) ((l &gt;&gt; 32) ^ l);
* </pre>
*
* @return the hashcode
@@ -543,7 +543,7 @@ public abstract class Rectangle2D extends RectangularShape
/**
* This class defines a rectangle in <code>double</code> precision.
*
- * @author Eric Blake <ebb9@email.byu.edu>
+ * @author Eric Blake (ebb9@email.byu.edu)
* @since 1.2
* @status updated to 1.4
*/
@@ -747,12 +747,12 @@ public abstract class Rectangle2D extends RectangularShape
return getClass().getName() + "[x=" + x + ",y=" + y + ",w=" + width
+ ",h=" + height + ']';
}
- } // class Double
+ }
/**
* This class defines a rectangle in <code>float</code> precision.
*
- * @author Eric Blake <ebb9@email.byu.edu>
+ * @author Eric Blake (ebb9@email.byu.edu)
* @since 1.2
* @status updated to 1.4
*/
@@ -988,5 +988,5 @@ public abstract class Rectangle2D extends RectangularShape
return getClass().getName() + "[x=" + x + ",y=" + y + ",w=" + width
+ ",h=" + height + ']';
}
- } // class Float
-} // class Rectangle2D
+ }
+}
diff --git a/libjava/java/awt/geom/RectangularShape.java b/libjava/java/awt/geom/RectangularShape.java
index 1801e80..78e393e 100644
--- a/libjava/java/awt/geom/RectangularShape.java
+++ b/libjava/java/awt/geom/RectangularShape.java
@@ -354,7 +354,7 @@ public abstract class RectangularShape implements Shape, Cloneable
* threadsafe if and only if the iterator returned by
* {@link #getPathIterator(AffineTransform)} is as well.
*
- * @param transform an optional transform to apply to the iterator
+ * @param at an optional transform to apply to the iterator
* @param flatness the desired flatness
* @return a new iterator over the boundary
* @throws IllegalArgumentException if flatness is invalid
generated by cgit v1.1 at 2025-04-06 08:53:07 +0000