QuadCurve2Dpublic abstract class QuadCurve2D extends Object implements Shape, CloneableThe QuadCurve2D class defines a quadratic parametric curve
segment in {@code (x,y)} coordinate space.
This class is only the abstract superclass for all objects that
store a 2D quadratic curve segment.
The actual storage representation of the coordinates is left to
the subclass. |
| Fields Summary |
|---|
| private static final int | BELOW | | private static final int | LOWEDGE | | private static final int | INSIDE | | private static final int | HIGHEDGE | | private static final int | ABOVE |
| Constructors Summary |
|---|
protected QuadCurve2D()This is an abstract class that cannot be instantiated directly.
Type-specific implementation subclasses are available for
instantiation and provide a number of formats for storing
the information necessary to satisfy the various accessor
methods below.
|
| Methods Summary |
|---|
| public java.lang.Object | clone()Creates a new object of the same class and with the same contents
as this object.
try {
return super.clone();
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
| | public boolean | contains(double x, double y){@inheritDoc}
double x1 = getX1();
double y1 = getY1();
double xc = getCtrlX();
double yc = getCtrlY();
double x2 = getX2();
double y2 = getY2();
/*
* We have a convex shape bounded by quad curve Pc(t)
* and ine Pl(t).
*
* P1 = (x1, y1) - start point of curve
* P2 = (x2, y2) - end point of curve
* Pc = (xc, yc) - control point
*
* Pq(t) = P1*(1 - t)^2 + 2*Pc*t*(1 - t) + P2*t^2 =
* = (P1 - 2*Pc + P2)*t^2 + 2*(Pc - P1)*t + P1
* Pl(t) = P1*(1 - t) + P2*t
* t = [0:1]
*
* P = (x, y) - point of interest
*
* Let's look at second derivative of quad curve equation:
*
* Pq''(t) = 2 * (P1 - 2 * Pc + P2) = Pq''
* It's constant vector.
*
* Let's draw a line through P to be parallel to this
* vector and find the intersection of the quad curve
* and the line.
*
* Pq(t) is point of intersection if system of equations
* below has the solution.
*
* L(s) = P + Pq''*s == Pq(t)
* Pq''*s + (P - Pq(t)) == 0
*
* | xq''*s + (x - xq(t)) == 0
* | yq''*s + (y - yq(t)) == 0
*
* This system has the solution if rank of its matrix equals to 1.
* That is, determinant of the matrix should be zero.
*
* (y - yq(t))*xq'' == (x - xq(t))*yq''
*
* Let's solve this equation with 't' variable.
* Also let kx = x1 - 2*xc + x2
* ky = y1 - 2*yc + y2
*
* t0q = (1/2)*((x - x1)*ky - (y - y1)*kx) /
* ((xc - x1)*ky - (yc - y1)*kx)
*
* Let's do the same for our line Pl(t):
*
* t0l = ((x - x1)*ky - (y - y1)*kx) /
* ((x2 - x1)*ky - (y2 - y1)*kx)
*
* It's easy to check that t0q == t0l. This fact means
* we can compute t0 only one time.
*
* In case t0 < 0 or t0 > 1, we have an intersections outside
* of shape bounds. So, P is definitely out of shape.
*
* In case t0 is inside [0:1], we should calculate Pq(t0)
* and Pl(t0). We have three points for now, and all of them
* lie on one line. So, we just need to detect, is our point
* of interest between points of intersections or not.
*
* If the denominator in the t0q and t0l equations is
* zero, then the points must be collinear and so the
* curve is degenerate and encloses no area. Thus the
* result is false.
*/
double kx = x1 - 2 * xc + x2;
double ky = y1 - 2 * yc + y2;
double dx = x - x1;
double dy = y - y1;
double dxl = x2 - x1;
double dyl = y2 - y1;
double t0 = (dx * ky - dy * kx) / (dxl * ky - dyl * kx);
if (t0 < 0 || t0 > 1 || t0 != t0) {
return false;
}
double xb = kx * t0 * t0 + 2 * (xc - x1) * t0 + x1;
double yb = ky * t0 * t0 + 2 * (yc - y1) * t0 + y1;
double xl = dxl * t0 + x1;
double yl = dyl * t0 + y1;
return (x >= xb && x < xl) ||
(x >= xl && x < xb) ||
(y >= yb && y < yl) ||
(y >= yl && y < yb);
| | public boolean | contains(java.awt.geom.Point2D p){@inheritDoc}
return contains(p.getX(), p.getY());
| | public boolean | contains(double x, double y, double w, double h){@inheritDoc}
if (w <= 0 || h <= 0) {
return false;
}
// Assertion: Quadratic curves closed by connecting their
// endpoints are always convex.
return (contains(x, y) &&
contains(x + w, y) &&
contains(x + w, y + h) &&
contains(x, y + h));
| | public boolean | contains(java.awt.geom.Rectangle2D r){@inheritDoc}
return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
| | private static int | evalQuadratic(double[] vals, int num, boolean include0, boolean include1, double[] inflect, double c1, double ctrl, double c2)Evaluate the t values in the first num slots of the vals[] array
and place the evaluated values back into the same array. Only
evaluate t values that are within the range <0, 1>, including
the 0 and 1 ends of the range iff the include0 or include1
booleans are true. If an "inflection" equation is handed in,
then any points which represent a point of inflection for that
quadratic equation are also ignored.
int j = 0;
for (int i = 0; i < num; i++) {
double t = vals[i];
if ((include0 ? t >= 0 : t > 0) &&
(include1 ? t <= 1 : t < 1) &&
(inflect == null ||
inflect[1] + 2*inflect[2]*t != 0))
{
double u = 1 - t;
vals[j++] = c1*u*u + 2*ctrl*t*u + c2*t*t;
}
}
return j;
| | private static void | fillEqn(double[] eqn, double val, double c1, double cp, double c2)Fill an array with the coefficients of the parametric equation
in t, ready for solving against val with solveQuadratic.
We currently have:
val = Py(t) = C1*(1-t)^2 + 2*CP*t*(1-t) + C2*t^2
= C1 - 2*C1*t + C1*t^2 + 2*CP*t - 2*CP*t^2 + C2*t^2
= C1 + (2*CP - 2*C1)*t + (C1 - 2*CP + C2)*t^2
0 = (C1 - val) + (2*CP - 2*C1)*t + (C1 - 2*CP + C2)*t^2
0 = C + Bt + At^2
C = C1 - val
B = 2*CP - 2*C1
A = C1 - 2*CP + C2
eqn[0] = c1 - val;
eqn[1] = cp + cp - c1 - c1;
eqn[2] = c1 - cp - cp + c2;
return;
| | public java.awt.Rectangle | getBounds(){@inheritDoc}
return getBounds2D().getBounds();
| | public abstract java.awt.geom.Point2D | getCtrlPt()Returns the control point.
| | public abstract double | getCtrlX()Returns the X coordinate of the control point in
double precision.
| | public abstract double | getCtrlY()Returns the Y coordinate of the control point in
double precision.
| | public static double | getFlatness(double x1, double y1, double ctrlx, double ctrly, double x2, double y2)Returns the flatness, or maximum distance of a
control point from the line connecting the end points, of the
quadratic curve specified by the indicated control points.
return Line2D.ptSegDist(x1, y1, x2, y2, ctrlx, ctrly);
| | public static double | getFlatness(double[] coords, int offset)Returns the flatness, or maximum distance of a
control point from the line connecting the end points, of the
quadratic curve specified by the control points stored in the
indicated array at the indicated index.
return Line2D.ptSegDist(coords[offset + 0], coords[offset + 1],
coords[offset + 4], coords[offset + 5],
coords[offset + 2], coords[offset + 3]);
| | public double | getFlatness()Returns the flatness, or maximum distance of a
control point from the line connecting the end points, of this
QuadCurve2D.
return Line2D.ptSegDist(getX1(), getY1(),
getX2(), getY2(),
getCtrlX(), getCtrlY());
| | public static double | getFlatnessSq(double x1, double y1, double ctrlx, double ctrly, double x2, double y2)Returns the square of the flatness, or maximum distance of a
control point from the line connecting the end points, of the
quadratic curve specified by the indicated control points.
return Line2D.ptSegDistSq(x1, y1, x2, y2, ctrlx, ctrly);
| | public static double | getFlatnessSq(double[] coords, int offset)Returns the square of the flatness, or maximum distance of a
control point from the line connecting the end points, of the
quadratic curve specified by the control points stored in the
indicated array at the indicated index.
return Line2D.ptSegDistSq(coords[offset + 0], coords[offset + 1],
coords[offset + 4], coords[offset + 5],
coords[offset + 2], coords[offset + 3]);
| | public double | getFlatnessSq()Returns the square of the flatness, or maximum distance of a
control point from the line connecting the end points, of this
QuadCurve2D.
return Line2D.ptSegDistSq(getX1(), getY1(),
getX2(), getY2(),
getCtrlX(), getCtrlY());
| | public abstract java.awt.geom.Point2D | getP1()Returns the start point.
| | public abstract java.awt.geom.Point2D | getP2()Returns the end point.
| | public java.awt.geom.PathIterator | getPathIterator(java.awt.geom.AffineTransform at)Returns an iteration object that defines the boundary of the
shape of this QuadCurve2D.
The iterator for this class is not multi-threaded safe,
which means that this QuadCurve2D class does not
guarantee that modifications to the geometry of this
QuadCurve2D object do not affect any iterations of
that geometry that are already in process.
return new QuadIterator(this, at);
| | public java.awt.geom.PathIterator | getPathIterator(java.awt.geom.AffineTransform at, double flatness)Returns an iteration object that defines the boundary of the
flattened shape of this QuadCurve2D.
The iterator for this class is not multi-threaded safe,
which means that this QuadCurve2D class does not
guarantee that modifications to the geometry of this
QuadCurve2D object do not affect any iterations of
that geometry that are already in process.
return new FlatteningPathIterator(getPathIterator(at), flatness);
| | private static int | getTag(double coord, double low, double high)Determine where coord lies with respect to the range from
low to high. It is assumed that low <= high. The return
value is one of the 5 values BELOW, LOWEDGE, INSIDE, HIGHEDGE,
or ABOVE.
if (coord <= low) {
return (coord < low ? BELOW : LOWEDGE);
}
if (coord >= high) {
return (coord > high ? ABOVE : HIGHEDGE);
}
return INSIDE;
| | public abstract double | getX1()Returns the X coordinate of the start point in
double in precision.
| | public abstract double | getX2()Returns the X coordinate of the end point in
double precision.
| | public abstract double | getY1()Returns the Y coordinate of the start point in
double precision.
| | public abstract double | getY2()Returns the Y coordinate of the end point in
double precision.
| | public boolean | intersects(double x, double y, double w, double h){@inheritDoc}
// Trivially reject non-existant rectangles
if (w <= 0 || h <= 0) {
return false;
}
// Trivially accept if either endpoint is inside the rectangle
// (not on its border since it may end there and not go inside)
// Record where they lie with respect to the rectangle.
// -1 => left, 0 => inside, 1 => right
double x1 = getX1();
double y1 = getY1();
int x1tag = getTag(x1, x, x+w);
int y1tag = getTag(y1, y, y+h);
if (x1tag == INSIDE && y1tag == INSIDE) {
return true;
}
double x2 = getX2();
double y2 = getY2();
int x2tag = getTag(x2, x, x+w);
int y2tag = getTag(y2, y, y+h);
if (x2tag == INSIDE && y2tag == INSIDE) {
return true;
}
double ctrlx = getCtrlX();
double ctrly = getCtrlY();
int ctrlxtag = getTag(ctrlx, x, x+w);
int ctrlytag = getTag(ctrly, y, y+h);
// Trivially reject if all points are entirely to one side of
// the rectangle.
if (x1tag < INSIDE && x2tag < INSIDE && ctrlxtag < INSIDE) {
return false; // All points left
}
if (y1tag < INSIDE && y2tag < INSIDE && ctrlytag < INSIDE) {
return false; // All points above
}
if (x1tag > INSIDE && x2tag > INSIDE && ctrlxtag > INSIDE) {
return false; // All points right
}
if (y1tag > INSIDE && y2tag > INSIDE && ctrlytag > INSIDE) {
return false; // All points below
}
// Test for endpoints on the edge where either the segment
// or the curve is headed "inwards" from them
// Note: These tests are a superset of the fast endpoint tests
// above and thus repeat those tests, but take more time
// and cover more cases
if (inwards(x1tag, x2tag, ctrlxtag) &&
inwards(y1tag, y2tag, ctrlytag))
{
// First endpoint on border with either edge moving inside
return true;
}
if (inwards(x2tag, x1tag, ctrlxtag) &&
inwards(y2tag, y1tag, ctrlytag))
{
// Second endpoint on border with either edge moving inside
return true;
}
// Trivially accept if endpoints span directly across the rectangle
boolean xoverlap = (x1tag * x2tag <= 0);
boolean yoverlap = (y1tag * y2tag <= 0);
if (x1tag == INSIDE && x2tag == INSIDE && yoverlap) {
return true;
}
if (y1tag == INSIDE && y2tag == INSIDE && xoverlap) {
return true;
}
// We now know that both endpoints are outside the rectangle
// but the 3 points are not all on one side of the rectangle.
// Therefore the curve cannot be contained inside the rectangle,
// but the rectangle might be contained inside the curve, or
// the curve might intersect the boundary of the rectangle.
double[] eqn = new double[3];
double[] res = new double[3];
if (!yoverlap) {
// Both Y coordinates for the closing segment are above or
// below the rectangle which means that we can only intersect
// if the curve crosses the top (or bottom) of the rectangle
// in more than one place and if those crossing locations
// span the horizontal range of the rectangle.
fillEqn(eqn, (y1tag < INSIDE ? y : y+h), y1, ctrly, y2);
return (solveQuadratic(eqn, res) == 2 &&
evalQuadratic(res, 2, true, true, null,
x1, ctrlx, x2) == 2 &&
getTag(res[0], x, x+w) * getTag(res[1], x, x+w) <= 0);
}
// Y ranges overlap. Now we examine the X ranges
if (!xoverlap) {
// Both X coordinates for the closing segment are left of
// or right of the rectangle which means that we can only
// intersect if the curve crosses the left (or right) edge
// of the rectangle in more than one place and if those
// crossing locations span the vertical range of the rectangle.
fillEqn(eqn, (x1tag < INSIDE ? x : x+w), x1, ctrlx, x2);
return (solveQuadratic(eqn, res) == 2 &&
evalQuadratic(res, 2, true, true, null,
y1, ctrly, y2) == 2 &&
getTag(res[0], y, y+h) * getTag(res[1], y, y+h) <= 0);
}
// The X and Y ranges of the endpoints overlap the X and Y
// ranges of the rectangle, now find out how the endpoint
// line segment intersects the Y range of the rectangle
double dx = x2 - x1;
double dy = y2 - y1;
double k = y2 * x1 - x2 * y1;
int c1tag, c2tag;
if (y1tag == INSIDE) {
c1tag = x1tag;
} else {
c1tag = getTag((k + dx * (y1tag < INSIDE ? y : y+h)) / dy, x, x+w);
}
if (y2tag == INSIDE) {
c2tag = x2tag;
} else {
c2tag = getTag((k + dx * (y2tag < INSIDE ? y : y+h)) / dy, x, x+w);
}
// If the part of the line segment that intersects the Y range
// of the rectangle crosses it horizontally - trivially accept
if (c1tag * c2tag <= 0) {
return true;
}
// Now we know that both the X and Y ranges intersect and that
// the endpoint line segment does not directly cross the rectangle.
//
// We can almost treat this case like one of the cases above
// where both endpoints are to one side, except that we will
// only get one intersection of the curve with the vertical
// side of the rectangle. This is because the endpoint segment
// accounts for the other intersection.
//
// (Remember there is overlap in both the X and Y ranges which
// means that the segment must cross at least one vertical edge
// of the rectangle - in particular, the "near vertical side" -
// leaving only one intersection for the curve.)
//
// Now we calculate the y tags of the two intersections on the
// "near vertical side" of the rectangle. We will have one with
// the endpoint segment, and one with the curve. If those two
// vertical intersections overlap the Y range of the rectangle,
// we have an intersection. Otherwise, we don't.
// c1tag = vertical intersection class of the endpoint segment
//
// Choose the y tag of the endpoint that was not on the same
// side of the rectangle as the subsegment calculated above.
// Note that we can "steal" the existing Y tag of that endpoint
// since it will be provably the same as the vertical intersection.
c1tag = ((c1tag * x1tag <= 0) ? y1tag : y2tag);
// c2tag = vertical intersection class of the curve
//
// We have to calculate this one the straightforward way.
// Note that the c2tag can still tell us which vertical edge
// to test against.
fillEqn(eqn, (c2tag < INSIDE ? x : x+w), x1, ctrlx, x2);
int num = solveQuadratic(eqn, res);
// Note: We should be able to assert(num == 2); since the
// X range "crosses" (not touches) the vertical boundary,
// but we pass num to evalQuadratic for completeness.
evalQuadratic(res, num, true, true, null, y1, ctrly, y2);
// Note: We can assert(num evals == 1); since one of the
// 2 crossings will be out of the [0,1] range.
c2tag = getTag(res[0], y, y+h);
// Finally, we have an intersection if the two crossings
// overlap the Y range of the rectangle.
return (c1tag * c2tag <= 0);
| | public boolean | intersects(java.awt.geom.Rectangle2D r){@inheritDoc}
return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
| | private static boolean | inwards(int pttag, int opt1tag, int opt2tag)Determine if the pttag represents a coordinate that is already
in its test range, or is on the border with either of the two
opttags representing another coordinate that is "towards the
inside" of that test range. In other words, are either of the
two "opt" points "drawing the pt inward"?
switch (pttag) {
case BELOW:
case ABOVE:
default:
return false;
case LOWEDGE:
return (opt1tag >= INSIDE || opt2tag >= INSIDE);
case INSIDE:
return true;
case HIGHEDGE:
return (opt1tag <= INSIDE || opt2tag <= INSIDE);
}
| | public abstract void | setCurve(double x1, double y1, double ctrlx, double ctrly, double x2, double y2)Sets the location of the end points and control point of this curve
to the specified double coordinates.
| | public void | setCurve(double[] coords, int offset)Sets the location of the end points and control points of this
QuadCurve2D to the double coordinates at
the specified offset in the specified array.
setCurve(coords[offset + 0], coords[offset + 1],
coords[offset + 2], coords[offset + 3],
coords[offset + 4], coords[offset + 5]);
| | public void | setCurve(java.awt.geom.Point2D p1, java.awt.geom.Point2D cp, java.awt.geom.Point2D p2)Sets the location of the end points and control point of this
QuadCurve2D to the specified Point2D
coordinates.
setCurve(p1.getX(), p1.getY(),
cp.getX(), cp.getY(),
p2.getX(), p2.getY());
| | public void | setCurve(java.awt.geom.Point2D[] pts, int offset)Sets the location of the end points and control points of this
QuadCurve2D to the coordinates of the
Point2D objects at the specified offset in
the specified array.
setCurve(pts[offset + 0].getX(), pts[offset + 0].getY(),
pts[offset + 1].getX(), pts[offset + 1].getY(),
pts[offset + 2].getX(), pts[offset + 2].getY());
| | public void | setCurve(java.awt.geom.QuadCurve2D c)Sets the location of the end points and control point of this
QuadCurve2D to the same as those in the specified
QuadCurve2D.
setCurve(c.getX1(), c.getY1(),
c.getCtrlX(), c.getCtrlY(),
c.getX2(), c.getY2());
| | public static int | solveQuadratic(double[] eqn)Solves the quadratic whose coefficients are in the eqn
array and places the non-complex roots back into the same array,
returning the number of roots. The quadratic solved is represented
by the equation:
eqn = {C, B, A};
ax^2 + bx + c = 0
A return value of -1 is used to distinguish a constant
equation, which might be always 0 or never 0, from an equation that
has no zeroes.
return solveQuadratic(eqn, eqn);
| | public static int | solveQuadratic(double[] eqn, double[] res)Solves the quadratic whose coefficients are in the eqn
array and places the non-complex roots into the res
array, returning the number of roots.
The quadratic solved is represented by the equation:
eqn = {C, B, A};
ax^2 + bx + c = 0
A return value of -1 is used to distinguish a constant
equation, which might be always 0 or never 0, from an equation that
has no zeroes.
double a = eqn[2];
double b = eqn[1];
double c = eqn[0];
int roots = 0;
if (a == 0.0) {
// The quadratic parabola has degenerated to a line.
if (b == 0.0) {
// The line has degenerated to a constant.
return -1;
}
res[roots++] = -c / b;
} else {
// From Numerical Recipes, 5.6, Quadratic and Cubic Equations
double d = b * b - 4.0 * a * c;
if (d < 0.0) {
// If d < 0.0, then there are no roots
return 0;
}
d = Math.sqrt(d);
// For accuracy, calculate one root using:
// (-b +/- d) / 2a
// and the other using:
// 2c / (-b +/- d)
// Choose the sign of the +/- so that b+d gets larger in magnitude
if (b < 0.0) {
d = -d;
}
double q = (b + d) / -2.0;
// We already tested a for being 0 above
res[roots++] = q / a;
if (q != 0.0) {
res[roots++] = c / q;
}
}
return roots;
| | public void | subdivide(java.awt.geom.QuadCurve2D left, java.awt.geom.QuadCurve2D right)Subdivides this QuadCurve2D and stores the resulting
two subdivided curves into the left and
right curve parameters.
Either or both of the left and right
objects can be the same as this QuadCurve2D or
null.
subdivide(this, left, right);
| | public static void | subdivide(java.awt.geom.QuadCurve2D src, java.awt.geom.QuadCurve2D left, java.awt.geom.QuadCurve2D right)Subdivides the quadratic curve specified by the src
parameter and stores the resulting two subdivided curves into the
left and right curve parameters.
Either or both of the left and right
objects can be the same as the src object or
null.
double x1 = src.getX1();
double y1 = src.getY1();
double ctrlx = src.getCtrlX();
double ctrly = src.getCtrlY();
double x2 = src.getX2();
double y2 = src.getY2();
double ctrlx1 = (x1 + ctrlx) / 2.0;
double ctrly1 = (y1 + ctrly) / 2.0;
double ctrlx2 = (x2 + ctrlx) / 2.0;
double ctrly2 = (y2 + ctrly) / 2.0;
ctrlx = (ctrlx1 + ctrlx2) / 2.0;
ctrly = (ctrly1 + ctrly2) / 2.0;
if (left != null) {
left.setCurve(x1, y1, ctrlx1, ctrly1, ctrlx, ctrly);
}
if (right != null) {
right.setCurve(ctrlx, ctrly, ctrlx2, ctrly2, x2, y2);
}
| | public static void | subdivide(double[] src, int srcoff, double[] left, int leftoff, double[] right, int rightoff)Subdivides the quadratic curve specified by the coordinates
stored in the src array at indices
srcoff through srcoff + 5
and stores the resulting two subdivided curves into the two
result arrays at the corresponding indices.
Either or both of the left and right
arrays can be null or a reference to the same array
and offset as the src array.
Note that the last point in the first subdivided curve is the
same as the first point in the second subdivided curve. Thus,
it is possible to pass the same array for left and
right and to use offsets such that
rightoff equals leftoff + 4 in order
to avoid allocating extra storage for this common point.
double x1 = src[srcoff + 0];
double y1 = src[srcoff + 1];
double ctrlx = src[srcoff + 2];
double ctrly = src[srcoff + 3];
double x2 = src[srcoff + 4];
double y2 = src[srcoff + 5];
if (left != null) {
left[leftoff + 0] = x1;
left[leftoff + 1] = y1;
}
if (right != null) {
right[rightoff + 4] = x2;
right[rightoff + 5] = y2;
}
x1 = (x1 + ctrlx) / 2.0;
y1 = (y1 + ctrly) / 2.0;
x2 = (x2 + ctrlx) / 2.0;
y2 = (y2 + ctrly) / 2.0;
ctrlx = (x1 + x2) / 2.0;
ctrly = (y1 + y2) / 2.0;
if (left != null) {
left[leftoff + 2] = x1;
left[leftoff + 3] = y1;
left[leftoff + 4] = ctrlx;
left[leftoff + 5] = ctrly;
}
if (right != null) {
right[rightoff + 0] = ctrlx;
right[rightoff + 1] = ctrly;
right[rightoff + 2] = x2;
right[rightoff + 3] = y2;
}
|
|
