001/* GeneralPath.java -- represents a shape built from subpaths
002   Copyright (C) 2002, 2003, 2004, 2006 Free Software Foundation
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038
039package java.awt.geom;
040
041import java.awt.Rectangle;
042import 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 * &#x2019;up&#x2019;
066 * direction, one in the &#x2019;down&#x2019; direction) Point <b>B</b> in
067 * the image is inside (one intersection &#x2019;down&#x2019;)
068 * Point <b>C</b> in the image is inside (two intersections in the
069 * &#x2019;down&#x2019; 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 */
080public 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&#x2019;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&#x2019;s winding rule, which controls which areas are
354   * considered &#x2019;inside&#x2019; or &#x2019;outside&#x2019; 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&#x2019;s bounding box.
422   */
423  public Rectangle getBounds()
424  {
425    return getBounds2D().getBounds();
426  }
427
428  /**
429   * Returns the path&#x2019;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