001/* Area.java -- represents a shape built by constructive area geometry 002 Copyright (C) 2002, 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.Vector; 043 044 045/** 046 * The Area class represents any area for the purpose of 047 * Constructive Area Geometry (CAG) manipulations. CAG manipulations 048 * work as an area-wise form of boolean logic, where the basic operations are: 049 * <P><li>Add (in boolean algebra: A <B>or</B> B)<BR> 050 * <li>Subtract (in boolean algebra: A <B>and</B> (<B>not</B> B) )<BR> 051 * <li>Intersect (in boolean algebra: A <B>and</B> B)<BR> 052 * <li>Exclusive Or <BR> 053 * <img src="doc-files/Area-1.png" width="342" height="302" 054 * alt="Illustration of CAG operations" /><BR> 055 * Above is an illustration of the CAG operations on two ring shapes.<P> 056 * 057 * The contains and intersects() methods are also more accurate than the 058 * specification of #Shape requires.<P> 059 * 060 * Please note that constructing an Area can be slow 061 * (Self-intersection resolving is proportional to the square of 062 * the number of segments).<P> 063 * @see #add(Area) 064 * @see #subtract(Area) 065 * @see #intersect(Area) 066 * @see #exclusiveOr(Area) 067 * 068 * @author Sven de Marothy (sven@physto.se) 069 * 070 * @since 1.2 071 * @status Works, but could be faster and more reliable. 072 */ 073public class Area implements Shape, Cloneable 074{ 075 /** 076 * General numerical precision 077 */ 078 private static final double EPSILON = 1E-11; 079 080 /** 081 * recursive subdivision epsilon - (see getRecursionDepth) 082 */ 083 private static final double RS_EPSILON = 1E-13; 084 085 /** 086 * Snap distance - points within this distance are considered equal 087 */ 088 private static final double PE_EPSILON = 1E-11; 089 090 /** 091 * Segment vectors containing solid areas and holes 092 * This is package-private to avoid an accessor method. 093 */ 094 Vector<Segment> solids; 095 096 /** 097 * Segment vectors containing solid areas and holes 098 * This is package-private to avoid an accessor method. 099 */ 100 Vector<Segment> holes; 101 102 /** 103 * Vector (temporary) storing curve-curve intersections 104 */ 105 private Vector<double[]> ccIntersections; 106 107 /** 108 * Winding rule WIND_NON_ZERO used, after construction, 109 * this is irrelevant. 110 */ 111 private int windingRule; 112 113 /** 114 * Constructs an empty Area 115 */ 116 public Area() 117 { 118 solids = new Vector<Segment>(); 119 holes = new Vector<Segment>(); 120 } 121 122 /** 123 * Constructs an Area from any given Shape. <P> 124 * 125 * If the Shape is self-intersecting, the created Area will consist 126 * of non-self-intersecting subpaths, and any inner paths which 127 * are found redundant in accordance with the Shape's winding rule 128 * will not be included. 129 * 130 * @param s the shape (<code>null</code> not permitted). 131 * 132 * @throws NullPointerException if <code>s</code> is <code>null</code>. 133 */ 134 public Area(Shape s) 135 { 136 this(); 137 138 Vector<Segment> p = makeSegment(s); 139 140 // empty path 141 if (p == null) 142 return; 143 144 // delete empty paths 145 for (int i = 0; i < p.size(); i++) 146 if (p.elementAt(i).getSignedArea() == 0.0) 147 p.remove(i--); 148 149 /* 150 * Resolve self intersecting paths into non-intersecting 151 * solids and holes. 152 * Algorithm is as follows: 153 * 1: Create nodes at all self intersections 154 * 2: Put all segments into a list 155 * 3: Grab a segment, follow it, change direction at each node, 156 * removing segments from the list in the process 157 * 4: Repeat (3) until no segments remain in the list 158 * 5: Remove redundant paths and sort into solids and holes 159 */ 160 Segment v; 161 162 for (int i = 0; i < p.size(); i++) 163 { 164 Segment path = p.elementAt(i); 165 createNodesSelf(path); 166 } 167 168 if (p.size() > 1) 169 { 170 for (int i = 0; i < p.size() - 1; i++) 171 for (int j = i + 1; j < p.size(); j++) 172 { 173 Segment path1 = p.elementAt(i); 174 Segment path2 = p.elementAt(j); 175 createNodes(path1, path2); 176 } 177 } 178 179 // we have intersecting points. 180 Vector<Segment> segments = new Vector<Segment>(); 181 182 for (int i = 0; i < p.size(); i++) 183 { 184 Segment path = v = p.elementAt(i); 185 do 186 { 187 segments.add(v); 188 v = v.next; 189 } 190 while (v != path); 191 } 192 193 Vector<Segment> paths = weilerAtherton(segments); 194 deleteRedundantPaths(paths); 195 } 196 197 /** 198 * Performs an add (union) operation on this area with another Area.<BR> 199 * @param area - the area to be unioned with this one 200 */ 201 public void add(Area area) 202 { 203 if (equals(area)) 204 return; 205 if (area.isEmpty()) 206 return; 207 208 Area B = (Area) area.clone(); 209 210 Vector<Segment> pathA = new Vector<Segment>(); 211 Vector<Segment> pathB = new Vector<Segment>(); 212 pathA.addAll(solids); 213 pathA.addAll(holes); 214 pathB.addAll(B.solids); 215 pathB.addAll(B.holes); 216 217 for (int i = 0; i < pathA.size(); i++) 218 { 219 Segment a = pathA.elementAt(i); 220 for (int j = 0; j < pathB.size(); j++) 221 { 222 Segment b = pathB.elementAt(j); 223 createNodes(a, b); 224 } 225 } 226 227 Vector<Segment> paths = new Vector<Segment>(); 228 Segment v; 229 230 // we have intersecting points. 231 Vector<Segment> segments = new Vector<Segment>(); 232 233 // In a union operation, we keep all 234 // segments of A oustide B and all B outside A 235 for (int i = 0; i < pathA.size(); i++) 236 { 237 v = pathA.elementAt(i); 238 Segment path = v; 239 do 240 { 241 if (v.isSegmentOutside(area)) 242 segments.add(v); 243 v = v.next; 244 } 245 while (v != path); 246 } 247 248 for (int i = 0; i < pathB.size(); i++) 249 { 250 v = pathB.elementAt(i); 251 Segment path = v; 252 do 253 { 254 if (v.isSegmentOutside(this)) 255 segments.add(v); 256 v = v.next; 257 } 258 while (v != path); 259 } 260 261 paths = weilerAtherton(segments); 262 deleteRedundantPaths(paths); 263 } 264 265 /** 266 * Performs a subtraction operation on this Area.<BR> 267 * @param area the area to be subtracted from this area. 268 * @throws NullPointerException if <code>area</code> is <code>null</code>. 269 */ 270 public void subtract(Area area) 271 { 272 if (isEmpty() || area.isEmpty()) 273 return; 274 275 if (equals(area)) 276 { 277 reset(); 278 return; 279 } 280 281 Vector<Segment> pathA = new Vector<Segment>(); 282 Area B = (Area) area.clone(); 283 pathA.addAll(solids); 284 pathA.addAll(holes); 285 286 // reverse the directions of B paths. 287 setDirection(B.holes, true); 288 setDirection(B.solids, false); 289 290 Vector<Segment> pathB = new Vector<Segment>(); 291 pathB.addAll(B.solids); 292 pathB.addAll(B.holes); 293 294 // create nodes 295 for (int i = 0; i < pathA.size(); i++) 296 { 297 Segment a = pathA.elementAt(i); 298 for (int j = 0; j < pathB.size(); j++) 299 { 300 Segment b = pathB.elementAt(j); 301 createNodes(a, b); 302 } 303 } 304 305 // we have intersecting points. 306 Vector<Segment> segments = new Vector<Segment>(); 307 308 // In a subtraction operation, we keep all 309 // segments of A oustide B and all B within A 310 // We outsideness-test only one segment in each path 311 // and the segments before and after any node 312 for (int i = 0; i < pathA.size(); i++) 313 { 314 Segment v = pathA.elementAt(i); 315 Segment path = v; 316 if (v.isSegmentOutside(area) && v.node == null) 317 segments.add(v); 318 boolean node = false; 319 do 320 { 321 if ((v.node != null || node)) 322 { 323 node = (v.node != null); 324 if (v.isSegmentOutside(area)) 325 segments.add(v); 326 } 327 v = v.next; 328 } 329 while (v != path); 330 } 331 332 for (int i = 0; i < pathB.size(); i++) 333 { 334 Segment v = (Segment) pathB.elementAt(i); 335 Segment path = v; 336 if (! v.isSegmentOutside(this) && v.node == null) 337 segments.add(v); 338 v = v.next; 339 boolean node = false; 340 do 341 { 342 if ((v.node != null || node)) 343 { 344 node = (v.node != null); 345 if (! v.isSegmentOutside(this)) 346 segments.add(v); 347 } 348 v = v.next; 349 } 350 while (v != path); 351 } 352 353 Vector<Segment> paths = weilerAtherton(segments); 354 deleteRedundantPaths(paths); 355 } 356 357 /** 358 * Performs an intersection operation on this Area.<BR> 359 * @param area - the area to be intersected with this area. 360 * @throws NullPointerException if <code>area</code> is <code>null</code>. 361 */ 362 public void intersect(Area area) 363 { 364 if (isEmpty() || area.isEmpty()) 365 { 366 reset(); 367 return; 368 } 369 if (equals(area)) 370 return; 371 372 Vector<Segment> pathA = new Vector<Segment>(); 373 Area B = (Area) area.clone(); 374 pathA.addAll(solids); 375 pathA.addAll(holes); 376 377 Vector<Segment> pathB = new Vector<Segment>(); 378 pathB.addAll(B.solids); 379 pathB.addAll(B.holes); 380 381 // create nodes 382 for (int i = 0; i < pathA.size(); i++) 383 { 384 Segment a = pathA.elementAt(i); 385 for (int j = 0; j < pathB.size(); j++) 386 { 387 Segment b = pathB.elementAt(j); 388 createNodes(a, b); 389 } 390 } 391 392 // we have intersecting points. 393 Vector<Segment> segments = new Vector<Segment>(); 394 395 // In an intersection operation, we keep all 396 // segments of A within B and all B within A 397 // (The rest must be redundant) 398 // We outsideness-test only one segment in each path 399 // and the segments before and after any node 400 for (int i = 0; i < pathA.size(); i++) 401 { 402 Segment v = pathA.elementAt(i); 403 Segment path = v; 404 if (! v.isSegmentOutside(area) && v.node == null) 405 segments.add(v); 406 boolean node = false; 407 do 408 { 409 if ((v.node != null || node)) 410 { 411 node = (v.node != null); 412 if (! v.isSegmentOutside(area)) 413 segments.add(v); 414 } 415 v = v.next; 416 } 417 while (v != path); 418 } 419 420 for (int i = 0; i < pathB.size(); i++) 421 { 422 Segment v = pathB.elementAt(i); 423 Segment path = v; 424 if (! v.isSegmentOutside(this) && v.node == null) 425 segments.add(v); 426 v = v.next; 427 boolean node = false; 428 do 429 { 430 if ((v.node != null || node)) 431 { 432 node = (v.node != null); 433 if (! v.isSegmentOutside(this)) 434 segments.add(v); 435 } 436 v = v.next; 437 } 438 while (v != path); 439 } 440 441 Vector<Segment> paths = weilerAtherton(segments); 442 deleteRedundantPaths(paths); 443 } 444 445 /** 446 * Performs an exclusive-or operation on this Area.<BR> 447 * @param area - the area to be XORed with this area. 448 * @throws NullPointerException if <code>area</code> is <code>null</code>. 449 */ 450 public void exclusiveOr(Area area) 451 { 452 if (area.isEmpty()) 453 return; 454 455 if (isEmpty()) 456 { 457 Area B = (Area) area.clone(); 458 solids = B.solids; 459 holes = B.holes; 460 return; 461 } 462 if (equals(area)) 463 { 464 reset(); 465 return; 466 } 467 468 Vector<Segment> pathA = new Vector<Segment>(); 469 470 Area B = (Area) area.clone(); 471 Vector<Segment> pathB = new Vector<Segment>(); 472 pathA.addAll(solids); 473 pathA.addAll(holes); 474 475 // reverse the directions of B paths. 476 setDirection(B.holes, true); 477 setDirection(B.solids, false); 478 pathB.addAll(B.solids); 479 pathB.addAll(B.holes); 480 481 for (int i = 0; i < pathA.size(); i++) 482 { 483 Segment a = pathA.elementAt(i); 484 for (int j = 0; j < pathB.size(); j++) 485 { 486 Segment b = pathB.elementAt(j); 487 createNodes(a, b); 488 } 489 } 490 491 Segment v; 492 493 // we have intersecting points. 494 Vector<Segment> segments = new Vector<Segment>(); 495 496 // In an XOR operation, we operate on all segments 497 for (int i = 0; i < pathA.size(); i++) 498 { 499 v = pathA.elementAt(i); 500 Segment path = v; 501 do 502 { 503 segments.add(v); 504 v = v.next; 505 } 506 while (v != path); 507 } 508 509 for (int i = 0; i < pathB.size(); i++) 510 { 511 v = pathB.elementAt(i); 512 Segment path = v; 513 do 514 { 515 segments.add(v); 516 v = v.next; 517 } 518 while (v != path); 519 } 520 521 Vector<Segment> paths = weilerAtherton(segments); 522 deleteRedundantPaths(paths); 523 } 524 525 /** 526 * Clears the Area object, creating an empty area. 527 */ 528 public void reset() 529 { 530 solids = new Vector<Segment>(); 531 holes = new Vector<Segment>(); 532 } 533 534 /** 535 * Returns whether this area encloses any area. 536 * @return true if the object encloses any area. 537 */ 538 public boolean isEmpty() 539 { 540 if (solids.size() == 0) 541 return true; 542 543 double totalArea = 0; 544 for (int i = 0; i < solids.size(); i++) 545 totalArea += Math.abs(solids.elementAt(i).getSignedArea()); 546 for (int i = 0; i < holes.size(); i++) 547 totalArea -= Math.abs(holes.elementAt(i).getSignedArea()); 548 if (totalArea <= EPSILON) 549 return true; 550 551 return false; 552 } 553 554 /** 555 * Determines whether the Area consists entirely of line segments 556 * @return true if the Area lines-only, false otherwise 557 */ 558 public boolean isPolygonal() 559 { 560 for (int i = 0; i < holes.size(); i++) 561 if (!holes.elementAt(i).isPolygonal()) 562 return false; 563 for (int i = 0; i < solids.size(); i++) 564 if (!solids.elementAt(i).isPolygonal()) 565 return false; 566 return true; 567 } 568 569 /** 570 * Determines if the Area is rectangular.<P> 571 * 572 * This is strictly qualified. An area is considered rectangular if:<BR> 573 * <li>It consists of a single polygonal path.<BR> 574 * <li>It is oriented parallel/perpendicular to the xy axis<BR> 575 * <li>It must be exactly rectangular, i.e. small errors induced by 576 * transformations may cause a false result, although the area is 577 * visibly rectangular.<P> 578 * @return true if the above criteria are met, false otherwise 579 */ 580 public boolean isRectangular() 581 { 582 if (isEmpty()) 583 return true; 584 585 if (holes.size() != 0 || solids.size() != 1) 586 return false; 587 588 Segment path = solids.elementAt(0); 589 if (! path.isPolygonal()) 590 return false; 591 592 int nCorners = 0; 593 Segment s = path; 594 do 595 { 596 Segment s2 = s.next; 597 double d1 = (s.P2.getX() - s.P1.getX())*(s2.P2.getX() - s2.P1.getX())/ 598 ((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2))); 599 double d2 = (s.P2.getY() - s.P1.getY())*(s2.P2.getY() - s2.P1.getY())/ 600 ((s.P1.distance(s.P2)) * (s2.P1.distance(s2.P2))); 601 double dotproduct = d1 + d2; 602 603 // For some reason, only rectangles on the XY axis count. 604 if (d1 != 0 && d2 != 0) 605 return false; 606 607 if (Math.abs(dotproduct) == 0) // 90 degree angle 608 nCorners++; 609 else if ((Math.abs(1.0 - dotproduct) > 0)) // 0 degree angle? 610 return false; // if not, return false 611 612 s = s.next; 613 } 614 while (s != path); 615 616 return nCorners == 4; 617 } 618 619 /** 620 * Returns whether the Area consists of more than one simple 621 * (non self-intersecting) subpath. 622 * 623 * @return true if the Area consists of none or one simple subpath, 624 * false otherwise. 625 */ 626 public boolean isSingular() 627 { 628 return (holes.size() == 0 && solids.size() <= 1); 629 } 630 631 /** 632 * Returns the bounding box of the Area.<P> Unlike the CubicCurve2D and 633 * QuadraticCurve2D classes, this method will return the tightest possible 634 * bounding box, evaluating the extreme points of each curved segment.<P> 635 * @return the bounding box 636 */ 637 public Rectangle2D getBounds2D() 638 { 639 if (solids.size() == 0) 640 return new Rectangle2D.Double(0.0, 0.0, 0.0, 0.0); 641 642 double xmin; 643 double xmax; 644 double ymin; 645 double ymax; 646 xmin = xmax = solids.elementAt(0).P1.getX(); 647 ymin = ymax = solids.elementAt(0).P1.getY(); 648 649 for (int path = 0; path < solids.size(); path++) 650 { 651 Rectangle2D r = solids.elementAt(path).getPathBounds(); 652 xmin = Math.min(r.getMinX(), xmin); 653 ymin = Math.min(r.getMinY(), ymin); 654 xmax = Math.max(r.getMaxX(), xmax); 655 ymax = Math.max(r.getMaxY(), ymax); 656 } 657 658 return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin))); 659 } 660 661 /** 662 * Returns the bounds of this object in Rectangle format. 663 * Please note that this may lead to loss of precision. 664 * 665 * @return The bounds. 666 * @see #getBounds2D() 667 */ 668 public Rectangle getBounds() 669 { 670 return getBounds2D().getBounds(); 671 } 672 673 /** 674 * Create a new area of the same run-time type with the same contents as 675 * this one. 676 * 677 * @return the clone 678 */ 679 public Object clone() 680 { 681 try 682 { 683 Area clone = new Area(); 684 for (int i = 0; i < solids.size(); i++) 685 clone.solids.add(solids.elementAt(i).cloneSegmentList()); 686 for (int i = 0; i < holes.size(); i++) 687 clone.holes.add(holes.elementAt(i).cloneSegmentList()); 688 return clone; 689 } 690 catch (CloneNotSupportedException e) 691 { 692 throw (Error) new InternalError().initCause(e); // Impossible 693 } 694 } 695 696 /** 697 * Compares two Areas. 698 * 699 * @param area the area to compare against this area (<code>null</code> 700 * permitted). 701 * @return <code>true</code> if the areas are equal, and <code>false</code> 702 * otherwise. 703 */ 704 public boolean equals(Area area) 705 { 706 if (area == null) 707 return false; 708 709 if (! getBounds2D().equals(area.getBounds2D())) 710 return false; 711 712 if (solids.size() != area.solids.size() 713 || holes.size() != area.holes.size()) 714 return false; 715 716 Vector<Segment> pathA = new Vector<Segment>(); 717 pathA.addAll(solids); 718 pathA.addAll(holes); 719 Vector<Segment> pathB = new Vector<Segment>(); 720 pathB.addAll(area.solids); 721 pathB.addAll(area.holes); 722 723 int nPaths = pathA.size(); 724 boolean[][] match = new boolean[2][nPaths]; 725 726 for (int i = 0; i < nPaths; i++) 727 { 728 for (int j = 0; j < nPaths; j++) 729 { 730 Segment p1 = pathA.elementAt(i); 731 Segment p2 = pathB.elementAt(j); 732 if (! match[0][i] && ! match[1][j]) 733 if (p1.pathEquals(p2)) 734 match[0][i] = match[1][j] = true; 735 } 736 } 737 738 boolean result = true; 739 for (int i = 0; i < nPaths; i++) 740 result = result && match[0][i] && match[1][i]; 741 return result; 742 } 743 744 /** 745 * Transforms this area by the AffineTransform at. 746 * 747 * @param at the transform. 748 */ 749 public void transform(AffineTransform at) 750 { 751 for (int i = 0; i < solids.size(); i++) 752 solids.elementAt(i).transformSegmentList(at); 753 for (int i = 0; i < holes.size(); i++) 754 holes.elementAt(i).transformSegmentList(at); 755 756 // Note that the orientation is not invariant under inversion 757 if ((at.getType() & AffineTransform.TYPE_FLIP) != 0) 758 { 759 setDirection(holes, false); 760 setDirection(solids, true); 761 } 762 } 763 764 /** 765 * Returns a new Area equal to this one, transformed 766 * by the AffineTransform at. 767 * @param at the transform. 768 * @return the transformed area 769 * @throws NullPointerException if <code>at</code> is <code>null</code>. 770 */ 771 public Area createTransformedArea(AffineTransform at) 772 { 773 Area a = (Area) clone(); 774 a.transform(at); 775 return a; 776 } 777 778 /** 779 * Determines if the point (x,y) is contained within this Area. 780 * 781 * @param x the x-coordinate of the point. 782 * @param y the y-coordinate of the point. 783 * @return true if the point is contained, false otherwise. 784 */ 785 public boolean contains(double x, double y) 786 { 787 int n = 0; 788 for (int i = 0; i < solids.size(); i++) 789 if (solids.elementAt(i).contains(x, y)) 790 n++; 791 792 for (int i = 0; i < holes.size(); i++) 793 if (holes.elementAt(i).contains(x, y)) 794 n--; 795 796 return (n != 0); 797 } 798 799 /** 800 * Determines if the Point2D p is contained within this Area. 801 * 802 * @param p the point. 803 * @return <code>true</code> if the point is contained, <code>false</code> 804 * otherwise. 805 * @throws NullPointerException if <code>p</code> is <code>null</code>. 806 */ 807 public boolean contains(Point2D p) 808 { 809 return contains(p.getX(), p.getY()); 810 } 811 812 /** 813 * Determines if the rectangle specified by (x,y) as the upper-left 814 * and with width w and height h is completely contained within this Area, 815 * returns false otherwise.<P> 816 * 817 * This method should always produce the correct results, unlike for other 818 * classes in geom. 819 * 820 * @param x the x-coordinate of the rectangle. 821 * @param y the y-coordinate of the rectangle. 822 * @param w the width of the the rectangle. 823 * @param h the height of the rectangle. 824 * @return <code>true</code> if the rectangle is considered contained 825 */ 826 public boolean contains(double x, double y, double w, double h) 827 { 828 LineSegment[] l = new LineSegment[4]; 829 l[0] = new LineSegment(x, y, x + w, y); 830 l[1] = new LineSegment(x, y + h, x + w, y + h); 831 l[2] = new LineSegment(x, y, x, y + h); 832 l[3] = new LineSegment(x + w, y, x + w, y + h); 833 834 // Since every segment in the area must a contour 835 // between inside/outside segments, ANY intersection 836 // will mean the rectangle is not entirely contained. 837 for (int i = 0; i < 4; i++) 838 { 839 for (int path = 0; path < solids.size(); path++) 840 { 841 Segment v; 842 Segment start; 843 start = v = solids.elementAt(path); 844 do 845 { 846 if (l[i].hasIntersections(v)) 847 return false; 848 v = v.next; 849 } 850 while (v != start); 851 } 852 for (int path = 0; path < holes.size(); path++) 853 { 854 Segment v; 855 Segment start; 856 start = v = holes.elementAt(path); 857 do 858 { 859 if (l[i].hasIntersections(v)) 860 return false; 861 v = v.next; 862 } 863 while (v != start); 864 } 865 } 866 867 // Is any point inside? 868 if (! contains(x, y)) 869 return false; 870 871 // Final hoop: Is the rectangle non-intersecting and inside, 872 // but encloses a hole? 873 Rectangle2D r = new Rectangle2D.Double(x, y, w, h); 874 for (int path = 0; path < holes.size(); path++) 875 if (! holes.elementAt(path).isSegmentOutside(r)) 876 return false; 877 878 return true; 879 } 880 881 /** 882 * Determines if the Rectangle2D specified by r is completely contained 883 * within this Area, returns false otherwise.<P> 884 * 885 * This method should always produce the correct results, unlike for other 886 * classes in geom. 887 * 888 * @param r the rectangle. 889 * @return <code>true</code> if the rectangle is considered contained 890 * 891 * @throws NullPointerException if <code>r</code> is <code>null</code>. 892 */ 893 public boolean contains(Rectangle2D r) 894 { 895 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 896 } 897 898 /** 899 * Determines if the rectangle specified by (x,y) as the upper-left 900 * and with width w and height h intersects any part of this Area. 901 * 902 * @param x the x-coordinate for the rectangle. 903 * @param y the y-coordinate for the rectangle. 904 * @param w the width of the rectangle. 905 * @param h the height of the rectangle. 906 * @return <code>true</code> if the rectangle intersects the area, 907 * <code>false</code> otherwise. 908 */ 909 public boolean intersects(double x, double y, double w, double h) 910 { 911 if (solids.size() == 0) 912 return false; 913 914 LineSegment[] l = new LineSegment[4]; 915 l[0] = new LineSegment(x, y, x + w, y); 916 l[1] = new LineSegment(x, y + h, x + w, y + h); 917 l[2] = new LineSegment(x, y, x, y + h); 918 l[3] = new LineSegment(x + w, y, x + w, y + h); 919 920 // Return true on any intersection 921 for (int i = 0; i < 4; i++) 922 { 923 for (int path = 0; path < solids.size(); path++) 924 { 925 Segment v; 926 Segment start; 927 start = v = solids.elementAt(path); 928 do 929 { 930 if (l[i].hasIntersections(v)) 931 return true; 932 v = v.next; 933 } 934 while (v != start); 935 } 936 for (int path = 0; path < holes.size(); path++) 937 { 938 Segment v; 939 Segment start; 940 start = v = holes.elementAt(path); 941 do 942 { 943 if (l[i].hasIntersections(v)) 944 return true; 945 v = v.next; 946 } 947 while (v != start); 948 } 949 } 950 951 // Non-intersecting, Is any point inside? 952 if (contains(x + w * 0.5, y + h * 0.5)) 953 return true; 954 955 // What if the rectangle encloses the whole shape? 956 Point2D p = solids.elementAt(0).getMidPoint(); 957 if ((new Rectangle2D.Double(x, y, w, h)).contains(p)) 958 return true; 959 return false; 960 } 961 962 /** 963 * Determines if the Rectangle2D specified by r intersects any 964 * part of this Area. 965 * @param r the rectangle to test intersection with (<code>null</code> 966 * not permitted). 967 * @return <code>true</code> if the rectangle intersects the area, 968 * <code>false</code> otherwise. 969 * @throws NullPointerException if <code>r</code> is <code>null</code>. 970 */ 971 public boolean intersects(Rectangle2D r) 972 { 973 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 974 } 975 976 /** 977 * Returns a PathIterator object defining the contour of this Area, 978 * transformed by at. 979 * 980 * @param at the transform. 981 * @return A path iterator. 982 */ 983 public PathIterator getPathIterator(AffineTransform at) 984 { 985 return (new AreaIterator(at)); 986 } 987 988 /** 989 * Returns a flattened PathIterator object defining the contour of this 990 * Area, transformed by at and with a defined flatness. 991 * 992 * @param at the transform. 993 * @param flatness the flatness. 994 * @return A path iterator. 995 */ 996 public PathIterator getPathIterator(AffineTransform at, double flatness) 997 { 998 return new FlatteningPathIterator(getPathIterator(at), flatness); 999 } 1000 1001 //--------------------------------------------------------------------- 1002 // Non-public methods and classes 1003 1004 /** 1005 * Private pathiterator object. 1006 */ 1007 private class AreaIterator implements PathIterator 1008 { 1009 private Vector<IteratorSegment> segments; 1010 private int index; 1011 private AffineTransform at; 1012 1013 // Simple compound type for segments 1014 class IteratorSegment 1015 { 1016 int type; 1017 double[] coords; 1018 1019 IteratorSegment() 1020 { 1021 coords = new double[6]; 1022 } 1023 } 1024 1025 /** 1026 * The contructor here does most of the work, 1027 * creates a vector of IteratorSegments, which can 1028 * readily be returned 1029 */ 1030 public AreaIterator(AffineTransform at) 1031 { 1032 this.at = at; 1033 index = 0; 1034 segments = new Vector<IteratorSegment>(); 1035 Vector<Segment> allpaths = new Vector<Segment>(); 1036 allpaths.addAll(solids); 1037 allpaths.addAll(holes); 1038 1039 for (int i = 0; i < allpaths.size(); i++) 1040 { 1041 Segment v = allpaths.elementAt(i); 1042 Segment start = v; 1043 1044 IteratorSegment is = new IteratorSegment(); 1045 is.type = SEG_MOVETO; 1046 is.coords[0] = start.P1.getX(); 1047 is.coords[1] = start.P1.getY(); 1048 segments.add(is); 1049 1050 do 1051 { 1052 is = new IteratorSegment(); 1053 is.type = v.pathIteratorFormat(is.coords); 1054 segments.add(is); 1055 v = v.next; 1056 } 1057 while (v != start); 1058 1059 is = new IteratorSegment(); 1060 is.type = SEG_CLOSE; 1061 segments.add(is); 1062 } 1063 } 1064 1065 public int currentSegment(double[] coords) 1066 { 1067 IteratorSegment s = segments.elementAt(index); 1068 if (at != null) 1069 at.transform(s.coords, 0, coords, 0, 3); 1070 else 1071 for (int i = 0; i < 6; i++) 1072 coords[i] = s.coords[i]; 1073 return (s.type); 1074 } 1075 1076 public int currentSegment(float[] coords) 1077 { 1078 IteratorSegment s = segments.elementAt(index); 1079 double[] d = new double[6]; 1080 if (at != null) 1081 { 1082 at.transform(s.coords, 0, d, 0, 3); 1083 for (int i = 0; i < 6; i++) 1084 coords[i] = (float) d[i]; 1085 } 1086 else 1087 for (int i = 0; i < 6; i++) 1088 coords[i] = (float) s.coords[i]; 1089 return (s.type); 1090 } 1091 1092 // Note that the winding rule should not matter here, 1093 // EVEN_ODD is chosen because it renders faster. 1094 public int getWindingRule() 1095 { 1096 return (PathIterator.WIND_EVEN_ODD); 1097 } 1098 1099 public boolean isDone() 1100 { 1101 return (index >= segments.size()); 1102 } 1103 1104 public void next() 1105 { 1106 index++; 1107 } 1108 } 1109 1110 /** 1111 * Performs the fundamental task of the Weiler-Atherton algorithm, 1112 * traverse a list of segments, for each segment: 1113 * Follow it, removing segments from the list and switching paths 1114 * at each node. Do so until the starting segment is reached. 1115 * 1116 * Returns a Vector of the resulting paths. 1117 */ 1118 private Vector<Segment> weilerAtherton(Vector<Segment> segments) 1119 { 1120 Vector<Segment> paths = new Vector<Segment>(); 1121 while (segments.size() > 0) 1122 { 1123 // Iterate over the path 1124 Segment start = segments.elementAt(0); 1125 Segment s = start; 1126 do 1127 { 1128 segments.remove(s); 1129 if (s.node != null) 1130 { // switch over 1131 s.next = s.node; 1132 s.node = null; 1133 } 1134 s = s.next; // continue 1135 } 1136 while (s != start); 1137 1138 paths.add(start); 1139 } 1140 return paths; 1141 } 1142 1143 /** 1144 * A small wrapper class to store intersection points 1145 */ 1146 private class Intersection 1147 { 1148 Point2D p; // the 2D point of intersection 1149 double ta; // the parametric value on a 1150 double tb; // the parametric value on b 1151 Segment seg; // segment placeholder for node setting 1152 1153 public Intersection(Point2D p, double ta, double tb) 1154 { 1155 this.p = p; 1156 this.ta = ta; 1157 this.tb = tb; 1158 } 1159 } 1160 1161 /** 1162 * Returns the recursion depth necessary to approximate the 1163 * curve by line segments within the error RS_EPSILON. 1164 * 1165 * This is done with Wang's formula: 1166 * L0 = max{0<=i<=N-2}(|xi - 2xi+1 + xi+2|,|yi - 2yi+1 + yi+2|) 1167 * r0 = log4(sqrt(2)*N*(N-1)*L0/8e) 1168 * Where e is the maximum distance error (RS_EPSILON) 1169 */ 1170 private int getRecursionDepth(CubicSegment curve) 1171 { 1172 double x0 = curve.P1.getX(); 1173 double y0 = curve.P1.getY(); 1174 1175 double x1 = curve.cp1.getX(); 1176 double y1 = curve.cp1.getY(); 1177 1178 double x2 = curve.cp2.getX(); 1179 double y2 = curve.cp2.getY(); 1180 1181 double x3 = curve.P2.getX(); 1182 double y3 = curve.P2.getY(); 1183 1184 double L0 = Math.max(Math.max(Math.abs(x0 - 2 * x1 + x2), 1185 Math.abs(x1 - 2 * x2 + x3)), 1186 Math.max(Math.abs(y0 - 2 * y1 + y2), 1187 Math.abs(y1 - 2 * y2 + y3))); 1188 1189 double f = Math.sqrt(2) * 6.0 * L0 / (8.0 * RS_EPSILON); 1190 1191 int r0 = (int) Math.ceil(Math.log(f) / Math.log(4.0)); 1192 return (r0); 1193 } 1194 1195 /** 1196 * Performs recursive subdivision: 1197 * @param c1 - curve 1 1198 * @param c2 - curve 2 1199 * @param depth1 - recursion depth of curve 1 1200 * @param depth2 - recursion depth of curve 2 1201 * @param t1 - global parametric value of the first curve's starting point 1202 * @param t2 - global parametric value of the second curve's starting point 1203 * @param w1 - global parametric length of curve 1 1204 * @param w2 - global parametric length of curve 2 1205 * 1206 * The final four parameters are for keeping track of the parametric 1207 * value of the curve. For a full curve t = 0, w = 1, w is halved with 1208 * each subdivision. 1209 */ 1210 private void recursiveSubdivide(CubicCurve2D c1, CubicCurve2D c2, 1211 int depth1, int depth2, double t1, 1212 double t2, double w1, double w2) 1213 { 1214 boolean flat1 = depth1 <= 0; 1215 boolean flat2 = depth2 <= 0; 1216 1217 if (flat1 && flat2) 1218 { 1219 double xlk = c1.getP2().getX() - c1.getP1().getX(); 1220 double ylk = c1.getP2().getY() - c1.getP1().getY(); 1221 1222 double xnm = c2.getP2().getX() - c2.getP1().getX(); 1223 double ynm = c2.getP2().getY() - c2.getP1().getY(); 1224 1225 double xmk = c2.getP1().getX() - c1.getP1().getX(); 1226 double ymk = c2.getP1().getY() - c1.getP1().getY(); 1227 double det = xnm * ylk - ynm * xlk; 1228 1229 if (det + 1.0 == 1.0) 1230 return; 1231 1232 double detinv = 1.0 / det; 1233 double s = (xnm * ymk - ynm * xmk) * detinv; 1234 double t = (xlk * ymk - ylk * xmk) * detinv; 1235 if ((s < 0.0) || (s > 1.0) || (t < 0.0) || (t > 1.0)) 1236 return; 1237 1238 double[] temp = new double[2]; 1239 temp[0] = t1 + s * w1; 1240 temp[1] = t2 + t * w1; 1241 ccIntersections.add(temp); 1242 return; 1243 } 1244 1245 CubicCurve2D.Double c11 = new CubicCurve2D.Double(); 1246 CubicCurve2D.Double c12 = new CubicCurve2D.Double(); 1247 CubicCurve2D.Double c21 = new CubicCurve2D.Double(); 1248 CubicCurve2D.Double c22 = new CubicCurve2D.Double(); 1249 1250 if (! flat1 && ! flat2) 1251 { 1252 depth1--; 1253 depth2--; 1254 w1 = w1 * 0.5; 1255 w2 = w2 * 0.5; 1256 c1.subdivide(c11, c12); 1257 c2.subdivide(c21, c22); 1258 if (c11.getBounds2D().intersects(c21.getBounds2D())) 1259 recursiveSubdivide(c11, c21, depth1, depth2, t1, t2, w1, w2); 1260 if (c11.getBounds2D().intersects(c22.getBounds2D())) 1261 recursiveSubdivide(c11, c22, depth1, depth2, t1, t2 + w2, w1, w2); 1262 if (c12.getBounds2D().intersects(c21.getBounds2D())) 1263 recursiveSubdivide(c12, c21, depth1, depth2, t1 + w1, t2, w1, w2); 1264 if (c12.getBounds2D().intersects(c22.getBounds2D())) 1265 recursiveSubdivide(c12, c22, depth1, depth2, t1 + w1, t2 + w2, w1, w2); 1266 return; 1267 } 1268 1269 if (! flat1) 1270 { 1271 depth1--; 1272 c1.subdivide(c11, c12); 1273 w1 = w1 * 0.5; 1274 if (c11.getBounds2D().intersects(c2.getBounds2D())) 1275 recursiveSubdivide(c11, c2, depth1, depth2, t1, t2, w1, w2); 1276 if (c12.getBounds2D().intersects(c2.getBounds2D())) 1277 recursiveSubdivide(c12, c2, depth1, depth2, t1 + w1, t2, w1, w2); 1278 return; 1279 } 1280 1281 depth2--; 1282 c2.subdivide(c21, c22); 1283 w2 = w2 * 0.5; 1284 if (c1.getBounds2D().intersects(c21.getBounds2D())) 1285 recursiveSubdivide(c1, c21, depth1, depth2, t1, t2, w1, w2); 1286 if (c1.getBounds2D().intersects(c22.getBounds2D())) 1287 recursiveSubdivide(c1, c22, depth1, depth2, t1, t2 + w2, w1, w2); 1288 } 1289 1290 /** 1291 * Returns a set of interesections between two Cubic segments 1292 * Or null if no intersections were found. 1293 * 1294 * The method used to find the intersection is recursive midpoint 1295 * subdivision. Outline description: 1296 * 1297 * 1) Check if the bounding boxes of the curves intersect, 1298 * 2) If so, divide the curves in the middle and test the bounding 1299 * boxes again, 1300 * 3) Repeat until a maximum recursion depth has been reached, where 1301 * the intersecting curves can be approximated by line segments. 1302 * 1303 * This is a reasonably accurate method, although the recursion depth 1304 * is typically around 20, the bounding-box tests allow for significant 1305 * pruning of the subdivision tree. 1306 * 1307 * This is package-private to avoid an accessor method. 1308 */ 1309 Intersection[] cubicCubicIntersect(CubicSegment curve1, CubicSegment curve2) 1310 { 1311 Rectangle2D r1 = curve1.getBounds(); 1312 Rectangle2D r2 = curve2.getBounds(); 1313 1314 if (! r1.intersects(r2)) 1315 return null; 1316 1317 ccIntersections = new Vector<double[]>(); 1318 recursiveSubdivide(curve1.getCubicCurve2D(), curve2.getCubicCurve2D(), 1319 getRecursionDepth(curve1), getRecursionDepth(curve2), 1320 0.0, 0.0, 1.0, 1.0); 1321 1322 if (ccIntersections.size() == 0) 1323 return null; 1324 1325 Intersection[] results = new Intersection[ccIntersections.size()]; 1326 for (int i = 0; i < ccIntersections.size(); i++) 1327 { 1328 double[] temp = ccIntersections.elementAt(i); 1329 results[i] = new Intersection(curve1.evaluatePoint(temp[0]), temp[0], 1330 temp[1]); 1331 } 1332 ccIntersections = null; 1333 return (results); 1334 } 1335 1336 /** 1337 * Returns the intersections between a line and a quadratic bezier 1338 * Or null if no intersections are found. 1339 * This is done through combining the line's equation with the 1340 * parametric form of the Bezier and solving the resulting quadratic. 1341 * This is package-private to avoid an accessor method. 1342 */ 1343 Intersection[] lineQuadIntersect(LineSegment l, QuadSegment c) 1344 { 1345 double[] y = new double[3]; 1346 double[] x = new double[3]; 1347 double[] r = new double[3]; 1348 int nRoots; 1349 double x0 = c.P1.getX(); 1350 double y0 = c.P1.getY(); 1351 double x1 = c.cp.getX(); 1352 double y1 = c.cp.getY(); 1353 double x2 = c.P2.getX(); 1354 double y2 = c.P2.getY(); 1355 1356 double lx0 = l.P1.getX(); 1357 double ly0 = l.P1.getY(); 1358 double lx1 = l.P2.getX(); 1359 double ly1 = l.P2.getY(); 1360 double dx = lx1 - lx0; 1361 double dy = ly1 - ly0; 1362 1363 // form r(t) = y(t) - x(t) for the bezier 1364 y[0] = y0; 1365 y[1] = 2 * (y1 - y0); 1366 y[2] = (y2 - 2 * y1 + y0); 1367 1368 x[0] = x0; 1369 x[1] = 2 * (x1 - x0); 1370 x[2] = (x2 - 2 * x1 + x0); 1371 1372 // a point, not a line 1373 if (dy == 0 && dx == 0) 1374 return null; 1375 1376 // line on y axis 1377 if (dx == 0 || (dy / dx) > 1.0) 1378 { 1379 double k = dx / dy; 1380 x[0] -= lx0; 1381 y[0] -= ly0; 1382 y[0] *= k; 1383 y[1] *= k; 1384 y[2] *= k; 1385 } 1386 else 1387 { 1388 double k = dy / dx; 1389 x[0] -= lx0; 1390 y[0] -= ly0; 1391 x[0] *= k; 1392 x[1] *= k; 1393 x[2] *= k; 1394 } 1395 1396 for (int i = 0; i < 3; i++) 1397 r[i] = y[i] - x[i]; 1398 1399 if ((nRoots = QuadCurve2D.solveQuadratic(r)) > 0) 1400 { 1401 Intersection[] temp = new Intersection[nRoots]; 1402 int intersections = 0; 1403 for (int i = 0; i < nRoots; i++) 1404 { 1405 double t = r[i]; 1406 if (t >= 0.0 && t <= 1.0) 1407 { 1408 Point2D p = c.evaluatePoint(t); 1409 1410 // if the line is on an axis, snap the point to that axis. 1411 if (dx == 0) 1412 p.setLocation(lx0, p.getY()); 1413 if (dy == 0) 1414 p.setLocation(p.getX(), ly0); 1415 1416 if (p.getX() <= Math.max(lx0, lx1) 1417 && p.getX() >= Math.min(lx0, lx1) 1418 && p.getY() <= Math.max(ly0, ly1) 1419 && p.getY() >= Math.min(ly0, ly1)) 1420 { 1421 double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1); 1422 temp[i] = new Intersection(p, lineparameter, t); 1423 intersections++; 1424 } 1425 } 1426 else 1427 temp[i] = null; 1428 } 1429 if (intersections == 0) 1430 return null; 1431 1432 Intersection[] rValues = new Intersection[intersections]; 1433 1434 for (int i = 0; i < nRoots; i++) 1435 if (temp[i] != null) 1436 rValues[--intersections] = temp[i]; 1437 return (rValues); 1438 } 1439 return null; 1440 } 1441 1442 /** 1443 * Returns the intersections between a line and a cubic segment 1444 * This is done through combining the line's equation with the 1445 * parametric form of the Bezier and solving the resulting quadratic. 1446 * This is package-private to avoid an accessor method. 1447 */ 1448 Intersection[] lineCubicIntersect(LineSegment l, CubicSegment c) 1449 { 1450 double[] y = new double[4]; 1451 double[] x = new double[4]; 1452 double[] r = new double[4]; 1453 int nRoots; 1454 double x0 = c.P1.getX(); 1455 double y0 = c.P1.getY(); 1456 double x1 = c.cp1.getX(); 1457 double y1 = c.cp1.getY(); 1458 double x2 = c.cp2.getX(); 1459 double y2 = c.cp2.getY(); 1460 double x3 = c.P2.getX(); 1461 double y3 = c.P2.getY(); 1462 1463 double lx0 = l.P1.getX(); 1464 double ly0 = l.P1.getY(); 1465 double lx1 = l.P2.getX(); 1466 double ly1 = l.P2.getY(); 1467 double dx = lx1 - lx0; 1468 double dy = ly1 - ly0; 1469 1470 // form r(t) = y(t) - x(t) for the bezier 1471 y[0] = y0; 1472 y[1] = 3 * (y1 - y0); 1473 y[2] = 3 * (y2 + y0 - 2 * y1); 1474 y[3] = y3 - 3 * y2 + 3 * y1 - y0; 1475 1476 x[0] = x0; 1477 x[1] = 3 * (x1 - x0); 1478 x[2] = 3 * (x2 + x0 - 2 * x1); 1479 x[3] = x3 - 3 * x2 + 3 * x1 - x0; 1480 1481 // a point, not a line 1482 if (dy == 0 && dx == 0) 1483 return null; 1484 1485 // line on y axis 1486 if (dx == 0 || (dy / dx) > 1.0) 1487 { 1488 double k = dx / dy; 1489 x[0] -= lx0; 1490 y[0] -= ly0; 1491 y[0] *= k; 1492 y[1] *= k; 1493 y[2] *= k; 1494 y[3] *= k; 1495 } 1496 else 1497 { 1498 double k = dy / dx; 1499 x[0] -= lx0; 1500 y[0] -= ly0; 1501 x[0] *= k; 1502 x[1] *= k; 1503 x[2] *= k; 1504 x[3] *= k; 1505 } 1506 for (int i = 0; i < 4; i++) 1507 r[i] = y[i] - x[i]; 1508 1509 if ((nRoots = CubicCurve2D.solveCubic(r)) > 0) 1510 { 1511 Intersection[] temp = new Intersection[nRoots]; 1512 int intersections = 0; 1513 for (int i = 0; i < nRoots; i++) 1514 { 1515 double t = r[i]; 1516 if (t >= 0.0 && t <= 1.0) 1517 { 1518 // if the line is on an axis, snap the point to that axis. 1519 Point2D p = c.evaluatePoint(t); 1520 if (dx == 0) 1521 p.setLocation(lx0, p.getY()); 1522 if (dy == 0) 1523 p.setLocation(p.getX(), ly0); 1524 1525 if (p.getX() <= Math.max(lx0, lx1) 1526 && p.getX() >= Math.min(lx0, lx1) 1527 && p.getY() <= Math.max(ly0, ly1) 1528 && p.getY() >= Math.min(ly0, ly1)) 1529 { 1530 double lineparameter = p.distance(l.P1) / l.P2.distance(l.P1); 1531 temp[i] = new Intersection(p, lineparameter, t); 1532 intersections++; 1533 } 1534 } 1535 else 1536 temp[i] = null; 1537 } 1538 1539 if (intersections == 0) 1540 return null; 1541 1542 Intersection[] rValues = new Intersection[intersections]; 1543 for (int i = 0; i < nRoots; i++) 1544 if (temp[i] != null) 1545 rValues[--intersections] = temp[i]; 1546 return (rValues); 1547 } 1548 return null; 1549 } 1550 1551 /** 1552 * Returns the intersection between two lines, or null if there is no 1553 * intersection. 1554 * This is package-private to avoid an accessor method. 1555 */ 1556 Intersection linesIntersect(LineSegment a, LineSegment b) 1557 { 1558 Point2D P1 = a.P1; 1559 Point2D P2 = a.P2; 1560 Point2D P3 = b.P1; 1561 Point2D P4 = b.P2; 1562 1563 if (! Line2D.linesIntersect(P1.getX(), P1.getY(), P2.getX(), P2.getY(), 1564 P3.getX(), P3.getY(), P4.getX(), P4.getY())) 1565 return null; 1566 1567 double x1 = P1.getX(); 1568 double y1 = P1.getY(); 1569 double rx = P2.getX() - x1; 1570 double ry = P2.getY() - y1; 1571 1572 double x2 = P3.getX(); 1573 double y2 = P3.getY(); 1574 double sx = P4.getX() - x2; 1575 double sy = P4.getY() - y2; 1576 1577 double determinant = sx * ry - sy * rx; 1578 double nom = (sx * (y2 - y1) + sy * (x1 - x2)); 1579 1580 // Parallel lines don't intersect. At least we pretend they don't. 1581 if (Math.abs(determinant) < EPSILON) 1582 return null; 1583 1584 nom = nom / determinant; 1585 1586 if (nom == 0.0) 1587 return null; 1588 if (nom == 1.0) 1589 return null; 1590 1591 Point2D p = new Point2D.Double(x1 + nom * rx, y1 + nom * ry); 1592 1593 return new Intersection(p, p.distance(P1) / P1.distance(P2), 1594 p.distance(P3) / P3.distance(P4)); 1595 } 1596 1597 /** 1598 * Determines if two points are equal, within an error margin 1599 * 'snap distance' 1600 * This is package-private to avoid an accessor method. 1601 */ 1602 boolean pointEquals(Point2D a, Point2D b) 1603 { 1604 return (a.equals(b) || a.distance(b) < PE_EPSILON); 1605 } 1606 1607 /** 1608 * Helper method 1609 * Turns a shape into a Vector of Segments 1610 */ 1611 private Vector<Segment> makeSegment(Shape s) 1612 { 1613 Vector<Segment> paths = new Vector<Segment>(); 1614 PathIterator pi = s.getPathIterator(null); 1615 double[] coords = new double[6]; 1616 Segment subpath = null; 1617 Segment current = null; 1618 double cx; 1619 double cy; 1620 double subpathx; 1621 double subpathy; 1622 cx = cy = subpathx = subpathy = 0.0; 1623 1624 this.windingRule = pi.getWindingRule(); 1625 1626 while (! pi.isDone()) 1627 { 1628 Segment v; 1629 switch (pi.currentSegment(coords)) 1630 { 1631 case PathIterator.SEG_MOVETO: 1632 if (subpath != null) 1633 { // close existing open path 1634 current.next = new LineSegment(cx, cy, subpathx, subpathy); 1635 current = current.next; 1636 current.next = subpath; 1637 } 1638 subpath = null; 1639 subpathx = cx = coords[0]; 1640 subpathy = cy = coords[1]; 1641 break; 1642 1643 // replace 'close' with a line-to. 1644 case PathIterator.SEG_CLOSE: 1645 if (subpath != null && (subpathx != cx || subpathy != cy)) 1646 { 1647 current.next = new LineSegment(cx, cy, subpathx, subpathy); 1648 current = current.next; 1649 current.next = subpath; 1650 cx = subpathx; 1651 cy = subpathy; 1652 subpath = null; 1653 } 1654 else if (subpath != null) 1655 { 1656 current.next = subpath; 1657 subpath = null; 1658 } 1659 break; 1660 case PathIterator.SEG_LINETO: 1661 if (cx != coords[0] || cy != coords[1]) 1662 { 1663 v = new LineSegment(cx, cy, coords[0], coords[1]); 1664 if (subpath == null) 1665 { 1666 subpath = current = v; 1667 paths.add(subpath); 1668 } 1669 else 1670 { 1671 current.next = v; 1672 current = current.next; 1673 } 1674 cx = coords[0]; 1675 cy = coords[1]; 1676 } 1677 break; 1678 case PathIterator.SEG_QUADTO: 1679 v = new QuadSegment(cx, cy, coords[0], coords[1], coords[2], 1680 coords[3]); 1681 if (subpath == null) 1682 { 1683 subpath = current = v; 1684 paths.add(subpath); 1685 } 1686 else 1687 { 1688 current.next = v; 1689 current = current.next; 1690 } 1691 cx = coords[2]; 1692 cy = coords[3]; 1693 break; 1694 case PathIterator.SEG_CUBICTO: 1695 v = new CubicSegment(cx, cy, coords[0], coords[1], coords[2], 1696 coords[3], coords[4], coords[5]); 1697 if (subpath == null) 1698 { 1699 subpath = current = v; 1700 paths.add(subpath); 1701 } 1702 else 1703 { 1704 current.next = v; 1705 current = current.next; 1706 } 1707 1708 // check if the cubic is self-intersecting 1709 double[] lpts = ((CubicSegment) v).getLoop(); 1710 if (lpts != null) 1711 { 1712 // if it is, break off the loop into its own path. 1713 v.subdivideInsert(lpts[0]); 1714 v.next.subdivideInsert((lpts[1] - lpts[0]) / (1.0 - lpts[0])); 1715 1716 CubicSegment loop = (CubicSegment) v.next; 1717 v.next = loop.next; 1718 loop.next = loop; 1719 1720 v.P2 = v.next.P1 = loop.P2 = loop.P1; // snap points 1721 paths.add(loop); 1722 current = v.next; 1723 } 1724 1725 cx = coords[4]; 1726 cy = coords[5]; 1727 break; 1728 } 1729 pi.next(); 1730 } 1731 1732 if (subpath != null) 1733 { // close any open path 1734 if (subpathx != cx || subpathy != cy) 1735 { 1736 current.next = new LineSegment(cx, cy, subpathx, subpathy); 1737 current = current.next; 1738 current.next = subpath; 1739 } 1740 else 1741 current.next = subpath; 1742 } 1743 1744 if (paths.size() == 0) 1745 return (null); 1746 1747 return (paths); 1748 } 1749 1750 /** 1751 * Find the intersections of two separate closed paths, 1752 * A and B, split the segments at the intersection points, 1753 * and create nodes pointing from one to the other 1754 */ 1755 private int createNodes(Segment A, Segment B) 1756 { 1757 int nNodes = 0; 1758 1759 Segment a = A; 1760 Segment b = B; 1761 1762 do 1763 { 1764 do 1765 { 1766 nNodes += a.splitIntersections(b); 1767 b = b.next; 1768 } 1769 while (b != B); 1770 1771 a = a.next; // move to the next segment 1772 } 1773 while (a != A); // until one wrap. 1774 1775 return nNodes; 1776 } 1777 1778 /** 1779 * Find the intersections of a path with itself. 1780 * Splits the segments at the intersection points, 1781 * and create nodes pointing from one to the other. 1782 */ 1783 private int createNodesSelf(Segment A) 1784 { 1785 int nNodes = 0; 1786 Segment a = A; 1787 1788 if (A.next == A) 1789 return 0; 1790 1791 do 1792 { 1793 Segment b = a.next; 1794 do 1795 { 1796 if (b != a) // necessary 1797 nNodes += a.splitIntersections(b); 1798 b = b.next; 1799 } 1800 while (b != A); 1801 a = a.next; // move to the next segment 1802 } 1803 while (a != A); // until one wrap. 1804 1805 return (nNodes); 1806 } 1807 1808 /** 1809 * Deletes paths which are redundant from a list, (i.e. solid areas within 1810 * solid areas) Clears any nodes. Sorts the remaining paths into solids 1811 * and holes, sets their orientation and sets the solids and holes lists. 1812 */ 1813 private void deleteRedundantPaths(Vector<Segment> paths) 1814 { 1815 int npaths = paths.size(); 1816 1817 int[][] contains = new int[npaths][npaths]; 1818 int[][] windingNumbers = new int[npaths][2]; 1819 int neg; 1820 Rectangle2D[] bb = new Rectangle2D[npaths]; // path bounding boxes 1821 1822 neg = ((windingRule == PathIterator.WIND_NON_ZERO) ? -1 : 1); 1823 1824 for (int i = 0; i < npaths; i++) 1825 bb[i] = paths.elementAt(i).getPathBounds(); 1826 1827 // Find which path contains which, assign winding numbers 1828 for (int i = 0; i < npaths; i++) 1829 { 1830 Segment pathA = paths.elementAt(i); 1831 pathA.nullNodes(); // remove any now-redundant nodes, in case. 1832 int windingA = pathA.hasClockwiseOrientation() ? 1 : neg; 1833 1834 for (int j = 0; j < npaths; j++) 1835 if (i != j) 1836 { 1837 Segment pathB = paths.elementAt(j); 1838 1839 // A contains B 1840 if (bb[i].intersects(bb[j])) 1841 { 1842 Segment s = pathB.next; 1843 while (s.P1.getY() == s.P2.getY() && s != pathB) 1844 s = s.next; 1845 Point2D p = s.getMidPoint(); 1846 if (pathA.contains(p.getX(), p.getY())) 1847 contains[i][j] = windingA; 1848 } 1849 else 1850 // A does not contain B 1851 contains[i][j] = 0; 1852 } 1853 else 1854 contains[i][j] = windingA; // i == j 1855 } 1856 1857 for (int i = 0; i < npaths; i++) 1858 { 1859 windingNumbers[i][0] = 0; 1860 for (int j = 0; j < npaths; j++) 1861 windingNumbers[i][0] += contains[j][i]; 1862 windingNumbers[i][1] = contains[i][i]; 1863 } 1864 1865 Vector<Segment> solids = new Vector<Segment>(); 1866 Vector<Segment> holes = new Vector<Segment>(); 1867 1868 if (windingRule == PathIterator.WIND_NON_ZERO) 1869 { 1870 for (int i = 0; i < npaths; i++) 1871 { 1872 if (windingNumbers[i][0] == 0) 1873 holes.add(paths.elementAt(i)); 1874 else if (windingNumbers[i][0] - windingNumbers[i][1] == 0 1875 && Math.abs(windingNumbers[i][0]) == 1) 1876 solids.add(paths.elementAt(i)); 1877 } 1878 } 1879 else 1880 { 1881 windingRule = PathIterator.WIND_NON_ZERO; 1882 for (int i = 0; i < npaths; i++) 1883 { 1884 if ((windingNumbers[i][0] & 1) == 0) 1885 holes.add(paths.elementAt(i)); 1886 else if ((windingNumbers[i][0] & 1) == 1) 1887 solids.add(paths.elementAt(i)); 1888 } 1889 } 1890 1891 setDirection(holes, false); 1892 setDirection(solids, true); 1893 this.holes = holes; 1894 this.solids = solids; 1895 } 1896 1897 /** 1898 * Sets the winding direction of a Vector of paths 1899 * @param clockwise gives the direction, 1900 * true = clockwise, false = counter-clockwise 1901 */ 1902 private void setDirection(Vector<Segment> paths, boolean clockwise) 1903 { 1904 Segment v; 1905 for (int i = 0; i < paths.size(); i++) 1906 { 1907 v = paths.elementAt(i); 1908 if (clockwise != v.hasClockwiseOrientation()) 1909 v.reverseAll(); 1910 } 1911 } 1912 1913 /** 1914 * Class representing a linked-list of vertices forming a closed polygon, 1915 * convex or concave, without holes. 1916 */ 1917 private abstract class Segment implements Cloneable 1918 { 1919 // segment type, PathIterator segment types are used. 1920 Point2D P1; 1921 Point2D P2; 1922 Segment next; 1923 Segment node; 1924 1925 Segment() 1926 { 1927 P1 = P2 = null; 1928 node = next = null; 1929 } 1930 1931 /** 1932 * Reverses the direction of a single segment 1933 */ 1934 abstract void reverseCoords(); 1935 1936 /** 1937 * Returns the segment's midpoint 1938 */ 1939 abstract Point2D getMidPoint(); 1940 1941 /** 1942 * Returns the bounding box of this segment 1943 */ 1944 abstract Rectangle2D getBounds(); 1945 1946 /** 1947 * Transforms a single segment 1948 */ 1949 abstract void transform(AffineTransform at); 1950 1951 /** 1952 * Returns the PathIterator type of a segment 1953 */ 1954 abstract int getType(); 1955 1956 /** 1957 */ 1958 abstract int splitIntersections(Segment b); 1959 1960 /** 1961 * Returns the PathIterator coords of a segment 1962 */ 1963 abstract int pathIteratorFormat(double[] coords); 1964 1965 /** 1966 * Returns the number of intersections on the positive X axis, 1967 * with the origin at (x,y), used for contains()-testing 1968 * 1969 * (Although that could be done by the line-intersect methods, 1970 * a dedicated method is better to guarantee consitent handling 1971 * of endpoint-special-cases) 1972 */ 1973 abstract int rayCrossing(double x, double y); 1974 1975 /** 1976 * Subdivides the segment at parametric value t, inserting 1977 * the new segment into the linked list after this, 1978 * such that this becomes [0,t] and this.next becomes [t,1] 1979 */ 1980 abstract void subdivideInsert(double t); 1981 1982 /** 1983 * Returns twice the area of a curve, relative the P1-P2 line 1984 * Used for area calculations. 1985 */ 1986 abstract double curveArea(); 1987 1988 /** 1989 * Compare two segments. 1990 */ 1991 abstract boolean equals(Segment b); 1992 1993 /** 1994 * Determines if this path of segments contains the point (x,y) 1995 */ 1996 boolean contains(double x, double y) 1997 { 1998 Segment v = this; 1999 int crossings = 0; 2000 do 2001 { 2002 int n = v.rayCrossing(x, y); 2003 crossings += n; 2004 v = v.next; 2005 } 2006 while (v != this); 2007 return ((crossings & 1) == 1); 2008 } 2009 2010 /** 2011 * Nulls all nodes of the path. Clean up any 'hairs'. 2012 */ 2013 void nullNodes() 2014 { 2015 Segment v = this; 2016 do 2017 { 2018 v.node = null; 2019 v = v.next; 2020 } 2021 while (v != this); 2022 } 2023 2024 /** 2025 * Transforms each segment in the closed path 2026 */ 2027 void transformSegmentList(AffineTransform at) 2028 { 2029 Segment v = this; 2030 do 2031 { 2032 v.transform(at); 2033 v = v.next; 2034 } 2035 while (v != this); 2036 } 2037 2038 /** 2039 * Determines the winding direction of the path 2040 * By the sign of the area. 2041 */ 2042 boolean hasClockwiseOrientation() 2043 { 2044 return (getSignedArea() > 0.0); 2045 } 2046 2047 /** 2048 * Returns the bounds of this path 2049 */ 2050 public Rectangle2D getPathBounds() 2051 { 2052 double xmin; 2053 double xmax; 2054 double ymin; 2055 double ymax; 2056 xmin = xmax = P1.getX(); 2057 ymin = ymax = P1.getY(); 2058 2059 Segment v = this; 2060 do 2061 { 2062 Rectangle2D r = v.getBounds(); 2063 xmin = Math.min(r.getMinX(), xmin); 2064 ymin = Math.min(r.getMinY(), ymin); 2065 xmax = Math.max(r.getMaxX(), xmax); 2066 ymax = Math.max(r.getMaxY(), ymax); 2067 v = v.next; 2068 } 2069 while (v != this); 2070 2071 return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin))); 2072 } 2073 2074 /** 2075 * Calculates twice the signed area of the path; 2076 */ 2077 double getSignedArea() 2078 { 2079 Segment s; 2080 double area = 0.0; 2081 2082 s = this; 2083 do 2084 { 2085 area += s.curveArea(); 2086 2087 area += s.P1.getX() * s.next.P1.getY() 2088 - s.P1.getY() * s.next.P1.getX(); 2089 s = s.next; 2090 } 2091 while (s != this); 2092 2093 return area; 2094 } 2095 2096 /** 2097 * Reverses the orientation of the whole polygon 2098 */ 2099 void reverseAll() 2100 { 2101 reverseCoords(); 2102 Segment v = next; 2103 Segment former = this; 2104 while (v != this) 2105 { 2106 v.reverseCoords(); 2107 Segment vnext = v.next; 2108 v.next = former; 2109 former = v; 2110 v = vnext; 2111 } 2112 next = former; 2113 } 2114 2115 /** 2116 * Inserts a Segment after this one 2117 */ 2118 void insert(Segment v) 2119 { 2120 Segment n = next; 2121 next = v; 2122 v.next = n; 2123 } 2124 2125 /** 2126 * Returns if this segment path is polygonal 2127 */ 2128 boolean isPolygonal() 2129 { 2130 Segment v = this; 2131 do 2132 { 2133 if (! (v instanceof LineSegment)) 2134 return false; 2135 v = v.next; 2136 } 2137 while (v != this); 2138 return true; 2139 } 2140 2141 /** 2142 * Clones this path 2143 */ 2144 Segment cloneSegmentList() throws CloneNotSupportedException 2145 { 2146 Vector<Segment> list = new Vector<Segment>(); 2147 Segment v = next; 2148 2149 while (v != this) 2150 { 2151 list.add(v); 2152 v = v.next; 2153 } 2154 2155 Segment clone = (Segment) this.clone(); 2156 v = clone; 2157 for (int i = 0; i < list.size(); i++) 2158 { 2159 clone.next = (Segment) list.elementAt(i).clone(); 2160 clone = clone.next; 2161 } 2162 clone.next = v; 2163 return v; 2164 } 2165 2166 /** 2167 * Creates a node between this segment and segment b 2168 * at the given intersection 2169 * @return the number of nodes created (0 or 1) 2170 */ 2171 int createNode(Segment b, Intersection i) 2172 { 2173 Point2D p = i.p; 2174 if ((pointEquals(P1, p) || pointEquals(P2, p)) 2175 && (pointEquals(b.P1, p) || pointEquals(b.P2, p))) 2176 return 0; 2177 2178 subdivideInsert(i.ta); 2179 b.subdivideInsert(i.tb); 2180 2181 // snap points 2182 b.P2 = b.next.P1 = P2 = next.P1 = i.p; 2183 2184 node = b.next; 2185 b.node = next; 2186 return 1; 2187 } 2188 2189 /** 2190 * Creates multiple nodes from a list of intersections, 2191 * This must be done in the order of ascending parameters, 2192 * and the parameters must be recalculated in accordance 2193 * with each split. 2194 * @return the number of nodes created 2195 */ 2196 protected int createNodes(Segment b, Intersection[] x) 2197 { 2198 Vector<Intersection> v = new Vector<Intersection>(); 2199 for (int i = 0; i < x.length; i++) 2200 { 2201 Point2D p = x[i].p; 2202 if (! ((pointEquals(P1, p) || pointEquals(P2, p)) 2203 && (pointEquals(b.P1, p) || pointEquals(b.P2, p)))) 2204 v.add(x[i]); 2205 } 2206 2207 int nNodes = v.size(); 2208 Intersection[] A = new Intersection[nNodes]; 2209 Intersection[] B = new Intersection[nNodes]; 2210 for (int i = 0; i < nNodes; i++) 2211 A[i] = B[i] = v.elementAt(i); 2212 2213 // Create two lists sorted by the parameter 2214 // Bubble sort, OK I suppose, since the number of intersections 2215 // cannot be larger than 9 (cubic-cubic worst case) anyway 2216 for (int i = 0; i < nNodes - 1; i++) 2217 { 2218 for (int j = i + 1; j < nNodes; j++) 2219 { 2220 if (A[i].ta > A[j].ta) 2221 { 2222 Intersection swap = A[i]; 2223 A[i] = A[j]; 2224 A[j] = swap; 2225 } 2226 if (B[i].tb > B[j].tb) 2227 { 2228 Intersection swap = B[i]; 2229 B[i] = B[j]; 2230 B[j] = swap; 2231 } 2232 } 2233 } 2234 // subdivide a 2235 Segment s = this; 2236 for (int i = 0; i < nNodes; i++) 2237 { 2238 s.subdivideInsert(A[i].ta); 2239 2240 // renormalize the parameters 2241 for (int j = i + 1; j < nNodes; j++) 2242 A[j].ta = (A[j].ta - A[i].ta) / (1.0 - A[i].ta); 2243 2244 A[i].seg = s; 2245 s = s.next; 2246 } 2247 2248 // subdivide b, set nodes 2249 s = b; 2250 for (int i = 0; i < nNodes; i++) 2251 { 2252 s.subdivideInsert(B[i].tb); 2253 2254 for (int j = i + 1; j < nNodes; j++) 2255 B[j].tb = (B[j].tb - B[i].tb) / (1.0 - B[i].tb); 2256 2257 // set nodes 2258 B[i].seg.node = s.next; // node a -> b 2259 s.node = B[i].seg.next; // node b -> a 2260 2261 // snap points 2262 B[i].seg.P2 = B[i].seg.next.P1 = s.P2 = s.next.P1 = B[i].p; 2263 s = s.next; 2264 } 2265 return nNodes; 2266 } 2267 2268 /** 2269 * Determines if two paths are equal. 2270 * Colinear line segments are ignored in the comparison. 2271 */ 2272 boolean pathEquals(Segment B) 2273 { 2274 if (! getPathBounds().equals(B.getPathBounds())) 2275 return false; 2276 2277 Segment startA = getTopLeft(); 2278 Segment startB = B.getTopLeft(); 2279 Segment a = startA; 2280 Segment b = startB; 2281 do 2282 { 2283 if (! a.equals(b)) 2284 return false; 2285 2286 if (a instanceof LineSegment) 2287 a = ((LineSegment) a).lastCoLinear(); 2288 if (b instanceof LineSegment) 2289 b = ((LineSegment) b).lastCoLinear(); 2290 2291 a = a.next; 2292 b = b.next; 2293 } 2294 while (a != startA && b != startB); 2295 return true; 2296 } 2297 2298 /** 2299 * Return the segment with the top-leftmost first point 2300 */ 2301 Segment getTopLeft() 2302 { 2303 Segment v = this; 2304 Segment tl = this; 2305 do 2306 { 2307 if (v.P1.getY() < tl.P1.getY()) 2308 tl = v; 2309 else if (v.P1.getY() == tl.P1.getY()) 2310 { 2311 if (v.P1.getX() < tl.P1.getX()) 2312 tl = v; 2313 } 2314 v = v.next; 2315 } 2316 while (v != this); 2317 return tl; 2318 } 2319 2320 /** 2321 * Returns if the path has a segment outside a shape 2322 */ 2323 boolean isSegmentOutside(Shape shape) 2324 { 2325 return ! shape.contains(getMidPoint()); 2326 } 2327 } // class Segment 2328 2329 private class LineSegment extends Segment 2330 { 2331 public LineSegment(double x1, double y1, double x2, double y2) 2332 { 2333 super(); 2334 P1 = new Point2D.Double(x1, y1); 2335 P2 = new Point2D.Double(x2, y2); 2336 } 2337 2338 public LineSegment(Point2D p1, Point2D p2) 2339 { 2340 super(); 2341 P1 = (Point2D) p1.clone(); 2342 P2 = (Point2D) p2.clone(); 2343 } 2344 2345 /** 2346 * Clones this segment 2347 */ 2348 public Object clone() 2349 { 2350 return new LineSegment(P1, P2); 2351 } 2352 2353 /** 2354 * Transforms the segment 2355 */ 2356 void transform(AffineTransform at) 2357 { 2358 P1 = at.transform(P1, null); 2359 P2 = at.transform(P2, null); 2360 } 2361 2362 /** 2363 * Swap start and end points 2364 */ 2365 void reverseCoords() 2366 { 2367 Point2D p = P1; 2368 P1 = P2; 2369 P2 = p; 2370 } 2371 2372 /** 2373 * Returns the segment's midpoint 2374 */ 2375 Point2D getMidPoint() 2376 { 2377 return (new Point2D.Double(0.5 * (P1.getX() + P2.getX()), 2378 0.5 * (P1.getY() + P2.getY()))); 2379 } 2380 2381 /** 2382 * Returns twice the area of a curve, relative the P1-P2 line 2383 * Obviously, a line does not enclose any area besides the line 2384 */ 2385 double curveArea() 2386 { 2387 return 0; 2388 } 2389 2390 /** 2391 * Returns the PathIterator type of a segment 2392 */ 2393 int getType() 2394 { 2395 return (PathIterator.SEG_LINETO); 2396 } 2397 2398 /** 2399 * Subdivides the segment at parametric value t, inserting 2400 * the new segment into the linked list after this, 2401 * such that this becomes [0,t] and this.next becomes [t,1] 2402 */ 2403 void subdivideInsert(double t) 2404 { 2405 Point2D p = new Point2D.Double((P2.getX() - P1.getX()) * t + P1.getX(), 2406 (P2.getY() - P1.getY()) * t + P1.getY()); 2407 insert(new LineSegment(p, P2)); 2408 P2 = p; 2409 next.node = node; 2410 node = null; 2411 } 2412 2413 /** 2414 * Determines if two line segments are strictly colinear 2415 */ 2416 boolean isCoLinear(LineSegment b) 2417 { 2418 double x1 = P1.getX(); 2419 double y1 = P1.getY(); 2420 double x2 = P2.getX(); 2421 double y2 = P2.getY(); 2422 double x3 = b.P1.getX(); 2423 double y3 = b.P1.getY(); 2424 double x4 = b.P2.getX(); 2425 double y4 = b.P2.getY(); 2426 2427 if ((y1 - y3) * (x4 - x3) - (x1 - x3) * (y4 - y3) != 0.0) 2428 return false; 2429 2430 return ((x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3) == 0.0); 2431 } 2432 2433 /** 2434 * Return the last segment colinear with this one. 2435 * Used in comparing paths. 2436 */ 2437 Segment lastCoLinear() 2438 { 2439 Segment prev = this; 2440 Segment v = next; 2441 2442 while (v instanceof LineSegment) 2443 { 2444 if (isCoLinear((LineSegment) v)) 2445 { 2446 prev = v; 2447 v = v.next; 2448 } 2449 else 2450 return prev; 2451 } 2452 return prev; 2453 } 2454 2455 /** 2456 * Compare two segments. 2457 * We must take into account that the lines may be broken into colinear 2458 * subsegments and ignore them. 2459 */ 2460 boolean equals(Segment b) 2461 { 2462 if (! (b instanceof LineSegment)) 2463 return false; 2464 Point2D p1 = P1; 2465 Point2D p3 = b.P1; 2466 2467 if (! p1.equals(p3)) 2468 return false; 2469 2470 Point2D p2 = lastCoLinear().P2; 2471 Point2D p4 = ((LineSegment) b).lastCoLinear().P2; 2472 return (p2.equals(p4)); 2473 } 2474 2475 /** 2476 * Returns a line segment 2477 */ 2478 int pathIteratorFormat(double[] coords) 2479 { 2480 coords[0] = P2.getX(); 2481 coords[1] = P2.getY(); 2482 return (PathIterator.SEG_LINETO); 2483 } 2484 2485 /** 2486 * Returns if the line has intersections. 2487 */ 2488 boolean hasIntersections(Segment b) 2489 { 2490 if (b instanceof LineSegment) 2491 return (linesIntersect(this, (LineSegment) b) != null); 2492 2493 if (b instanceof QuadSegment) 2494 return (lineQuadIntersect(this, (QuadSegment) b) != null); 2495 2496 if (b instanceof CubicSegment) 2497 return (lineCubicIntersect(this, (CubicSegment) b) != null); 2498 2499 return false; 2500 } 2501 2502 /** 2503 * Splits intersections into nodes, 2504 * This one handles line-line, line-quadratic, line-cubic 2505 */ 2506 int splitIntersections(Segment b) 2507 { 2508 if (b instanceof LineSegment) 2509 { 2510 Intersection i = linesIntersect(this, (LineSegment) b); 2511 2512 if (i == null) 2513 return 0; 2514 2515 return createNode(b, i); 2516 } 2517 2518 Intersection[] x = null; 2519 2520 if (b instanceof QuadSegment) 2521 x = lineQuadIntersect(this, (QuadSegment) b); 2522 2523 if (b instanceof CubicSegment) 2524 x = lineCubicIntersect(this, (CubicSegment) b); 2525 2526 if (x == null) 2527 return 0; 2528 2529 if (x.length == 1) 2530 return createNode(b, (Intersection) x[0]); 2531 2532 return createNodes(b, x); 2533 } 2534 2535 /** 2536 * Returns the bounding box of this segment 2537 */ 2538 Rectangle2D getBounds() 2539 { 2540 return (new Rectangle2D.Double(Math.min(P1.getX(), P2.getX()), 2541 Math.min(P1.getY(), P2.getY()), 2542 Math.abs(P1.getX() - P2.getX()), 2543 Math.abs(P1.getY() - P2.getY()))); 2544 } 2545 2546 /** 2547 * Returns the number of intersections on the positive X axis, 2548 * with the origin at (x,y), used for contains()-testing 2549 */ 2550 int rayCrossing(double x, double y) 2551 { 2552 double x0 = P1.getX() - x; 2553 double y0 = P1.getY() - y; 2554 double x1 = P2.getX() - x; 2555 double y1 = P2.getY() - y; 2556 2557 if (y0 * y1 > 0) 2558 return 0; 2559 2560 if (x0 < 0 && x1 < 0) 2561 return 0; 2562 2563 if (y0 == 0.0) 2564 y0 -= EPSILON; 2565 2566 if (y1 == 0.0) 2567 y1 -= EPSILON; 2568 2569 if (Line2D.linesIntersect(x0, y0, x1, y1, 2570 EPSILON, 0.0, Double.MAX_VALUE, 0.0)) 2571 return 1; 2572 return 0; 2573 } 2574 } // class LineSegment 2575 2576 /** 2577 * Quadratic Bezier curve segment 2578 * 2579 * Note: Most peers don't support quadratics directly, so it might make 2580 * sense to represent them as cubics internally and just be done with it. 2581 * I think we should be peer-agnostic, however, and stay faithful to the 2582 * input geometry types as far as possible. 2583 */ 2584 private class QuadSegment extends Segment 2585 { 2586 Point2D cp; // control point 2587 2588 /** 2589 * Constructor, takes the coordinates of the start, control, 2590 * and end point, respectively. 2591 */ 2592 QuadSegment(double x1, double y1, double cx, double cy, double x2, 2593 double y2) 2594 { 2595 super(); 2596 P1 = new Point2D.Double(x1, y1); 2597 P2 = new Point2D.Double(x2, y2); 2598 cp = new Point2D.Double(cx, cy); 2599 } 2600 2601 /** 2602 * Clones this segment 2603 */ 2604 public Object clone() 2605 { 2606 return new QuadSegment(P1.getX(), P1.getY(), cp.getX(), cp.getY(), 2607 P2.getX(), P2.getY()); 2608 } 2609 2610 /** 2611 * Returns twice the area of a curve, relative the P1-P2 line 2612 * 2613 * The area formula can be derived by using Green's formula in the 2614 * plane on the parametric form of the bezier. 2615 */ 2616 double curveArea() 2617 { 2618 double x0 = P1.getX(); 2619 double y0 = P1.getY(); 2620 double x1 = cp.getX(); 2621 double y1 = cp.getY(); 2622 double x2 = P2.getX(); 2623 double y2 = P2.getY(); 2624 2625 double P = (y2 - 2 * y1 + y0); 2626 double Q = 2 * (y1 - y0); 2627 2628 double A = (x2 - 2 * x1 + x0); 2629 double B = 2 * (x1 - x0); 2630 2631 double area = (B * P - A * Q) / 3.0; 2632 return (area); 2633 } 2634 2635 /** 2636 * Compare two segments. 2637 */ 2638 boolean equals(Segment b) 2639 { 2640 if (! (b instanceof QuadSegment)) 2641 return false; 2642 2643 return (P1.equals(b.P1) && cp.equals(((QuadSegment) b).cp) 2644 && P2.equals(b.P2)); 2645 } 2646 2647 /** 2648 * Returns a Point2D corresponding to the parametric value t 2649 * of the curve 2650 */ 2651 Point2D evaluatePoint(double t) 2652 { 2653 double x0 = P1.getX(); 2654 double y0 = P1.getY(); 2655 double x1 = cp.getX(); 2656 double y1 = cp.getY(); 2657 double x2 = P2.getX(); 2658 double y2 = P2.getY(); 2659 2660 return new Point2D.Double(t * t * (x2 - 2 * x1 + x0) + 2 * t * (x1 - x0) 2661 + x0, 2662 t * t * (y2 - 2 * y1 + y0) + 2 * t * (y1 - y0) 2663 + y0); 2664 } 2665 2666 /** 2667 * Returns the bounding box of this segment 2668 */ 2669 Rectangle2D getBounds() 2670 { 2671 double x0 = P1.getX(); 2672 double y0 = P1.getY(); 2673 double x1 = cp.getX(); 2674 double y1 = cp.getY(); 2675 double x2 = P2.getX(); 2676 double y2 = P2.getY(); 2677 double r0; 2678 double r1; 2679 2680 double xmax = Math.max(x0, x2); 2681 double ymax = Math.max(y0, y2); 2682 double xmin = Math.min(x0, x2); 2683 double ymin = Math.min(y0, y2); 2684 2685 r0 = 2 * (y1 - y0); 2686 r1 = 2 * (y2 - 2 * y1 + y0); 2687 if (r1 != 0.0) 2688 { 2689 double t = -r0 / r1; 2690 if (t > 0.0 && t < 1.0) 2691 { 2692 double y = evaluatePoint(t).getY(); 2693 ymax = Math.max(y, ymax); 2694 ymin = Math.min(y, ymin); 2695 } 2696 } 2697 r0 = 2 * (x1 - x0); 2698 r1 = 2 * (x2 - 2 * x1 + x0); 2699 if (r1 != 0.0) 2700 { 2701 double t = -r0 / r1; 2702 if (t > 0.0 && t < 1.0) 2703 { 2704 double x = evaluatePoint(t).getY(); 2705 xmax = Math.max(x, xmax); 2706 xmin = Math.min(x, xmin); 2707 } 2708 } 2709 2710 return (new Rectangle2D.Double(xmin, ymin, xmax - xmin, ymax - ymin)); 2711 } 2712 2713 /** 2714 * Returns a cubic segment corresponding to this curve 2715 */ 2716 CubicSegment getCubicSegment() 2717 { 2718 double x1 = P1.getX() + 2.0 * (cp.getX() - P1.getX()) / 3.0; 2719 double y1 = P1.getY() + 2.0 * (cp.getY() - P1.getY()) / 3.0; 2720 double x2 = cp.getX() + (P2.getX() - cp.getX()) / 3.0; 2721 double y2 = cp.getY() + (P2.getY() - cp.getY()) / 3.0; 2722 2723 return new CubicSegment(P1.getX(), P1.getY(), x1, y1, x2, y2, P2.getX(), 2724 P2.getY()); 2725 } 2726 2727 /** 2728 * Returns the segment's midpoint 2729 */ 2730 Point2D getMidPoint() 2731 { 2732 return evaluatePoint(0.5); 2733 } 2734 2735 /** 2736 * Returns the PathIterator type of a segment 2737 */ 2738 int getType() 2739 { 2740 return (PathIterator.SEG_QUADTO); 2741 } 2742 2743 /** 2744 * Returns the PathIterator coords of a segment 2745 */ 2746 int pathIteratorFormat(double[] coords) 2747 { 2748 coords[0] = cp.getX(); 2749 coords[1] = cp.getY(); 2750 coords[2] = P2.getX(); 2751 coords[3] = P2.getY(); 2752 return (PathIterator.SEG_QUADTO); 2753 } 2754 2755 /** 2756 * Returns the number of intersections on the positive X axis, 2757 * with the origin at (x,y), used for contains()-testing 2758 */ 2759 int rayCrossing(double x, double y) 2760 { 2761 double x0 = P1.getX() - x; 2762 double y0 = P1.getY() - y; 2763 double x1 = cp.getX() - x; 2764 double y1 = cp.getY() - y; 2765 double x2 = P2.getX() - x; 2766 double y2 = P2.getY() - y; 2767 double[] r = new double[3]; 2768 int nRoots; 2769 int nCrossings = 0; 2770 2771 /* check if curve may intersect X+ axis. */ 2772 if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0) && (y0 * y1 <= 0 || y1 * y2 <= 0)) 2773 { 2774 if (y0 == 0.0) 2775 y0 -= EPSILON; 2776 if (y2 == 0.0) 2777 y2 -= EPSILON; 2778 2779 r[0] = y0; 2780 r[1] = 2 * (y1 - y0); 2781 r[2] = (y2 - 2 * y1 + y0); 2782 2783 nRoots = QuadCurve2D.solveQuadratic(r); 2784 for (int i = 0; i < nRoots; i++) 2785 if (r[i] > 0.0f && r[i] < 1.0f) 2786 { 2787 double t = r[i]; 2788 if (t * t * (x2 - 2 * x1 + x0) + 2 * t * (x1 - x0) + x0 > 0.0) 2789 nCrossings++; 2790 } 2791 } 2792 return nCrossings; 2793 } 2794 2795 /** 2796 * Swap start and end points 2797 */ 2798 void reverseCoords() 2799 { 2800 Point2D temp = P1; 2801 P1 = P2; 2802 P2 = temp; 2803 } 2804 2805 /** 2806 * Splits intersections into nodes, 2807 * This one handles quadratic-quadratic only, 2808 * Quadratic-line is passed on to the LineSegment class, 2809 * Quadratic-cubic is passed on to the CubicSegment class 2810 */ 2811 int splitIntersections(Segment b) 2812 { 2813 if (b instanceof LineSegment) 2814 return (b.splitIntersections(this)); 2815 2816 if (b instanceof CubicSegment) 2817 return (b.splitIntersections(this)); 2818 2819 if (b instanceof QuadSegment) 2820 { 2821 // Use the cubic-cubic intersection routine for quads as well, 2822 // Since a quadratic can be exactly described as a cubic, this 2823 // should not be a problem; 2824 // The recursion depth will be the same in any case. 2825 Intersection[] x = cubicCubicIntersect(getCubicSegment(), 2826 ((QuadSegment) b) 2827 .getCubicSegment()); 2828 if (x == null) 2829 return 0; 2830 2831 if (x.length == 1) 2832 return createNode(b, (Intersection) x[0]); 2833 2834 return createNodes(b, x); 2835 } 2836 return 0; 2837 } 2838 2839 /** 2840 * Subdivides the segment at parametric value t, inserting 2841 * the new segment into the linked list after this, 2842 * such that this becomes [0,t] and this.next becomes [t,1] 2843 */ 2844 void subdivideInsert(double t) 2845 { 2846 double x0 = P1.getX(); 2847 double y0 = P1.getY(); 2848 double x1 = cp.getX(); 2849 double y1 = cp.getY(); 2850 double x2 = P2.getX(); 2851 double y2 = P2.getY(); 2852 2853 double p10x = x0 + t * (x1 - x0); 2854 double p10y = y0 + t * (y1 - y0); 2855 double p11x = x1 + t * (x2 - x1); 2856 double p11y = y1 + t * (y2 - y1); 2857 double p20x = p10x + t * (p11x - p10x); 2858 double p20y = p10y + t * (p11y - p10y); 2859 2860 insert(new QuadSegment(p20x, p20y, p11x, p11y, x2, y2)); 2861 P2 = next.P1; 2862 cp.setLocation(p10x, p10y); 2863 2864 next.node = node; 2865 node = null; 2866 } 2867 2868 /** 2869 * Transforms the segment 2870 */ 2871 void transform(AffineTransform at) 2872 { 2873 P1 = at.transform(P1, null); 2874 P2 = at.transform(P2, null); 2875 cp = at.transform(cp, null); 2876 } 2877 } // class QuadSegment 2878 2879 /** 2880 * Cubic Bezier curve segment 2881 */ 2882 private class CubicSegment extends Segment 2883 { 2884 Point2D cp1; // control points 2885 Point2D cp2; // control points 2886 2887 /** 2888 * Constructor - takes coordinates of the starting point, 2889 * first control point, second control point and end point, 2890 * respecively. 2891 */ 2892 public CubicSegment(double x1, double y1, double c1x, double c1y, 2893 double c2x, double c2y, double x2, double y2) 2894 { 2895 super(); 2896 P1 = new Point2D.Double(x1, y1); 2897 P2 = new Point2D.Double(x2, y2); 2898 cp1 = new Point2D.Double(c1x, c1y); 2899 cp2 = new Point2D.Double(c2x, c2y); 2900 } 2901 2902 /** 2903 * Clones this segment 2904 */ 2905 public Object clone() 2906 { 2907 return new CubicSegment(P1.getX(), P1.getY(), cp1.getX(), cp1.getY(), 2908 cp2.getX(), cp2.getY(), P2.getX(), P2.getY()); 2909 } 2910 2911 /** 2912 * Returns twice the area of a curve, relative the P1-P2 line 2913 * 2914 * The area formula can be derived by using Green's formula in the 2915 * plane on the parametric form of the bezier. 2916 */ 2917 double curveArea() 2918 { 2919 double x0 = P1.getX(); 2920 double y0 = P1.getY(); 2921 double x1 = cp1.getX(); 2922 double y1 = cp1.getY(); 2923 double x2 = cp2.getX(); 2924 double y2 = cp2.getY(); 2925 double x3 = P2.getX(); 2926 double y3 = P2.getY(); 2927 2928 double P = y3 - 3 * y2 + 3 * y1 - y0; 2929 double Q = 3 * (y2 + y0 - 2 * y1); 2930 double R = 3 * (y1 - y0); 2931 2932 double A = x3 - 3 * x2 + 3 * x1 - x0; 2933 double B = 3 * (x2 + x0 - 2 * x1); 2934 double C = 3 * (x1 - x0); 2935 2936 double area = (B * P - A * Q) / 5.0 + (C * P - A * R) / 2.0 2937 + (C * Q - B * R) / 3.0; 2938 2939 return (area); 2940 } 2941 2942 /** 2943 * Compare two segments. 2944 */ 2945 boolean equals(Segment b) 2946 { 2947 if (! (b instanceof CubicSegment)) 2948 return false; 2949 2950 return (P1.equals(b.P1) && cp1.equals(((CubicSegment) b).cp1) 2951 && cp2.equals(((CubicSegment) b).cp2) && P2.equals(b.P2)); 2952 } 2953 2954 /** 2955 * Returns a Point2D corresponding to the parametric value t 2956 * of the curve 2957 */ 2958 Point2D evaluatePoint(double t) 2959 { 2960 double x0 = P1.getX(); 2961 double y0 = P1.getY(); 2962 double x1 = cp1.getX(); 2963 double y1 = cp1.getY(); 2964 double x2 = cp2.getX(); 2965 double y2 = cp2.getY(); 2966 double x3 = P2.getX(); 2967 double y3 = P2.getY(); 2968 2969 return new Point2D.Double(-(t * t * t) * (x0 - 3 * x1 + 3 * x2 - x3) 2970 + 3 * t * t * (x0 - 2 * x1 + x2) 2971 + 3 * t * (x1 - x0) + x0, 2972 -(t * t * t) * (y0 - 3 * y1 + 3 * y2 - y3) 2973 + 3 * t * t * (y0 - 2 * y1 + y2) 2974 + 3 * t * (y1 - y0) + y0); 2975 } 2976 2977 /** 2978 * Returns the bounding box of this segment 2979 */ 2980 Rectangle2D getBounds() 2981 { 2982 double x0 = P1.getX(); 2983 double y0 = P1.getY(); 2984 double x1 = cp1.getX(); 2985 double y1 = cp1.getY(); 2986 double x2 = cp2.getX(); 2987 double y2 = cp2.getY(); 2988 double x3 = P2.getX(); 2989 double y3 = P2.getY(); 2990 double[] r = new double[3]; 2991 2992 double xmax = Math.max(x0, x3); 2993 double ymax = Math.max(y0, y3); 2994 double xmin = Math.min(x0, x3); 2995 double ymin = Math.min(y0, y3); 2996 2997 r[0] = 3 * (y1 - y0); 2998 r[1] = 6.0 * (y2 + y0 - 2 * y1); 2999 r[2] = 3.0 * (y3 - 3 * y2 + 3 * y1 - y0); 3000 3001 int n = QuadCurve2D.solveQuadratic(r); 3002 for (int i = 0; i < n; i++) 3003 { 3004 double t = r[i]; 3005 if (t > 0 && t < 1.0) 3006 { 3007 double y = evaluatePoint(t).getY(); 3008 ymax = Math.max(y, ymax); 3009 ymin = Math.min(y, ymin); 3010 } 3011 } 3012 3013 r[0] = 3 * (x1 - x0); 3014 r[1] = 6.0 * (x2 + x0 - 2 * x1); 3015 r[2] = 3.0 * (x3 - 3 * x2 + 3 * x1 - x0); 3016 n = QuadCurve2D.solveQuadratic(r); 3017 for (int i = 0; i < n; i++) 3018 { 3019 double t = r[i]; 3020 if (t > 0 && t < 1.0) 3021 { 3022 double x = evaluatePoint(t).getX(); 3023 xmax = Math.max(x, xmax); 3024 xmin = Math.min(x, xmin); 3025 } 3026 } 3027 return (new Rectangle2D.Double(xmin, ymin, (xmax - xmin), (ymax - ymin))); 3028 } 3029 3030 /** 3031 * Returns a CubicCurve2D object corresponding to this segment. 3032 */ 3033 CubicCurve2D getCubicCurve2D() 3034 { 3035 return new CubicCurve2D.Double(P1.getX(), P1.getY(), cp1.getX(), 3036 cp1.getY(), cp2.getX(), cp2.getY(), 3037 P2.getX(), P2.getY()); 3038 } 3039 3040 /** 3041 * Returns the parametric points of self-intersection if the cubic 3042 * is self-intersecting, null otherwise. 3043 */ 3044 double[] getLoop() 3045 { 3046 double x0 = P1.getX(); 3047 double y0 = P1.getY(); 3048 double x1 = cp1.getX(); 3049 double y1 = cp1.getY(); 3050 double x2 = cp2.getX(); 3051 double y2 = cp2.getY(); 3052 double x3 = P2.getX(); 3053 double y3 = P2.getY(); 3054 double[] r = new double[4]; 3055 double k; 3056 double R; 3057 double T; 3058 double A; 3059 double B; 3060 double[] results = new double[2]; 3061 3062 R = x3 - 3 * x2 + 3 * x1 - x0; 3063 T = y3 - 3 * y2 + 3 * y1 - y0; 3064 3065 // A qudratic 3066 if (R == 0.0 && T == 0.0) 3067 return null; 3068 3069 // true cubic 3070 if (R != 0.0 && T != 0.0) 3071 { 3072 A = 3 * (x2 + x0 - 2 * x1) / R; 3073 B = 3 * (x1 - x0) / R; 3074 3075 double P = 3 * (y2 + y0 - 2 * y1) / T; 3076 double Q = 3 * (y1 - y0) / T; 3077 3078 if (A == P || Q == B) 3079 return null; 3080 3081 k = (Q - B) / (A - P); 3082 } 3083 else 3084 { 3085 if (R == 0.0) 3086 { 3087 // quadratic in x 3088 k = -(3 * (x1 - x0)) / (3 * (x2 + x0 - 2 * x1)); 3089 A = 3 * (y2 + y0 - 2 * y1) / T; 3090 B = 3 * (y1 - y0) / T; 3091 } 3092 else 3093 { 3094 // quadratic in y 3095 k = -(3 * (y1 - y0)) / (3 * (y2 + y0 - 2 * y1)); 3096 A = 3 * (x2 + x0 - 2 * x1) / R; 3097 B = 3 * (x1 - x0) / R; 3098 } 3099 } 3100 3101 r[0] = -k * k * k - A * k * k - B * k; 3102 r[1] = 3 * k * k + 2 * k * A + 2 * B; 3103 r[2] = -3 * k; 3104 r[3] = 2; 3105 3106 int n = CubicCurve2D.solveCubic(r); 3107 if (n != 3) 3108 return null; 3109 3110 // sort r 3111 double t; 3112 for (int i = 0; i < 2; i++) 3113 for (int j = i + 1; j < 3; j++) 3114 if (r[j] < r[i]) 3115 { 3116 t = r[i]; 3117 r[i] = r[j]; 3118 r[j] = t; 3119 } 3120 3121 if (Math.abs(r[0] + r[2] - k) < 1E-13) 3122 if (r[0] >= 0.0 && r[0] <= 1.0 && r[2] >= 0.0 && r[2] <= 1.0) 3123 if (evaluatePoint(r[0]).distance(evaluatePoint(r[2])) < PE_EPSILON * 10) 3124 { // we snap the points anyway 3125 results[0] = r[0]; 3126 results[1] = r[2]; 3127 return (results); 3128 } 3129 return null; 3130 } 3131 3132 /** 3133 * Returns the segment's midpoint 3134 */ 3135 Point2D getMidPoint() 3136 { 3137 return evaluatePoint(0.5); 3138 } 3139 3140 /** 3141 * Returns the PathIterator type of a segment 3142 */ 3143 int getType() 3144 { 3145 return (PathIterator.SEG_CUBICTO); 3146 } 3147 3148 /** 3149 * Returns the PathIterator coords of a segment 3150 */ 3151 int pathIteratorFormat(double[] coords) 3152 { 3153 coords[0] = cp1.getX(); 3154 coords[1] = cp1.getY(); 3155 coords[2] = cp2.getX(); 3156 coords[3] = cp2.getY(); 3157 coords[4] = P2.getX(); 3158 coords[5] = P2.getY(); 3159 return (PathIterator.SEG_CUBICTO); 3160 } 3161 3162 /** 3163 * Returns the number of intersections on the positive X axis, 3164 * with the origin at (x,y), used for contains()-testing 3165 */ 3166 int rayCrossing(double x, double y) 3167 { 3168 double x0 = P1.getX() - x; 3169 double y0 = P1.getY() - y; 3170 double x1 = cp1.getX() - x; 3171 double y1 = cp1.getY() - y; 3172 double x2 = cp2.getX() - x; 3173 double y2 = cp2.getY() - y; 3174 double x3 = P2.getX() - x; 3175 double y3 = P2.getY() - y; 3176 double[] r = new double[4]; 3177 int nRoots; 3178 int nCrossings = 0; 3179 3180 /* check if curve may intersect X+ axis. */ 3181 if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0 || x3 > 0.0) 3182 && (y0 * y1 <= 0 || y1 * y2 <= 0 || y2 * y3 <= 0)) 3183 { 3184 if (y0 == 0.0) 3185 y0 -= EPSILON; 3186 if (y3 == 0.0) 3187 y3 -= EPSILON; 3188 3189 r[0] = y0; 3190 r[1] = 3 * (y1 - y0); 3191 r[2] = 3 * (y2 + y0 - 2 * y1); 3192 r[3] = y3 - 3 * y2 + 3 * y1 - y0; 3193 3194 if ((nRoots = CubicCurve2D.solveCubic(r)) > 0) 3195 for (int i = 0; i < nRoots; i++) 3196 { 3197 if (r[i] > 0.0 && r[i] < 1.0) 3198 { 3199 double t = r[i]; 3200 if (-(t * t * t) * (x0 - 3 * x1 + 3 * x2 - x3) 3201 + 3 * t * t * (x0 - 2 * x1 + x2) + 3 * t * (x1 - x0) 3202 + x0 > 0.0) 3203 nCrossings++; 3204 } 3205 } 3206 } 3207 return nCrossings; 3208 } 3209 3210 /** 3211 * Swap start and end points 3212 */ 3213 void reverseCoords() 3214 { 3215 Point2D p = P1; 3216 P1 = P2; 3217 P2 = p; 3218 p = cp1; // swap control points 3219 cp1 = cp2; 3220 cp2 = p; 3221 } 3222 3223 /** 3224 * Splits intersections into nodes, 3225 * This one handles cubic-cubic and cubic-quadratic intersections 3226 */ 3227 int splitIntersections(Segment b) 3228 { 3229 if (b instanceof LineSegment) 3230 return (b.splitIntersections(this)); 3231 3232 Intersection[] x = null; 3233 3234 if (b instanceof QuadSegment) 3235 x = cubicCubicIntersect(this, ((QuadSegment) b).getCubicSegment()); 3236 3237 if (b instanceof CubicSegment) 3238 x = cubicCubicIntersect(this, (CubicSegment) b); 3239 3240 if (x == null) 3241 return 0; 3242 3243 if (x.length == 1) 3244 return createNode(b, x[0]); 3245 3246 return createNodes(b, x); 3247 } 3248 3249 /** 3250 * Subdivides the segment at parametric value t, inserting 3251 * the new segment into the linked list after this, 3252 * such that this becomes [0,t] and this.next becomes [t,1] 3253 */ 3254 void subdivideInsert(double t) 3255 { 3256 CubicSegment s = (CubicSegment) clone(); 3257 double p1x = (s.cp1.getX() - s.P1.getX()) * t + s.P1.getX(); 3258 double p1y = (s.cp1.getY() - s.P1.getY()) * t + s.P1.getY(); 3259 3260 double px = (s.cp2.getX() - s.cp1.getX()) * t + s.cp1.getX(); 3261 double py = (s.cp2.getY() - s.cp1.getY()) * t + s.cp1.getY(); 3262 3263 s.cp2.setLocation((s.P2.getX() - s.cp2.getX()) * t + s.cp2.getX(), 3264 (s.P2.getY() - s.cp2.getY()) * t + s.cp2.getY()); 3265 3266 s.cp1.setLocation((s.cp2.getX() - px) * t + px, 3267 (s.cp2.getY() - py) * t + py); 3268 3269 double p2x = (px - p1x) * t + p1x; 3270 double p2y = (py - p1y) * t + p1y; 3271 3272 double p3x = (s.cp1.getX() - p2x) * t + p2x; 3273 double p3y = (s.cp1.getY() - p2y) * t + p2y; 3274 s.P1.setLocation(p3x, p3y); 3275 3276 // insert new curve 3277 insert(s); 3278 3279 // set this curve 3280 cp1.setLocation(p1x, p1y); 3281 cp2.setLocation(p2x, p2y); 3282 P2 = s.P1; 3283 next.node = node; 3284 node = null; 3285 } 3286 3287 /** 3288 * Transforms the segment 3289 */ 3290 void transform(AffineTransform at) 3291 { 3292 P1 = at.transform(P1, null); 3293 P2 = at.transform(P2, null); 3294 cp1 = at.transform(cp1, null); 3295 cp2 = at.transform(cp2, null); 3296 } 3297 } // class CubicSegment 3298} // class Area