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