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     * &#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     */
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&#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
993