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 23 * questions. 24 */ 25 26 package java.awt.geom; 27 28 import java.awt.Shape; 29 import java.awt.Rectangle; 30 import java.io.Serializable; 31 import sun.awt.geom.Curve; 32 33 /** 34 * The {@code QuadCurve2D} class defines a quadratic parametric curve 35 * segment in {@code (x,y)} coordinate space. 36 * <p> 37 * This class is only the abstract superclass for all objects that 38 * store a 2D quadratic curve segment. 39 * The actual storage representation of the coordinates is left to 40 * the subclass. 41 * 42 * @author Jim Graham 43 * @since 1.2 44 */ 45 public abstract class QuadCurve2D implements Shape, Cloneable { 46 47 /** 48 * A quadratic parametric curve segment specified with 49 * {@code float} coordinates. 50 * 51 * @since 1.2 52 */ 53 public static class Float extends QuadCurve2D implements Serializable { 54 /** 55 * The X coordinate of the start point of the quadratic curve 56 * segment. 57 * @since 1.2 58 * @serial 59 */ 60 public float x1; 61 62 /** 63 * The Y coordinate of the start point of the quadratic curve 64 * segment. 65 * @since 1.2 66 * @serial 67 */ 68 public float y1; 69 70 /** 71 * The X coordinate of the control point of the quadratic curve 72 * segment. 73 * @since 1.2 74 * @serial 75 */ 76 public float ctrlx; 77 78 /** 79 * The Y coordinate of the control point of the quadratic curve 80 * segment. 81 * @since 1.2 82 * @serial 83 */ 84 public float ctrly; 85 86 /** 87 * The X coordinate of the end point of the quadratic curve 88 * segment. 89 * @since 1.2 90 * @serial 91 */ 92 public float x2; 93 94 /** 95 * The Y coordinate of the end point of the quadratic curve 96 * segment. 97 * @since 1.2 98 * @serial 99 */ 100 public float y2; 101 102 /** 103 * Constructs and initializes a {@code QuadCurve2D} with 104 * coordinates (0, 0, 0, 0, 0, 0). 105 * @since 1.2 106 */ 107 public Float() { 108 } 109 110 /** 111 * Constructs and initializes a {@code QuadCurve2D} from the 112 * specified {@code float} coordinates. 113 * 114 * @param x1 the X coordinate of the start point 115 * @param y1 the Y coordinate of the start point 116 * @param ctrlx the X coordinate of the control point 117 * @param ctrly the Y coordinate of the control point 118 * @param x2 the X coordinate of the end point 119 * @param y2 the Y coordinate of the end point 120 * @since 1.2 121 */ 122 public Float(float x1, float y1, 123 float ctrlx, float ctrly, 124 float x2, float y2) 125 { 126 setCurve(x1, y1, ctrlx, ctrly, x2, y2); 127 } 128 129 /** 130 * {@inheritDoc} 131 * @since 1.2 132 */ 133 public double getX1() { 134 return (double) x1; 135 } 136 137 /** 138 * {@inheritDoc} 139 * @since 1.2 140 */ 141 public double getY1() { 142 return (double) y1; 143 } 144 145 /** 146 * {@inheritDoc} 147 * @since 1.2 148 */ 149 public Point2D getP1() { 150 return new Point2D.Float(x1, y1); 151 } 152 153 /** 154 * {@inheritDoc} 155 * @since 1.2 156 */ 157 public double getCtrlX() { 158 return (double) ctrlx; 159 } 160 161 /** 162 * {@inheritDoc} 163 * @since 1.2 164 */ 165 public double getCtrlY() { 166 return (double) ctrly; 167 } 168 169 /** 170 * {@inheritDoc} 171 * @since 1.2 172 */ 173 public Point2D getCtrlPt() { 174 return new Point2D.Float(ctrlx, ctrly); 175 } 176 177 /** 178 * {@inheritDoc} 179 * @since 1.2 180 */ 181 public double getX2() { 182 return (double) x2; 183 } 184 185 /** 186 * {@inheritDoc} 187 * @since 1.2 188 */ 189 public double getY2() { 190 return (double) y2; 191 } 192 193 /** 194 * {@inheritDoc} 195 * @since 1.2 196 */ 197 public Point2D getP2() { 198 return new Point2D.Float(x2, y2); 199 } 200 201 /** 202 * {@inheritDoc} 203 * @since 1.2 204 */ 205 public void setCurve(double x1, double y1, 206 double ctrlx, double ctrly, 207 double x2, double y2) 208 { 209 this.x1 = (float) x1; 210 this.y1 = (float) y1; 211 this.ctrlx = (float) ctrlx; 212 this.ctrly = (float) ctrly; 213 this.x2 = (float) x2; 214 this.y2 = (float) y2; 215 } 216 217 /** 218 * Sets the location of the end points and control point of this curve 219 * to the specified {@code float} coordinates. 220 * 221 * @param x1 the X coordinate of the start point 222 * @param y1 the Y coordinate of the start point 223 * @param ctrlx the X coordinate of the control point 224 * @param ctrly the Y coordinate of the control point 225 * @param x2 the X coordinate of the end point 226 * @param y2 the Y coordinate of the end point 227 * @since 1.2 228 */ 229 public void setCurve(float x1, float y1, 230 float ctrlx, float ctrly, 231 float x2, float y2) 232 { 233 this.x1 = x1; 234 this.y1 = y1; 235 this.ctrlx = ctrlx; 236 this.ctrly = ctrly; 237 this.x2 = x2; 238 this.y2 = y2; 239 } 240 241 /** 242 * {@inheritDoc} 243 * @since 1.2 244 */ 245 public Rectangle2D getBounds2D() { 246 float left = Math.min(Math.min(x1, x2), ctrlx); 247 float top = Math.min(Math.min(y1, y2), ctrly); 248 float right = Math.max(Math.max(x1, x2), ctrlx); 249 float bottom = Math.max(Math.max(y1, y2), ctrly); 250 return new Rectangle2D.Float(left, top, 251 right - left, bottom - top); 252 } 253 254 /* 255 * JDK 1.6 serialVersionUID 256 */ 257 private static final long serialVersionUID = -8511188402130719609L; 258 } 259 260 /** 261 * A quadratic parametric curve segment specified with 262 * {@code double} coordinates. 263 * 264 * @since 1.2 265 */ 266 public static class Double extends QuadCurve2D implements Serializable { 267 /** 268 * The X coordinate of the start point of the quadratic curve 269 * segment. 270 * @since 1.2 271 * @serial 272 */ 273 public double x1; 274 275 /** 276 * The Y coordinate of the start point of the quadratic curve 277 * segment. 278 * @since 1.2 279 * @serial 280 */ 281 public double y1; 282 283 /** 284 * The X coordinate of the control point of the quadratic curve 285 * segment. 286 * @since 1.2 287 * @serial 288 */ 289 public double ctrlx; 290 291 /** 292 * The Y coordinate of the control point of the quadratic curve 293 * segment. 294 * @since 1.2 295 * @serial 296 */ 297 public double ctrly; 298 299 /** 300 * The X coordinate of the end point of the quadratic curve 301 * segment. 302 * @since 1.2 303 * @serial 304 */ 305 public double x2; 306 307 /** 308 * The Y coordinate of the end point of the quadratic curve 309 * segment. 310 * @since 1.2 311 * @serial 312 */ 313 public double y2; 314 315 /** 316 * Constructs and initializes a {@code QuadCurve2D} with 317 * coordinates (0, 0, 0, 0, 0, 0). 318 * @since 1.2 319 */ 320 public Double() { 321 } 322 323 /** 324 * Constructs and initializes a {@code QuadCurve2D} from the 325 * specified {@code double} coordinates. 326 * 327 * @param x1 the X coordinate of the start point 328 * @param y1 the Y coordinate of the start point 329 * @param ctrlx the X coordinate of the control point 330 * @param ctrly the Y coordinate of the control point 331 * @param x2 the X coordinate of the end point 332 * @param y2 the Y coordinate of the end point 333 * @since 1.2 334 */ 335 public Double(double x1, double y1, 336 double ctrlx, double ctrly, 337 double x2, double y2) 338 { 339 setCurve(x1, y1, ctrlx, ctrly, x2, y2); 340 } 341 342 /** 343 * {@inheritDoc} 344 * @since 1.2 345 */ 346 public double getX1() { 347 return x1; 348 } 349 350 /** 351 * {@inheritDoc} 352 * @since 1.2 353 */ 354 public double getY1() { 355 return y1; 356 } 357 358 /** 359 * {@inheritDoc} 360 * @since 1.2 361 */ 362 public Point2D getP1() { 363 return new Point2D.Double(x1, y1); 364 } 365 366 /** 367 * {@inheritDoc} 368 * @since 1.2 369 */ 370 public double getCtrlX() { 371 return ctrlx; 372 } 373 374 /** 375 * {@inheritDoc} 376 * @since 1.2 377 */ 378 public double getCtrlY() { 379 return ctrly; 380 } 381 382 /** 383 * {@inheritDoc} 384 * @since 1.2 385 */ 386 public Point2D getCtrlPt() { 387 return new Point2D.Double(ctrlx, ctrly); 388 } 389 390 /** 391 * {@inheritDoc} 392 * @since 1.2 393 */ 394 public double getX2() { 395 return x2; 396 } 397 398 /** 399 * {@inheritDoc} 400 * @since 1.2 401 */ 402 public double getY2() { 403 return y2; 404 } 405 406 /** 407 * {@inheritDoc} 408 * @since 1.2 409 */ 410 public Point2D getP2() { 411 return new Point2D.Double(x2, y2); 412 } 413 414 /** 415 * {@inheritDoc} 416 * @since 1.2 417 */ 418 public void setCurve(double x1, double y1, 419 double ctrlx, double ctrly, 420 double x2, double y2) 421 { 422 this.x1 = x1; 423 this.y1 = y1; 424 this.ctrlx = ctrlx; 425 this.ctrly = ctrly; 426 this.x2 = x2; 427 this.y2 = y2; 428 } 429 430 /** 431 * {@inheritDoc} 432 * @since 1.2 433 */ 434 public Rectangle2D getBounds2D() { 435 double left = Math.min(Math.min(x1, x2), ctrlx); 436 double top = Math.min(Math.min(y1, y2), ctrly); 437 double right = Math.max(Math.max(x1, x2), ctrlx); 438 double bottom = Math.max(Math.max(y1, y2), ctrly); 439 return new Rectangle2D.Double(left, top, 440 right - left, bottom - top); 441 } 442 443 /* 444 * JDK 1.6 serialVersionUID 445 */ 446 private static final long serialVersionUID = 4217149928428559721L; 447 } 448 449 /** 450 * This is an abstract class that cannot be instantiated directly. 451 * Type-specific implementation subclasses are available for 452 * instantiation and provide a number of formats for storing 453 * the information necessary to satisfy the various accessor 454 * methods below. 455 * 456 * @see java.awt.geom.QuadCurve2D.Float 457 * @see java.awt.geom.QuadCurve2D.Double 458 * @since 1.2 459 */ 460 protected QuadCurve2D() { 461 } 462 463 /** 464 * Returns the X coordinate of the start point in 465 * {@code double} in precision. 466 * @return the X coordinate of the start point. 467 * @since 1.2 468 */ 469 public abstract double getX1(); 470 471 /** 472 * Returns the Y coordinate of the start point in 473 * {@code double} precision. 474 * @return the Y coordinate of the start point. 475 * @since 1.2 476 */ 477 public abstract double getY1(); 478 479 /** 480 * Returns the start point. 481 * @return a {@code Point2D} that is the start point of this 482 * {@code QuadCurve2D}. 483 * @since 1.2 484 */ 485 public abstract Point2D getP1(); 486 487 /** 488 * Returns the X coordinate of the control point in 489 * {@code double} precision. 490 * @return X coordinate the control point 491 * @since 1.2 492 */ 493 public abstract double getCtrlX(); 494 495 /** 496 * Returns the Y coordinate of the control point in 497 * {@code double} precision. 498 * @return the Y coordinate of the control point. 499 * @since 1.2 500 */ 501 public abstract double getCtrlY(); 502 503 /** 504 * Returns the control point. 505 * @return a {@code Point2D} that is the control point of this 506 * {@code Point2D}. 507 * @since 1.2 508 */ 509 public abstract Point2D getCtrlPt(); 510 511 /** 512 * Returns the X coordinate of the end point in 513 * {@code double} precision. 514 * @return the x coordinate of the end point. 515 * @since 1.2 516 */ 517 public abstract double getX2(); 518 519 /** 520 * Returns the Y coordinate of the end point in 521 * {@code double} precision. 522 * @return the Y coordinate of the end point. 523 * @since 1.2 524 */ 525 public abstract double getY2(); 526 527 /** 528 * Returns the end point. 529 * @return a {@code Point} object that is the end point 530 * of this {@code Point2D}. 531 * @since 1.2 532 */ 533 public abstract Point2D getP2(); 534 535 /** 536 * Sets the location of the end points and control point of this curve 537 * to the specified {@code double} coordinates. 538 * 539 * @param x1 the X coordinate of the start point 540 * @param y1 the Y coordinate of the start point 541 * @param ctrlx the X coordinate of the control point 542 * @param ctrly the Y coordinate of the control point 543 * @param x2 the X coordinate of the end point 544 * @param y2 the Y coordinate of the end point 545 * @since 1.2 546 */ 547 public abstract void setCurve(double x1, double y1, 548 double ctrlx, double ctrly, 549 double x2, double y2); 550 551 /** 552 * Sets the location of the end points and control points of this 553 * {@code QuadCurve2D} to the {@code double} coordinates at 554 * the specified offset in the specified array. 555 * @param coords the array containing coordinate values 556 * @param offset the index into the array from which to start 557 * getting the coordinate values and assigning them to this 558 * {@code QuadCurve2D} 559 * @since 1.2 560 */ 561 public void setCurve(double[] coords, int offset) { 562 setCurve(coords[offset + 0], coords[offset + 1], 563 coords[offset + 2], coords[offset + 3], 564 coords[offset + 4], coords[offset + 5]); 565 } 566 567 /** 568 * Sets the location of the end points and control point of this 569 * {@code QuadCurve2D} to the specified {@code Point2D} 570 * coordinates. 571 * @param p1 the start point 572 * @param cp the control point 573 * @param p2 the end point 574 * @since 1.2 575 */ 576 public void setCurve(Point2D p1, Point2D cp, Point2D p2) { 577 setCurve(p1.getX(), p1.getY(), 578 cp.getX(), cp.getY(), 579 p2.getX(), p2.getY()); 580 } 581 582 /** 583 * Sets the location of the end points and control points of this 584 * {@code QuadCurve2D} to the coordinates of the 585 * {@code Point2D} objects at the specified offset in 586 * the specified array. 587 * @param pts an array containing {@code Point2D} that define 588 * coordinate values 589 * @param offset the index into {@code pts} from which to start 590 * getting the coordinate values and assigning them to this 591 * {@code QuadCurve2D} 592 * @since 1.2 593 */ 594 public void setCurve(Point2D[] pts, int offset) { 595 setCurve(pts[offset + 0].getX(), pts[offset + 0].getY(), 596 pts[offset + 1].getX(), pts[offset + 1].getY(), 597 pts[offset + 2].getX(), pts[offset + 2].getY()); 598 } 599 600 /** 601 * Sets the location of the end points and control point of this 602 * {@code QuadCurve2D} to the same as those in the specified 603 * {@code QuadCurve2D}. 604 * @param c the specified {@code QuadCurve2D} 605 * @since 1.2 606 */ 607 public void setCurve(QuadCurve2D c) { 608 setCurve(c.getX1(), c.getY1(), 609 c.getCtrlX(), c.getCtrlY(), 610 c.getX2(), c.getY2()); 611 } 612 613 /** 614 * Returns the square of the flatness, or maximum distance of a 615 * control point from the line connecting the end points, of the 616 * quadratic curve specified by the indicated control points. 617 * 618 * @param x1 the X coordinate of the start point 619 * @param y1 the Y coordinate of the start point 620 * @param ctrlx the X coordinate of the control point 621 * @param ctrly the Y coordinate of the control point 622 * @param x2 the X coordinate of the end point 623 * @param y2 the Y coordinate of the end point 624 * @return the square of the flatness of the quadratic curve 625 * defined by the specified coordinates. 626 * @since 1.2 627 */ 628 public static double getFlatnessSq(double x1, double y1, 629 double ctrlx, double ctrly, 630 double x2, double y2) { 631 return Line2D.ptSegDistSq(x1, y1, x2, y2, ctrlx, ctrly); 632 } 633 634 /** 635 * Returns the flatness, or maximum distance of a 636 * control point from the line connecting the end points, of the 637 * quadratic curve specified by the indicated control points. 638 * 639 * @param x1 the X coordinate of the start point 640 * @param y1 the Y coordinate of the start point 641 * @param ctrlx the X coordinate of the control point 642 * @param ctrly the Y coordinate of the control point 643 * @param x2 the X coordinate of the end point 644 * @param y2 the Y coordinate of the end point 645 * @return the flatness of the quadratic curve defined by the 646 * specified coordinates. 647 * @since 1.2 648 */ 649 public static double getFlatness(double x1, double y1, 650 double ctrlx, double ctrly, 651 double x2, double y2) { 652 return Line2D.ptSegDist(x1, y1, x2, y2, ctrlx, ctrly); 653 } 654 655 /** 656 * Returns the square of the flatness, or maximum distance of a 657 * control point from the line connecting the end points, of the 658 * quadratic curve specified by the control points stored in the 659 * indicated array at the indicated index. 660 * @param coords an array containing coordinate values 661 * @param offset the index into {@code coords} from which to 662 * to start getting the values from the array 663 * @return the flatness of the quadratic curve that is defined by the 664 * values in the specified array at the specified index. 665 * @since 1.2 666 */ 667 public static double getFlatnessSq(double[] coords, int offset) { 668 return Line2D.ptSegDistSq(coords[offset + 0], coords[offset + 1], 669 coords[offset + 4], coords[offset + 5], 670 coords[offset + 2], coords[offset + 3]); 671 } 672 673 /** 674 * Returns the flatness, or maximum distance of a 675 * control point from the line connecting the end points, of the 676 * quadratic curve specified by the control points stored in the 677 * indicated array at the indicated index. 678 * @param coords an array containing coordinate values 679 * @param offset the index into {@code coords} from which to 680 * start getting the coordinate values 681 * @return the flatness of a quadratic curve defined by the 682 * specified array at the specified offset. 683 * @since 1.2 684 */ 685 public static double getFlatness(double[] coords, int offset) { 686 return Line2D.ptSegDist(coords[offset + 0], coords[offset + 1], 687 coords[offset + 4], coords[offset + 5], 688 coords[offset + 2], coords[offset + 3]); 689 } 690 691 /** 692 * Returns the square of the flatness, or maximum distance of a 693 * control point from the line connecting the end points, of this 694 * {@code QuadCurve2D}. 695 * @return the square of the flatness of this 696 * {@code QuadCurve2D}. 697 * @since 1.2 698 */ 699 public double getFlatnessSq() { 700 return Line2D.ptSegDistSq(getX1(), getY1(), 701 getX2(), getY2(), 702 getCtrlX(), getCtrlY()); 703 } 704 705 /** 706 * Returns the flatness, or maximum distance of a 707 * control point from the line connecting the end points, of this 708 * {@code QuadCurve2D}. 709 * @return the flatness of this {@code QuadCurve2D}. 710 * @since 1.2 711 */ 712 public double getFlatness() { 713 return Line2D.ptSegDist(getX1(), getY1(), 714 getX2(), getY2(), 715 getCtrlX(), getCtrlY()); 716 } 717 718 /** 719 * Subdivides this {@code QuadCurve2D} and stores the resulting 720 * two subdivided curves into the {@code left} and 721 * {@code right} curve parameters. 722 * Either or both of the {@code left} and {@code right} 723 * objects can be the same as this {@code QuadCurve2D} or 724 * {@code null}. 725 * @param left the {@code QuadCurve2D} object for storing the 726 * left or first half of the subdivided curve 727 * @param right the {@code QuadCurve2D} object for storing the 728 * right or second half of the subdivided curve 729 * @since 1.2 730 */ 731 public void subdivide(QuadCurve2D left, QuadCurve2D right) { 732 subdivide(this, left, right); 733 } 734 735 /** 736 * Subdivides the quadratic curve specified by the {@code src} 737 * parameter and stores the resulting two subdivided curves into the 738 * {@code left} and {@code right} curve parameters. 739 * Either or both of the {@code left} and {@code right} 740 * objects can be the same as the {@code src} object or 741 * {@code null}. 742 * @param src the quadratic curve to be subdivided 743 * @param left the {@code QuadCurve2D} object for storing the 744 * left or first half of the subdivided curve 745 * @param right the {@code QuadCurve2D} object for storing the 746 * right or second half of the subdivided curve 747 * @since 1.2 748 */ 749 public static void subdivide(QuadCurve2D src, 750 QuadCurve2D left, 751 QuadCurve2D right) { 752 double x1 = src.getX1(); 753 double y1 = src.getY1(); 754 double ctrlx = src.getCtrlX(); 755 double ctrly = src.getCtrlY(); 756 double x2 = src.getX2(); 757 double y2 = src.getY2(); 758 double ctrlx1 = (x1 + ctrlx) / 2.0; 759 double ctrly1 = (y1 + ctrly) / 2.0; 760 double ctrlx2 = (x2 + ctrlx) / 2.0; 761 double ctrly2 = (y2 + ctrly) / 2.0; 762 ctrlx = (ctrlx1 + ctrlx2) / 2.0; 763 ctrly = (ctrly1 + ctrly2) / 2.0; 764 if (left != null) { 765 left.setCurve(x1, y1, ctrlx1, ctrly1, ctrlx, ctrly); 766 } 767 if (right != null) { 768 right.setCurve(ctrlx, ctrly, ctrlx2, ctrly2, x2, y2); 769 } 770 } 771 772 /** 773 * Subdivides the quadratic curve specified by the coordinates 774 * stored in the {@code src} array at indices 775 * {@code srcoff} through {@code srcoff} + 5 776 * and stores the resulting two subdivided curves into the two 777 * result arrays at the corresponding indices. 778 * Either or both of the {@code left} and {@code right} 779 * arrays can be {@code null} or a reference to the same array 780 * and offset as the {@code src} array. 781 * Note that the last point in the first subdivided curve is the 782 * same as the first point in the second subdivided curve. Thus, 783 * it is possible to pass the same array for {@code left} and 784 * {@code right} and to use offsets such that 785 * {@code rightoff} equals {@code leftoff} + 4 in order 786 * to avoid allocating extra storage for this common point. 787 * @param src the array holding the coordinates for the source curve 788 * @param srcoff the offset into the array of the beginning of the 789 * the 6 source coordinates 790 * @param left the array for storing the coordinates for the first 791 * half of the subdivided curve 792 * @param leftoff the offset into the array of the beginning of the 793 * the 6 left coordinates 794 * @param right the array for storing the coordinates for the second 795 * half of the subdivided curve 796 * @param rightoff the offset into the array of the beginning of the 797 * the 6 right coordinates 798 * @since 1.2 799 */ 800 public static void subdivide(double[] src, int srcoff, 801 double[] left, int leftoff, 802 double[] right, int rightoff) { 803 double x1 = src[srcoff + 0]; 804 double y1 = src[srcoff + 1]; 805 double ctrlx = src[srcoff + 2]; 806 double ctrly = src[srcoff + 3]; 807 double x2 = src[srcoff + 4]; 808 double y2 = src[srcoff + 5]; 809 if (left != null) { 810 left[leftoff + 0] = x1; 811 left[leftoff + 1] = y1; 812 } 813 if (right != null) { 814 right[rightoff + 4] = x2; 815 right[rightoff + 5] = y2; 816 } 817 x1 = (x1 + ctrlx) / 2.0; 818 y1 = (y1 + ctrly) / 2.0; 819 x2 = (x2 + ctrlx) / 2.0; 820 y2 = (y2 + ctrly) / 2.0; 821 ctrlx = (x1 + x2) / 2.0; 822 ctrly = (y1 + y2) / 2.0; 823 if (left != null) { 824 left[leftoff + 2] = x1; 825 left[leftoff + 3] = y1; 826 left[leftoff + 4] = ctrlx; 827 left[leftoff + 5] = ctrly; 828 } 829 if (right != null) { 830 right[rightoff + 0] = ctrlx; 831 right[rightoff + 1] = ctrly; 832 right[rightoff + 2] = x2; 833 right[rightoff + 3] = y2; 834 } 835 } 836 837 /** 838 * Solves the quadratic whose coefficients are in the {@code eqn} 839 * array and places the non-complex roots back into the same array, 840 * returning the number of roots. The quadratic solved is represented 841 * by the equation: 842 * <pre> 843 * eqn = {C, B, A}; 844 * ax^2 + bx + c = 0 845 * </pre> 846 * A return value of {@code -1} is used to distinguish a constant 847 * equation, which might be always 0 or never 0, from an equation that 848 * has no zeroes. 849 * @param eqn the array that contains the quadratic coefficients 850 * @return the number of roots, or {@code -1} if the equation is 851 * a constant 852 * @since 1.2 853 */ 854 public static int solveQuadratic(double[] eqn) { 855 return solveQuadratic(eqn, eqn); 856 } 857 858 /** 859 * Solves the quadratic whose coefficients are in the {@code eqn} 860 * array and places the non-complex roots into the {@code res} 861 * array, returning the number of roots. 862 * The quadratic solved is represented by the equation: 863 * <pre> 864 * eqn = {C, B, A}; 865 * ax^2 + bx + c = 0 866 * </pre> 867 * A return value of {@code -1} is used to distinguish a constant 868 * equation, which might be always 0 or never 0, from an equation that 869 * has no zeroes. 870 * @param eqn the specified array of coefficients to use to solve 871 * the quadratic equation 872 * @param res the array that contains the non-complex roots 873 * resulting from the solution of the quadratic equation 874 * @return the number of roots, or {@code -1} if the equation is 875 * a constant. 876 * @since 1.3 877 */ 878 public static int solveQuadratic(double[] eqn, double[] res) { 879 double a = eqn[2]; 880 double b = eqn[1]; 881 double c = eqn[0]; 882 int roots = 0; 883 if (a == 0.0) { 884 // The quadratic parabola has degenerated to a line. 885 if (b == 0.0) { 886 // The line has degenerated to a constant. 887 return -1; 888 } 889 res[roots++] = -c / b; 890 } else { 891 // From Numerical Recipes, 5.6, Quadratic and Cubic Equations 892 double d = b * b - 4.0 * a * c; 893 if (d < 0.0) { 894 // If d < 0.0, then there are no roots 895 return 0; 896 } 897 d = Math.sqrt(d); 898 // For accuracy, calculate one root using: 899 // (-b +/- d) / 2a 900 // and the other using: 901 // 2c / (-b +/- d) 902 // Choose the sign of the +/- so that b+d gets larger in magnitude 903 if (b < 0.0) { 904 d = -d; 905 } 906 double q = (b + d) / -2.0; 907 // We already tested a for being 0 above 908 res[roots++] = q / a; 909 if (q != 0.0) { 910 res[roots++] = c / q; 911 } 912 } 913 return roots; 914 } 915 916 /** 917 * {@inheritDoc} 918 * @since 1.2 919 */ 920 public boolean contains(double x, double y) { 921 922 double x1 = getX1(); 923 double y1 = getY1(); 924 double xc = getCtrlX(); 925 double yc = getCtrlY(); 926 double x2 = getX2(); 927 double y2 = getY2(); 928 929 /* 930 * We have a convex shape bounded by quad curve Pc(t) 931 * and ine Pl(t). 932 * 933 * P1 = (x1, y1) - start point of curve 934 * P2 = (x2, y2) - end point of curve 935 * Pc = (xc, yc) - control point 936 * 937 * Pq(t) = P1*(1 - t)^2 + 2*Pc*t*(1 - t) + P2*t^2 = 938 * = (P1 - 2*Pc + P2)*t^2 + 2*(Pc - P1)*t + P1 939 * Pl(t) = P1*(1 - t) + P2*t 940 * t = [0:1] 941 * 942 * P = (x, y) - point of interest 943 * 944 * Let's look at second derivative of quad curve equation: 945 * 946 * Pq''(t) = 2 * (P1 - 2 * Pc + P2) = Pq'' 947 * It's constant vector. 948 * 949 * Let's draw a line through P to be parallel to this 950 * vector and find the intersection of the quad curve 951 * and the line. 952 * 953 * Pq(t) is point of intersection if system of equations 954 * below has the solution. 955 * 956 * L(s) = P + Pq''*s == Pq(t) 957 * Pq''*s + (P - Pq(t)) == 0 958 * 959 * | xq''*s + (x - xq(t)) == 0 960 * | yq''*s + (y - yq(t)) == 0 961 * 962 * This system has the solution if rank of its matrix equals to 1. 963 * That is, determinant of the matrix should be zero. 964 * 965 * (y - yq(t))*xq'' == (x - xq(t))*yq'' 966 * 967 * Let's solve this equation with 't' variable. 968 * Also let kx = x1 - 2*xc + x2 969 * ky = y1 - 2*yc + y2 970 * 971 * t0q = (1/2)*((x - x1)*ky - (y - y1)*kx) / 972 * ((xc - x1)*ky - (yc - y1)*kx) 973 * 974 * Let's do the same for our line Pl(t): 975 * 976 * t0l = ((x - x1)*ky - (y - y1)*kx) / 977 * ((x2 - x1)*ky - (y2 - y1)*kx) 978 * 979 * It's easy to check that t0q == t0l. This fact means 980 * we can compute t0 only one time. 981 * 982 * In case t0 < 0 or t0 > 1, we have an intersections outside 983 * of shape bounds. So, P is definitely out of shape. 984 * 985 * In case t0 is inside [0:1], we should calculate Pq(t0) 986 * and Pl(t0). We have three points for now, and all of them 987 * lie on one line. So, we just need to detect, is our point 988 * of interest between points of intersections or not. 989 * 990 * If the denominator in the t0q and t0l equations is 991 * zero, then the points must be collinear and so the 992 * curve is degenerate and encloses no area. Thus the 993 * result is false. 994 */ 995 double kx = x1 - 2 * xc + x2; 996 double ky = y1 - 2 * yc + y2; 997 double dx = x - x1; 998 double dy = y - y1; 999 double dxl = x2 - x1; 1000 double dyl = y2 - y1; 1001 1002 double t0 = (dx * ky - dy * kx) / (dxl * ky - dyl * kx); 1003 if (t0 < 0 || t0 > 1 || t0 != t0) { 1004 return false; 1005 } 1006 1007 double xb = kx * t0 * t0 + 2 * (xc - x1) * t0 + x1; 1008 double yb = ky * t0 * t0 + 2 * (yc - y1) * t0 + y1; 1009 double xl = dxl * t0 + x1; 1010 double yl = dyl * t0 + y1; 1011 1012 return (x >= xb && x < xl) || 1013 (x >= xl && x < xb) || 1014 (y >= yb && y < yl) || 1015 (y >= yl && y < yb); 1016 } 1017 1018 /** 1019 * {@inheritDoc} 1020 * @since 1.2 1021 */ 1022 public boolean contains(Point2D p) { 1023 return contains(p.getX(), p.getY()); 1024 } 1025 1026 /** 1027 * Fill an array with the coefficients of the parametric equation 1028 * in t, ready for solving against val with solveQuadratic. 1029 * We currently have: 1030 * val = Py(t) = C1*(1-t)^2 + 2*CP*t*(1-t) + C2*t^2 1031 * = C1 - 2*C1*t + C1*t^2 + 2*CP*t - 2*CP*t^2 + C2*t^2 1032 * = C1 + (2*CP - 2*C1)*t + (C1 - 2*CP + C2)*t^2 1033 * 0 = (C1 - val) + (2*CP - 2*C1)*t + (C1 - 2*CP + C2)*t^2 1034 * 0 = C + Bt + At^2 1035 * C = C1 - val 1036 * B = 2*CP - 2*C1 1037 * A = C1 - 2*CP + C2 1038 */ 1039 private static void fillEqn(double[] eqn, double val, 1040 double c1, double cp, double c2) { 1041 eqn[0] = c1 - val; 1042 eqn[1] = cp + cp - c1 - c1; 1043 eqn[2] = c1 - cp - cp + c2; 1044 return; 1045 } 1046 1047 /** 1048 * Evaluate the t values in the first num slots of the vals[] array 1049 * and place the evaluated values back into the same array. Only 1050 * evaluate t values that are within the range <0, 1>, including 1051 * the 0 and 1 ends of the range iff the include0 or include1 1052 * booleans are true. If an "inflection" equation is handed in, 1053 * then any points which represent a point of inflection for that 1054 * quadratic equation are also ignored. 1055 */ 1056 private static int evalQuadratic(double[] vals, int num, 1057 boolean include0, 1058 boolean include1, 1059 double[] inflect, 1060 double c1, double ctrl, double c2) { 1061 int j = 0; 1062 for (int i = 0; i < num; i++) { 1063 double t = vals[i]; 1064 if ((include0 ? t >= 0 : t > 0) && 1065 (include1 ? t <= 1 : t < 1) && 1066 (inflect == null || 1067 inflect[1] + 2*inflect[2]*t != 0)) 1068 { 1069 double u = 1 - t; 1070 vals[j++] = c1*u*u + 2*ctrl*t*u + c2*t*t; 1071 } 1072 } 1073 return j; 1074 } 1075 1076 private static final int BELOW = -2; 1077 private static final int LOWEDGE = -1; 1078 private static final int INSIDE = 0; 1079 private static final int HIGHEDGE = 1; 1080 private static final int ABOVE = 2; 1081 1082 /** 1083 * Determine where coord lies with respect to the range from 1084 * low to high. It is assumed that low <= high. The return 1085 * value is one of the 5 values BELOW, LOWEDGE, INSIDE, HIGHEDGE, 1086 * or ABOVE. 1087 */ 1088 private static int getTag(double coord, double low, double high) { 1089 if (coord <= low) { 1090 return (coord < low ? BELOW : LOWEDGE); 1091 } 1092 if (coord >= high) { 1093 return (coord > high ? ABOVE : HIGHEDGE); 1094 } 1095 return INSIDE; 1096 } 1097 1098 /** 1099 * Determine if the pttag represents a coordinate that is already 1100 * in its test range, or is on the border with either of the two 1101 * opttags representing another coordinate that is "towards the 1102 * inside" of that test range. In other words, are either of the 1103 * two "opt" points "drawing the pt inward"? 1104 */ 1105 private static boolean inwards(int pttag, int opt1tag, int opt2tag) { 1106 switch (pttag) { 1107 case BELOW: 1108 case ABOVE: 1109 default: 1110 return false; 1111 case LOWEDGE: 1112 return (opt1tag >= INSIDE || opt2tag >= INSIDE); 1113 case INSIDE: 1114 return true; 1115 case HIGHEDGE: 1116 return (opt1tag <= INSIDE || opt2tag <= INSIDE); 1117 } 1118 } 1119 1120 /** 1121 * {@inheritDoc} 1122 * @since 1.2 1123 */ 1124 public boolean intersects(double x, double y, double w, double h) { 1125 // Trivially reject non-existant rectangles 1126 if (w <= 0 || h <= 0) { 1127 return false; 1128 } 1129 1130 // Trivially accept if either endpoint is inside the rectangle 1131 // (not on its border since it may end there and not go inside) 1132 // Record where they lie with respect to the rectangle. 1133 // -1 => left, 0 => inside, 1 => right 1134 double x1 = getX1(); 1135 double y1 = getY1(); 1136 int x1tag = getTag(x1, x, x+w); 1137 int y1tag = getTag(y1, y, y+h); 1138 if (x1tag == INSIDE && y1tag == INSIDE) { 1139 return true; 1140 } 1141 double x2 = getX2(); 1142 double y2 = getY2(); 1143 int x2tag = getTag(x2, x, x+w); 1144 int y2tag = getTag(y2, y, y+h); 1145 if (x2tag == INSIDE && y2tag == INSIDE) { 1146 return true; 1147 } 1148 double ctrlx = getCtrlX(); 1149 double ctrly = getCtrlY(); 1150 int ctrlxtag = getTag(ctrlx, x, x+w); 1151 int ctrlytag = getTag(ctrly, y, y+h); 1152 1153 // Trivially reject if all points are entirely to one side of 1154 // the rectangle. 1155 if (x1tag < INSIDE && x2tag < INSIDE && ctrlxtag < INSIDE) { 1156 return false; // All points left 1157 } 1158 if (y1tag < INSIDE && y2tag < INSIDE && ctrlytag < INSIDE) { 1159 return false; // All points above 1160 } 1161 if (x1tag > INSIDE && x2tag > INSIDE && ctrlxtag > INSIDE) { 1162 return false; // All points right 1163 } 1164 if (y1tag > INSIDE && y2tag > INSIDE && ctrlytag > INSIDE) { 1165 return false; // All points below 1166 } 1167 1168 // Test for endpoints on the edge where either the segment 1169 // or the curve is headed "inwards" from them 1170 // Note: These tests are a superset of the fast endpoint tests 1171 // above and thus repeat those tests, but take more time 1172 // and cover more cases 1173 if (inwards(x1tag, x2tag, ctrlxtag) && 1174 inwards(y1tag, y2tag, ctrlytag)) 1175 { 1176 // First endpoint on border with either edge moving inside 1177 return true; 1178 } 1179 if (inwards(x2tag, x1tag, ctrlxtag) && 1180 inwards(y2tag, y1tag, ctrlytag)) 1181 { 1182 // Second endpoint on border with either edge moving inside 1183 return true; 1184 } 1185 1186 // Trivially accept if endpoints span directly across the rectangle 1187 boolean xoverlap = (x1tag * x2tag <= 0); 1188 boolean yoverlap = (y1tag * y2tag <= 0); 1189 if (x1tag == INSIDE && x2tag == INSIDE && yoverlap) { 1190 return true; 1191 } 1192 if (y1tag == INSIDE && y2tag == INSIDE && xoverlap) { 1193 return true; 1194 } 1195 1196 // We now know that both endpoints are outside the rectangle 1197 // but the 3 points are not all on one side of the rectangle. 1198 // Therefore the curve cannot be contained inside the rectangle, 1199 // but the rectangle might be contained inside the curve, or 1200 // the curve might intersect the boundary of the rectangle. 1201 1202 double[] eqn = new double[3]; 1203 double[] res = new double[3]; 1204 if (!yoverlap) { 1205 // Both Y coordinates for the closing segment are above or 1206 // below the rectangle which means that we can only intersect 1207 // if the curve crosses the top (or bottom) of the rectangle 1208 // in more than one place and if those crossing locations 1209 // span the horizontal range of the rectangle. 1210 fillEqn(eqn, (y1tag < INSIDE ? y : y+h), y1, ctrly, y2); 1211 return (solveQuadratic(eqn, res) == 2 && 1212 evalQuadratic(res, 2, true, true, null, 1213 x1, ctrlx, x2) == 2 && 1214 getTag(res[0], x, x+w) * getTag(res[1], x, x+w) <= 0); 1215 } 1216 1217 // Y ranges overlap. Now we examine the X ranges 1218 if (!xoverlap) { 1219 // Both X coordinates for the closing segment are left of 1220 // or right of the rectangle which means that we can only 1221 // intersect if the curve crosses the left (or right) edge 1222 // of the rectangle in more than one place and if those 1223 // crossing locations span the vertical range of the rectangle. 1224 fillEqn(eqn, (x1tag < INSIDE ? x : x+w), x1, ctrlx, x2); 1225 return (solveQuadratic(eqn, res) == 2 && 1226 evalQuadratic(res, 2, true, true, null, 1227 y1, ctrly, y2) == 2 && 1228 getTag(res[0], y, y+h) * getTag(res[1], y, y+h) <= 0); 1229 } 1230 1231 // The X and Y ranges of the endpoints overlap the X and Y 1232 // ranges of the rectangle, now find out how the endpoint 1233 // line segment intersects the Y range of the rectangle 1234 double dx = x2 - x1; 1235 double dy = y2 - y1; 1236 double k = y2 * x1 - x2 * y1; 1237 int c1tag, c2tag; 1238 if (y1tag == INSIDE) { 1239 c1tag = x1tag; 1240 } else { 1241 c1tag = getTag((k + dx * (y1tag < INSIDE ? y : y+h)) / dy, x, x+w); 1242 } 1243 if (y2tag == INSIDE) { 1244 c2tag = x2tag; 1245 } else { 1246 c2tag = getTag((k + dx * (y2tag < INSIDE ? y : y+h)) / dy, x, x+w); 1247 } 1248 // If the part of the line segment that intersects the Y range 1249 // of the rectangle crosses it horizontally - trivially accept 1250 if (c1tag * c2tag <= 0) { 1251 return true; 1252 } 1253 1254 // Now we know that both the X and Y ranges intersect and that 1255 // the endpoint line segment does not directly cross the rectangle. 1256 // 1257 // We can almost treat this case like one of the cases above 1258 // where both endpoints are to one side, except that we will 1259 // only get one intersection of the curve with the vertical 1260 // side of the rectangle. This is because the endpoint segment 1261 // accounts for the other intersection. 1262 // 1263 // (Remember there is overlap in both the X and Y ranges which 1264 // means that the segment must cross at least one vertical edge 1265 // of the rectangle - in particular, the "near vertical side" - 1266 // leaving only one intersection for the curve.) 1267 // 1268 // Now we calculate the y tags of the two intersections on the 1269 // "near vertical side" of the rectangle. We will have one with 1270 // the endpoint segment, and one with the curve. If those two 1271 // vertical intersections overlap the Y range of the rectangle, 1272 // we have an intersection. Otherwise, we don't. 1273 1274 // c1tag = vertical intersection class of the endpoint segment 1275 // 1276 // Choose the y tag of the endpoint that was not on the same 1277 // side of the rectangle as the subsegment calculated above. 1278 // Note that we can "steal" the existing Y tag of that endpoint 1279 // since it will be provably the same as the vertical intersection. 1280 c1tag = ((c1tag * x1tag <= 0) ? y1tag : y2tag); 1281 1282 // c2tag = vertical intersection class of the curve 1283 // 1284 // We have to calculate this one the straightforward way. 1285 // Note that the c2tag can still tell us which vertical edge 1286 // to test against. 1287 fillEqn(eqn, (c2tag < INSIDE ? x : x+w), x1, ctrlx, x2); 1288 int num = solveQuadratic(eqn, res); 1289 1290 // Note: We should be able to assert(num == 2); since the 1291 // X range "crosses" (not touches) the vertical boundary, 1292 // but we pass num to evalQuadratic for completeness. 1293 evalQuadratic(res, num, true, true, null, y1, ctrly, y2); 1294 1295 // Note: We can assert(num evals == 1); since one of the 1296 // 2 crossings will be out of the [0,1] range. 1297 c2tag = getTag(res[0], y, y+h); 1298 1299 // Finally, we have an intersection if the two crossings 1300 // overlap the Y range of the rectangle. 1301 return (c1tag * c2tag <= 0); 1302 } 1303 1304 /** 1305 * {@inheritDoc} 1306 * @since 1.2 1307 */ 1308 public boolean intersects(Rectangle2D r) { 1309 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 1310 } 1311 1312 /** 1313 * {@inheritDoc} 1314 * @since 1.2 1315 */ 1316 public boolean contains(double x, double y, double w, double h) { 1317 if (w <= 0 || h <= 0) { 1318 return false; 1319 } 1320 // Assertion: Quadratic curves closed by connecting their 1321 // endpoints are always convex. 1322 return (contains(x, y) && 1323 contains(x + w, y) && 1324 contains(x + w, y + h) && 1325 contains(x, y + h)); 1326 } 1327 1328 /** 1329 * {@inheritDoc} 1330 * @since 1.2 1331 */ 1332 public boolean contains(Rectangle2D r) { 1333 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 1334 } 1335 1336 /** 1337 * {@inheritDoc} 1338 * @since 1.2 1339 */ 1340 public Rectangle getBounds() { 1341 return getBounds2D().getBounds(); 1342 } 1343 1344 /** 1345 * Returns an iteration object that defines the boundary of the 1346 * shape of this {@code QuadCurve2D}. 1347 * The iterator for this class is not multi-threaded safe, 1348 * which means that this {@code QuadCurve2D} class does not 1349 * guarantee that modifications to the geometry of this 1350 * {@code QuadCurve2D} object do not affect any iterations of 1351 * that geometry that are already in process. 1352 * @param at an optional {@link AffineTransform} to apply to the 1353 * shape boundary 1354 * @return a {@link PathIterator} object that defines the boundary 1355 * of the shape. 1356 * @since 1.2 1357 */ 1358 public PathIterator getPathIterator(AffineTransform at) { 1359 return new QuadIterator(this, at); 1360 } 1361 1362 /** 1363 * Returns an iteration object that defines the boundary of the 1364 * flattened shape of this {@code QuadCurve2D}. 1365 * The iterator for this class is not multi-threaded safe, 1366 * which means that this {@code QuadCurve2D} class does not 1367 * guarantee that modifications to the geometry of this 1368 * {@code QuadCurve2D} object do not affect any iterations of 1369 * that geometry that are already in process. 1370 * @param at an optional {@code AffineTransform} to apply 1371 * to the boundary of the shape 1372 * @param flatness the maximum distance that the control points for a 1373 * subdivided curve can be with respect to a line connecting 1374 * the end points of this curve before this curve is 1375 * replaced by a straight line connecting the end points. 1376 * @return a {@code PathIterator} object that defines the 1377 * flattened boundary of the shape. 1378 * @since 1.2 1379 */ 1380 public PathIterator getPathIterator(AffineTransform at, double flatness) { 1381 return new FlatteningPathIterator(getPathIterator(at), flatness); 1382 } 1383 1384 /** 1385 * Creates a new object of the same class and with the same contents 1386 * as this object. 1387 * 1388 * @return a clone of this instance. 1389 * @exception OutOfMemoryError if there is not enough memory. 1390 * @see java.lang.Cloneable 1391 * @since 1.2 1392 */ 1393 public Object clone() { 1394 try { 1395 return super.clone(); 1396 } catch (CloneNotSupportedException e) { 1397 // this shouldn't happen, since we are Cloneable 1398 throw new InternalError(e); 1399 } 1400 } 1401 }