1: /* GeneralPath.java -- represents a shape built from subpaths 2: Copyright (C) 2002, 2003, 2004, 2006 Free Software Foundation 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package java.awt.geom; 40: 41: import java.awt.Rectangle; 42: import java.awt.Shape; 43: 44: 45: /** 46: * A general geometric path, consisting of any number of subpaths 47: * constructed out of straight lines and cubic or quadratic Bezier 48: * curves. 49: * 50: * <p>The inside of the curve is defined for drawing purposes by a winding 51: * rule. Either the WIND_EVEN_ODD or WIND_NON_ZERO winding rule can be chosen. 52: * 53: * <p><img src="doc-files/GeneralPath-1.png" width="300" height="210" 54: * alt="A drawing of a GeneralPath" /> 55: * <p>The EVEN_ODD winding rule defines a point as inside a path if: 56: * A ray from the point towards infinity in an arbitrary direction 57: * intersects the path an odd number of times. Points <b>A</b> and 58: * <b>C</b> in the image are considered to be outside the path. 59: * (both intersect twice) 60: * Point <b>B</b> intersects once, and is inside. 61: * 62: * <p>The NON_ZERO winding rule defines a point as inside a path if: 63: * The path intersects the ray in an equal number of opposite directions. 64: * Point <b>A</b> in the image is outside (one intersection in the 65: * ’up’ 66: * direction, one in the ’down’ direction) Point <b>B</b> in 67: * the image is inside (one intersection ’down’) 68: * Point <b>C</b> in the image is inside (two intersections in the 69: * ’down’ direction) 70: * 71: * @see Line2D 72: * @see CubicCurve2D 73: * @see QuadCurve2D 74: * 75: * @author Sascha Brawer (brawer@dandelis.ch) 76: * @author Sven de Marothy (sven@physto.se) 77: * 78: * @since 1.2 79: */ 80: public final class GeneralPath implements Shape, Cloneable 81: { 82: /** Same constant as {@link PathIterator#WIND_EVEN_ODD}. */ 83: public static final int WIND_EVEN_ODD = PathIterator.WIND_EVEN_ODD; 84: 85: /** Same constant as {@link PathIterator#WIND_NON_ZERO}. */ 86: public static final int WIND_NON_ZERO = PathIterator.WIND_NON_ZERO; 87: 88: /** Initial size if not specified. */ 89: private static final int INIT_SIZE = 10; 90: 91: /** A big number, but not so big it can't survive a few float operations */ 92: private static final double BIG_VALUE = Double.MAX_VALUE / 10.0; 93: 94: /** The winding rule. 95: * This is package-private to avoid an accessor method. 96: */ 97: int rule; 98: 99: /** 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