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