1 /*
2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.awt.geom;
27
28 import java.util.*;
29
30 /**
31 * The {@code FlatteningPathIterator} class returns a flattened view of
32 * another {@link PathIterator} object. Other {@link java.awt.Shape Shape}
33 * classes can use this class to provide flattening behavior for their paths
34 * without having to perform the interpolation calculations themselves.
35 *
36 * @author Jim Graham
37 */
38 public class FlatteningPathIterator implements PathIterator {
39 static final int GROW_SIZE = 24; // Multiple of cubic & quad curve size
40
41 PathIterator src; // The source iterator
42
43 double squareflat; // Square of the flatness parameter
44 // for testing against squared lengths
45
46 int limit; // Maximum number of recursion levels
47
48 double hold[] = new double[14]; // The cache of interpolated coords
49 // Note that this must be long enough
50 // to store a full cubic segment and
51 // a relative cubic segment to avoid
52 // aliasing when copying the coords
53 // of a curve to the end of the array.
54 // This is also serendipitously equal
55 // to the size of a full quad segment
56 // and 2 relative quad segments.
57
58 double curx, cury; // The ending x,y of the last segment
59
60 double movx, movy; // The x,y of the last move segment
61
62 int holdType; // The type of the curve being held
63 // for interpolation
64
65 int holdEnd; // The index of the last curve segment
66 // being held for interpolation
67
68 int holdIndex; // The index of the curve segment
69 // that was last interpolated. This
70 // is the curve segment ready to be
71 // returned in the next call to
72 // currentSegment().
73
74 int levels[]; // The recursion level at which
75 // each curve being held in storage
76 // was generated.
77
78 int levelIndex; // The index of the entry in the
79 // levels array of the curve segment
80 // at the holdIndex
81
82 boolean done; // True when iteration is done
83
84 /**
85 * Constructs a new {@code FlatteningPathIterator} object that
86 * flattens a path as it iterates over it. The iterator does not
87 * subdivide any curve read from the source iterator to more than
88 * 10 levels of subdivision which yields a maximum of 1024 line
89 * segments per curve.
90 * @param src the original unflattened path being iterated over
91 * @param flatness the maximum allowable distance between the
92 * control points and the flattened curve
93 */
94 public FlatteningPathIterator(PathIterator src, double flatness) {
95 this(src, flatness, 10);
96 }
97
98 /**
99 * Constructs a new {@code FlatteningPathIterator} object
100 * that flattens a path as it iterates over it.
101 * The {@code limit} parameter allows you to control the
102 * maximum number of recursive subdivisions that the iterator
103 * can make before it assumes that the curve is flat enough
104 * without measuring against the {@code flatness} parameter.
105 * The flattened iteration therefore never generates more than
106 * a maximum of {@code (2^limit)} line segments per curve.
107 * @param src the original unflattened path being iterated over
108 * @param flatness the maximum allowable distance between the
109 * control points and the flattened curve
110 * @param limit the maximum number of recursive subdivisions
111 * allowed for any curved segment
112 * @exception IllegalArgumentException if
113 * {@code flatness} or {@code limit}
114 * is less than zero
115 */
116 public FlatteningPathIterator(PathIterator src, double flatness,
117 int limit) {
118 if (flatness < 0.0) {
119 throw new IllegalArgumentException("flatness must be >= 0");
120 }
121 if (limit < 0) {
122 throw new IllegalArgumentException("limit must be >= 0");
123 }
124 this.src = src;
125 this.squareflat = flatness * flatness;
126 this.limit = limit;
127 this.levels = new int[limit + 1];
128 // prime the first path segment
129 next(false);
130 }
131
132 /**
133 * Returns the flatness of this iterator.
134 * @return the flatness of this {@code FlatteningPathIterator}.
135 */
136 public double getFlatness() {
137 return Math.sqrt(squareflat);
138 }
139
140 /**
141 * Returns the recursion limit of this iterator.
142 * @return the recursion limit of this
143 * {@code FlatteningPathIterator}.
144 */
145 public int getRecursionLimit() {
146 return limit;
147 }
148
149 /**
150 * Returns the winding rule for determining the interior of the
151 * path.
152 * @return the winding rule of the original unflattened path being
153 * iterated over.
154 * @see PathIterator#WIND_EVEN_ODD
155 * @see PathIterator#WIND_NON_ZERO
156 */
157 public int getWindingRule() {
158 return src.getWindingRule();
159 }
160
161 /**
162 * Tests if the iteration is complete.
163 * @return {@code true} if all the segments have
164 * been read; {@code false} otherwise.
165 */
166 public boolean isDone() {
167 return done;
168 }
169
170 /*
171 * Ensures that the hold array can hold up to (want) more values.
172 * It is currently holding (hold.length - holdIndex) values.
173 */
174 void ensureHoldCapacity(int want) {
175 if (holdIndex - want < 0) {
176 int have = hold.length - holdIndex;
177 int newsize = hold.length + GROW_SIZE;
178 double newhold[] = new double[newsize];
179 System.arraycopy(hold, holdIndex,
180 newhold, holdIndex + GROW_SIZE,
181 have);
182 hold = newhold;
183 holdIndex += GROW_SIZE;
184 holdEnd += GROW_SIZE;
185 }
186 }
187
188 /**
189 * Moves the iterator to the next segment of the path forwards
190 * along the primary direction of traversal as long as there are
191 * more points in that direction.
192 */
193 public void next() {
194 next(true);
195 }
196
197 private void next(boolean doNext) {
198 int level;
199
200 if (holdIndex >= holdEnd) {
201 if (doNext) {
202 src.next();
203 }
204 if (src.isDone()) {
205 done = true;
206 return;
207 }
208 holdType = src.currentSegment(hold);
209 levelIndex = 0;
210 levels[0] = 0;
211 }
212
213 switch (holdType) {
214 case SEG_MOVETO:
215 case SEG_LINETO:
216 curx = hold[0];
217 cury = hold[1];
218 if (holdType == SEG_MOVETO) {
219 movx = curx;
220 movy = cury;
221 }
222 holdIndex = 0;
223 holdEnd = 0;
224 break;
225 case SEG_CLOSE:
226 curx = movx;
227 cury = movy;
228 holdIndex = 0;
229 holdEnd = 0;
230 break;
231 case SEG_QUADTO:
232 if (holdIndex >= holdEnd) {
233 // Move the coordinates to the end of the array.
234 holdIndex = hold.length - 6;
235 holdEnd = hold.length - 2;
236 hold[holdIndex + 0] = curx;
237 hold[holdIndex + 1] = cury;
238 hold[holdIndex + 2] = hold[0];
239 hold[holdIndex + 3] = hold[1];
240 hold[holdIndex + 4] = curx = hold[2];
241 hold[holdIndex + 5] = cury = hold[3];
242 }
243
244 level = levels[levelIndex];
245 while (level < limit) {
246 if (QuadCurve2D.getFlatnessSq(hold, holdIndex) < squareflat) {
247 break;
248 }
249
250 ensureHoldCapacity(4);
251 QuadCurve2D.subdivide(hold, holdIndex,
252 hold, holdIndex - 4,
253 hold, holdIndex);
254 holdIndex -= 4;
255
256 // Now that we have subdivided, we have constructed
257 // two curves of one depth lower than the original
258 // curve. One of those curves is in the place of
259 // the former curve and one of them is in the next
260 // set of held coordinate slots. We now set both
261 // curves level values to the next higher level.
262 level++;
263 levels[levelIndex] = level;
264 levelIndex++;
265 levels[levelIndex] = level;
266 }
267
268 // This curve segment is flat enough, or it is too deep
269 // in recursion levels to try to flatten any more. The
270 // two coordinates at holdIndex+4 and holdIndex+5 now
271 // contain the endpoint of the curve which can be the
272 // endpoint of an approximating line segment.
273 holdIndex += 4;
274 levelIndex--;
275 break;
276 case SEG_CUBICTO:
277 if (holdIndex >= holdEnd) {
278 // Move the coordinates to the end of the array.
279 holdIndex = hold.length - 8;
280 holdEnd = hold.length - 2;
281 hold[holdIndex + 0] = curx;
282 hold[holdIndex + 1] = cury;
283 hold[holdIndex + 2] = hold[0];
284 hold[holdIndex + 3] = hold[1];
285 hold[holdIndex + 4] = hold[2];
286 hold[holdIndex + 5] = hold[3];
287 hold[holdIndex + 6] = curx = hold[4];
288 hold[holdIndex + 7] = cury = hold[5];
289 }
290
291 level = levels[levelIndex];
292 while (level < limit) {
293 if (CubicCurve2D.getFlatnessSq(hold, holdIndex) < squareflat) {
294 break;
295 }
296
297 ensureHoldCapacity(6);
298 CubicCurve2D.subdivide(hold, holdIndex,
299 hold, holdIndex - 6,
300 hold, holdIndex);
301 holdIndex -= 6;
302
303 // Now that we have subdivided, we have constructed
304 // two curves of one depth lower than the original
305 // curve. One of those curves is in the place of
306 // the former curve and one of them is in the next
307 // set of held coordinate slots. We now set both
308 // curves level values to the next higher level.
309 level++;
310 levels[levelIndex] = level;
311 levelIndex++;
312 levels[levelIndex] = level;
313 }
314
315 // This curve segment is flat enough, or it is too deep
316 // in recursion levels to try to flatten any more. The
317 // two coordinates at holdIndex+6 and holdIndex+7 now
318 // contain the endpoint of the curve which can be the
319 // endpoint of an approximating line segment.
320 holdIndex += 6;
321 levelIndex--;
322 break;
323 }
324 }
325
326 /**
327 * Returns the coordinates and type of the current path segment in
328 * the iteration.
329 * The return value is the path segment type:
330 * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE.
331 * A float array of length 6 must be passed in and can be used to
332 * store the coordinates of the point(s).
333 * Each point is stored as a pair of float x,y coordinates.
334 * SEG_MOVETO and SEG_LINETO types return one point,
335 * and SEG_CLOSE does not return any points.
336 * @param coords an array that holds the data returned from
337 * this method
338 * @return the path segment type of the current path segment.
339 * @exception NoSuchElementException if there
340 * are no more elements in the flattening path to be
341 * returned.
342 * @see PathIterator#SEG_MOVETO
343 * @see PathIterator#SEG_LINETO
344 * @see PathIterator#SEG_CLOSE
345 */
346 public int currentSegment(float[] coords) {
347 if (isDone()) {
348 throw new NoSuchElementException("flattening iterator out of bounds");
349 }
350 int type = holdType;
351 if (type != SEG_CLOSE) {
352 coords[0] = (float) hold[holdIndex + 0];
353 coords[1] = (float) hold[holdIndex + 1];
354 if (type != SEG_MOVETO) {
355 type = SEG_LINETO;
356 }
357 }
358 return type;
359 }
360
361 /**
362 * Returns the coordinates and type of the current path segment in
363 * the iteration.
364 * The return value is the path segment type:
365 * SEG_MOVETO, SEG_LINETO, or SEG_CLOSE.
366 * A double array of length 6 must be passed in and can be used to
367 * store the coordinates of the point(s).
368 * Each point is stored as a pair of double x,y coordinates.
369 * SEG_MOVETO and SEG_LINETO types return one point,
370 * and SEG_CLOSE does not return any points.
371 * @param coords an array that holds the data returned from
372 * this method
373 * @return the path segment type of the current path segment.
374 * @exception NoSuchElementException if there
375 * are no more elements in the flattening path to be
376 * returned.
377 * @see PathIterator#SEG_MOVETO
378 * @see PathIterator#SEG_LINETO
379 * @see PathIterator#SEG_CLOSE
380 */
381 public int currentSegment(double[] coords) {
382 if (isDone()) {
383 throw new NoSuchElementException("flattening iterator out of bounds");
384 }
385 int type = holdType;
386 if (type != SEG_CLOSE) {
387 coords[0] = hold[holdIndex + 0];
388 coords[1] = hold[holdIndex + 1];
389 if (type != SEG_MOVETO) {
390 type = SEG_LINETO;
391 }
392 }
393 return type;
394 }
395 }