1 /* GeneralPath.java -- represents a shape built from subpaths
2 Copyright (C) 2002, 2003, 2004 Free Software Foundation
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
39 package java.awt.geom;
41 import java.awt.Rectangle;
42 import java.awt.Shape;
46 * A general geometric path, consisting of any number of subpaths
47 * constructed out of straight lines and cubic or quadratic Bezier
50 * <p>The inside of the curve is defined for drawing purposes by a winding
51 * rule. Either the WIND_EVEN_ODD or WIND_NON_ZERO winding rule can be chosen.
53 * <p><img src="doc-files/GeneralPath-1.png" width="300" height="210"
54 * alt="A drawing of a GeneralPath" />
55 * <p>The EVEN_ODD winding rule defines a point as inside a path if:
56 * A ray from the point towards infinity in an arbitrary direction
57 * intersects the path an odd number of times. Points <b>A</b> and
58 * <b>C</b> in the image are considered to be outside the path.
59 * (both intersect twice)
60 * Point <b>B</b> intersects once, and is inside.
62 * <p>The NON_ZERO winding rule defines a point as inside a path if:
63 * The path intersects the ray in an equal number of opposite directions.
64 * Point <b>A</b> in the image is outside (one intersection in the
66 * direction, one in the ’down’ direction) Point <b>B</b> in
67 * the image is inside (one intersection ’down’)
68 * Point <b>C</b> in the image is outside (two intersections
69 * ’down’)
75 * @author Sascha Brawer (brawer@dandelis.ch)
76 * @author Sven de Marothy (sven@physto.se)
80 public final class GeneralPath implements Shape, Cloneable
82 public static final int WIND_EVEN_ODD = PathIterator.WIND_EVEN_ODD;
83 public static final int WIND_NON_ZERO = PathIterator.WIND_NON_ZERO;
85 /** Initial size if not specified. */
86 private static final int INIT_SIZE = 10;
88 /** A big number, but not so big it can't survive a few float operations */
89 private static final double BIG_VALUE = java.lang.Double.MAX_VALUE / 10.0;
91 /** The winding rule. */
95 * The path type in points. Note that xpoints[index] and ypoints[index] maps
96 * to types[index]; the control points of quad and cubic paths map as
97 * well but are ignored.
102 * The list of all points seen. Since you can only append floats, it makes
103 * sense for these to be float[]. I have no idea why Sun didn't choose to
104 * allow a general path of double precision points.
105 * Note: Storing x and y coords seperately makes for a slower transforms,
106 * But it speeds up and simplifies box-intersection checking a lot.
108 private float[] xpoints;
109 private float[] ypoints;
111 /** The index of the most recent moveto point, or null. */
112 private int subpath = -1;
114 /** The next available index into points. */
118 * Constructs a GeneralPath with the default (NON_ZERO)
119 * winding rule and initial capacity (20).
123 this(WIND_NON_ZERO, INIT_SIZE);
127 * Constructs a GeneralPath with a specific winding rule
128 * and the default initial capacity (20).
129 * @param rule the winding rule (WIND_NON_ZERO or WIND_EVEN_ODD)
131 public GeneralPath(int rule)
133 this(rule, INIT_SIZE);
137 * Constructs a GeneralPath with a specific winding rule
138 * and the initial capacity. The initial capacity should be
139 * the approximate number of path segments to be used.
140 * @param rule the winding rule (WIND_NON_ZERO or WIND_EVEN_ODD)
141 * @param capacity the inital capacity, in path segments
143 public GeneralPath(int rule, int capacity)
145 if (rule != WIND_EVEN_ODD && rule != WIND_NON_ZERO)
146 throw new IllegalArgumentException();
148 if (capacity < INIT_SIZE)
149 capacity = INIT_SIZE;
150 types = new byte[capacity];
151 xpoints = new float[capacity];
152 ypoints = new float[capacity];
156 * Constructs a GeneralPath from an arbitrary shape object.
157 * The Shapes PathIterator path and winding rule will be used.
160 public GeneralPath(Shape s)
162 types = new byte[INIT_SIZE];
163 xpoints = new float[INIT_SIZE];
164 ypoints = new float[INIT_SIZE];
165 PathIterator pi = s.getPathIterator(null);
166 setWindingRule(pi.getWindingRule());
171 * Adds a new point to a path.
173 public void moveTo(float x, float y)
176 ensureSize(index + 1);
177 types[index] = PathIterator.SEG_MOVETO;
179 ypoints[index++] = y;
183 * Appends a straight line to the current path.
184 * @param x x coordinate of the line endpoint.
185 * @param y y coordinate of the line endpoint.
187 public void lineTo(float x, float y)
189 ensureSize(index + 1);
190 types[index] = PathIterator.SEG_LINETO;
192 ypoints[index++] = y;
196 * Appends a quadratic Bezier curve to the current path.
197 * @param x1 x coordinate of the control point
198 * @param y1 y coordinate of the control point
199 * @param x2 x coordinate of the curve endpoint.
200 * @param y2 y coordinate of the curve endpoint.
202 public void quadTo(float x1, float y1, float x2, float y2)
204 ensureSize(index + 2);
205 types[index] = PathIterator.SEG_QUADTO;
207 ypoints[index++] = y1;
209 ypoints[index++] = y2;
213 * Appends a cubic Bezier curve to the current path.
214 * @param x1 x coordinate of the first control point
215 * @param y1 y coordinate of the first control point
216 * @param x2 x coordinate of the second control point
217 * @param y2 y coordinate of the second control point
218 * @param x3 x coordinate of the curve endpoint.
219 * @param y3 y coordinate of the curve endpoint.
221 public void curveTo(float x1, float y1, float x2, float y2, float x3,
224 ensureSize(index + 3);
225 types[index] = PathIterator.SEG_CUBICTO;
227 ypoints[index++] = y1;
229 ypoints[index++] = y2;
231 ypoints[index++] = y3;
235 * Closes the current subpath by drawing a line
236 * back to the point of the last moveTo.
238 public void closePath()
240 ensureSize(index + 1);
241 types[index] = PathIterator.SEG_CLOSE;
242 xpoints[index] = xpoints[subpath];
243 ypoints[index++] = ypoints[subpath];
247 * Appends the segments of a Shape to the path. If <code>connect</code> is
248 * true, the new path segments are connected to the existing one with a line.
249 * The winding rule of the Shape is ignored.
251 public void append(Shape s, boolean connect)
253 append(s.getPathIterator(null), connect);
257 * Appends the segments of a PathIterator to this GeneralPath.
258 * Optionally, the initial {@link PathIterator#SEG_MOVETO} segment
259 * of the appended path is changed into a {@link
260 * PathIterator#SEG_LINETO} segment.
262 * @param iter the PathIterator specifying which segments shall be
265 * @param connect <code>true</code> for substituting the initial
266 * {@link PathIterator#SEG_MOVETO} segment by a {@link
267 * PathIterator#SEG_LINETO}, or <code>false</code> for not
268 * performing any substitution. If this GeneralPath is currently
269 * empty, <code>connect</code> is assumed to be <code>false</code>,
270 * thus leaving the initial {@link PathIterator#SEG_MOVETO}
273 public void append(PathIterator iter, boolean connect)
275 // A bad implementation of this method had caused Classpath bug #6076.
276 float[] f = new float[6];
277 while (! iter.isDone())
279 switch (iter.currentSegment(f))
281 case PathIterator.SEG_MOVETO:
282 if (! connect || (index == 0))
287 if ((index >= 1) && (types[index - 1] == PathIterator.SEG_CLOSE)
288 && (f[0] == xpoints[index - 1])
289 && (f[1] == ypoints[index - 1]))
293 case PathIterator.SEG_LINETO:
296 case PathIterator.SEG_QUADTO:
297 quadTo(f[0], f[1], f[2], f[3]);
299 case PathIterator.SEG_CUBICTO:
300 curveTo(f[0], f[1], f[2], f[3], f[4], f[5]);
302 case PathIterator.SEG_CLOSE:
313 * Returns the path’s current winding rule.
315 public int getWindingRule()
321 * Sets the path’s winding rule, which controls which areas are
322 * considered ’inside’ or ’outside’ the path
323 * on drawing. Valid rules are WIND_EVEN_ODD for an even-odd winding rule,
324 * or WIND_NON_ZERO for a non-zero winding rule.
326 public void setWindingRule(int rule)
328 if (rule != WIND_EVEN_ODD && rule != WIND_NON_ZERO)
329 throw new IllegalArgumentException();
334 * Returns the current appending point of the path.
336 public Point2D getCurrentPoint()
340 return new Point2D.Float(xpoints[index - 1], ypoints[index - 1]);
344 * Resets the path. All points and segments are destroyed.
353 * Applies a transform to the path.
355 public void transform(AffineTransform xform)
359 double[] m = new double[6];
361 for (int i = 0; i < index; i++)
363 nx = m[0] * xpoints[i] + m[2] * ypoints[i] + m[4];
364 ny = m[1] * xpoints[i] + m[3] * ypoints[i] + m[5];
365 xpoints[i] = (float) nx;
366 ypoints[i] = (float) ny;
371 * Creates a transformed version of the path.
372 * @param xform the transform to apply
373 * @return a new transformed GeneralPath
375 public Shape createTransformedShape(AffineTransform xform)
377 GeneralPath p = new GeneralPath(this);
383 * Returns the path’s bounding box.
385 public Rectangle getBounds()
387 return getBounds2D().getBounds();
391 * Returns the path’s bounding box, in <code>float</code> precision
393 public Rectangle2D getBounds2D()
402 x1 = x2 = xpoints[0];
403 y1 = y2 = ypoints[0];
406 x1 = x2 = y1 = y2 = 0.0f;
408 for (int i = 0; i < index; i++)
410 x1 = Math.min(xpoints[i], x1);
411 y1 = Math.min(ypoints[i], y1);
412 x2 = Math.max(xpoints[i], x2);
413 y2 = Math.max(ypoints[i], y2);
415 return (new Rectangle2D.Float(x1, y1, x2 - x1, y2 - y1));
419 * Evaluates if a point is within the GeneralPath,
420 * The NON_ZERO winding rule is used, regardless of the
422 * @param x x coordinate of the point to evaluate
423 * @param y y coordinate of the point to evaluate
424 * @return true if the point is within the path, false otherwise
426 public boolean contains(double x, double y)
428 return (getWindingNumber(x, y) != 0);
432 * Evaluates if a Point2D is within the GeneralPath,
433 * The NON_ZERO winding rule is used, regardless of the
435 * @param p The Point2D to evaluate
436 * @return true if the point is within the path, false otherwise
438 public boolean contains(Point2D p)
440 return contains(p.getX(), p.getY());
444 * Evaluates if a rectangle is completely contained within the path.
445 * This method will return false in the cases when the box
446 * intersects an inner segment of the path.
447 * (i.e.: The method is accurate for the EVEN_ODD winding rule)
449 public boolean contains(double x, double y, double w, double h)
451 if (! getBounds2D().intersects(x, y, w, h))
454 /* Does any edge intersect? */
455 if (getAxisIntersections(x, y, false, w) != 0 /* top */
456 || getAxisIntersections(x, y + h, false, w) != 0 /* bottom */
457 || getAxisIntersections(x + w, y, true, h) != 0 /* right */
458 || getAxisIntersections(x, y, true, h) != 0) /* left */
461 /* No intersections, is any point inside? */
462 if (getWindingNumber(x, y) != 0)
469 * Evaluates if a rectangle is completely contained within the path.
470 * This method will return false in the cases when the box
471 * intersects an inner segment of the path.
472 * (i.e.: The method is accurate for the EVEN_ODD winding rule)
473 * @param r the rectangle
474 * @return <code>true</code> if the rectangle is completely contained
475 * within the path, <code>false</code> otherwise
477 public boolean contains(Rectangle2D r)
479 return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
483 * Evaluates if a rectangle intersects the path.
484 * @param x x coordinate of the rectangle
485 * @param y y coordinate of the rectangle
486 * @param w width of the rectangle
487 * @param h height of the rectangle
488 * @return <code>true</code> if the rectangle intersects the path,
489 * <code>false</code> otherwise
491 public boolean intersects(double x, double y, double w, double h)
493 /* Does any edge intersect? */
494 if (getAxisIntersections(x, y, false, w) != 0 /* top */
495 || getAxisIntersections(x, y + h, false, w) != 0 /* bottom */
496 || getAxisIntersections(x + w, y, true, h) != 0 /* right */
497 || getAxisIntersections(x, y, true, h) != 0) /* left */
500 /* No intersections, is any point inside? */
501 if (getWindingNumber(x, y) != 0)
508 * Evaluates if a Rectangle2D intersects the path.
509 * @param r The rectangle
510 * @return <code>true</code> if the rectangle intersects the path,
511 * <code>false</code> otherwise
513 public boolean intersects(Rectangle2D r)
515 return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
519 * A PathIterator that iterates over the segments of a GeneralPath.
521 * @author Sascha Brawer (brawer@dandelis.ch)
523 private static class GeneralPathIterator implements PathIterator
526 * The number of coordinate values for each segment type.
528 private static final int[] NUM_COORDS = {
529 /* 0: SEG_MOVETO */ 1,
530 /* 1: SEG_LINETO */ 1,
531 /* 2: SEG_QUADTO */ 2,
532 /* 3: SEG_CUBICTO */ 3,
533 /* 4: SEG_CLOSE */ 0};
536 * The GeneralPath whose segments are being iterated.
538 private final GeneralPath path;
541 * The affine transformation used to transform coordinates.
543 private final AffineTransform transform;
546 * The current position of the iterator.
551 * Constructs a new iterator for enumerating the segments of a
554 * @param at an affine transformation for projecting the returned
555 * points, or <code>null</code> to return the original points
556 * without any mapping.
558 GeneralPathIterator(GeneralPath path, AffineTransform transform)
561 this.transform = transform;
565 * Returns the current winding rule of the GeneralPath.
567 public int getWindingRule()
573 * Determines whether the iterator has reached the last segment in
576 public boolean isDone()
578 return pos >= path.index;
582 * Advances the iterator position by one segment.
589 * Increment pos by the number of coordinate pairs.
591 seg = path.types[pos];
592 if (seg == SEG_CLOSE)
595 pos += NUM_COORDS[seg];
599 * Returns the current segment in float coordinates.
601 public int currentSegment(float[] coords)
606 seg = path.types[pos];
607 numCoords = NUM_COORDS[seg];
610 for (int i = 0; i < numCoords; i++)
612 coords[i << 1] = path.xpoints[pos + i];
613 coords[(i << 1) + 1] = path.ypoints[pos + i];
616 if (transform != null)
617 transform.transform( /* src */
618 coords, /* srcOffset */
619 0, /* dest */ coords, /* destOffset */
620 0, /* numPoints */ numCoords);
626 * Returns the current segment in double coordinates.
628 public int currentSegment(double[] coords)
633 seg = path.types[pos];
634 numCoords = NUM_COORDS[seg];
637 for (int i = 0; i < numCoords; i++)
639 coords[i << 1] = (double) path.xpoints[pos + i];
640 coords[(i << 1) + 1] = (double) path.ypoints[pos + i];
642 if (transform != null)
643 transform.transform( /* src */
644 coords, /* srcOffset */
645 0, /* dest */ coords, /* destOffset */
646 0, /* numPoints */ numCoords);
653 * Creates a PathIterator for iterating along the segments of the path.
655 * @param at an affine transformation for projecting the returned
656 * points, or <code>null</code> to let the created iterator return
657 * the original points without any mapping.
659 public PathIterator getPathIterator(AffineTransform at)
661 return new GeneralPathIterator(this, at);
665 * Creates a new FlatteningPathIterator for the path
667 public PathIterator getPathIterator(AffineTransform at, double flatness)
669 return new FlatteningPathIterator(getPathIterator(at), flatness);
673 * Creates a new shape of the same run-time type with the same contents
678 * @exception OutOfMemoryError If there is not enough memory available.
682 public Object clone()
684 // This class is final; no need to use super.clone().
685 return new GeneralPath(this);
689 * Helper method - ensure the size of the data arrays,
690 * otherwise, reallocate new ones twice the size
692 private void ensureSize(int size)
695 throw new IllegalPathStateException("need initial moveto");
696 if (size <= xpoints.length)
698 byte[] b = new byte[types.length << 1];
699 System.arraycopy(types, 0, b, 0, index);
701 float[] f = new float[xpoints.length << 1];
702 System.arraycopy(xpoints, 0, f, 0, index);
704 f = new float[ypoints.length << 1];
705 System.arraycopy(ypoints, 0, f, 0, index);
710 * Helper method - Get the total number of intersections from (x,y) along
711 * a given axis, within a given distance.
713 private int getAxisIntersections(double x, double y, boolean useYaxis,
716 return (evaluateCrossings(x, y, false, useYaxis, distance));
720 * Helper method - returns the winding number of a point.
722 private int getWindingNumber(double x, double y)
724 /* Evaluate the crossings from x,y to infinity on the y axis (arbitrary
725 choice). Note that we don't actually use Double.INFINITY, since that's
726 slower, and may cause problems. */
727 return (evaluateCrossings(x, y, true, true, BIG_VALUE));
731 * Helper method - evaluates the number of intersections on an axis from
732 * the point (x,y) to the point (x,y+distance) or (x+distance,y).
733 * @param x x coordinate.
734 * @param y y coordinate.
735 * @param neg True if opposite-directed intersections should cancel,
736 * false to sum all intersections.
737 * @param useYaxis Use the Y axis, false uses the X axis.
738 * @param distance Interval from (x,y) on the selected axis to find
741 private int evaluateCrossings(double x, double y, boolean neg,
742 boolean useYaxis, double distance)
749 int negative = (neg) ? -1 : 1;
758 double[] r = new double[4];
760 double epsilon = 0.0;
762 int windingNumber = 0;
763 boolean pathStarted = false;
779 /* Get a value which is hopefully small but not insignificant relative
781 epsilon = ypoints[0] * 1E-7;
791 case PathIterator.SEG_MOVETO:
792 if (pathStarted) // close old path
803 if (Line2D.linesIntersect(x0, y0, x1, y1,
804 epsilon, 0.0, distance, 0.0))
805 windingNumber += (y1 < y0) ? 1 : negative;
810 cx = firstx = xpoints[pos] - (float) x;
811 cy = firsty = ypoints[pos++] - (float) y;
814 case PathIterator.SEG_CLOSE:
824 if (Line2D.linesIntersect(x0, y0, x1, y1,
825 epsilon, 0.0, distance, 0.0))
826 windingNumber += (y1 < y0) ? 1 : negative;
833 case PathIterator.SEG_LINETO:
836 x1 = xpoints[pos] - (float) x;
837 y1 = ypoints[pos++] - (float) y;
843 if (Line2D.linesIntersect(x0, y0, x1, y1,
844 epsilon, 0.0, distance, 0.0))
845 windingNumber += (y1 < y0) ? 1 : negative;
847 cx = xpoints[pos - 1] - (float) x;
848 cy = ypoints[pos - 1] - (float) y;
850 case PathIterator.SEG_QUADTO:
853 x1 = xpoints[pos] - x;
854 y1 = ypoints[pos++] - y;
855 x2 = xpoints[pos] - x;
856 y2 = ypoints[pos++] - y;
858 /* check if curve may intersect X+ axis. */
859 if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0)
860 && (y0 * y1 <= 0 || y1 * y2 <= 0))
868 r[1] = 2 * (y1 - y0);
869 r[2] = (y2 - 2 * y1 + y0);
871 /* degenerate roots (=tangent points) do not
872 contribute to the winding number. */
873 if ((nRoots = QuadCurve2D.solveQuadratic(r)) == 2)
874 for (int i = 0; i < nRoots; i++)
876 float t = (float) r[i];
877 if (t > 0.0f && t < 1.0f)
879 double crossing = t * t * (x2 - 2 * x1 + x0)
880 + 2 * t * (x1 - x0) + x0;
881 if (crossing >= 0.0 && crossing <= distance)
882 windingNumber += (2 * t * (y2 - 2 * y1 + y0)
883 + 2 * (y1 - y0) < 0) ? 1 : negative;
888 cx = xpoints[pos - 1] - (float) x;
889 cy = ypoints[pos - 1] - (float) y;
891 case PathIterator.SEG_CUBICTO:
894 x1 = xpoints[pos] - x;
895 y1 = ypoints[pos++] - y;
896 x2 = xpoints[pos] - x;
897 y2 = ypoints[pos++] - y;
898 x3 = xpoints[pos] - x;
899 y3 = ypoints[pos++] - y;
901 /* check if curve may intersect X+ axis. */
902 if ((x0 > 0.0 || x1 > 0.0 || x2 > 0.0 || x3 > 0.0)
903 && (y0 * y1 <= 0 || y1 * y2 <= 0 || y2 * y3 <= 0))
911 r[1] = 3 * (y1 - y0);
912 r[2] = 3 * (y2 + y0 - 2 * y1);
913 r[3] = y3 - 3 * y2 + 3 * y1 - y0;
915 if ((nRoots = CubicCurve2D.solveCubic(r)) != 0)
916 for (int i = 0; i < nRoots; i++)
918 float t = (float) r[i];
919 if (t > 0.0 && t < 1.0)
921 double crossing = -(t * t * t) * (x0 - 3 * x1
923 + 3 * t * t * (x0 - 2 * x1 + x2)
924 + 3 * t * (x1 - x0) + x0;
925 if (crossing >= 0 && crossing <= distance)
926 windingNumber += (3 * t * t * (y3 + 3 * y1
928 + 6 * t * (y0 - 2 * y1 + y2)
929 + 3 * (y1 - y0) < 0) ? 1 : negative;
934 cx = xpoints[pos - 1] - (float) x;
935 cy = ypoints[pos - 1] - (float) y;
940 // swap coordinates back
948 return (windingNumber);
950 } // class GeneralPath