1 /* 2 * Copyright (c) 1998, 2006, 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 23 * questions. 24 */ 25 26 package sun.awt.geom; 27 28 import java.awt.geom.Rectangle2D; 29 import java.awt.geom.PathIterator; 30 import java.awt.geom.QuadCurve2D; 31 import java.util.Vector; 32 33 final class Order2 extends Curve { 34 private double x0; 35 private double y0; 36 private double cx0; 37 private double cy0; 38 private double x1; 39 private double y1; 40 private double xmin; 41 private double xmax; 42 43 private double xcoeff0; 44 private double xcoeff1; 45 private double xcoeff2; 46 private double ycoeff0; 47 private double ycoeff1; 48 private double ycoeff2; 49 50 public static void insert(Vector<? super Order2> curves, double tmp[], 51 double x0, double y0, 52 double cx0, double cy0, 53 double x1, double y1, 54 int direction) 55 { 56 int numparams = getHorizontalParams(y0, cy0, y1, tmp); 57 if (numparams == 0) { 58 // We are using addInstance here to avoid inserting horisontal 59 // segments 60 addInstance(curves, x0, y0, cx0, cy0, x1, y1, direction); 61 return; 62 } 63 // assert(numparams == 1); 64 double t = tmp[0]; 65 tmp[0] = x0; tmp[1] = y0; 66 tmp[2] = cx0; tmp[3] = cy0; 67 tmp[4] = x1; tmp[5] = y1; 68 split(tmp, 0, t); 69 int i0 = (direction == INCREASING)? 0 : 4; 70 int i1 = 4 - i0; 71 addInstance(curves, tmp[i0], tmp[i0 + 1], tmp[i0 + 2], tmp[i0 + 3], 72 tmp[i0 + 4], tmp[i0 + 5], direction); 73 addInstance(curves, tmp[i1], tmp[i1 + 1], tmp[i1 + 2], tmp[i1 + 3], 74 tmp[i1 + 4], tmp[i1 + 5], direction); 75 } 76 77 public static void addInstance(Vector<? super Order2> curves, 78 double x0, double y0, 79 double cx0, double cy0, 80 double x1, double y1, 81 int direction) { 82 if (y0 > y1) { 83 curves.add(new Order2(x1, y1, cx0, cy0, x0, y0, -direction)); 84 } else if (y1 > y0) { 85 curves.add(new Order2(x0, y0, cx0, cy0, x1, y1, direction)); 86 } 87 } 88 89 /* 90 * Return the count of the number of horizontal sections of the 91 * specified quadratic Bezier curve. Put the parameters for the 92 * horizontal sections into the specified <code>ret</code> array. 93 * <p> 94 * If we examine the parametric equation in t, we have: 95 * Py(t) = C0*(1-t)^2 + 2*CP*t*(1-t) + C1*t^2 96 * = C0 - 2*C0*t + C0*t^2 + 2*CP*t - 2*CP*t^2 + C1*t^2 97 * = C0 + (2*CP - 2*C0)*t + (C0 - 2*CP + C1)*t^2 98 * Py(t) = (C0 - 2*CP + C1)*t^2 + (2*CP - 2*C0)*t + (C0) 99 * If we take the derivative, we get: 100 * Py(t) = At^2 + Bt + C 101 * dPy(t) = 2At + B = 0 102 * 2*(C0 - 2*CP + C1)t + 2*(CP - C0) = 0 103 * 2*(C0 - 2*CP + C1)t = 2*(C0 - CP) 104 * t = 2*(C0 - CP) / 2*(C0 - 2*CP + C1) 105 * t = (C0 - CP) / (C0 - CP + C1 - CP) 106 * Note that this method will return 0 if the equation is a line, 107 * which is either always horizontal or never horizontal. 108 * Completely horizontal curves need to be eliminated by other 109 * means outside of this method. 110 */ 111 public static int getHorizontalParams(double c0, double cp, double c1, 112 double ret[]) { 113 if (c0 <= cp && cp <= c1) { 114 return 0; 115 } 116 c0 -= cp; 117 c1 -= cp; 118 double denom = c0 + c1; 119 // If denom == 0 then cp == (c0+c1)/2 and we have a line. 120 if (denom == 0) { 121 return 0; 122 } 123 double t = c0 / denom; 124 // No splits at t==0 and t==1 125 if (t <= 0 || t >= 1) { 126 return 0; 127 } 128 ret[0] = t; 129 return 1; 130 } 131 132 /* 133 * Split the quadratic Bezier stored at coords[pos...pos+5] representing 134 * the paramtric range [0..1] into two subcurves representing the 135 * parametric subranges [0..t] and [t..1]. Store the results back 136 * into the array at coords[pos...pos+5] and coords[pos+4...pos+9]. 137 */ 138 public static void split(double coords[], int pos, double t) { 139 double x0, y0, cx, cy, x1, y1; 140 coords[pos+8] = x1 = coords[pos+4]; 141 coords[pos+9] = y1 = coords[pos+5]; 142 cx = coords[pos+2]; 143 cy = coords[pos+3]; 144 x1 = cx + (x1 - cx) * t; 145 y1 = cy + (y1 - cy) * t; 146 x0 = coords[pos+0]; 147 y0 = coords[pos+1]; 148 x0 = x0 + (cx - x0) * t; 149 y0 = y0 + (cy - y0) * t; 150 cx = x0 + (x1 - x0) * t; 151 cy = y0 + (y1 - y0) * t; 152 coords[pos+2] = x0; 153 coords[pos+3] = y0; 154 coords[pos+4] = cx; 155 coords[pos+5] = cy; 156 coords[pos+6] = x1; 157 coords[pos+7] = y1; 158 } 159 160 public Order2(double x0, double y0, 161 double cx0, double cy0, 162 double x1, double y1, 163 int direction) 164 { 165 super(direction); 166 // REMIND: Better accuracy in the root finding methods would 167 // ensure that cy0 is in range. As it stands, it is never 168 // more than "1 mantissa bit" out of range... 169 if (cy0 < y0) { 170 cy0 = y0; 171 } else if (cy0 > y1) { 172 cy0 = y1; 173 } 174 this.x0 = x0; 175 this.y0 = y0; 176 this.cx0 = cx0; 177 this.cy0 = cy0; 178 this.x1 = x1; 179 this.y1 = y1; 180 xmin = Math.min(Math.min(x0, x1), cx0); 181 xmax = Math.max(Math.max(x0, x1), cx0); 182 xcoeff0 = x0; 183 xcoeff1 = cx0 + cx0 - x0 - x0; 184 xcoeff2 = x0 - cx0 - cx0 + x1; 185 ycoeff0 = y0; 186 ycoeff1 = cy0 + cy0 - y0 - y0; 187 ycoeff2 = y0 - cy0 - cy0 + y1; 188 } 189 190 public int getOrder() { 191 return 2; 192 } 193 194 public double getXTop() { 195 return x0; 196 } 197 198 public double getYTop() { 199 return y0; 200 } 201 202 public double getXBot() { 203 return x1; 204 } 205 206 public double getYBot() { 207 return y1; 208 } 209 210 public double getXMin() { 211 return xmin; 212 } 213 214 public double getXMax() { 215 return xmax; 216 } 217 218 public double getX0() { 219 return (direction == INCREASING) ? x0 : x1; 220 } 221 222 public double getY0() { 223 return (direction == INCREASING) ? y0 : y1; 224 } 225 226 public double getCX0() { 227 return cx0; 228 } 229 230 public double getCY0() { 231 return cy0; 232 } 233 234 public double getX1() { 235 return (direction == DECREASING) ? x0 : x1; 236 } 237 238 public double getY1() { 239 return (direction == DECREASING) ? y0 : y1; 240 } 241 242 public double XforY(double y) { 243 if (y <= y0) { 244 return x0; 245 } 246 if (y >= y1) { 247 return x1; 248 } 249 return XforT(TforY(y)); 250 } 251 252 public double TforY(double y) { 253 if (y <= y0) { 254 return 0; 255 } 256 if (y >= y1) { 257 return 1; 258 } 259 return TforY(y, ycoeff0, ycoeff1, ycoeff2); 260 } 261 262 public static double TforY(double y, 263 double ycoeff0, double ycoeff1, double ycoeff2) 264 { 265 // The caller should have already eliminated y values 266 // outside of the y0 to y1 range. 267 ycoeff0 -= y; 268 if (ycoeff2 == 0.0) { 269 // The quadratic parabola has degenerated to a line. 270 // ycoeff1 should not be 0.0 since we have already eliminated 271 // totally horizontal lines, but if it is, then we will generate 272 // infinity here for the root, which will not be in the [0,1] 273 // range so we will pass to the failure code below. 274 double root = -ycoeff0 / ycoeff1; 275 if (root >= 0 && root <= 1) { 276 return root; 277 } 278 } else { 279 // From Numerical Recipes, 5.6, Quadratic and Cubic Equations 280 double d = ycoeff1 * ycoeff1 - 4.0 * ycoeff2 * ycoeff0; 281 // If d < 0.0, then there are no roots 282 if (d >= 0.0) { 283 d = Math.sqrt(d); 284 // For accuracy, calculate one root using: 285 // (-ycoeff1 +/- d) / 2ycoeff2 286 // and the other using: 287 // 2ycoeff0 / (-ycoeff1 +/- d) 288 // Choose the sign of the +/- so that ycoeff1+d 289 // gets larger in magnitude 290 if (ycoeff1 < 0.0) { 291 d = -d; 292 } 293 double q = (ycoeff1 + d) / -2.0; 294 // We already tested ycoeff2 for being 0 above 295 double root = q / ycoeff2; 296 if (root >= 0 && root <= 1) { 297 return root; 298 } 299 if (q != 0.0) { 300 root = ycoeff0 / q; 301 if (root >= 0 && root <= 1) { 302 return root; 303 } 304 } 305 } 306 } 307 /* We failed to find a root in [0,1]. What could have gone wrong? 308 * First, remember that these curves are constructed to be monotonic 309 * in Y and totally horizontal curves have already been eliminated. 310 * Now keep in mind that the Y coefficients of the polynomial form 311 * of the curve are calculated from the Y coordinates which define 312 * our curve. They should theoretically define the same curve, 313 * but they can be off by a couple of bits of precision after the 314 * math is done and so can represent a slightly modified curve. 315 * This is normally not an issue except when we have solutions near 316 * the endpoints. Since the answers we get from solving the polynomial 317 * may be off by a few bits that means that they could lie just a 318 * few bits of precision outside the [0,1] range. 319 * 320 * Another problem could be that while the parametric curve defined 321 * by the Y coordinates has a local minima or maxima at or just 322 * outside of the endpoints, the polynomial form might express 323 * that same min/max just inside of and just shy of the Y coordinate 324 * of that endpoint. In that case, if we solve for a Y coordinate 325 * at or near that endpoint, we may be solving for a Y coordinate 326 * that is below that minima or above that maxima and we would find 327 * no solutions at all. 328 * 329 * In either case, we can assume that y is so near one of the 330 * endpoints that we can just collapse it onto the nearest endpoint 331 * without losing more than a couple of bits of precision. 332 */ 333 // First calculate the midpoint between y0 and y1 and choose to 334 // return either 0.0 or 1.0 depending on whether y is above 335 // or below the midpoint... 336 // Note that we subtracted y from ycoeff0 above so both y0 and y1 337 // will be "relative to y" so we are really just looking at where 338 // zero falls with respect to the "relative midpoint" here. 339 double y0 = ycoeff0; 340 double y1 = ycoeff0 + ycoeff1 + ycoeff2; 341 return (0 < (y0 + y1) / 2) ? 0.0 : 1.0; 342 } 343 344 public double XforT(double t) { 345 return (xcoeff2 * t + xcoeff1) * t + xcoeff0; 346 } 347 348 public double YforT(double t) { 349 return (ycoeff2 * t + ycoeff1) * t + ycoeff0; 350 } 351 352 public double dXforT(double t, int deriv) { 353 switch (deriv) { 354 case 0: 355 return (xcoeff2 * t + xcoeff1) * t + xcoeff0; 356 case 1: 357 return 2 * xcoeff2 * t + xcoeff1; 358 case 2: 359 return 2 * xcoeff2; 360 default: 361 return 0; 362 } 363 } 364 365 public double dYforT(double t, int deriv) { 366 switch (deriv) { 367 case 0: 368 return (ycoeff2 * t + ycoeff1) * t + ycoeff0; 369 case 1: 370 return 2 * ycoeff2 * t + ycoeff1; 371 case 2: 372 return 2 * ycoeff2; 373 default: 374 return 0; 375 } 376 } 377 378 public double nextVertical(double t0, double t1) { 379 double t = -xcoeff1 / (2 * xcoeff2); 380 if (t > t0 && t < t1) { 381 return t; 382 } 383 return t1; 384 } 385 386 public void enlarge(Rectangle2D r) { 387 r.add(x0, y0); 388 double t = -xcoeff1 / (2 * xcoeff2); 389 if (t > 0 && t < 1) { 390 r.add(XforT(t), YforT(t)); 391 } 392 r.add(x1, y1); 393 } 394 395 public Curve getSubCurve(double ystart, double yend, int dir) { 396 double t0, t1; 397 if (ystart <= y0) { 398 if (yend >= y1) { 399 return getWithDirection(dir); 400 } 401 t0 = 0; 402 } else { 403 t0 = TforY(ystart, ycoeff0, ycoeff1, ycoeff2); 404 } 405 if (yend >= y1) { 406 t1 = 1; 407 } else { 408 t1 = TforY(yend, ycoeff0, ycoeff1, ycoeff2); 409 } 410 double eqn[] = new double[10]; 411 eqn[0] = x0; 412 eqn[1] = y0; 413 eqn[2] = cx0; 414 eqn[3] = cy0; 415 eqn[4] = x1; 416 eqn[5] = y1; 417 if (t1 < 1) { 418 split(eqn, 0, t1); 419 } 420 int i; 421 if (t0 <= 0) { 422 i = 0; 423 } else { 424 split(eqn, 0, t0 / t1); 425 i = 4; 426 } 427 return new Order2(eqn[i+0], ystart, 428 eqn[i+2], eqn[i+3], 429 eqn[i+4], yend, 430 dir); 431 } 432 433 public Curve getReversedCurve() { 434 return new Order2(x0, y0, cx0, cy0, x1, y1, -direction); 435 } 436 437 public int getSegment(double coords[]) { 438 coords[0] = cx0; 439 coords[1] = cy0; 440 if (direction == INCREASING) { 441 coords[2] = x1; 442 coords[3] = y1; 443 } else { 444 coords[2] = x0; 445 coords[3] = y0; 446 } 447 return PathIterator.SEG_QUADTO; 448 } 449 450 public String controlPointString() { 451 return ("("+round(cx0)+", "+round(cy0)+"), "); 452 } 453 }