001/* 002 * @(#)QuadCurve2D.java 1.34 06/04/17 003 * 004 * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 005 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. 006 */ 007 008package armyc2.c2sd.graphics2d; 009 010/** 011 * The <code>QuadCurve2D</code> class defines a quadratic parametric curve 012 * segment in {@code (x,y)} coordinate space. 013 * <p> 014 * This class is only the abstract superclass for all objects that 015 * store a 2D quadratic curve segment. 016 * The actual storage representation of the coordinates is left to 017 * the subclass. 018 * 019 * @version 1.34, 04/17/06 020 * @author Jim Graham 021 * @since 1.2 022 */ 023public /*abstract*/ final class QuadCurve2D /*implements Shape, Cloneable*/ { 024 025 026 /** 027 * This is an abstract class that cannot be instantiated directly. 028 * Type-specific implementation subclasses are available for 029 * instantiation and provide a number of formats for storing 030 * the information necessary to satisfy the various accessor 031 * methods below. 032 * 033 * @see java.awt.geom.QuadCurve2D.Float 034 * @see java.awt.geom.QuadCurve2D.Double 035 * @since 1.2 036 */ 037// protected QuadCurve2D() { 038// } 039 040 041 /** 042 * Returns the square of the flatness, or maximum distance of a 043 * control point from the line connecting the end points, of the 044 * quadratic curve specified by the indicated control points. 045 * 046 * @param x1 the X coordinate of the start point 047 * @param y1 the Y coordinate of the start point 048 * @param ctrlx the X coordinate of the control point 049 * @param ctrly the Y coordinate of the control point 050 * @param x2 the X coordinate of the end point 051 * @param y2 the Y coordinate of the end point 052 * @return the square of the flatness of the quadratic curve 053 * defined by the specified coordinates. 054 * @since 1.2 055 */ 056 public static double getFlatnessSq2(double x1, double y1, 057 double ctrlx, double ctrly, 058 double x2, double y2) { 059 //return Line2D.ptSegDistSq(x1, y1, x2, y2, ctrlx, ctrly); 060 return Line2D.ptLineDistSq(x1, y1, x2, y2, ctrlx, ctrly); 061 } 062 063 064 /** 065 * Returns the square of the flatness, or maximum distance of a 066 * control point from the line connecting the end points, of the 067 * quadratic curve specified by the control points stored in the 068 * indicated array at the indicated index. 069 * @param coords an array containing coordinate values 070 * @param offset the index into <code>coords</code> from which to 071 * to start getting the values from the array 072 * @return the flatness of the quadratic curve that is defined by the 073 * values in the specified array at the specified index. 074 * @since 1.2 075 */ 076 public static double getFlatnessSq(double coords[], int offset) { 077// return Line2D.ptSegDistSq(coords[offset + 0], coords[offset + 1], 078// coords[offset + 4], coords[offset + 5], 079// coords[offset + 2], coords[offset + 3]); 080 return Line2D.ptLineDistSq(coords[offset + 0], coords[offset + 1], 081 coords[offset + 4], coords[offset + 5], 082 coords[offset + 2], coords[offset + 3]); 083 } 084 085 /** 086 * Subdivides the quadratic curve specified by the coordinates 087 * stored in the <code>src</code> array at indices 088 * <code>srcoff</code> through <code>srcoff</code> + 5 089 * and stores the resulting two subdivided curves into the two 090 * result arrays at the corresponding indices. 091 * Either or both of the <code>left</code> and <code>right</code> 092 * arrays can be <code>null</code> or a reference to the same array 093 * and offset as the <code>src</code> array. 094 * Note that the last point in the first subdivided curve is the 095 * same as the first point in the second subdivided curve. Thus, 096 * it is possible to pass the same array for <code>left</code> and 097 * <code>right</code> and to use offsets such that 098 * <code>rightoff</code> equals <code>leftoff</code> + 4 in order 099 * to avoid allocating extra storage for this common point. 100 * @param src the array holding the coordinates for the source curve 101 * @param srcoff the offset into the array of the beginning of the 102 * the 6 source coordinates 103 * @param left the array for storing the coordinates for the first 104 * half of the subdivided curve 105 * @param leftoff the offset into the array of the beginning of the 106 * the 6 left coordinates 107 * @param right the array for storing the coordinates for the second 108 * half of the subdivided curve 109 * @param rightoff the offset into the array of the beginning of the 110 * the 6 right coordinates 111 * @since 1.2 112 */ 113 public static void subdivide(double src[], int srcoff, 114 double left[], int leftoff, 115 double right[], int rightoff) { 116 double x1 = src[srcoff + 0]; 117 double y1 = src[srcoff + 1]; 118 double ctrlx = src[srcoff + 2]; 119 double ctrly = src[srcoff + 3]; 120 double x2 = src[srcoff + 4]; 121 double y2 = src[srcoff + 5]; 122 if (left != null) { 123 left[leftoff + 0] = x1; 124 left[leftoff + 1] = y1; 125 } 126 if (right != null) { 127 right[rightoff + 4] = x2; 128 right[rightoff + 5] = y2; 129 } 130 x1 = (x1 + ctrlx) / 2.0; 131 y1 = (y1 + ctrly) / 2.0; 132 x2 = (x2 + ctrlx) / 2.0; 133 y2 = (y2 + ctrly) / 2.0; 134 ctrlx = (x1 + x2) / 2.0; 135 ctrly = (y1 + y2) / 2.0; 136 if (left != null) { 137 left[leftoff + 2] = x1; 138 left[leftoff + 3] = y1; 139 left[leftoff + 4] = ctrlx; 140 left[leftoff + 5] = ctrly; 141 } 142 if (right != null) { 143 right[rightoff + 0] = ctrlx; 144 right[rightoff + 1] = ctrly; 145 right[rightoff + 2] = x2; 146 right[rightoff + 3] = y2; 147 } 148 } 149 150 /** 151 * Solves the quadratic whose coefficients are in the <code>eqn</code> 152 * array and places the non-complex roots back into the same array, 153 * returning the number of roots. The quadratic solved is represented 154 * by the equation: 155 * <pre> 156 * eqn = {C, B, A}; 157 * ax^2 + bx + c = 0 158 * </pre> 159 * A return value of <code>-1</code> is used to distinguish a constant 160 * equation, which might be always 0 or never 0, from an equation that 161 * has no zeroes. 162 * @param eqn the array that contains the quadratic coefficients 163 * @return the number of roots, or <code>-1</code> if the equation is 164 * a constant 165 * @since 1.2 166 */ 167 public static int solveQuadratic(double eqn[]) { 168 return solveQuadratic2(eqn, eqn); 169 } 170 171 /** 172 * Solves the quadratic whose coefficients are in the <code>eqn</code> 173 * array and places the non-complex roots into the <code>res</code> 174 * array, returning the number of roots. 175 * The quadratic solved is represented by the equation: 176 * <pre> 177 * eqn = {C, B, A}; 178 * ax^2 + bx + c = 0 179 * </pre> 180 * A return value of <code>-1</code> is used to distinguish a constant 181 * equation, which might be always 0 or never 0, from an equation that 182 * has no zeroes. 183 * @param eqn the specified array of coefficients to use to solve 184 * the quadratic equation 185 * @param res the array that contains the non-complex roots 186 * resulting from the solution of the quadratic equation 187 * @return the number of roots, or <code>-1</code> if the equation is 188 * a constant. 189 * @since 1.3 190 */ 191 public static int solveQuadratic2(double eqn[], double res[]) { 192 double a = eqn[2]; 193 double b = eqn[1]; 194 double c = eqn[0]; 195 int roots = 0; 196 if (a == 0.0) { 197 // The quadratic parabola has degenerated to a line. 198 if (b == 0.0) { 199 // The line has degenerated to a constant. 200 return -1; 201 } 202 res[roots++] = -c / b; 203 } else { 204 // From Numerical Recipes, 5.6, Quadratic and Cubic Equations 205 double d = b * b - 4.0 * a * c; 206 if (d < 0.0) { 207 // If d < 0.0, then there are no roots 208 return 0; 209 } 210 d = Math.sqrt(d); 211 // For accuracy, calculate one root using: 212 // (-b +/- d) / 2a 213 // and the other using: 214 // 2c / (-b +/- d) 215 // Choose the sign of the +/- so that b+d gets larger in magnitude 216 if (b < 0.0) { 217 d = -d; 218 } 219 double q = (b + d) / -2.0; 220 // We already tested a for being 0 above 221 res[roots++] = q / a; 222 if (q != 0.0) { 223 res[roots++] = c / q; 224 } 225 } 226 return roots; 227 } 228 229 /** 230 * Fill an array with the coefficients of the parametric equation 231 * in t, ready for solving against val with solveQuadratic. 232 * We currently have: 233 * val = Py(t) = C1*(1-t)^2 + 2*CP*t*(1-t) + C2*t^2 234 * = C1 - 2*C1*t + C1*t^2 + 2*CP*t - 2*CP*t^2 + C2*t^2 235 * = C1 + (2*CP - 2*C1)*t + (C1 - 2*CP + C2)*t^2 236 * 0 = (C1 - val) + (2*CP - 2*C1)*t + (C1 - 2*CP + C2)*t^2 237 * 0 = C + Bt + At^2 238 * C = C1 - val 239 * B = 2*CP - 2*C1 240 * A = C1 - 2*CP + C2 241 */ 242 private static void fillEqn(double eqn[], double val, 243 double c1, double cp, double c2) { 244 eqn[0] = c1 - val; 245 eqn[1] = cp + cp - c1 - c1; 246 eqn[2] = c1 - cp - cp + c2; 247 } 248 249 private static final int BELOW = -2; 250 private static final int LOWEDGE = -1; 251 private static final int INSIDE = 0; 252 private static final int HIGHEDGE = 1; 253 private static final int ABOVE = 2; 254 255 /** 256 * Determine where coord lies with respect to the range from 257 * low to high. It is assumed that low <= high. The return 258 * value is one of the 5 values BELOW, LOWEDGE, INSIDE, HIGHEDGE, 259 * or ABOVE. 260 */ 261 private static int getTag(double coord, double low, double high) { 262 if (coord <= low) { 263 return (coord < low ? BELOW : LOWEDGE); 264 } 265 if (coord >= high) { 266 return (coord > high ? ABOVE : HIGHEDGE); 267 } 268 return INSIDE; 269 } 270 271 /** 272 * Determine if the pttag represents a coordinate that is already 273 * in its test range, or is on the border with either of the two 274 * opttags representing another coordinate that is "towards the 275 * inside" of that test range. In other words, are either of the 276 * two "opt" points "drawing the pt inward"? 277 */ 278 private static boolean inwards(int pttag, int opt1tag, int opt2tag) { 279 switch (pttag) { 280 case BELOW: 281 case ABOVE: 282 default: 283 return false; 284 case LOWEDGE: 285 return (opt1tag >= INSIDE || opt2tag >= INSIDE); 286 case INSIDE: 287 return true; 288 case HIGHEDGE: 289 return (opt1tag <= INSIDE || opt2tag <= INSIDE); 290 } 291 } 292 293 294 @Override 295 /** 296 * Creates a new object of the same class and with the same contents 297 * as this object. 298 * 299 * @return a clone of this instance. 300 * @exception OutOfMemoryError if there is not enough memory. 301 * @see java.lang.Cloneable 302 * @since 1.2 303 */ 304 public Object clone() { 305 try { 306 return super.clone(); 307 } catch (CloneNotSupportedException e) { 308 // this shouldn't happen, since we are Cloneable 309 throw new InternalError(); 310 } 311 } 312}