From 51510efaee031b53bcf01fec41fceab67504e334 Mon Sep 17 00:00:00 2001 From: mkoch Date: Mon, 5 Jan 2004 19:19:29 +0000 Subject: 2004-01-05 Sascha Brawer Thanks to Brian Gough * java/awt/geom/CubicCurve2D.java (solveCubic): Implemented. * java/awt/geom/QuadCurve2D.java (solveQuadratic): Re-written. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@75437 138bc75d-0d04-0410-961f-82ee72b054a4 --- libjava/java/awt/geom/QuadCurve2D.java | 144 ++++++++++++++++++++++++++++++--- 1 file changed, 131 insertions(+), 13 deletions(-) (limited to 'libjava/java/awt/geom/QuadCurve2D.java') diff --git a/libjava/java/awt/geom/QuadCurve2D.java b/libjava/java/awt/geom/QuadCurve2D.java index 5bc63e6c6cf..409c4841e15 100644 --- a/libjava/java/awt/geom/QuadCurve2D.java +++ b/libjava/java/awt/geom/QuadCurve2D.java @@ -550,39 +550,157 @@ public abstract class QuadCurve2D } + /** + * Finds the non-complex roots of a quadratic equation, placing the + * results into the same array as the equation coefficients. The + * following equation is being solved: + * + *
eqn[2] · x2 + * + eqn[1] · x + * + eqn[0] + * = 0 + *
+ * + *

For some background about solving quadratic equations, see the + * article “Quadratic Formula” in PlanetMath. For an extensive library + * of numerical algorithms written in the C programming language, + * see the GNU Scientific + * Library. + * + * @see #solveQuadratic(double[], double[]) + * @see CubicCurve2D#solveCubic(double[], double[]) + * + * @param eqn an array with the coefficients of the equation. When + * this procedure has returned, eqn will contain the + * non-complex solutions of the equation, in no particular order. + * + * @return the number of non-complex solutions. A result of 0 + * indicates that the equation has no non-complex solutions. A + * result of -1 indicates that the equation is constant (i.e., + * always or never zero). + * + * @author Brian Gough + * (original C implementation in the GNU Scientific Library) + * + * @author Sascha Brawer + * (adaptation to Java) + */ public static int solveQuadratic(double[] eqn) { return solveQuadratic(eqn, eqn); } + /** + * Finds the non-complex roots of a quadratic equation. The + * following equation is being solved: + * + *

eqn[2] · x2 + * + eqn[1] · x + * + eqn[0] + * = 0 + *
+ * + *

For some background about solving quadratic equations, see the + * article “Quadratic Formula” in PlanetMath. For an extensive library + * of numerical algorithms written in the C programming language, + * see the GNU Scientific + * Library. + * + * @see CubicCurve2D#solveCubic(double[],double[]) + * + * @param eqn an array with the coefficients of the equation. + * + * @param res an array into which the non-complex roots will be + * stored. The results may be in an arbitrary order. It is safe to + * pass the same array object reference for both eqn + * and res. + * + * @return the number of non-complex solutions. A result of 0 + * indicates that the equation has no non-complex solutions. A + * result of -1 indicates that the equation is constant (i.e., + * always or never zero). + * + * @author Brian Gough + * (original C implementation in the GNU Scientific Library) + * + * @author Sascha Brawer + * (adaptation to Java) + */ public static int solveQuadratic(double[] eqn, double[] res) { - double c = eqn[0]; - double b = eqn[1]; - double a = eqn[2]; + // Taken from poly/solve_quadratic.c in the GNU Scientific Library + // (GSL), cvs revision 1.7 of 2003-07-26. For the original source, + // see http://www.gnu.org/software/gsl/ + // + // Brian Gough, the author of that code, has granted the + // permission to use it in GNU Classpath under the GNU Classpath + // license, and has assigned the copyright to the Free Software + // Foundation. + // + // The Java implementation is very similar to the GSL code, but + // not a strict one-to-one copy. For example, GSL would sort the + // result. + + double a, b, c, disc; + + c = eqn[0]; + b = eqn[1]; + a = eqn[2]; + + // Check for linear or constant functions. This is not done by the + // GNU Scientific Library. Without this special check, we + // wouldn't return -1 for constant functions, and 2 instead of 1 + // for linear functions. if (a == 0) { if (b == 0) return -1; + res[0] = -c / b; return 1; } - c /= a; - b /= a * 2; - double det = Math.sqrt(b * b - c); - if (det != det) + + disc = b * b - 4 * a * c; + + if (disc < 0) return 0; - // For fewer rounding errors, we calculate the two roots differently. - if (b > 0) + + if (disc == 0) + { + // The GNU Scientific Library returns two identical results here. + // We just return one. + res[0] = -0.5 * b / a ; + return 1; + } + + // disc > 0 + if (b == 0) { - res[0] = -b - det; - res[1] = -c / (b + det); + double r; + + r = Math.abs(0.5 * Math.sqrt(disc) / a); + res[0] = -r; + res[1] = r; } else { - res[0] = -c / (b - det); - res[1] = -b + det; + double sgnb, temp; + + sgnb = (b > 0 ? 1 : -1); + temp = -0.5 * (b + sgnb * Math.sqrt(disc)); + + // The GNU Scientific Library sorts the result here. We don't. + res[0] = temp / a; + res[1] = c / temp; } return 2; } -- cgit v1.2.3