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 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 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 }