1 /*
2 * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
843 double ctrlx1, double ctrly1,
844 double ctrlx2, double ctrly2,
845 double x2, double y2) {
846 return Math.sqrt(getFlatnessSq(x1, y1, ctrlx1, ctrly1,
847 ctrlx2, ctrly2, x2, y2));
848 }
849
850 /**
851 * Returns the square of the flatness of the cubic curve specified
852 * by the control points stored in the indicated array at the
853 * indicated index. The flatness is the maximum distance
854 * of a control point from the line connecting the end points.
855 * @param coords an array containing coordinates
856 * @param offset the index of {@code coords} from which to begin
857 * getting the end points and control points of the curve
858 * @return the square of the flatness of the {@code CubicCurve2D}
859 * specified by the coordinates in {@code coords} at
860 * the specified offset.
861 * @since 1.2
862 */
863 public static double getFlatnessSq(double coords[], int offset) {
864 return getFlatnessSq(coords[offset + 0], coords[offset + 1],
865 coords[offset + 2], coords[offset + 3],
866 coords[offset + 4], coords[offset + 5],
867 coords[offset + 6], coords[offset + 7]);
868 }
869
870 /**
871 * Returns the flatness of the cubic curve specified
872 * by the control points stored in the indicated array at the
873 * indicated index. The flatness is the maximum distance
874 * of a control point from the line connecting the end points.
875 * @param coords an array containing coordinates
876 * @param offset the index of {@code coords} from which to begin
877 * getting the end points and control points of the curve
878 * @return the flatness of the {@code CubicCurve2D}
879 * specified by the coordinates in {@code coords} at
880 * the specified offset.
881 * @since 1.2
882 */
883 public static double getFlatness(double coords[], int offset) {
884 return getFlatness(coords[offset + 0], coords[offset + 1],
885 coords[offset + 2], coords[offset + 3],
886 coords[offset + 4], coords[offset + 5],
887 coords[offset + 6], coords[offset + 7]);
888 }
889
890 /**
891 * Returns the square of the flatness of this curve. The flatness is the
892 * maximum distance of a control point from the line connecting the
893 * end points.
894 * @return the square of the flatness of this curve.
895 * @since 1.2
896 */
897 public double getFlatnessSq() {
898 return getFlatnessSq(getX1(), getY1(), getCtrlX1(), getCtrlY1(),
899 getCtrlX2(), getCtrlY2(), getX2(), getY2());
900 }
901
902 /**
903 * Returns the flatness of this curve. The flatness is the
983 * as the {@code src} array.
984 * Note that the last point in the first subdivided curve is the
985 * same as the first point in the second subdivided curve. Thus,
986 * it is possible to pass the same array for {@code left}
987 * and {@code right} and to use offsets, such as {@code rightoff}
988 * equals ({@code leftoff} + 6), in order
989 * to avoid allocating extra storage for this common point.
990 * @param src the array holding the coordinates for the source curve
991 * @param srcoff the offset into the array of the beginning of the
992 * the 6 source coordinates
993 * @param left the array for storing the coordinates for the first
994 * half of the subdivided curve
995 * @param leftoff the offset into the array of the beginning of the
996 * the 6 left coordinates
997 * @param right the array for storing the coordinates for the second
998 * half of the subdivided curve
999 * @param rightoff the offset into the array of the beginning of the
1000 * the 6 right coordinates
1001 * @since 1.2
1002 */
1003 public static void subdivide(double src[], int srcoff,
1004 double left[], int leftoff,
1005 double right[], int rightoff) {
1006 double x1 = src[srcoff + 0];
1007 double y1 = src[srcoff + 1];
1008 double ctrlx1 = src[srcoff + 2];
1009 double ctrly1 = src[srcoff + 3];
1010 double ctrlx2 = src[srcoff + 4];
1011 double ctrly2 = src[srcoff + 5];
1012 double x2 = src[srcoff + 6];
1013 double y2 = src[srcoff + 7];
1014 if (left != null) {
1015 left[leftoff + 0] = x1;
1016 left[leftoff + 1] = y1;
1017 }
1018 if (right != null) {
1019 right[rightoff + 6] = x2;
1020 right[rightoff + 7] = y2;
1021 }
1022 x1 = (x1 + ctrlx1) / 2.0;
1023 y1 = (y1 + ctrly1) / 2.0;
1024 x2 = (x2 + ctrlx2) / 2.0;
1025 y2 = (y2 + ctrly2) / 2.0;
1048 right[rightoff + 5] = y2;
1049 }
1050 }
1051
1052 /**
1053 * Solves the cubic whose coefficients are in the {@code eqn}
1054 * array and places the non-complex roots back into the same array,
1055 * returning the number of roots. The solved cubic is represented
1056 * by the equation:
1057 * <pre>
1058 * eqn = {c, b, a, d}
1059 * dx^3 + ax^2 + bx + c = 0
1060 * </pre>
1061 * A return value of -1 is used to distinguish a constant equation
1062 * that might be always 0 or never 0 from an equation that has no
1063 * zeroes.
1064 * @param eqn an array containing coefficients for a cubic
1065 * @return the number of roots, or -1 if the equation is a constant.
1066 * @since 1.2
1067 */
1068 public static int solveCubic(double eqn[]) {
1069 return solveCubic(eqn, eqn);
1070 }
1071
1072 /**
1073 * Solve the cubic whose coefficients are in the {@code eqn}
1074 * array and place the non-complex roots into the {@code res}
1075 * array, returning the number of roots.
1076 * The cubic solved is represented by the equation:
1077 * eqn = {c, b, a, d}
1078 * dx^3 + ax^2 + bx + c = 0
1079 * A return value of -1 is used to distinguish a constant equation,
1080 * which may be always 0 or never 0, from an equation which has no
1081 * zeroes.
1082 * @param eqn the specified array of coefficients to use to solve
1083 * the cubic equation
1084 * @param res the array that contains the non-complex roots
1085 * resulting from the solution of the cubic equation
1086 * @return the number of roots, or -1 if the equation is a constant
1087 * @since 1.3
1088 */
1089 public static int solveCubic(double eqn[], double res[]) {
1090 // From Graphics Gems:
1091 // http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c
1092 final double d = eqn[3];
1093 if (d == 0) {
1094 return QuadCurve2D.solveQuadratic(eqn, res);
1095 }
1096
1097 /* normal form: x^3 + Ax^2 + Bx + C = 0 */
1098 final double A = eqn[2] / d;
1099 final double B = eqn[1] / d;
1100 final double C = eqn[0] / d;
1101
1102
1103 // substitute x = y - A/3 to eliminate quadratic term:
1104 // x^3 +Px + Q = 0
1105 //
1106 // Since we actually need P/3 and Q/2 for all of the
1107 // calculations that follow, we will calculate
1108 // p = P/3
1109 // q = Q/2
1352 return m;
1353 }
1354
1355 private static boolean inInterval(double t, double min, double max) {
1356 return min <= t && t <= max;
1357 }
1358
1359 private static boolean within(double x, double y, double err) {
1360 double d = y - x;
1361 return (d <= err && d >= -err);
1362 }
1363
1364 private static boolean iszero(double x, double err) {
1365 return within(x, 0, err);
1366 }
1367
1368 private static boolean oppositeSigns(double x1, double x2) {
1369 return (x1 < 0 && x2 > 0) || (x1 > 0 && x2 < 0);
1370 }
1371
1372 private static double solveEqn(double eqn[], int order, double t) {
1373 double v = eqn[order];
1374 while (--order >= 0) {
1375 v = v * t + eqn[order];
1376 }
1377 return v;
1378 }
1379
1380 /*
1381 * Computes M+1 where M is an upper bound for all the roots in of eqn.
1382 * See: http://en.wikipedia.org/wiki/Sturm%27s_theorem#Applications.
1383 * The above link doesn't contain a proof, but I [dlila] proved it myself
1384 * so the result is reliable. The proof isn't difficult, but it's a bit
1385 * long to include here.
1386 * Precondition: eqn must represent a cubic polynomial
1387 */
1388 private static double getRootUpperBound(double[] eqn) {
1389 double d = eqn[3];
1390 double a = eqn[2];
1391 double b = eqn[1];
1392 double c = eqn[0];
|
1 /*
2 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
843 double ctrlx1, double ctrly1,
844 double ctrlx2, double ctrly2,
845 double x2, double y2) {
846 return Math.sqrt(getFlatnessSq(x1, y1, ctrlx1, ctrly1,
847 ctrlx2, ctrly2, x2, y2));
848 }
849
850 /**
851 * Returns the square of the flatness of the cubic curve specified
852 * by the control points stored in the indicated array at the
853 * indicated index. The flatness is the maximum distance
854 * of a control point from the line connecting the end points.
855 * @param coords an array containing coordinates
856 * @param offset the index of {@code coords} from which to begin
857 * getting the end points and control points of the curve
858 * @return the square of the flatness of the {@code CubicCurve2D}
859 * specified by the coordinates in {@code coords} at
860 * the specified offset.
861 * @since 1.2
862 */
863 public static double getFlatnessSq(double[] coords, int offset) {
864 return getFlatnessSq(coords[offset + 0], coords[offset + 1],
865 coords[offset + 2], coords[offset + 3],
866 coords[offset + 4], coords[offset + 5],
867 coords[offset + 6], coords[offset + 7]);
868 }
869
870 /**
871 * Returns the flatness of the cubic curve specified
872 * by the control points stored in the indicated array at the
873 * indicated index. The flatness is the maximum distance
874 * of a control point from the line connecting the end points.
875 * @param coords an array containing coordinates
876 * @param offset the index of {@code coords} from which to begin
877 * getting the end points and control points of the curve
878 * @return the flatness of the {@code CubicCurve2D}
879 * specified by the coordinates in {@code coords} at
880 * the specified offset.
881 * @since 1.2
882 */
883 public static double getFlatness(double[] coords, int offset) {
884 return getFlatness(coords[offset + 0], coords[offset + 1],
885 coords[offset + 2], coords[offset + 3],
886 coords[offset + 4], coords[offset + 5],
887 coords[offset + 6], coords[offset + 7]);
888 }
889
890 /**
891 * Returns the square of the flatness of this curve. The flatness is the
892 * maximum distance of a control point from the line connecting the
893 * end points.
894 * @return the square of the flatness of this curve.
895 * @since 1.2
896 */
897 public double getFlatnessSq() {
898 return getFlatnessSq(getX1(), getY1(), getCtrlX1(), getCtrlY1(),
899 getCtrlX2(), getCtrlY2(), getX2(), getY2());
900 }
901
902 /**
903 * Returns the flatness of this curve. The flatness is the
983 * as the {@code src} array.
984 * Note that the last point in the first subdivided curve is the
985 * same as the first point in the second subdivided curve. Thus,
986 * it is possible to pass the same array for {@code left}
987 * and {@code right} and to use offsets, such as {@code rightoff}
988 * equals ({@code leftoff} + 6), in order
989 * to avoid allocating extra storage for this common point.
990 * @param src the array holding the coordinates for the source curve
991 * @param srcoff the offset into the array of the beginning of the
992 * the 6 source coordinates
993 * @param left the array for storing the coordinates for the first
994 * half of the subdivided curve
995 * @param leftoff the offset into the array of the beginning of the
996 * the 6 left coordinates
997 * @param right the array for storing the coordinates for the second
998 * half of the subdivided curve
999 * @param rightoff the offset into the array of the beginning of the
1000 * the 6 right coordinates
1001 * @since 1.2
1002 */
1003 public static void subdivide(double[] src, int srcoff,
1004 double[] left, int leftoff,
1005 double[] right, int rightoff) {
1006 double x1 = src[srcoff + 0];
1007 double y1 = src[srcoff + 1];
1008 double ctrlx1 = src[srcoff + 2];
1009 double ctrly1 = src[srcoff + 3];
1010 double ctrlx2 = src[srcoff + 4];
1011 double ctrly2 = src[srcoff + 5];
1012 double x2 = src[srcoff + 6];
1013 double y2 = src[srcoff + 7];
1014 if (left != null) {
1015 left[leftoff + 0] = x1;
1016 left[leftoff + 1] = y1;
1017 }
1018 if (right != null) {
1019 right[rightoff + 6] = x2;
1020 right[rightoff + 7] = y2;
1021 }
1022 x1 = (x1 + ctrlx1) / 2.0;
1023 y1 = (y1 + ctrly1) / 2.0;
1024 x2 = (x2 + ctrlx2) / 2.0;
1025 y2 = (y2 + ctrly2) / 2.0;
1048 right[rightoff + 5] = y2;
1049 }
1050 }
1051
1052 /**
1053 * Solves the cubic whose coefficients are in the {@code eqn}
1054 * array and places the non-complex roots back into the same array,
1055 * returning the number of roots. The solved cubic is represented
1056 * by the equation:
1057 * <pre>
1058 * eqn = {c, b, a, d}
1059 * dx^3 + ax^2 + bx + c = 0
1060 * </pre>
1061 * A return value of -1 is used to distinguish a constant equation
1062 * that might be always 0 or never 0 from an equation that has no
1063 * zeroes.
1064 * @param eqn an array containing coefficients for a cubic
1065 * @return the number of roots, or -1 if the equation is a constant.
1066 * @since 1.2
1067 */
1068 public static int solveCubic(double[] eqn) {
1069 return solveCubic(eqn, eqn);
1070 }
1071
1072 /**
1073 * Solve the cubic whose coefficients are in the {@code eqn}
1074 * array and place the non-complex roots into the {@code res}
1075 * array, returning the number of roots.
1076 * The cubic solved is represented by the equation:
1077 * eqn = {c, b, a, d}
1078 * dx^3 + ax^2 + bx + c = 0
1079 * A return value of -1 is used to distinguish a constant equation,
1080 * which may be always 0 or never 0, from an equation which has no
1081 * zeroes.
1082 * @param eqn the specified array of coefficients to use to solve
1083 * the cubic equation
1084 * @param res the array that contains the non-complex roots
1085 * resulting from the solution of the cubic equation
1086 * @return the number of roots, or -1 if the equation is a constant
1087 * @since 1.3
1088 */
1089 public static int solveCubic(double[] eqn, double[] res) {
1090 // From Graphics Gems:
1091 // http://tog.acm.org/resources/GraphicsGems/gems/Roots3And4.c
1092 final double d = eqn[3];
1093 if (d == 0) {
1094 return QuadCurve2D.solveQuadratic(eqn, res);
1095 }
1096
1097 /* normal form: x^3 + Ax^2 + Bx + C = 0 */
1098 final double A = eqn[2] / d;
1099 final double B = eqn[1] / d;
1100 final double C = eqn[0] / d;
1101
1102
1103 // substitute x = y - A/3 to eliminate quadratic term:
1104 // x^3 +Px + Q = 0
1105 //
1106 // Since we actually need P/3 and Q/2 for all of the
1107 // calculations that follow, we will calculate
1108 // p = P/3
1109 // q = Q/2
1352 return m;
1353 }
1354
1355 private static boolean inInterval(double t, double min, double max) {
1356 return min <= t && t <= max;
1357 }
1358
1359 private static boolean within(double x, double y, double err) {
1360 double d = y - x;
1361 return (d <= err && d >= -err);
1362 }
1363
1364 private static boolean iszero(double x, double err) {
1365 return within(x, 0, err);
1366 }
1367
1368 private static boolean oppositeSigns(double x1, double x2) {
1369 return (x1 < 0 && x2 > 0) || (x1 > 0 && x2 < 0);
1370 }
1371
1372 private static double solveEqn(double[] eqn, int order, double t) {
1373 double v = eqn[order];
1374 while (--order >= 0) {
1375 v = v * t + eqn[order];
1376 }
1377 return v;
1378 }
1379
1380 /*
1381 * Computes M+1 where M is an upper bound for all the roots in of eqn.
1382 * See: http://en.wikipedia.org/wiki/Sturm%27s_theorem#Applications.
1383 * The above link doesn't contain a proof, but I [dlila] proved it myself
1384 * so the result is reliable. The proof isn't difficult, but it's a bit
1385 * long to include here.
1386 * Precondition: eqn must represent a cubic polynomial
1387 */
1388 private static double getRootUpperBound(double[] eqn) {
1389 double d = eqn[3];
1390 double a = eqn[2];
1391 double b = eqn[1];
1392 double c = eqn[0];
|