Back to index...

	/*
	* 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 + 2CPt(1-t) + C1*t^2
	* = C0 - 2C0t + C0t^2 + 2CPt - 2CPt^2 + C1t^2
	* = C0 + (2CP - 2C0)t + (C0 - 2CP + C1)*t^2
	* Py(t) = (C0 - 2CP + C1)t^2 + (2CP - 2C0)*t + (C0)
	* If we take the derivative, we get:
	* Py(t) = At^2 + Bt + C
	* dPy(t) = 2At + B = 0
	* 2(C0 - 2CP + C1)t + 2*(CP - C0) = 0
	* 2(C0 - 2CP + 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)+"), ");
	}
	}

Back to index...