This is the mail archive of the java-patches@gcc.gnu.org mailing list for the Java project.
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
| Other format: | [Raw text] | |
Hi,
This (massive) patch adds the java.awt.geom fixes and the
java.awt.geom.Area implementation from GNU Classpath to the libgcj gui
branch:
2004-09-03 Sven de Marothy <sven@physto.se>
* java/awt/geom/Area.java: Implemented.
2004-09-03 Mark Wielaard <mark@klomp.org>
* java/awt/geom/Arc2D.java (ArcIterator): Make package private.
2004-09-03 Sven de Marothy <sven@physto.se>
* java/awt/geom/Arc2D.java
Reformatted.
(setArc): Correct documentation to say 'upper left corner'.
(setArcByTangent,contains,intersects): Implemented.
(containsAngle): Corrected to handle negative extents.
(ArcIterator): Set to private.
(ArcIterator): Corrected for CHORD-type arcs, negative extents.
* java/awt/geom/Ellipse2D.java
Documented.
(contains,intersects): Implemented.
* java/awt/geom/Line2D.java
(linesIntersect): Correct handling of special cases.
Committed to the gui branch.
The Meter Charts and Compass Plot of JFreeChart now work!
Cheers,
Mark
Index: java/awt/geom/Arc2D.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/awt/geom/Arc2D.java,v
retrieving revision 1.3.14.1
diff -u -r1.3.14.1 Arc2D.java
--- java/awt/geom/Arc2D.java 24 Jun 2004 05:30:18 -0000 1.3.14.1
+++ java/awt/geom/Arc2D.java 4 Sep 2004 00:46:34 -0000
@@ -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 @@
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 @@
* 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 @@
* 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 @@
* 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 @@
* @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 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 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 @@
* @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 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());
}
/**
@@ -413,8 +453,8 @@
* @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,18 +466,28 @@
public boolean containsAngle(double a)
{
double start = getAngleStart();
- double end = start + getAngleExtent();
+ double extent = getAngleExtent();
+ double end = start + extent;
+
+ 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;
@@ -447,6 +497,10 @@
* 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 PIE-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 +509,50 @@
{
double w = getWidth();
double h = getHeight();
- if (w <= 0 || h <= 0)
+ double extent = getAngleExtent();
+ if (w <= 0 || h <= 0 || extent == 0)
+ return false;
+
+ 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;
- // XXX Finish implementing.
- throw new Error("not implemented");
+
+ double angle = Math.toDegrees(Math.atan2(-dy, dx));
+ if (getArcType() != CHORD)
+ 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 +561,51 @@
*/
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;
+
+ double mx = getX() + getWidth() / 2;
+ double my = getY() + getHeight() / 2;
+ double x1 = mx
+ + getWidth() * Math.cos(Math.toRadians(getAngleStart())) / 2;
+ double y1 = my
+ - getHeight() * Math.sin(Math.toRadians(getAngleStart())) / 2;
+ double x2 = mx
+ + getWidth() * Math.cos(Math.toRadians(getAngleStart()
+ + extent)) / 2;
+ double y2 = my
+ - getHeight() * Math.sin(Math.toRadians(getAngleStart()
+ + extent)) / 2;
+ if (getArcType() != CHORD)
+ {
+ // check intersections against the pie radii
+ if (Line2D.linesIntersect(mx, my, x1, y1, x, y, x + w, y)
+ || Line2D.linesIntersect(mx, my, x1, y1, x + w, y, x + w, y + h)
+ || Line2D.linesIntersect(mx, my, x1, y1, x, y, x, y + h)
+ || Line2D.linesIntersect(mx, my, x1, y1, x, y + h, x + w, y + h))
+ return true;
+
+ if (Line2D.linesIntersect(mx, my, x2, y2, x, y, x + w, y)
+ || Line2D.linesIntersect(mx, my, x2, y2, x + w, y, x + w, y + h)
+ || Line2D.linesIntersect(mx, my, x2, y2, x, y, x, y + h)
+ || Line2D.linesIntersect(mx, my, x2, y2, x, y + h, x + w, y + h))
+ return true;
+ }
+ else if (Line2D.linesIntersect(x1, y1, x2, y2, x, y, x + w, y)
+ || Line2D.linesIntersect(x1, y1, x2, y2, x + w, y, x + w, y + h)
+ || Line2D.linesIntersect(x1, y1, x2, y2, x, y, x, y + h)
+ || Line2D.linesIntersect(x1, y1, x2, y2, x, y + h, x + w, y + h))
+ return true;
+
+ if ((new Rectangle2D.Double(x, y, w, h)).contains(x1, y1))
+ return true;
+
+ return false;
}
/**
@@ -491,12 +619,47 @@
*/
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;
+
+ double mx = getX() + getWidth() / 2;
+ double my = getY() + getHeight() / 2;
+ double x1 = mx
+ + getWidth() * Math.cos(Math.toRadians(getAngleStart())) / 2;
+ double y1 = my
+ - getHeight() * Math.sin(Math.toRadians(getAngleStart())) / 2;
+ double x2 = mx
+ + getWidth() * Math.cos(Math.toRadians(getAngleStart()
+ + extent)) / 2;
+ double y2 = my
+ - getHeight() * Math.sin(Math.toRadians(getAngleStart()
+ + extent)) / 2;
+ if (getArcType() != CHORD)
+ {
+ // check intersections against the pie radii
+ if (Line2D.linesIntersect(mx, my, x1, y1, x, y, x + w, y)
+ || Line2D.linesIntersect(mx, my, x1, y1, x + w, y, x + w, y + h)
+ || Line2D.linesIntersect(mx, my, x1, y1, x, y, x, y + h)
+ || Line2D.linesIntersect(mx, my, x1, y1, x, y + h, x + w, y + h))
+ return false;
+
+ if (Line2D.linesIntersect(mx, my, x2, y2, x, y, x + w, y)
+ || Line2D.linesIntersect(mx, my, x2, y2, x + w, y, x + w, y + h)
+ || Line2D.linesIntersect(mx, my, x2, y2, x, y, x, y + h)
+ || Line2D.linesIntersect(mx, my, x2, y2, x, y + h, x + w, y + h))
+ return false;
+ }
+ else if (Line2D.linesIntersect(x1, y1, x2, y2, x, y, x + w, y)
+ || Line2D.linesIntersect(x1, y1, x2, y2, x + w, y, x + w, y + h)
+ || Line2D.linesIntersect(x1, y1, x2, y2, x, y, x, y + h)
+ || Line2D.linesIntersect(x1, y1, x2, y2, x, y + h, x + w, y + h))
return false;
- // XXX Finish implementing.
- throw new Error("not implemented");
+ return true;
}
/**
@@ -567,29 +730,37 @@
* @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 +769,7 @@
* @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 +777,7 @@
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 +821,9 @@
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 +837,38 @@
*/
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 +878,14 @@
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 +894,29 @@
// 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 +979,8 @@
* @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 +990,7 @@
this.start = start;
this.extent = extent;
}
-
+
/**
* Create a new arc with the given dimensions.
*
@@ -935,8 +1094,8 @@
* @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;
@@ -1039,8 +1198,8 @@
* @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 +1209,7 @@
this.start = start;
this.extent = extent;
}
-
+
/**
* Create a new arc with the given dimensions.
*
@@ -1069,7 +1228,7 @@
width = (float) r.getWidth();
height = (float) r.getHeight();
this.start = start;
- this.extent = extent;
+ this.extent = (float) extent;
}
/**
@@ -1154,8 +1313,8 @@
* @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;
Index: java/awt/geom/Area.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/awt/geom/Area.java,v
retrieving revision 1.1
diff -u -r1.1 Area.java
--- java/awt/geom/Area.java 9 Aug 2002 04:26:15 -0000 1.1
+++ java/awt/geom/Area.java 4 Sep 2004 00:46:34 -0000
@@ -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,636 @@
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 final double EPSILON = 1E-11;
+
+ /**
+ * recursive subdivision epsilon - (see getRecursionDepth)
+ */
+ private final double RS_EPSILON = 1E-13;
+
+ /**
+ * Snap distance - points within this distance are considered equal
+ */
+ private 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.
+ */
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.
+ */
+ 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.
+ */
+ 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.
+ */
+ 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 (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.
+ * @see #getBounds2D()
+ */
public Rectangle getBounds()
{
return getBounds2D().getBounds();
@@ -118,66 +680,2576 @@
{
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.
+ *
+ * @return true if the areas are equal. False otherwise.
+ */
+ public boolean equals(Area area)
{
- // XXX Implement.
- throw new Error("not implemented");
+ 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
+ */
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
+ * @return the transformed area
+ */
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.
+ *
+ * @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.
+ *
+ * @return true if the point is contained, false otherwise.
+ */
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.
+ * @return true 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.
+ * @return true if the rectangle is considered contained
+ */
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.
+ * @return true if the rectangle intersects the area, false 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, y))
+ 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.
+ * @return true if the rectangle intersects the area, false otherwise.
+ */
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.
+ */
public PathIterator getPathIterator(AffineTransform at)
{
- // XXX Implement.
- throw new Error("not implemented");
+ return (new AreaIterator(at));
}
+
+ //---------------------------------------------------------------------
+ // Non-public methods and classes
+
+ /**
+ * Returns a flattened PathIterator object defining the contour of this
+ * Area, transformed by at and with a defined flatness.
+ */
public PathIterator getPathIterator(AffineTransform at, double flatness)
{
return new FlatteningPathIterator(getPathIterator(at), flatness);
}
+
+ /**
+ * 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, 0.0, 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
Index: java/awt/geom/Ellipse2D.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/awt/geom/Ellipse2D.java,v
retrieving revision 1.4
diff -u -r1.4 Ellipse2D.java
--- java/awt/geom/Ellipse2D.java 9 Aug 2002 04:26:15 -0000 1.4
+++ java/awt/geom/Ellipse2D.java 4 Sep 2004 00:46:34 -0000
@@ -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,147 @@
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.
+ */
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;
}
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-right 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-right of the bounding rectangle
+ * @param y - y coordinate of the upper-right 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 +186,64 @@
width = w;
}
+ /**
+ * Returns the bounding-box of the ellipse.
+ */
public Rectangle2D getBounds2D()
{
return new Rectangle2D.Double(x, y, width, height);
}
+ /**
+ * Returns the height of the ellipse.
+ */
public double getHeight()
{
return height;
}
+ /**
+ * Returns the width of the ellipse.
+ */
public double getWidth()
{
return width;
}
+ /**
+ * Returns x coordinate of the upper-left corner of
+ * the ellipse's bounding-box.
+ */
public double getX()
{
return x;
}
+ /**
+ * Returns y coordinate of the upper-left corner of
+ * the ellipse's bounding-box.
+ */
public double getY()
{
return y;
}
+ /**
+ * Returns true if the ellipse encloses any area.
+ */
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-right of the bounding rectangle
+ * @param y - y coordinate of the upper-right 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;
@@ -138,15 +255,43 @@
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-right 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-right of the bounding rectangle
+ * @param y - y coordinate of the upper-right 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 +300,64 @@
this.width = w;
}
+ /**
+ * Returns the bounding-box of the ellipse.
+ */
public Rectangle2D getBounds2D()
{
return new Rectangle2D.Float(x, y, width, height);
}
+ /**
+ * Returns the height of the ellipse.
+ */
public double getHeight()
{
return height;
}
+ /**
+ * Returns the width of the ellipse.
+ */
public double getWidth()
{
return width;
}
+ /**
+ * Returns x coordinate of the upper-left corner of
+ * the ellipse's bounding-box.
+ */
public double getX()
{
return x;
}
+ /**
+ * Returns y coordinate of the upper-left corner of
+ * the ellipse's bounding-box.
+ */
public double getY()
{
return y;
}
+ /**
+ * Returns true if the ellipse encloses any area.
+ */
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-right of the bounding rectangle
+ * @param y - y coordinate of the upper-right 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 +366,16 @@
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-right of the bounding rectangle
+ * @param y - y coordinate of the upper-right 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;
Index: java/awt/geom/Line2D.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/awt/geom/Line2D.java,v
retrieving revision 1.6
diff -u -r1.6 Line2D.java
--- java/awt/geom/Line2D.java 18 Jul 2003 19:20:33 -0000 1.6
+++ java/awt/geom/Line2D.java 4 Sep 2004 00:46:34 -0000
@@ -48,6 +48,7 @@
*
* @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 @@
}
/**
- * Test if the line segment (x1,y1)->(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)->(x2,y2) intersects the line segment
* (x3,y3)->(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 @@
* @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 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 x2, double y2,
+ double x3, double y3,
+ double x4, double y4)
+ {
+ 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));
+ }
}
/**
Attachment:
signature.asc
Description: This is a digitally signed message part
| Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
|---|---|---|
| Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |