/*
* Copyright (c) 1998, 2006, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
package sun.awt.geom;
import java.awt.geom.Rectangle2D;
import java.awt.geom.PathIterator;
import java.awt.geom.QuadCurve2D;
import java.util.Vector;
final class Order2 extends Curve {
private double x0;
private double y0;
private double cx0;
private double cy0;
private double x1;
private double y1;
private double xmin;
private double xmax;
private double xcoeff0;
private double xcoeff1;
private double xcoeff2;
private double ycoeff0;
private double ycoeff1;
private double ycoeff2;
public static void insert(Vector curves, double tmp[],
double x0, double y0,
double cx0, double cy0,
double x1, double y1,
int direction)
{
int numparams = getHorizontalParams(y0, cy0, y1, tmp);
if (numparams == 0) {
// We are using addInstance here to avoid inserting horisontal
// segments
addInstance(curves, x0, y0, cx0, cy0, x1, y1, direction);
return;
}
// assert(numparams == 1);
double t = tmp[0];
tmp[0] = x0; tmp[1] = y0;
tmp[2] = cx0; tmp[3] = cy0;
tmp[4] = x1; tmp[5] = y1;
split(tmp, 0, t);
int i0 = (direction == INCREASING)? 0 : 4;
int i1 = 4 - i0;
addInstance(curves, tmp[i0], tmp[i0 + 1], tmp[i0 + 2], tmp[i0 + 3],
tmp[i0 + 4], tmp[i0 + 5], direction);
addInstance(curves, tmp[i1], tmp[i1 + 1], tmp[i1 + 2], tmp[i1 + 3],
tmp[i1 + 4], tmp[i1 + 5], direction);
}
public static void addInstance(Vector curves,
double x0, double y0,
double cx0, double cy0,
double x1, double y1,
int direction) {
if (y0 > y1) {
curves.add(new Order2(x1, y1, cx0, cy0, x0, y0, -direction));
} else if (y1 > y0) {
curves.add(new Order2(x0, y0, cx0, cy0, x1, y1, direction));
}
}
/*
* Return the count of the number of horizontal sections of the
* specified quadratic Bezier curve. Put the parameters for the
* horizontal sections into the specified <code>ret</code> array.
* <p>
* If we examine the parametric equation in t, we have:
* Py(t) = C0*(1-t)^2 + 2*CP*t*(1-t) + C1*t^2
* = C0 - 2*C0*t + C0*t^2 + 2*CP*t - 2*CP*t^2 + C1*t^2
* = C0 + (2*CP - 2*C0)*t + (C0 - 2*CP + C1)*t^2
* Py(t) = (C0 - 2*CP + C1)*t^2 + (2*CP - 2*C0)*t + (C0)
* If we take the derivative, we get:
* Py(t) = At^2 + Bt + C
* dPy(t) = 2At + B = 0
* 2*(C0 - 2*CP + C1)t + 2*(CP - C0) = 0
* 2*(C0 - 2*CP + C1)t = 2*(C0 - CP)
* t = 2*(C0 - CP) / 2*(C0 - 2*CP + C1)
* t = (C0 - CP) / (C0 - CP + C1 - CP)
* Note that this method will return 0 if the equation is a line,
* which is either always horizontal or never horizontal.
* Completely horizontal curves need to be eliminated by other
* means outside of this method.
*/
public static int getHorizontalParams(double c0, double cp, double c1,
double ret[]) {
if (c0 <= cp && cp <= c1) {
return 0;
}
c0 -= cp;
c1 -= cp;
double denom = c0 + c1;
// If denom == 0 then cp == (c0+c1)/2 and we have a line.
if (denom == 0) {
return 0;
}
double t = c0 / denom;
// No splits at t==0 and t==1
if (t <= 0 || t >= 1) {
return 0;
}
ret[0] = t;
return 1;
}
/*
* Split the quadratic Bezier stored at coords[pos...pos+5] representing
* the paramtric range [0..1] into two subcurves representing the
* parametric subranges [0..t] and [t..1]. Store the results back
* into the array at coords[pos...pos+5] and coords[pos+4...pos+9].
*/
public static void split(double coords[], int pos, double t) {
double x0, y0, cx, cy, x1, y1;
coords[pos+8] = x1 = coords[pos+4];
coords[pos+9] = y1 = coords[pos+5];
cx = coords[pos+2];
cy = coords[pos+3];
x1 = cx + (x1 - cx) * t;
y1 = cy + (y1 - cy) * t;
x0 = coords[pos+0];
y0 = coords[pos+1];
x0 = x0 + (cx - x0) * t;
y0 = y0 + (cy - y0) * t;
cx = x0 + (x1 - x0) * t;
cy = y0 + (y1 - y0) * t;
coords[pos+2] = x0;
coords[pos+3] = y0;
coords[pos+4] = cx;
coords[pos+5] = cy;
coords[pos+6] = x1;
coords[pos+7] = y1;
}
public Order2(double x0, double y0,
double cx0, double cy0,
double x1, double y1,
int direction)
{
super(direction);
// REMIND: Better accuracy in the root finding methods would
// ensure that cy0 is in range. As it stands, it is never
// more than "1 mantissa bit" out of range...
if (cy0 < y0) {
cy0 = y0;
} else if (cy0 > y1) {
cy0 = y1;
}
this.x0 = x0;
this.y0 = y0;
this.cx0 = cx0;
this.cy0 = cy0;
this.x1 = x1;
this.y1 = y1;
xmin = Math.min(Math.min(x0, x1), cx0);
xmax = Math.max(Math.max(x0, x1), cx0);
xcoeff0 = x0;
xcoeff1 = cx0 + cx0 - x0 - x0;
xcoeff2 = x0 - cx0 - cx0 + x1;
ycoeff0 = y0;
ycoeff1 = cy0 + cy0 - y0 - y0;
ycoeff2 = y0 - cy0 - cy0 + y1;
}
public int getOrder() {
return 2;
}
public double getXTop() {
return x0;
}
public double getYTop() {
return y0;
}
public double getXBot() {
return x1;
}
public double getYBot() {
return y1;
}
public double getXMin() {
return xmin;
}
public double getXMax() {
return xmax;
}
public double getX0() {
return (direction == INCREASING) ? x0 : x1;
}
public double getY0() {
return (direction == INCREASING) ? y0 : y1;
}
public double getCX0() {
return cx0;
}
public double getCY0() {
return cy0;
}
public double getX1() {
return (direction == DECREASING) ? x0 : x1;
}
public double getY1() {
return (direction == DECREASING) ? y0 : y1;
}
public double XforY(double y) {
if (y <= y0) {
return x0;
}
if (y >= y1) {
return x1;
}
return XforT(TforY(y));
}
public double TforY(double y) {
if (y <= y0) {
return 0;
}
if (y >= y1) {
return 1;
}
return TforY(y, ycoeff0, ycoeff1, ycoeff2);
}
public static double TforY(double y,
double ycoeff0, double ycoeff1, double ycoeff2)
{
// The caller should have already eliminated y values
// outside of the y0 to y1 range.
ycoeff0 -= y;
if (ycoeff2 == 0.0) {
// The quadratic parabola has degenerated to a line.
// ycoeff1 should not be 0.0 since we have already eliminated
// totally horizontal lines, but if it is, then we will generate
// infinity here for the root, which will not be in the [0,1]
// range so we will pass to the failure code below.
double root = -ycoeff0 / ycoeff1;
if (root >= 0 && root <= 1) {
return root;
}
} else {
// From Numerical Recipes, 5.6, Quadratic and Cubic Equations
double d = ycoeff1 * ycoeff1 - 4.0 * ycoeff2 * ycoeff0;
// If d < 0.0, then there are no roots
if (d >= 0.0) {
d = Math.sqrt(d);
// For accuracy, calculate one root using:
// (-ycoeff1 +/- d) / 2ycoeff2
// and the other using:
// 2ycoeff0 / (-ycoeff1 +/- d)
// Choose the sign of the +/- so that ycoeff1+d
// gets larger in magnitude
if (ycoeff1 < 0.0) {
d = -d;
}
double q = (ycoeff1 + d) / -2.0;
// We already tested ycoeff2 for being 0 above
double root = q / ycoeff2;
if (root >= 0 && root <= 1) {
return root;
}
if (q != 0.0) {
root = ycoeff0 / q;
if (root >= 0 && root <= 1) {
return root;
}
}
}
}
/* We failed to find a root in [0,1]. What could have gone wrong?
* First, remember that these curves are constructed to be monotonic
* in Y and totally horizontal curves have already been eliminated.
* Now keep in mind that the Y coefficients of the polynomial form
* of the curve are calculated from the Y coordinates which define
* our curve. They should theoretically define the same curve,
* but they can be off by a couple of bits of precision after the
* math is done and so can represent a slightly modified curve.
* This is normally not an issue except when we have solutions near
* the endpoints. Since the answers we get from solving the polynomial
* may be off by a few bits that means that they could lie just a
* few bits of precision outside the [0,1] range.
*
* Another problem could be that while the parametric curve defined
* by the Y coordinates has a local minima or maxima at or just
* outside of the endpoints, the polynomial form might express
* that same min/max just inside of and just shy of the Y coordinate
* of that endpoint. In that case, if we solve for a Y coordinate
* at or near that endpoint, we may be solving for a Y coordinate
* that is below that minima or above that maxima and we would find
* no solutions at all.
*
* In either case, we can assume that y is so near one of the
* endpoints that we can just collapse it onto the nearest endpoint
* without losing more than a couple of bits of precision.
*/
// First calculate the midpoint between y0 and y1 and choose to
// return either 0.0 or 1.0 depending on whether y is above
// or below the midpoint...
// Note that we subtracted y from ycoeff0 above so both y0 and y1
// will be "relative to y" so we are really just looking at where
// zero falls with respect to the "relative midpoint" here.
double y0 = ycoeff0;
double y1 = ycoeff0 + ycoeff1 + ycoeff2;
return (0 < (y0 + y1) / 2) ? 0.0 : 1.0;
}
public double XforT(double t) {
return (xcoeff2 * t + xcoeff1) * t + xcoeff0;
}
public double YforT(double t) {
return (ycoeff2 * t + ycoeff1) * t + ycoeff0;
}
public double dXforT(double t, int deriv) {
switch (deriv) {
case 0:
return (xcoeff2 * t + xcoeff1) * t + xcoeff0;
case 1:
return 2 * xcoeff2 * t + xcoeff1;
case 2:
return 2 * xcoeff2;
default:
return 0;
}
}
public double dYforT(double t, int deriv) {
switch (deriv) {
case 0:
return (ycoeff2 * t + ycoeff1) * t + ycoeff0;
case 1:
return 2 * ycoeff2 * t + ycoeff1;
case 2:
return 2 * ycoeff2;
default:
return 0;
}
}
public double nextVertical(double t0, double t1) {
double t = -xcoeff1 / (2 * xcoeff2);
if (t > t0 && t < t1) {
return t;
}
return t1;
}
public void enlarge(Rectangle2D r) {
r.add(x0, y0);
double t = -xcoeff1 / (2 * xcoeff2);
if (t > 0 && t < 1) {
r.add(XforT(t), YforT(t));
}
r.add(x1, y1);
}
public Curve getSubCurve(double ystart, double yend, int dir) {
double t0, t1;
if (ystart <= y0) {
if (yend >= y1) {
return getWithDirection(dir);
}
t0 = 0;
} else {
t0 = TforY(ystart, ycoeff0, ycoeff1, ycoeff2);
}
if (yend >= y1) {
t1 = 1;
} else {
t1 = TforY(yend, ycoeff0, ycoeff1, ycoeff2);
}
double eqn[] = new double[10];
eqn[0] = x0;
eqn[1] = y0;
eqn[2] = cx0;
eqn[3] = cy0;
eqn[4] = x1;
eqn[5] = y1;
if (t1 < 1) {
split(eqn, 0, t1);
}
int i;
if (t0 <= 0) {
i = 0;
} else {
split(eqn, 0, t0 / t1);
i = 4;
}
return new Order2(eqn[i+0], ystart,
eqn[i+2], eqn[i+3],
eqn[i+4], yend,
dir);
}
public Curve getReversedCurve() {
return new Order2(x0, y0, cx0, cy0, x1, y1, -direction);
}
public int getSegment(double coords[]) {
coords[0] = cx0;
coords[1] = cy0;
if (direction == INCREASING) {
coords[2] = x1;
coords[3] = y1;
} else {
coords[2] = x0;
coords[3] = y0;
}
return PathIterator.SEG_QUADTO;
}
public String controlPointString() {
return ("("+round(cx0)+", "+round(cy0)+"), ");
}
}