001 /* GeneralPath.java -- represents a shape built from subpaths 002 Copyright (C) 2002, 2003, 2004, 2006 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 039 package java.awt.geom; 040 041 import java.awt.Rectangle; 042 import java.awt.Shape; 043 044 045 /** 046 * A general geometric path, consisting of any number of subpaths 047 * constructed out of straight lines and cubic or quadratic Bezier 048 * curves. 049 * 050 * <p>The inside of the curve is defined for drawing purposes by a winding 051 * rule. Either the WIND_EVEN_ODD or WIND_NON_ZERO winding rule can be chosen. 052 * 053 * <p><img src="doc-files/GeneralPath-1.png" width="300" height="210" 054 * alt="A drawing of a GeneralPath" /> 055 * <p>The EVEN_ODD winding rule defines a point as inside a path if: 056 * A ray from the point towards infinity in an arbitrary direction 057 * intersects the path an odd number of times. Points <b>A</b> and 058 * <b>C</b> in the image are considered to be outside the path. 059 * (both intersect twice) 060 * Point <b>B</b> intersects once, and is inside. 061 * 062 * <p>The NON_ZERO winding rule defines a point as inside a path if: 063 * The path intersects the ray in an equal number of opposite directions. 064 * Point <b>A</b> in the image is outside (one intersection in the 065 * ’up’ 066 * direction, one in the ’down’ direction) Point <b>B</b> in 067 * the image is inside (one intersection ’down’) 068 * Point <b>C</b> in the image is inside (two intersections in the 069 * ’down’ direction) 070 * 071 * @see Line2D 072 * @see CubicCurve2D 073 * @see QuadCurve2D 074 * 075 * @author Sascha Brawer (brawer@dandelis.ch) 076 * @author Sven de Marothy (sven@physto.se) 077 * 078 * @since 1.2 079 */ 080 public final class GeneralPath implements Shape, Cloneable 081 { 082 /** Same constant as {@link PathIterator#WIND_EVEN_ODD}. */ 083 public static final int WIND_EVEN_ODD = PathIterator.WIND_EVEN_ODD; 084 085 /** Same constant as {@link PathIterator#WIND_NON_ZERO}. */ 086 public static final int WIND_NON_ZERO = PathIterator.WIND_NON_ZERO; 087 088 /** Initial size if not specified. */ 089 private static final int INIT_SIZE = 10; 090 091 /** A big number, but not so big it can't survive a few float operations */ 092 private static final double BIG_VALUE = Double.MAX_VALUE / 10.0; 093 094 /** The winding rule. 095 * This is package-private to avoid an accessor method. 096 */ 097 int rule; 098 099 /** 100 * The path type in points. Note that xpoints[index] and ypoints[index] maps 101 * to types[index]; the control points of quad and cubic paths map as 102 * well but are ignored. 103 * This is package-private to avoid an accessor method. 104 */ 105 byte[] types; 106 107 /** 108 * The list of all points seen. Since you can only append floats, it makes 109 * sense for these to be float[]. I have no idea why Sun didn't choose to 110 * allow a general path of double precision points. 111 * Note: Storing x and y coords seperately makes for a slower transforms, 112 * But it speeds up and simplifies box-intersection checking a lot. 113 * These are package-private to avoid accessor methods. 114 */ 115 float[] xpoints; 116 float[] ypoints; 117 118 /** The index of the most recent moveto point, or null. */ 119 private int subpath = -1; 120 121 /** The next available index into points. 122 * This is package-private to avoid an accessor method. 123 */ 124 int index; 125 126 /** 127 * Constructs a GeneralPath with the default (NON_ZERO) 128 * winding rule and initial capacity (20). 129 */ 130 public GeneralPath() 131 { 132 this(WIND_NON_ZERO, INIT_SIZE); 133 } 134 135 /** 136 * Constructs a GeneralPath with a specific winding rule 137 * and the default initial capacity (20). 138 * @param rule the winding rule ({@link #WIND_NON_ZERO} or 139 * {@link #WIND_EVEN_ODD}) 140 * 141 * @throws IllegalArgumentException if <code>rule</code> is not one of the 142 * listed values. 143 */ 144 public GeneralPath(int rule) 145 { 146 this(rule, INIT_SIZE); 147 } 148 149 /** 150 * Constructs a GeneralPath with a specific winding rule 151 * and the initial capacity. The initial capacity should be 152 * the approximate number of path segments to be used. 153 * @param rule the winding rule ({@link #WIND_NON_ZERO} or 154 * {@link #WIND_EVEN_ODD}) 155 * @param capacity the inital capacity, in path segments 156 * 157 * @throws IllegalArgumentException if <code>rule</code> is not one of the 158 * listed values. 159 */ 160 public GeneralPath(int rule, int capacity) 161 { 162 if (rule != WIND_EVEN_ODD && rule != WIND_NON_ZERO) 163 throw new IllegalArgumentException(); 164 this.rule = rule; 165 if (capacity < INIT_SIZE) 166 capacity = INIT_SIZE; 167 types = new byte[capacity]; 168 xpoints = new float[capacity]; 169 ypoints = new float[capacity]; 170 } 171 172 /** 173 * Constructs a GeneralPath from an arbitrary shape object. 174 * The Shapes PathIterator path and winding rule will be used. 175 * 176 * @param s the shape (<code>null</code> not permitted). 177 * 178 * @throws NullPointerException if <code>shape</code> is <code>null</code>. 179 */ 180 public GeneralPath(Shape s) 181 { 182 types = new byte[INIT_SIZE]; 183 xpoints = new float[INIT_SIZE]; 184 ypoints = new float[INIT_SIZE]; 185 PathIterator pi = s.getPathIterator(null); 186 setWindingRule(pi.getWindingRule()); 187 append(pi, false); 188 } 189 190 /** 191 * Adds a new point to a path. 192 * 193 * @param x the x-coordinate. 194 * @param y the y-coordinate. 195 */ 196 public void moveTo(float x, float y) 197 { 198 subpath = index; 199 ensureSize(index + 1); 200 types[index] = PathIterator.SEG_MOVETO; 201 xpoints[index] = x; 202 ypoints[index++] = y; 203 } 204 205 /** 206 * Appends a straight line to the current path. 207 * @param x x coordinate of the line endpoint. 208 * @param y y coordinate of the line endpoint. 209 */ 210 public void lineTo(float x, float y) 211 { 212 ensureSize(index + 1); 213 types[index] = PathIterator.SEG_LINETO; 214 xpoints[index] = x; 215 ypoints[index++] = y; 216 } 217 218 /** 219 * Appends a quadratic Bezier curve to the current path. 220 * @param x1 x coordinate of the control point 221 * @param y1 y coordinate of the control point 222 * @param x2 x coordinate of the curve endpoint. 223 * @param y2 y coordinate of the curve endpoint. 224 */ 225 public void quadTo(float x1, float y1, float x2, float y2) 226 { 227 ensureSize(index + 2); 228 types[index] = PathIterator.SEG_QUADTO; 229 xpoints[index] = x1; 230 ypoints[index++] = y1; 231 xpoints[index] = x2; 232 ypoints[index++] = y2; 233 } 234 235 /** 236 * Appends a cubic Bezier curve to the current path. 237 * @param x1 x coordinate of the first control point 238 * @param y1 y coordinate of the first control point 239 * @param x2 x coordinate of the second control point 240 * @param y2 y coordinate of the second control point 241 * @param x3 x coordinate of the curve endpoint. 242 * @param y3 y coordinate of the curve endpoint. 243 */ 244 public void curveTo(float x1, float y1, float x2, float y2, float x3, 245 float y3) 246 { 247 ensureSize(index + 3); 248 types[index] = PathIterator.SEG_CUBICTO; 249 xpoints[index] = x1; 250 ypoints[index++] = y1; 251 xpoints[index] = x2; 252 ypoints[index++] = y2; 253 xpoints[index] = x3; 254 ypoints[index++] = y3; 255 } 256 257 /** 258 * Closes the current subpath by drawing a line 259 * back to the point of the last moveTo, unless the path is already closed. 260 */ 261 public void closePath() 262 { 263 if (index >= 1 && types[index - 1] == PathIterator.SEG_CLOSE) 264 return; 265 ensureSize(index + 1); 266 types[index] = PathIterator.SEG_CLOSE; 267 xpoints[index] = xpoints[subpath]; 268 ypoints[index++] = ypoints[subpath]; 269 } 270 271 /** 272 * Appends the segments of a Shape to the path. If <code>connect</code> is 273 * true, the new path segments are connected to the existing one with a line. 274 * The winding rule of the Shape is ignored. 275 * 276 * @param s the shape (<code>null</code> not permitted). 277 * @param connect whether to connect the new shape to the existing path. 278 * 279 * @throws NullPointerException if <code>s</code> is <code>null</code>. 280 */ 281 public void append(Shape s, boolean connect) 282 { 283 append(s.getPathIterator(null), connect); 284 } 285 286 /** 287 * Appends the segments of a PathIterator to this GeneralPath. 288 * Optionally, the initial {@link PathIterator#SEG_MOVETO} segment 289 * of the appended path is changed into a {@link 290 * PathIterator#SEG_LINETO} segment. 291 * 292 * @param iter the PathIterator specifying which segments shall be 293 * appended (<code>null</code> not permitted). 294 * 295 * @param connect <code>true</code> for substituting the initial 296 * {@link PathIterator#SEG_MOVETO} segment by a {@link 297 * PathIterator#SEG_LINETO}, or <code>false</code> for not 298 * performing any substitution. If this GeneralPath is currently 299 * empty, <code>connect</code> is assumed to be <code>false</code>, 300 * thus leaving the initial {@link PathIterator#SEG_MOVETO} 301 * unchanged. 302 */ 303 public void append(PathIterator iter, boolean connect) 304 { 305 // A bad implementation of this method had caused Classpath bug #6076. 306 float[] f = new float[6]; 307 while (! iter.isDone()) 308 { 309 switch (iter.currentSegment(f)) 310 { 311 case PathIterator.SEG_MOVETO: 312 if (! connect || (index == 0)) 313 { 314 moveTo(f[0], f[1]); 315 break; 316 } 317 if ((index >= 1) && (types[index - 1] == PathIterator.SEG_CLOSE) 318 && (f[0] == xpoints[index - 1]) 319 && (f[1] == ypoints[index - 1])) 320 break; 321 322 // Fall through. 323 case PathIterator.SEG_LINETO: 324 lineTo(f[0], f[1]); 325 break; 326 case PathIterator.SEG_QUADTO: 327 quadTo(f[0], f[1], f[2], f[3]); 328 break; 329 case PathIterator.SEG_CUBICTO: 330 curveTo(f[0], f[1], f[2], f[3], f[4], f[5]); 331 break; 332 case PathIterator.SEG_CLOSE: 333 closePath(); 334 break; 335 } 336 337 connect = false; 338 iter.next(); 339 } 340 } 341 342 /** 343 * Returns the path’s current winding rule. 344 * 345 * @return {@link #WIND_EVEN_ODD} or {@link #WIND_NON_ZERO}. 346 */ 347 public int getWindingRule() 348 { 349 return rule; 350 } 351 352 /** 353 * Sets the path’s winding rule, which controls which areas are 354 * considered ’inside’ or ’outside’ the path 355 * on drawing. Valid rules are WIND_EVEN_ODD for an even-odd winding rule, 356 * or WIND_NON_ZERO for a non-zero winding rule. 357 * 358 * @param rule the rule ({@link #WIND_EVEN_ODD} or {@link #WIND_NON_ZERO}). 359 */ 360 public void setWindingRule(int rule) 361 { 362 if (rule != WIND_EVEN_ODD && rule != WIND_NON_ZERO) 363 throw new IllegalArgumentException(); 364 this.rule = rule; 365 } 366 367 /** 368 * Returns the current appending point of the path. 369 * 370 * @return The point. 371 */ 372 public Point2D getCurrentPoint() 373 { 374 if (subpath < 0) 375 return null; 376 return new Point2D.Float(xpoints[index - 1], ypoints[index - 1]); 377 } 378 379 /** 380 * Resets the path. All points and segments are destroyed. 381 */ 382 public void reset() 383 { 384 subpath = -1; 385 index = 0; 386 } 387 388 /** 389 * Applies a transform to the path. 390 * 391 * @param xform the transform (<code>null</code> not permitted). 392 */ 393 public void transform(AffineTransform xform) 394 { 395 double nx; 396 double ny; 397 double[] m = new double[6]; 398 xform.getMatrix(m); 399 for (int i = 0; i < index; i++) 400 { 401 nx = m[0] * xpoints[i] + m[2] * ypoints[i] + m[4]; 402 ny = m[1] * xpoints[i] + m[3] * ypoints[i] + m[5]; 403 xpoints[i] = (float) nx; 404 ypoints[i] = (float) ny; 405 } 406 } 407 408 /** 409 * Creates a transformed version of the path. 410 * @param xform the transform to apply 411 * @return a new transformed GeneralPath 412 */ 413 public Shape createTransformedShape(AffineTransform xform) 414 { 415 GeneralPath p = new GeneralPath(this); 416 p.transform(xform); 417 return p; 418 } 419 420 /** 421 * Returns the path’s bounding box. 422 */ 423 public Rectangle getBounds() 424 { 425 return getBounds2D().getBounds(); 426 } 427 428 /** 429 * Returns the path’s bounding box, in <code>float</code> precision 430 */ 431 public Rectangle2D getBounds2D() 432 { 433 float x1; 434 float y1; 435 float x2; 436 float y2; 437 438 if (index > 0) 439 { 440 x1 = x2 = xpoints[0]; 441 y1 = y2 = ypoints[0]; 442 } 443 else 444 x1 = x2 = y1 = y2 = 0.0f; 445 446 for (int i = 0; i < index; i++) 447 { 448 x1 = Math.min(xpoints[i], x1); 449 y1 = Math.min(ypoints[i], y1); 450 x2 = Math.max(xpoints[i], x2); 451 y2 = Math.max(ypoints[i], y2); 452 } 453 return (new Rectangle2D.Float(x1, y1, x2 - x1, y2 - y1)); 454 } 455 456 /** 457 * Evaluates if a point is within the GeneralPath, 458 * The NON_ZERO winding rule is used, regardless of the 459 * set winding rule. 460 * @param x x coordinate of the point to evaluate 461 * @param y y coordinate of the point to evaluate 462 * @return true if the point is within the path, false otherwise 463 */ 464 public boolean contains(double x, double y) 465 { 466 return (getWindingNumber(x, y) != 0); 467 } 468 469 /** 470 * Evaluates if a Point2D is within the GeneralPath, 471 * The NON_ZERO winding rule is used, regardless of the 472 * set winding rule. 473 * @param p The Point2D to evaluate 474 * @return true if the point is within the path, false otherwise 475 */ 476 public boolean contains(Point2D p) 477 { 478 return contains(p.getX(), p.getY()); 479 } 480 481 /** 482 * Evaluates if a rectangle is completely contained within the path. 483 * This method will return false in the cases when the box 484 * intersects an inner segment of the path. 485 * (i.e.: The method is accurate for the EVEN_ODD winding rule) 486 */ 487 public boolean contains(double x, double y, double w, double h) 488 { 489 if (! getBounds2D().intersects(x, y, w, h)) 490 return false; 491 492 /* Does any edge intersect? */ 493 if (getAxisIntersections(x, y, false, w) != 0 /* top */ 494 || getAxisIntersections(x, y + h, false, w) != 0 /* bottom */ 495 || getAxisIntersections(x + w, y, true, h) != 0 /* right */ 496 || getAxisIntersections(x, y, true, h) != 0) /* left */ 497 return false; 498 499 /* No intersections, is any point inside? */ 500 if (getWindingNumber(x, y) != 0) 501 return true; 502 503 return false; 504 } 505 506 /** 507 * Evaluates if a rectangle is completely contained within the path. 508 * This method will return false in the cases when the box 509 * intersects an inner segment of the path. 510 * (i.e.: The method is accurate for the EVEN_ODD winding rule) 511 * @param r the rectangle 512 * @return <code>true</code> if the rectangle is completely contained 513 * within the path, <code>false</code> otherwise 514 */ 515 public boolean contains(Rectangle2D r) 516 { 517 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 518 } 519 520 /** 521 * Evaluates if a rectangle intersects the path. 522 * @param x x coordinate of the rectangle 523 * @param y y coordinate of the rectangle 524 * @param w width of the rectangle 525 * @param h height of the rectangle 526 * @return <code>true</code> if the rectangle intersects the path, 527 * <code>false</code> otherwise 528 */ 529 public boolean intersects(double x, double y, double w, double h) 530 { 531 /* Does any edge intersect? */ 532 if (getAxisIntersections(x, y, false, w) != 0 /* top */ 533 || getAxisIntersections(x, y + h, false, w) != 0 /* bottom */ 534 || getAxisIntersections(x + w, y, true, h) != 0 /* right */ 535 || getAxisIntersections(x, y, true, h) != 0) /* left */ 536 return true; 537 538 /* No intersections, is any point inside? */ 539 if (getWindingNumber(x, y) != 0) 540 return true; 541 542 return false; 543 } 544 545 /** 546 * Evaluates if a Rectangle2D intersects the path. 547 * @param r The rectangle 548 * @return <code>true</code> if the rectangle intersects the path, 549 * <code>false</code> otherwise 550 */ 551 public boolean intersects(Rectangle2D r) 552 { 553 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight()); 554 } 555 556 /** 557 * A PathIterator that iterates over the segments of a GeneralPath. 558 * 559 * @author Sascha Brawer (brawer@dandelis.ch) 560 */ 561 private static class GeneralPathIterator implements PathIterator 562 { 563 /** 564 * The number of coordinate values for each segment type. 565 */ 566 private static final int[] NUM_COORDS = { 567 /* 0: SEG_MOVETO */ 1, 568 /* 1: SEG_LINETO */ 1, 569 /* 2: SEG_QUADTO */ 2, 570 /* 3: SEG_CUBICTO */ 3, 571 /* 4: SEG_CLOSE */ 0}; 572 573 /** 574 * The GeneralPath whose segments are being iterated. 575 * This is package-private to avoid an accessor method. 576 */ 577 final GeneralPath path; 578 579 /** 580 * The affine transformation used to transform coordinates. 581 */ 582 private final AffineTransform transform; 583 584 /** 585 * The current position of the iterator. 586 */ 587 private int pos; 588 589 /** 590 * Constructs a new iterator for enumerating the segments of a 591 * GeneralPath. 592 * 593 * @param path the path to enumerate 594 * @param transform an affine transformation for projecting the returned 595 * points, or <code>null</code> to return the original points 596 * without any mapping. 597 */ 598 GeneralPathIterator(GeneralPath path, AffineTransform transform) 599 { 600 this.path = path; 601 this.transform = transform; 602 } 603 604 /** 605 * Returns the current winding rule of the GeneralPath. 606 */ 607 public int getWindingRule() 608 { 609 return path.rule; 610 } 611 612 /** 613 * Determines whether the iterator has reached the last segment in 614 * the path. 615 */ 616 public boolean isDone() 617 { 618 return pos >= path.index; 619 } 620 621 /** 622 * Advances the iterator position by one segment. 623 */ 624 public void next() 625 { 626 int seg; 627 628 /* 629 * Increment pos by the number of coordinate pairs. 630 */ 631 seg = path.types[pos]; 632 if (seg == SEG_CLOSE) 633 pos++; 634 else 635 pos += NUM_COORDS[seg]; 636 } 637 638 /** 639 * Returns the current segment in float coordinates. 640 */ 641 public int currentSegment(float[] coords) 642 { 643 int seg; 644 int numCoords; 645 646 seg = path.types[pos]; 647 numCoords = NUM_COORDS[seg]; 648 if (numCoords > 0) 649 { 650 for (int i = 0; i < numCoords; i++) 651 { 652 coords[i << 1] = path.xpoints[pos + i]; 653 coords[(i << 1) + 1] = path.ypoints[pos + i]; 654 } 655 656 if (transform != null) 657 transform.transform( /* src */ 658 coords, /* srcOffset */ 659 0, /* dest */ coords, /* destOffset */ 660 0, /* numPoints */ numCoords); 661 } 662 return seg; 663 } 664 665 /** 666 * Returns the current segment in double coordinates. 667 */ 668 public int currentSegment(double[] coords) 669 { 670 int seg; 671 int numCoords; 672 673 seg = path.types[pos]; 674 numCoords = NUM_COORDS[seg]; 675 if (numCoords > 0) 676 { 677 for (int i = 0; i < numCoords; i++) 678 { 679 coords[i << 1] = (double) path.xpoints[pos + i]; 680 coords[(i << 1) + 1] = (double) path.ypoints[pos + i]; 681 } 682 if (transform != null) 683 transform.transform( /* src */ 684 coords, /* srcOffset */ 685 0, /* dest */ coords, /* destOffset */ 686 0, /* numPoints */ numCoords); 687 } 688 return seg; 689 } 690 } 691 692 /** 693 * Creates a PathIterator for iterating along the segments of the path. 694 * 695 * @param at an affine transformation for projecting the returned 696 * points, or <code>null</code> to let the created iterator return 697 * the original points without any mapping. 698 */ 699 public PathIterator getPathIterator(AffineTransform at) 700 { 701 return new GeneralPathIterator(this, at); 702 } 703 704 /** 705 * Creates a new FlatteningPathIterator for the path 706 */ 707 public PathIterator getPathIterator(AffineTransform at, double flatness) 708 { 709 return new FlatteningPathIterator(getPathIterator(at), flatness); 710 } 711 712 /** 713 * Creates a new shape of the same run-time type with the same contents 714 * as this one. 715 * 716 * @return the clone 717 * 718 * @exception OutOfMemoryError If there is not enough memory available. 719 * 720 * @since 1.2 721 */ 722 public Object clone() 723 { 724 // This class is final; no need to use super.clone(). 725 return new GeneralPath(this); 726 } 727 728 /** 729 * Helper method - ensure the size of the data arrays, 730 * otherwise, reallocate new ones twice the size 731 * 732 * @param size the minimum array size. 733 */ 734 private void ensureSize(int size) 735 { 736 if (subpath < 0) 737 throw new IllegalPathStateException("need initial moveto"); 738 if (size <= xpoints.length) 739 return; 740 byte[] b = new byte[types.length << 1]; 741 System.arraycopy(types, 0, b, 0, index); 742 types = b; 743 float[] f = new float[xpoints.length << 1]; 744 System.arraycopy(xpoints, 0, f, 0, index); 745 xpoints = f; 746 f = new float[ypoints.length << 1]; 747 System.arraycopy(ypoints, 0, f, 0, index); 748 ypoints = f; 749 } 750 751 /** 752 * Helper method - Get the total number of intersections from (x,y) along 753 * a given axis, within a given distance. 754 */ 755 private int getAxisIntersections(double x, double y, boolean useYaxis, 756 double distance) 757 { 758 return (evaluateCrossings(x, y, false, useYaxis, distance)); 759 } 760 761 /** 762 * Helper method - returns the winding number of a point. 763 */ 764 private int getWindingNumber(double x, double y) 765 { 766 /* Evaluate the crossings from x,y to infinity on the y axis (arbitrary 767 choice). Note that we don't actually use Double.INFINITY, since that's 768 slower, and may cause problems. */ 769 return (evaluateCrossings(x, y, true, true, BIG_VALUE)); 770 } 771 772 /** 773 * Helper method - evaluates the number of intersections on an axis from 774 * the point (x,y) to the point (x,y+distance) or (x+distance,y). 775 * @param x x coordinate. 776 * @param y y coordinate. 777 * @param neg True if opposite-directed intersections should cancel, 778 * false to sum all intersections. 779 * @param useYaxis Use the Y axis, false uses the X axis. 780 * @param distance Interval from (x,y) on the selected axis to find 781 * intersections. 782 */ 783 private int evaluateCrossings(double x, double y, boolean neg, 784 boolean useYaxis, double distance) 785 { 786 float cx = 0.0f; 787 float cy = 0.0f; 788 float firstx = 0.0f; 789 float firsty = 0.0f; 790 791 int negative = (neg) ? -1 : 1; 792 double x0; 793 double x1; 794 double x2; 795 double x3; 796 double y0; 797 double y1; 798 double y2; 799 double y3; 800 double[] r = new double[4]; 801 int nRoots; 802 double epsilon = 0.0; 803 int pos = 0; 804 int windingNumber = 0; 805 boolean pathStarted = false; 806 807 if (index == 0) 808 return (0); 809 if (useYaxis) 810 { 811 float[] swap1; 812 swap1 = ypoints; 813 ypoints = xpoints; 814 xpoints = swap1; 815 double swap2; 816 swap2 = y; 817 y = x; 818 x = swap2; 819 } 820 821 /* Get a value which is hopefully small but not insignificant relative 822 the path. */ 823 epsilon = ypoints[0] * 1E-7; 824 825 if(epsilon == 0) 826 epsilon = 1E-7; 827 828 pos = 0; 829 while (pos < index) 830 { 831 switch (types[pos]) 832 { 833 case PathIterator.SEG_MOVETO: 834 if (pathStarted) // close old path 835 { 836 x0 = cx; 837 y0 = cy; 838 x1 = firstx; 839 y1 = firsty; 840 841 if (y0 == 0.0) 842 y0 -= epsilon; 843 if (y1 == 0.0) 844 y1 -= epsilon; 845 if (Line2D.linesIntersect(x0, y0, x1, y1, 846 epsilon, 0.0, distance, 0.0)) 847 windingNumber += (y1 < y0) ? 1 : negative; 848 849 cx = firstx; 850 cy = firsty; 851 } 852 cx = firstx = xpoints[pos] - (float) x; 853 cy = firsty = ypoints[pos++] - (float) y; 854 pathStarted = true; 855 break; 856 case PathIterator.SEG_CLOSE: 857 x0 = cx; 858 y0 = cy; 859 x1 = firstx; 860 y1 = firsty; 861 862 if (y0 == 0.0) 863 y0 -= epsilon; 864 if (y1 == 0.0) 865 y1 -= epsilon; 866 if (Line2D.linesIntersect(x0, y0, x1, y1, 867 epsilon, 0.0, distance, 0.0)) 868 windingNumber += (y1 < y0) ? 1 : negative; 869 870 cx = firstx; 871 cy = firsty; 872 pos++; 873 pathStarted = false; 874 break; 875 case PathIterator.SEG_LINETO: 876 x0 = cx; 877 y0 = cy; 878 x1 = xpoints[pos] - (float) x; 879 y1 = ypoints[pos++] - (float) y; 880 881 if (y0 == 0.0) 882 y0 -= epsilon; 883 if (y1 == 0.0) 884 y1 -= epsilon; 885 if (Line2D.linesIntersect(x0, y0, x1, y1, 886 epsilon, 0.0, distance, 0.0)) 887 windingNumber += (y1 < y0) ? 1 : negative; 888 889 cx = xpoints[pos - 1] - (float) x; 890 cy = ypoints[pos - 1] - (float) y; 891 break; 892 case PathIterator.SEG_QUADTO: 893 x0 = cx; 894 y0 = cy; 895 x1 = xpoints[pos] - x; 896 y1 = ypoints[pos++] - y; 897 x2 = xpoints[pos] - x; 898 y2 = ypoints[pos++] - y; 899 900 /* check if curve may intersect X+ axis. */ 901 if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0) 902 && (y0 * y1 <= 0 || y1 * y2 <= 0)) 903 { 904 if (y0 == 0.0) 905 y0 -= epsilon; 906 if (y2 == 0.0) 907 y2 -= epsilon; 908 909 r[0] = y0; 910 r[1] = 2 * (y1 - y0); 911 r[2] = (y2 - 2 * y1 + y0); 912 913 /* degenerate roots (=tangent points) do not 914 contribute to the winding number. */ 915 if ((nRoots = QuadCurve2D.solveQuadratic(r)) == 2) 916 for (int i = 0; i < nRoots; i++) 917 { 918 float t = (float) r[i]; 919 if (t > 0.0f && t < 1.0f) 920 { 921 double crossing = t * t * (x2 - 2 * x1 + x0) 922 + 2 * t * (x1 - x0) + x0; 923 if (crossing >= 0.0 && crossing <= distance) 924 windingNumber += (2 * t * (y2 - 2 * y1 + y0) 925 + 2 * (y1 - y0) < 0) ? 1 : negative; 926 } 927 } 928 } 929 930 cx = xpoints[pos - 1] - (float) x; 931 cy = ypoints[pos - 1] - (float) y; 932 break; 933 case PathIterator.SEG_CUBICTO: 934 x0 = cx; 935 y0 = cy; 936 x1 = xpoints[pos] - x; 937 y1 = ypoints[pos++] - y; 938 x2 = xpoints[pos] - x; 939 y2 = ypoints[pos++] - y; 940 x3 = xpoints[pos] - x; 941 y3 = ypoints[pos++] - y; 942 943 /* check if curve may intersect X+ axis. */ 944 if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0 || x3 > 0.0) 945 && (y0 * y1 <= 0 || y1 * y2 <= 0 || y2 * y3 <= 0)) 946 { 947 if (y0 == 0.0) 948 y0 -= epsilon; 949 if (y3 == 0.0) 950 y3 -= epsilon; 951 952 r[0] = y0; 953 r[1] = 3 * (y1 - y0); 954 r[2] = 3 * (y2 + y0 - 2 * y1); 955 r[3] = y3 - 3 * y2 + 3 * y1 - y0; 956 957 if ((nRoots = CubicCurve2D.solveCubic(r)) != 0) 958 for (int i = 0; i < nRoots; i++) 959 { 960 float t = (float) r[i]; 961 if (t > 0.0 && t < 1.0) 962 { 963 double crossing = -(t * t * t) * (x0 - 3 * x1 964 + 3 * x2 - x3) 965 + 3 * t * t * (x0 - 2 * x1 + x2) 966 + 3 * t * (x1 - x0) + x0; 967 if (crossing >= 0 && crossing <= distance) 968 windingNumber += (3 * t * t * (y3 + 3 * y1 969 - 3 * y2 - y0) 970 + 6 * t * (y0 - 2 * y1 + y2) 971 + 3 * (y1 - y0) < 0) ? 1 : negative; 972 } 973 } 974 } 975 976 cx = xpoints[pos - 1] - (float) x; 977 cy = ypoints[pos - 1] - (float) y; 978 break; 979 } 980 } 981 982 // swap coordinates back 983 if (useYaxis) 984 { 985 float[] swap; 986 swap = ypoints; 987 ypoints = xpoints; 988 xpoints = swap; 989 } 990 return (windingNumber); 991 } 992 } // class GeneralPath 993