001/* QuadCurve2D.java -- represents a parameterized quadratic curve in 2-D space 002 Copyright (C) 2002, 2003, 2004 Free Software Foundation 003 004This file is part of GNU Classpath. 005 006GNU Classpath is free software; you can redistribute it and/or modify 007it under the terms of the GNU General Public License as published by 008the Free Software Foundation; either version 2, or (at your option) 009any later version. 010 011GNU Classpath is distributed in the hope that it will be useful, but 012WITHOUT ANY WARRANTY; without even the implied warranty of 013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014General Public License for more details. 015 016You should have received a copy of the GNU General Public License 017along with GNU Classpath; see the file COPYING. If not, write to the 018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 01902110-1301 USA. 020 021Linking this library statically or dynamically with other modules is 022making a combined work based on this library. Thus, the terms and 023conditions of the GNU General Public License cover the whole 024combination. 025 026As a special exception, the copyright holders of this library give you 027permission to link this library with independent modules to produce an 028executable, regardless of the license terms of these independent 029modules, and to copy and distribute the resulting executable under 030terms of your choice, provided that you also meet, for each linked 031independent module, the terms and conditions of the license of that 032module. An independent module is a module which is not derived from 033or based on this library. If you modify this library, you may extend 034this exception to your version of the library, but you are not 035obligated to do so. If you do not wish to do so, delete this 036exception statement from your version. */ 037 038package java.awt.geom; 039 040import java.awt.Rectangle; 041import java.awt.Shape; 042import java.util.NoSuchElementException; 043 044/** 045 * A two-dimensional curve that is parameterized with a quadratic 046 * function. 047 * 048 * <p><img src="doc-files/QuadCurve2D-1.png" width="350" height="180" 049 * alt="A drawing of a QuadCurve2D" /> 050 * 051 * @author Eric Blake (ebb9@email.byu.edu) 052 * @author Graydon Hoare (graydon@redhat.com) 053 * @author Sascha Brawer (brawer@dandelis.ch) 054 * @author Sven de Marothy (sven@physto.se) 055 * 056 * @since 1.2 057 */ 058public abstract class QuadCurve2D implements Shape, Cloneable 059{ 060 private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0; 061 private static final double EPSILON = 1E-10; 062 063 /** 064 * Constructs a new QuadCurve2D. Typical users will want to 065 * construct instances of a subclass, such as {@link 066 * QuadCurve2D.Float} or {@link QuadCurve2D.Double}. 067 */ 068 protected QuadCurve2D() 069 { 070 } 071 072 /** 073 * Returns the <i>x</i> coordinate of the curve’s start 074 * point. 075 */ 076 public abstract double getX1(); 077 078 /** 079 * Returns the <i>y</i> coordinate of the curve’s start 080 * point. 081 */ 082 public abstract double getY1(); 083 084 /** 085 * Returns the curve’s start point. 086 */ 087 public abstract Point2D getP1(); 088 089 /** 090 * Returns the <i>x</i> coordinate of the curve’s control 091 * point. 092 */ 093 public abstract double getCtrlX(); 094 095 /** 096 * Returns the <i>y</i> coordinate of the curve’s control 097 * point. 098 */ 099 public abstract double getCtrlY(); 100 101 /** 102 * Returns the curve’s control point. 103 */ 104 public abstract Point2D getCtrlPt(); 105 106 /** 107 * Returns the <i>x</i> coordinate of the curve’s end 108 * point. 109 */ 110 public abstract double getX2(); 111 112 /** 113 * Returns the <i>y</i> coordinate of the curve’s end 114 * point. 115 */ 116 public abstract double getY2(); 117 118 /** 119 * Returns the curve’s end point. 120 */ 121 public abstract Point2D getP2(); 122 123 /** 124 * Changes the curve geometry, separately specifying each coordinate 125 * value. 126 * 127 * @param x1 the <i>x</i> coordinate of the curve’s new start 128 * point. 129 * 130 * @param y1 the <i>y</i> coordinate of the curve’s new start 131 * point. 132 * 133 * @param cx the <i>x</i> coordinate of the curve’s new 134 * control point. 135 * 136 * @param cy the <i>y</i> coordinate of the curve’s new 137 * control point. 138 * 139 * @param x2 the <i>x</i> coordinate of the curve’s new end 140 * point. 141 * 142 * @param y2 the <i>y</i> coordinate of the curve’s new end 143 * point. 144 */ 145 public abstract void setCurve(double x1, double y1, double cx, double cy, 146 double x2, double y2); 147 148 /** 149 * Changes the curve geometry, passing coordinate values in an 150 * array. 151 * 152 * @param coords an array containing the new coordinate values. The 153 * <i>x</i> coordinate of the new start point is located at 154 * <code>coords[offset]</code>, its <i>y</i> coordinate at 155 * <code>coords[offset + 1]</code>. The <i>x</i> coordinate of the 156 * new control point is located at <code>coords[offset + 2]</code>, 157 * its <i>y</i> coordinate at <code>coords[offset + 3]</code>. The 158 * <i>x</i> coordinate of the new end point is located at 159 * <code>coords[offset + 4]</code>, its <i>y</i> coordinate at 160 * <code>coords[offset + 5]</code>. 161 * 162 * @param offset the offset of the first coordinate value in 163 * <code>coords</code>. 164 */ 165 public void setCurve(double[] coords, int offset) 166 { 167 setCurve(coords[offset++], coords[offset++], coords[offset++], 168 coords[offset++], coords[offset++], coords[offset++]); 169 } 170 171 /** 172 * Changes the curve geometry, specifying coordinate values in 173 * separate Point objects. 174 * 175 * <p><img src="doc-files/QuadCurve2D-1.png" width="350" height="180" 176 * alt="A drawing of a QuadCurve2D" /> 177 * 178 * <p>The curve does not keep any reference to the passed point 179 * objects. Therefore, a later change to <code>p1</code>, 180 * <code>c</code> <code>p2</code> will not affect the curve 181 * geometry. 182 * 183 * @param p1 the new start point. 184 * @param c the new control point. 185 * @param p2 the new end point. 186 */ 187 public void setCurve(Point2D p1, Point2D c, Point2D p2) 188 { 189 setCurve(p1.getX(), p1.getY(), c.getX(), c.getY(), p2.getX(), p2.getY()); 190 } 191 192 /** 193 * Changes the curve geometry, specifying coordinate values in an 194 * array of Point objects. 195 * 196 * <p><img src="doc-files/QuadCurve2D-1.png" width="350" height="180" 197 * alt="A drawing of a QuadCurve2D" /> 198 * 199 * <p>The curve does not keep references to the passed point 200 * objects. Therefore, a later change to the <code>pts</code> array 201 * or any of its elements will not affect the curve geometry. 202 * 203 * @param pts an array containing the points. The new start point 204 * is located at <code>pts[offset]</code>, the new control 205 * point at <code>pts[offset + 1]</code>, and the new end point 206 * at <code>pts[offset + 2]</code>. 207 * 208 * @param offset the offset of the start point in <code>pts</code>. 209 */ 210 public void setCurve(Point2D[] pts, int offset) 211 { 212 setCurve(pts[offset].getX(), pts[offset].getY(), pts[offset + 1].getX(), 213 pts[offset + 1].getY(), pts[offset + 2].getX(), 214 pts[offset + 2].getY()); 215 } 216 217 /** 218 * Changes the geometry of the curve to that of another curve. 219 * 220 * @param c the curve whose coordinates will be copied. 221 */ 222 public void setCurve(QuadCurve2D c) 223 { 224 setCurve(c.getX1(), c.getY1(), c.getCtrlX(), c.getCtrlY(), c.getX2(), 225 c.getY2()); 226 } 227 228 /** 229 * Calculates the squared flatness of a quadratic curve, directly 230 * specifying each coordinate value. The flatness is the distance of 231 * the control point to the line between start and end point. 232 * 233 * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180" 234 * alt="A drawing that illustrates the flatness" /> 235 * 236 * <p>In the above drawing, the straight line connecting start point 237 * P1 and end point P2 is depicted in gray. The result will be the 238 * the square of the distance between C and the gray line, i.e. 239 * the squared length of the red line. 240 * 241 * @param x1 the <i>x</i> coordinate of the start point P1. 242 * @param y1 the <i>y</i> coordinate of the start point P1. 243 * @param cx the <i>x</i> coordinate of the control point C. 244 * @param cy the <i>y</i> coordinate of the control point C. 245 * @param x2 the <i>x</i> coordinate of the end point P2. 246 * @param y2 the <i>y</i> coordinate of the end point P2. 247 */ 248 public static double getFlatnessSq(double x1, double y1, double cx, 249 double cy, double x2, double y2) 250 { 251 return Line2D.ptSegDistSq(x1, y1, x2, y2, cx, cy); 252 } 253 254 /** 255 * Calculates the flatness of a quadratic curve, directly specifying 256 * each coordinate value. The flatness is the distance of the 257 * control point to the line between start and end point. 258 * 259 * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180" 260 * alt="A drawing that illustrates the flatness" /> 261 * 262 * <p>In the above drawing, the straight line connecting start point 263 * P1 and end point P2 is depicted in gray. The result will be the 264 * the distance between C and the gray line, i.e. the length of 265 * the red line. 266 * 267 * @param x1 the <i>x</i> coordinate of the start point P1. 268 * @param y1 the <i>y</i> coordinate of the start point P1. 269 * @param cx the <i>x</i> coordinate of the control point C. 270 * @param cy the <i>y</i> coordinate of the control point C. 271 * @param x2 the <i>x</i> coordinate of the end point P2. 272 * @param y2 the <i>y</i> coordinate of the end point P2. 273 */ 274 public static double getFlatness(double x1, double y1, double cx, double cy, 275 double x2, double y2) 276 { 277 return Line2D.ptSegDist(x1, y1, x2, y2, cx, cy); 278 } 279 280 /** 281 * Calculates the squared flatness of a quadratic curve, specifying 282 * the coordinate values in an array. The flatness is the distance 283 * of the control point to the line between start and end point. 284 * 285 * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180" 286 * alt="A drawing that illustrates the flatness" /> 287 * 288 * <p>In the above drawing, the straight line connecting start point 289 * P1 and end point P2 is depicted in gray. The result will be the 290 * the square of the distance between C and the gray line, i.e. 291 * the squared length of the red line. 292 * 293 * @param coords an array containing the coordinate values. The 294 * <i>x</i> coordinate of the start point P1 is located at 295 * <code>coords[offset]</code>, its <i>y</i> coordinate at 296 * <code>coords[offset + 1]</code>. The <i>x</i> coordinate of the 297 * control point C is located at <code>coords[offset + 2]</code>, 298 * its <i>y</i> coordinate at <code>coords[offset + 3]</code>. The 299 * <i>x</i> coordinate of the end point P2 is located at 300 * <code>coords[offset + 4]</code>, its <i>y</i> coordinate at 301 * <code>coords[offset + 5]</code>. 302 * 303 * @param offset the offset of the first coordinate value in 304 * <code>coords</code>. 305 */ 306 public static double getFlatnessSq(double[] coords, int offset) 307 { 308 return Line2D.ptSegDistSq(coords[offset], coords[offset + 1], 309 coords[offset + 4], coords[offset + 5], 310 coords[offset + 2], coords[offset + 3]); 311 } 312 313 /** 314 * Calculates the flatness of a quadratic curve, specifying the 315 * coordinate values in an array. The flatness is the distance of 316 * the control point to the line between start and end point. 317 * 318 * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180" 319 * alt="A drawing that illustrates the flatness" /> 320 * 321 * <p>In the above drawing, the straight line connecting start point 322 * P1 and end point P2 is depicted in gray. The result will be the 323 * the the distance between C and the gray line, i.e. the length of 324 * the red line. 325 * 326 * @param coords an array containing the coordinate values. The 327 * <i>x</i> coordinate of the start point P1 is located at 328 * <code>coords[offset]</code>, its <i>y</i> coordinate at 329 * <code>coords[offset + 1]</code>. The <i>x</i> coordinate of the 330 * control point C is located at <code>coords[offset + 2]</code>, 331 * its <i>y</i> coordinate at <code>coords[offset + 3]</code>. The 332 * <i>x</i> coordinate of the end point P2 is located at 333 * <code>coords[offset + 4]</code>, its <i>y</i> coordinate at 334 * <code>coords[offset + 5]</code>. 335 * 336 * @param offset the offset of the first coordinate value in 337 * <code>coords</code>. 338 */ 339 public static double getFlatness(double[] coords, int offset) 340 { 341 return Line2D.ptSegDist(coords[offset], coords[offset + 1], 342 coords[offset + 4], coords[offset + 5], 343 coords[offset + 2], coords[offset + 3]); 344 } 345 346 /** 347 * Calculates the squared flatness of this curve. The flatness is 348 * the distance of the control point to the line between start and 349 * end point. 350 * 351 * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180" 352 * alt="A drawing that illustrates the flatness" /> 353 * 354 * <p>In the above drawing, the straight line connecting start point 355 * P1 and end point P2 is depicted in gray. The result will be the 356 * the square of the distance between C and the gray line, i.e. the 357 * squared length of the red line. 358 */ 359 public double getFlatnessSq() 360 { 361 return Line2D.ptSegDistSq(getX1(), getY1(), getX2(), getY2(), getCtrlX(), 362 getCtrlY()); 363 } 364 365 /** 366 * Calculates the flatness of this curve. The flatness is the 367 * distance of the control point to the line between start and end 368 * point. 369 * 370 * <p><img src="doc-files/QuadCurve2D-4.png" width="350" height="180" 371 * alt="A drawing that illustrates the flatness" /> 372 * 373 * <p>In the above drawing, the straight line connecting start point 374 * P1 and end point P2 is depicted in gray. The result will be the 375 * the distance between C and the gray line, i.e. the length of the 376 * red line. 377 */ 378 public double getFlatness() 379 { 380 return Line2D.ptSegDist(getX1(), getY1(), getX2(), getY2(), getCtrlX(), 381 getCtrlY()); 382 } 383 384 /** 385 * Subdivides this curve into two halves. 386 * 387 * <p><img src="doc-files/QuadCurve2D-3.png" width="700" 388 * height="180" alt="A drawing that illustrates the effects of 389 * subdividing a QuadCurve2D" /> 390 * 391 * @param left a curve whose geometry will be set to the left half 392 * of this curve, or <code>null</code> if the caller is not 393 * interested in the left half. 394 * 395 * @param right a curve whose geometry will be set to the right half 396 * of this curve, or <code>null</code> if the caller is not 397 * interested in the right half. 398 */ 399 public void subdivide(QuadCurve2D left, QuadCurve2D right) 400 { 401 // Use empty slots at end to share single array. 402 double[] d = new double[] 403 { 404 getX1(), getY1(), getCtrlX(), getCtrlY(), getX2(), getY2(), 405 0, 0, 0, 0 406 }; 407 subdivide(d, 0, d, 0, d, 4); 408 if (left != null) 409 left.setCurve(d, 0); 410 if (right != null) 411 right.setCurve(d, 4); 412 } 413 414 /** 415 * Subdivides a quadratic curve into two halves. 416 * 417 * <p><img src="doc-files/QuadCurve2D-3.png" width="700" 418 * height="180" alt="A drawing that illustrates the effects of 419 * subdividing a QuadCurve2D" /> 420 * 421 * @param src the curve to be subdivided. 422 * 423 * @param left a curve whose geometry will be set to the left half 424 * of <code>src</code>, or <code>null</code> if the caller is not 425 * interested in the left half. 426 * 427 * @param right a curve whose geometry will be set to the right half 428 * of <code>src</code>, or <code>null</code> if the caller is not 429 * interested in the right half. 430 */ 431 public static void subdivide(QuadCurve2D src, QuadCurve2D left, 432 QuadCurve2D right) 433 { 434 src.subdivide(left, right); 435 } 436 437 /** 438 * Subdivides a quadratic curve into two halves, passing all 439 * coordinates in an array. 440 * 441 * <p><img src="doc-files/QuadCurve2D-3.png" width="700" 442 * height="180" alt="A drawing that illustrates the effects of 443 * subdividing a QuadCurve2D" /> 444 * 445 * <p>The left end point and the right start point will always be 446 * identical. Memory-concious programmers thus may want to pass the 447 * same array for both <code>left</code> and <code>right</code>, and 448 * set <code>rightOff</code> to <code>leftOff + 4</code>. 449 * 450 * @param src an array containing the coordinates of the curve to be 451 * subdivided. The <i>x</i> coordinate of the start point is 452 * located at <code>src[srcOff]</code>, its <i>y</i> at 453 * <code>src[srcOff + 1]</code>. The <i>x</i> coordinate of the 454 * control point is located at <code>src[srcOff + 2]</code>, its 455 * <i>y</i> at <code>src[srcOff + 3]</code>. The <i>x</i> 456 * coordinate of the end point is located at <code>src[srcOff + 457 * 4]</code>, its <i>y</i> at <code>src[srcOff + 5]</code>. 458 * 459 * @param srcOff an offset into <code>src</code>, specifying 460 * the index of the start point’s <i>x</i> coordinate. 461 * 462 * @param left an array that will receive the coordinates of the 463 * left half of <code>src</code>. It is acceptable to pass 464 * <code>src</code>. A caller who is not interested in the left half 465 * can pass <code>null</code>. 466 * 467 * @param leftOff an offset into <code>left</code>, specifying the 468 * index where the start point’s <i>x</i> coordinate will be 469 * stored. 470 * 471 * @param right an array that will receive the coordinates of the 472 * right half of <code>src</code>. It is acceptable to pass 473 * <code>src</code> or <code>left</code>. A caller who is not 474 * interested in the right half can pass <code>null</code>. 475 * 476 * @param rightOff an offset into <code>right</code>, specifying the 477 * index where the start point’s <i>x</i> coordinate will be 478 * stored. 479 */ 480 public static void subdivide(double[] src, int srcOff, double[] left, 481 int leftOff, double[] right, int rightOff) 482 { 483 double x1; 484 double y1; 485 double xc; 486 double yc; 487 double x2; 488 double y2; 489 490 x1 = src[srcOff]; 491 y1 = src[srcOff + 1]; 492 xc = src[srcOff + 2]; 493 yc = src[srcOff + 3]; 494 x2 = src[srcOff + 4]; 495 y2 = src[srcOff + 5]; 496 497 if (left != null) 498 { 499 left[leftOff] = x1; 500 left[leftOff + 1] = y1; 501 } 502 503 if (right != null) 504 { 505 right[rightOff + 4] = x2; 506 right[rightOff + 5] = y2; 507 } 508 509 x1 = (x1 + xc) / 2; 510 x2 = (xc + x2) / 2; 511 xc = (x1 + x2) / 2; 512 y1 = (y1 + yc) / 2; 513 y2 = (y2 + yc) / 2; 514 yc = (y1 + y2) / 2; 515 516 if (left != null) 517 { 518 left[leftOff + 2] = x1; 519 left[leftOff + 3] = y1; 520 left[leftOff + 4] = xc; 521 left[leftOff + 5] = yc; 522 } 523 524 if (right != null) 525 { 526 right[rightOff] = xc; 527 right[rightOff + 1] = yc; 528 right[rightOff + 2] = x2; 529 right[rightOff + 3] = y2; 530 } 531 } 532 533 /** 534 * Finds the non-complex roots of a quadratic equation, placing the 535 * results into the same array as the equation coefficients. The 536 * following equation is being solved: 537 * 538 * <blockquote><code>eqn[2]</code> · <i>x</i><sup>2</sup> 539 * + <code>eqn[1]</code> · <i>x</i> 540 * + <code>eqn[0]</code> 541 * = 0 542 * </blockquote> 543 * 544 * <p>For some background about solving quadratic equations, see the 545 * article <a href= 546 * "http://planetmath.org/encyclopedia/QuadraticFormula.html" 547 * >“Quadratic Formula”</a> in <a href= 548 * "http://planetmath.org/">PlanetMath</a>. For an extensive library 549 * of numerical algorithms written in the C programming language, 550 * see the <a href="http://www.gnu.org/software/gsl/">GNU Scientific 551 * Library</a>. 552 * 553 * @see #solveQuadratic(double[], double[]) 554 * @see CubicCurve2D#solveCubic(double[], double[]) 555 * 556 * @param eqn an array with the coefficients of the equation. When 557 * this procedure has returned, <code>eqn</code> will contain the 558 * non-complex solutions of the equation, in no particular order. 559 * 560 * @return the number of non-complex solutions. A result of 0 561 * indicates that the equation has no non-complex solutions. A 562 * result of -1 indicates that the equation is constant (i.e., 563 * always or never zero). 564 * 565 * @author Brian Gough (bjg@network-theory.com) 566 * (original C implementation in the <a href= 567 * "http://www.gnu.org/software/gsl/">GNU Scientific Library</a>) 568 * 569 * @author Sascha Brawer (brawer@dandelis.ch) 570 * (adaptation to Java) 571 */ 572 public static int solveQuadratic(double[] eqn) 573 { 574 return solveQuadratic(eqn, eqn); 575 } 576 577 /** 578 * Finds the non-complex roots of a quadratic equation. The 579 * following equation is being solved: 580 * 581 * <blockquote><code>eqn[2]</code> · <i>x</i><sup>2</sup> 582 * + <code>eqn[1]</code> · <i>x</i> 583 * + <code>eqn[0]</code> 584 * = 0 585 * </blockquote> 586 * 587 * <p>For some background about solving quadratic equations, see the 588 * article <a href= 589 * "http://planetmath.org/encyclopedia/QuadraticFormula.html" 590 * >“Quadratic Formula”</a> in <a href= 591 * "http://planetmath.org/">PlanetMath</a>. For an extensive library 592 * of numerical algorithms written in the C programming language, 593 * see the <a href="http://www.gnu.org/software/gsl/">GNU Scientific 594 * Library</a>. 595 * 596 * @see CubicCurve2D#solveCubic(double[],double[]) 597 * 598 * @param eqn an array with the coefficients of the equation. 599 * 600 * @param res an array into which the non-complex roots will be 601 * stored. The results may be in an arbitrary order. It is safe to 602 * pass the same array object reference for both <code>eqn</code> 603 * and <code>res</code>. 604 * 605 * @return the number of non-complex solutions. A result of 0 606 * indicates that the equation has no non-complex solutions. A 607 * result of -1 indicates that the equation is constant (i.e., 608 * always or never zero). 609 * 610 * @author Brian Gough (bjg@network-theory.com) 611 * (original C implementation in the <a href= 612 * "http://www.gnu.org/software/gsl/">GNU Scientific Library</a>) 613 * 614 * @author Sascha Brawer (brawer@dandelis.ch) 615 * (adaptation to Java) 616 */ 617 public static int solveQuadratic(double[] eqn, double[] res) 618 { 619 // Taken from poly/solve_quadratic.c in the GNU Scientific Library 620 // (GSL), cvs revision 1.7 of 2003-07-26. For the original source, 621 // see http://www.gnu.org/software/gsl/ 622 // 623 // Brian Gough, the author of that code, has granted the 624 // permission to use it in GNU Classpath under the GNU Classpath 625 // license, and has assigned the copyright to the Free Software 626 // Foundation. 627 // 628 // The Java implementation is very similar to the GSL code, but 629 // not a strict one-to-one copy. For example, GSL would sort the 630 // result. 631 double a; 632 double b; 633 double c; 634 double disc; 635 636 c = eqn[0]; 637 b = eqn[1]; 638 a = eqn[2]; 639 640 // Check for linear or constant functions. This is not done by the 641 // GNU Scientific Library. Without this special check, we 642 // wouldn't return -1 for constant functions, and 2 instead of 1 643 // for linear functions. 644 if (a == 0) 645 { 646 if (b == 0) 647 return -1; 648 649 res[0] = -c / b; 650 return 1; 651 } 652 653 disc = b * b - 4 * a * c; 654 655 if (disc < 0) 656 return 0; 657 658 if (disc == 0) 659 { 660 // The GNU Scientific Library returns two identical results here. 661 // We just return one. 662 res[0] = -0.5 * b / a; 663 return 1; 664 } 665 666 // disc > 0 667 if (b == 0) 668 { 669 double r; 670 671 r = Math.abs(0.5 * Math.sqrt(disc) / a); 672 res[0] = -r; 673 res[1] = r; 674 } 675 else 676 { 677 double sgnb; 678 double temp; 679 680 sgnb = (b > 0 ? 1 : -1); 681 temp = -0.5 * (b + sgnb * Math.sqrt(disc)); 682 683 // The GNU Scientific Library sorts the result here. We don't. 684 res[0] = temp / a; 685 res[1] = c / temp; 686 } 687 return 2; 688 } 689 690 /** 691 * Determines whether a point is inside the area bounded 692 * by the curve and the straight line connecting its end points. 693 * 694 * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180" 695 * alt="A drawing of the area spanned by the curve" /> 696 * 697 * <p>The above drawing illustrates in which area points are 698 * considered “inside” a QuadCurve2D. 699 */ 700 public boolean contains(double x, double y) 701 { 702 if (! getBounds2D().contains(x, y)) 703 return false; 704 705 return ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0); 706 } 707 708 /** 709 * Determines whether a point is inside the area bounded 710 * by the curve and the straight line connecting its end points. 711 * 712 * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180" 713 * alt="A drawing of the area spanned by the curve" /> 714 * 715 * <p>The above drawing illustrates in which area points are 716 * considered “inside” a QuadCurve2D. 717 */ 718 public boolean contains(Point2D p) 719 { 720 return contains(p.getX(), p.getY()); 721 } 722 723 /** 724 * Determines whether any part of a rectangle is inside the area bounded 725 * by the curve and the straight line connecting its end points. 726 * 727 * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180" 728 * alt="A drawing of the area spanned by the curve" /> 729 * 730 * <p>The above drawing illustrates in which area points are 731 * considered “inside” in a CubicCurve2D. 732 */ 733 public boolean intersects(double x, double y, double w, double h) 734 { 735 if (! getBounds2D().contains(x, y, w, h)) 736 return false; 737 738 /* Does any edge intersect? */ 739 if (getAxisIntersections(x, y, true, w) != 0 /* top */ 740 || getAxisIntersections(x, y + h, true, w) != 0 /* bottom */ 741 || getAxisIntersections(x + w, y, false, h) != 0 /* right */ 742 || getAxisIntersections(x, y, false, h) != 0) /* left */ 743 return true; 744 745 /* No intersections, is any point inside? */ 746 if ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0) 747 return true; 748 749 return false; 750 } 751 752 /** 753 * Determines whether any part of a Rectangle2D is inside the area bounded 754 * by the curve and the straight line connecting its end points. 755 * @see #intersects(double, double, double, double) 756 */ 757 public boolean intersects(Rectangle2D r) 758 { 759 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 760 } 761 762 /** 763 * Determines whether a rectangle is entirely inside the area bounded 764 * by the curve and the straight line connecting its end points. 765 * 766 * <p><img src="doc-files/QuadCurve2D-5.png" width="350" height="180" 767 * alt="A drawing of the area spanned by the curve" /> 768 * 769 * <p>The above drawing illustrates in which area points are 770 * considered “inside” a QuadCurve2D. 771 * @see #contains(double, double) 772 */ 773 public boolean contains(double x, double y, double w, double h) 774 { 775 if (! getBounds2D().intersects(x, y, w, h)) 776 return false; 777 778 /* Does any edge intersect? */ 779 if (getAxisIntersections(x, y, true, w) != 0 /* top */ 780 || getAxisIntersections(x, y + h, true, w) != 0 /* bottom */ 781 || getAxisIntersections(x + w, y, false, h) != 0 /* right */ 782 || getAxisIntersections(x, y, false, h) != 0) /* left */ 783 return false; 784 785 /* No intersections, is any point inside? */ 786 if ((getAxisIntersections(x, y, true, BIG_VALUE) & 1) != 0) 787 return true; 788 789 return false; 790 } 791 792 /** 793 * Determines whether a Rectangle2D is entirely inside the area that is 794 * bounded by the curve and the straight line connecting its end points. 795 * @see #contains(double, double, double, double) 796 */ 797 public boolean contains(Rectangle2D r) 798 { 799 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 800 } 801 802 /** 803 * Determines the smallest rectangle that encloses the 804 * curve’s start, end and control point. As the illustration 805 * below shows, the invisible control point may cause the bounds to 806 * be much larger than the area that is actually covered by the 807 * curve. 808 * 809 * <p><img src="doc-files/QuadCurve2D-2.png" width="350" height="180" 810 * alt="An illustration of the bounds of a QuadCurve2D" /> 811 */ 812 public Rectangle getBounds() 813 { 814 return getBounds2D().getBounds(); 815 } 816 817 public PathIterator getPathIterator(final AffineTransform at) 818 { 819 return new PathIterator() 820 { 821 /** Current coordinate. */ 822 private int current = 0; 823 824 public int getWindingRule() 825 { 826 return WIND_NON_ZERO; 827 } 828 829 public boolean isDone() 830 { 831 return current >= 2; 832 } 833 834 public void next() 835 { 836 current++; 837 } 838 839 public int currentSegment(float[] coords) 840 { 841 int result; 842 switch (current) 843 { 844 case 0: 845 coords[0] = (float) getX1(); 846 coords[1] = (float) getY1(); 847 result = SEG_MOVETO; 848 break; 849 case 1: 850 coords[0] = (float) getCtrlX(); 851 coords[1] = (float) getCtrlY(); 852 coords[2] = (float) getX2(); 853 coords[3] = (float) getY2(); 854 result = SEG_QUADTO; 855 break; 856 default: 857 throw new NoSuchElementException("quad iterator out of bounds"); 858 } 859 if (at != null) 860 at.transform(coords, 0, coords, 0, 2); 861 return result; 862 } 863 864 public int currentSegment(double[] coords) 865 { 866 int result; 867 switch (current) 868 { 869 case 0: 870 coords[0] = getX1(); 871 coords[1] = getY1(); 872 result = SEG_MOVETO; 873 break; 874 case 1: 875 coords[0] = getCtrlX(); 876 coords[1] = getCtrlY(); 877 coords[2] = getX2(); 878 coords[3] = getY2(); 879 result = SEG_QUADTO; 880 break; 881 default: 882 throw new NoSuchElementException("quad iterator out of bounds"); 883 } 884 if (at != null) 885 at.transform(coords, 0, coords, 0, 2); 886 return result; 887 } 888 }; 889 } 890 891 public PathIterator getPathIterator(AffineTransform at, double flatness) 892 { 893 return new FlatteningPathIterator(getPathIterator(at), flatness); 894 } 895 896 /** 897 * Creates a new curve with the same contents as this one. 898 * 899 * @return the clone. 900 */ 901 public Object clone() 902 { 903 try 904 { 905 return super.clone(); 906 } 907 catch (CloneNotSupportedException e) 908 { 909 throw (Error) new InternalError().initCause(e); // Impossible 910 } 911 } 912 913 /** 914 * Helper method used by contains() and intersects() methods 915 * Return the number of curve/line intersections on a given axis 916 * extending from a certain point. useYaxis is true for using the Y axis, 917 * @param x x coordinate of the origin point 918 * @param y y coordinate of the origin point 919 * @param useYaxis axis to follow, if true the positive Y axis is used, 920 * false uses the positive X axis. 921 * 922 * This is an implementation of the line-crossings algorithm, 923 * Detailed in an article on Eric Haines' page: 924 * http://www.acm.org/tog/editors/erich/ptinpoly/ 925 */ 926 private int getAxisIntersections(double x, double y, boolean useYaxis, 927 double distance) 928 { 929 int nCrossings = 0; 930 double a0; 931 double a1; 932 double a2; 933 double b0; 934 double b1; 935 double b2; 936 double[] r = new double[3]; 937 int nRoots; 938 939 a0 = a2 = 0.0; 940 941 if (useYaxis) 942 { 943 a0 = getY1() - y; 944 a1 = getCtrlY() - y; 945 a2 = getY2() - y; 946 b0 = getX1() - x; 947 b1 = getCtrlX() - x; 948 b2 = getX2() - x; 949 } 950 else 951 { 952 a0 = getX1() - x; 953 a1 = getCtrlX() - x; 954 a2 = getX2() - x; 955 b0 = getY1() - y; 956 b1 = getCtrlY() - y; 957 b2 = getY2() - y; 958 } 959 960 /* If the axis intersects a start/endpoint, shift it up by some small 961 amount to guarantee the line is 'inside' 962 If this is not done,bad behaviour may result for points on that axis. */ 963 if (a0 == 0.0 || a2 == 0.0) 964 { 965 double small = getFlatness() * EPSILON; 966 if (a0 == 0.0) 967 a0 -= small; 968 969 if (a2 == 0.0) 970 a2 -= small; 971 } 972 973 r[0] = a0; 974 r[1] = 2 * (a1 - a0); 975 r[2] = (a2 - 2 * a1 + a0); 976 977 nRoots = solveQuadratic(r); 978 for (int i = 0; i < nRoots; i++) 979 { 980 double t = r[i]; 981 if (t >= 0.0 && t <= 1.0) 982 { 983 double crossing = t * t * (b2 - 2 * b1 + b0) + 2 * t * (b1 - b0) 984 + b0; 985 /* single root is always doubly degenerate in quads */ 986 if (crossing > 0 && crossing < distance) 987 nCrossings += (nRoots == 1) ? 2 : 1; 988 } 989 } 990 991 if (useYaxis) 992 { 993 if (Line2D.linesIntersect(b0, a0, b2, a2, EPSILON, 0.0, distance, 0.0)) 994 nCrossings++; 995 } 996 else 997 { 998 if (Line2D.linesIntersect(a0, b0, a2, b2, 0.0, EPSILON, 0.0, distance)) 999 nCrossings++; 1000 } 1001 1002 return (nCrossings); 1003 } 1004 1005 /** 1006 * A two-dimensional curve that is parameterized with a quadratic 1007 * function and stores coordinate values in double-precision 1008 * floating-point format. 1009 * 1010 * @see QuadCurve2D.Float 1011 * 1012 * @author Eric Blake (ebb9@email.byu.edu) 1013 * @author Sascha Brawer (brawer@dandelis.ch) 1014 */ 1015 public static class Double extends QuadCurve2D 1016 { 1017 /** 1018 * The <i>x</i> coordinate of the curve’s start point. 1019 */ 1020 public double x1; 1021 1022 /** 1023 * The <i>y</i> coordinate of the curve’s start point. 1024 */ 1025 public double y1; 1026 1027 /** 1028 * The <i>x</i> coordinate of the curve’s control point. 1029 */ 1030 public double ctrlx; 1031 1032 /** 1033 * The <i>y</i> coordinate of the curve’s control point. 1034 */ 1035 public double ctrly; 1036 1037 /** 1038 * The <i>x</i> coordinate of the curve’s end point. 1039 */ 1040 public double x2; 1041 1042 /** 1043 * The <i>y</i> coordinate of the curve’s end point. 1044 */ 1045 public double y2; 1046 1047 /** 1048 * Constructs a new QuadCurve2D that stores its coordinate values 1049 * in double-precision floating-point format. All points are 1050 * initially at position (0, 0). 1051 */ 1052 public Double() 1053 { 1054 } 1055 1056 /** 1057 * Constructs a new QuadCurve2D that stores its coordinate values 1058 * in double-precision floating-point format, specifying the 1059 * initial position of each point. 1060 * 1061 * @param x1 the <i>x</i> coordinate of the curve’s start 1062 * point. 1063 * 1064 * @param y1 the <i>y</i> coordinate of the curve’s start 1065 * point. 1066 * 1067 * @param cx the <i>x</i> coordinate of the curve’s control 1068 * point. 1069 * 1070 * @param cy the <i>y</i> coordinate of the curve’s control 1071 * point. 1072 * 1073 * @param x2 the <i>x</i> coordinate of the curve’s end 1074 * point. 1075 * 1076 * @param y2 the <i>y</i> coordinate of the curve’s end 1077 * point. 1078 */ 1079 public Double(double x1, double y1, double cx, double cy, double x2, 1080 double y2) 1081 { 1082 this.x1 = x1; 1083 this.y1 = y1; 1084 ctrlx = cx; 1085 ctrly = cy; 1086 this.x2 = x2; 1087 this.y2 = y2; 1088 } 1089 1090 /** 1091 * Returns the <i>x</i> coordinate of the curve’s start 1092 * point. 1093 */ 1094 public double getX1() 1095 { 1096 return x1; 1097 } 1098 1099 /** 1100 * Returns the <i>y</i> coordinate of the curve’s start 1101 * point. 1102 */ 1103 public double getY1() 1104 { 1105 return y1; 1106 } 1107 1108 /** 1109 * Returns the curve’s start point. 1110 */ 1111 public Point2D getP1() 1112 { 1113 return new Point2D.Double(x1, y1); 1114 } 1115 1116 /** 1117 * Returns the <i>x</i> coordinate of the curve’s control 1118 * point. 1119 */ 1120 public double getCtrlX() 1121 { 1122 return ctrlx; 1123 } 1124 1125 /** 1126 * Returns the <i>y</i> coordinate of the curve’s control 1127 * point. 1128 */ 1129 public double getCtrlY() 1130 { 1131 return ctrly; 1132 } 1133 1134 /** 1135 * Returns the curve’s control point. 1136 */ 1137 public Point2D getCtrlPt() 1138 { 1139 return new Point2D.Double(ctrlx, ctrly); 1140 } 1141 1142 /** 1143 * Returns the <i>x</i> coordinate of the curve’s end 1144 * point. 1145 */ 1146 public double getX2() 1147 { 1148 return x2; 1149 } 1150 1151 /** 1152 * Returns the <i>y</i> coordinate of the curve’s end 1153 * point. 1154 */ 1155 public double getY2() 1156 { 1157 return y2; 1158 } 1159 1160 /** 1161 * Returns the curve’s end point. 1162 */ 1163 public Point2D getP2() 1164 { 1165 return new Point2D.Double(x2, y2); 1166 } 1167 1168 /** 1169 * Changes the geometry of the curve. 1170 * 1171 * @param x1 the <i>x</i> coordinate of the curve’s new 1172 * start point. 1173 * 1174 * @param y1 the <i>y</i> coordinate of the curve’s new 1175 * start point. 1176 * 1177 * @param cx the <i>x</i> coordinate of the curve’s new 1178 * control point. 1179 * 1180 * @param cy the <i>y</i> coordinate of the curve’s new 1181 * control point. 1182 * 1183 * @param x2 the <i>x</i> coordinate of the curve’s new 1184 * end point. 1185 * 1186 * @param y2 the <i>y</i> coordinate of the curve’s new 1187 * end point. 1188 */ 1189 public void setCurve(double x1, double y1, double cx, double cy, 1190 double x2, double y2) 1191 { 1192 this.x1 = x1; 1193 this.y1 = y1; 1194 ctrlx = cx; 1195 ctrly = cy; 1196 this.x2 = x2; 1197 this.y2 = y2; 1198 } 1199 1200 /** 1201 * Determines the smallest rectangle that encloses the 1202 * curve’s start, end and control point. As the 1203 * illustration below shows, the invisible control point may cause 1204 * the bounds to be much larger than the area that is actually 1205 * covered by the curve. 1206 * 1207 * <p><img src="doc-files/QuadCurve2D-2.png" width="350" height="180" 1208 * alt="An illustration of the bounds of a QuadCurve2D" /> 1209 */ 1210 public Rectangle2D getBounds2D() 1211 { 1212 double nx1 = Math.min(Math.min(x1, ctrlx), x2); 1213 double ny1 = Math.min(Math.min(y1, ctrly), y2); 1214 double nx2 = Math.max(Math.max(x1, ctrlx), x2); 1215 double ny2 = Math.max(Math.max(y1, ctrly), y2); 1216 return new Rectangle2D.Double(nx1, ny1, nx2 - nx1, ny2 - ny1); 1217 } 1218 } 1219 1220 /** 1221 * A two-dimensional curve that is parameterized with a quadratic 1222 * function and stores coordinate values in single-precision 1223 * floating-point format. 1224 * 1225 * @see QuadCurve2D.Double 1226 * 1227 * @author Eric Blake (ebb9@email.byu.edu) 1228 * @author Sascha Brawer (brawer@dandelis.ch) 1229 */ 1230 public static class Float extends QuadCurve2D 1231 { 1232 /** 1233 * The <i>x</i> coordinate of the curve’s start point. 1234 */ 1235 public float x1; 1236 1237 /** 1238 * The <i>y</i> coordinate of the curve’s start point. 1239 */ 1240 public float y1; 1241 1242 /** 1243 * The <i>x</i> coordinate of the curve’s control point. 1244 */ 1245 public float ctrlx; 1246 1247 /** 1248 * The <i>y</i> coordinate of the curve’s control point. 1249 */ 1250 public float ctrly; 1251 1252 /** 1253 * The <i>x</i> coordinate of the curve’s end point. 1254 */ 1255 public float x2; 1256 1257 /** 1258 * The <i>y</i> coordinate of the curve’s end point. 1259 */ 1260 public float y2; 1261 1262 /** 1263 * Constructs a new QuadCurve2D that stores its coordinate values 1264 * in single-precision floating-point format. All points are 1265 * initially at position (0, 0). 1266 */ 1267 public Float() 1268 { 1269 } 1270 1271 /** 1272 * Constructs a new QuadCurve2D that stores its coordinate values 1273 * in single-precision floating-point format, specifying the 1274 * initial position of each point. 1275 * 1276 * @param x1 the <i>x</i> coordinate of the curve’s start 1277 * point. 1278 * 1279 * @param y1 the <i>y</i> coordinate of the curve’s start 1280 * point. 1281 * 1282 * @param cx the <i>x</i> coordinate of the curve’s control 1283 * point. 1284 * 1285 * @param cy the <i>y</i> coordinate of the curve’s control 1286 * point. 1287 * 1288 * @param x2 the <i>x</i> coordinate of the curve’s end 1289 * point. 1290 * 1291 * @param y2 the <i>y</i> coordinate of the curve’s end 1292 * point. 1293 */ 1294 public Float(float x1, float y1, float cx, float cy, float x2, float y2) 1295 { 1296 this.x1 = x1; 1297 this.y1 = y1; 1298 ctrlx = cx; 1299 ctrly = cy; 1300 this.x2 = x2; 1301 this.y2 = y2; 1302 } 1303 1304 /** 1305 * Returns the <i>x</i> coordinate of the curve’s start 1306 * point. 1307 */ 1308 public double getX1() 1309 { 1310 return x1; 1311 } 1312 1313 /** 1314 * Returns the <i>y</i> coordinate of the curve’s start 1315 * point. 1316 */ 1317 public double getY1() 1318 { 1319 return y1; 1320 } 1321 1322 /** 1323 * Returns the curve’s start point. 1324 */ 1325 public Point2D getP1() 1326 { 1327 return new Point2D.Float(x1, y1); 1328 } 1329 1330 /** 1331 * Returns the <i>x</i> coordinate of the curve’s control 1332 * point. 1333 */ 1334 public double getCtrlX() 1335 { 1336 return ctrlx; 1337 } 1338 1339 /** 1340 * Returns the <i>y</i> coordinate of the curve’s control 1341 * point. 1342 */ 1343 public double getCtrlY() 1344 { 1345 return ctrly; 1346 } 1347 1348 /** 1349 * Returns the curve’s control point. 1350 */ 1351 public Point2D getCtrlPt() 1352 { 1353 return new Point2D.Float(ctrlx, ctrly); 1354 } 1355 1356 /** 1357 * Returns the <i>x</i> coordinate of the curve’s end 1358 * point. 1359 */ 1360 public double getX2() 1361 { 1362 return x2; 1363 } 1364 1365 /** 1366 * Returns the <i>y</i> coordinate of the curve’s end 1367 * point. 1368 */ 1369 public double getY2() 1370 { 1371 return y2; 1372 } 1373 1374 /** 1375 * Returns the curve’s end point. 1376 */ 1377 public Point2D getP2() 1378 { 1379 return new Point2D.Float(x2, y2); 1380 } 1381 1382 /** 1383 * Changes the geometry of the curve, specifying coordinate values 1384 * as double-precision floating-point numbers. 1385 * 1386 * @param x1 the <i>x</i> coordinate of the curve’s new 1387 * start point. 1388 * 1389 * @param y1 the <i>y</i> coordinate of the curve’s new 1390 * start point. 1391 * 1392 * @param cx the <i>x</i> coordinate of the curve’s new 1393 * control point. 1394 * 1395 * @param cy the <i>y</i> coordinate of the curve’s new 1396 * control point. 1397 * 1398 * @param x2 the <i>x</i> coordinate of the curve’s new 1399 * end point. 1400 * 1401 * @param y2 the <i>y</i> coordinate of the curve’s new 1402 * end point. 1403 */ 1404 public void setCurve(double x1, double y1, double cx, double cy, 1405 double x2, double y2) 1406 { 1407 this.x1 = (float) x1; 1408 this.y1 = (float) y1; 1409 ctrlx = (float) cx; 1410 ctrly = (float) cy; 1411 this.x2 = (float) x2; 1412 this.y2 = (float) y2; 1413 } 1414 1415 /** 1416 * Changes the geometry of the curve, specifying coordinate values 1417 * as single-precision floating-point numbers. 1418 * 1419 * @param x1 the <i>x</i> coordinate of the curve’s new 1420 * start point. 1421 * 1422 * @param y1 the <i>y</i> coordinate of the curve’s new 1423 * start point. 1424 * 1425 * @param cx the <i>x</i> coordinate of the curve’s new 1426 * control point. 1427 * 1428 * @param cy the <i>y</i> coordinate of the curve’s new 1429 * control point. 1430 * 1431 * @param x2 the <i>x</i> coordinate of the curve’s new 1432 * end point. 1433 * 1434 * @param y2 the <i>y</i> coordinate of the curve’s new 1435 * end point. 1436 */ 1437 public void setCurve(float x1, float y1, float cx, float cy, float x2, 1438 float y2) 1439 { 1440 this.x1 = x1; 1441 this.y1 = y1; 1442 ctrlx = cx; 1443 ctrly = cy; 1444 this.x2 = x2; 1445 this.y2 = y2; 1446 } 1447 1448 /** 1449 * Determines the smallest rectangle that encloses the 1450 * curve’s start, end and control point. As the 1451 * illustration below shows, the invisible control point may cause 1452 * the bounds to be much larger than the area that is actually 1453 * covered by the curve. 1454 * 1455 * <p><img src="doc-files/QuadCurve2D-2.png" width="350" height="180" 1456 * alt="An illustration of the bounds of a QuadCurve2D" /> 1457 */ 1458 public Rectangle2D getBounds2D() 1459 { 1460 float nx1 = Math.min(Math.min(x1, ctrlx), x2); 1461 float ny1 = Math.min(Math.min(y1, ctrly), y2); 1462 float nx2 = Math.max(Math.max(x1, ctrlx), x2); 1463 float ny2 = Math.max(Math.max(y1, ctrly), y2); 1464 return new Rectangle2D.Float(nx1, ny1, nx2 - nx1, ny2 - ny1); 1465 } 1466 } 1467}