001: /*
002:
003: Licensed to the Apache Software Foundation (ASF) under one or more
004: contributor license agreements. See the NOTICE file distributed with
005: this work for additional information regarding copyright ownership.
006: The ASF licenses this file to You under the Apache License, Version 2.0
007: (the "License"); you may not use this file except in compliance with
008: the License. You may obtain a copy of the License at
009:
010: http://www.apache.org/licenses/LICENSE-2.0
011:
012: Unless required by applicable law or agreed to in writing, software
013: distributed under the License is distributed on an "AS IS" BASIS,
014: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015: See the License for the specific language governing permissions and
016: limitations under the License.
017:
018: */
019: package org.apache.batik.ext.awt.geom;
020:
021: import java.awt.Shape;
022: import java.awt.geom.AffineTransform;
023: import java.awt.geom.FlatteningPathIterator;
024: import java.awt.geom.PathIterator;
025: import java.awt.geom.Point2D;
026: import java.util.List;
027: import java.util.ArrayList;
028:
029: /**
030: * Utilitiy class for length calculations of paths.
031: * <p>
032: * PathLength is a utility class for calculating the length
033: * of a path, the location of a point at a particular length
034: * along the path, and the angle of the tangent to the path
035: * at a given length.
036: * </p>
037: * <p>
038: * It uses a FlatteningPathIterator to create a flattened version
039: * of the Path. This means the values returned are not always
040: * exact (in fact, they rarely are), but in most cases they
041: * are reasonably accurate.
042: * </p>
043: *
044: * @author <a href="mailto:dean.jackson@cmis.csiro.au">Dean Jackson</a>
045: * @version $Id: PathLength.java 489226 2006-12-21 00:05:36Z cam $
046: */
047: public class PathLength {
048:
049: /**
050: * The path to use for calculations.
051: */
052: protected Shape path;
053:
054: /**
055: * The list of flattened path segments.
056: */
057: protected List segments;
058:
059: /**
060: * Array where the index is the index of the original path segment
061: * and the value is the index of the first of the flattened segments
062: * in {@link #segments} that corresponds to that original path segment.
063: */
064: protected int[] segmentIndexes;
065:
066: /**
067: * Cached copy of the path length.
068: */
069: protected float pathLength;
070:
071: /**
072: * Whether this path been flattened yet.
073: */
074: protected boolean initialised;
075:
076: /**
077: * Creates a new PathLength object for the specified {@link Shape}.
078: * @param path The Path (or Shape) to use.
079: */
080: public PathLength(Shape path) {
081: setPath(path);
082: }
083:
084: /**
085: * Returns the path to use for calculations.
086: * @return Path used in calculations.
087: */
088: public Shape getPath() {
089: return path;
090: }
091:
092: /**
093: * Sets the path to use for calculations.
094: * @param v Path to be used in calculations.
095: */
096: public void setPath(Shape v) {
097: this .path = v;
098: initialised = false;
099: }
100:
101: /**
102: * Returns the length of the path used by this PathLength object.
103: * @return The length of the path.
104: */
105: public float lengthOfPath() {
106: if (!initialised) {
107: initialise();
108: }
109: return pathLength;
110: }
111:
112: /**
113: * Flattens the path and determines the path length.
114: */
115: protected void initialise() {
116: pathLength = 0f;
117:
118: PathIterator pi = path.getPathIterator(new AffineTransform());
119: SingleSegmentPathIterator sspi = new SingleSegmentPathIterator();
120: segments = new ArrayList(20);
121: List indexes = new ArrayList(20);
122: int index = 0;
123: int origIndex = -1;
124: float lastMoveX = 0f;
125: float lastMoveY = 0f;
126: float currentX = 0f;
127: float currentY = 0f;
128: float[] seg = new float[6];
129: int segType;
130:
131: segments.add(new PathSegment(PathIterator.SEG_MOVETO, 0f, 0f,
132: 0f, origIndex));
133:
134: while (!pi.isDone()) {
135: origIndex++;
136: indexes.add(new Integer(index));
137: segType = pi.currentSegment(seg);
138: switch (segType) {
139: case PathIterator.SEG_MOVETO:
140: segments.add(new PathSegment(segType, seg[0], seg[1],
141: pathLength, origIndex));
142: currentX = seg[0];
143: currentY = seg[1];
144: lastMoveX = currentX;
145: lastMoveY = currentY;
146: index++;
147: pi.next();
148: break;
149: case PathIterator.SEG_LINETO:
150: pathLength += Point2D.distance(currentX, currentY,
151: seg[0], seg[1]);
152: segments.add(new PathSegment(segType, seg[0], seg[1],
153: pathLength, origIndex));
154: currentX = seg[0];
155: currentY = seg[1];
156: index++;
157: pi.next();
158: break;
159: case PathIterator.SEG_CLOSE:
160: pathLength += Point2D.distance(currentX, currentY,
161: lastMoveX, lastMoveY);
162: segments.add(new PathSegment(PathIterator.SEG_LINETO,
163: lastMoveX, lastMoveY, pathLength, origIndex));
164: currentX = lastMoveX;
165: currentY = lastMoveY;
166: index++;
167: pi.next();
168: break;
169: default:
170: sspi.setPathIterator(pi, currentX, currentY);
171: FlatteningPathIterator fpi = new FlatteningPathIterator(
172: sspi, 0.01f);
173: while (!fpi.isDone()) {
174: segType = fpi.currentSegment(seg);
175: if (segType == PathIterator.SEG_LINETO) {
176: pathLength += Point2D.distance(currentX,
177: currentY, seg[0], seg[1]);
178: segments.add(new PathSegment(segType, seg[0],
179: seg[1], pathLength, origIndex));
180: currentX = seg[0];
181: currentY = seg[1];
182: index++;
183: }
184: fpi.next();
185: }
186: }
187: }
188: segmentIndexes = new int[indexes.size()];
189: for (int i = 0; i < segmentIndexes.length; i++) {
190: segmentIndexes[i] = ((Integer) indexes.get(i)).intValue();
191: }
192: initialised = true;
193: }
194:
195: /**
196: * Returns the number of segments in the path.
197: */
198: public int getNumberOfSegments() {
199: if (!initialised) {
200: initialise();
201: }
202: return segmentIndexes.length;
203: }
204:
205: /**
206: * Returns the length at the start of the segment given by the specified
207: * index.
208: */
209: public float getLengthAtSegment(int index) {
210: if (!initialised) {
211: initialise();
212: }
213: if (index <= 0) {
214: return 0;
215: }
216: if (index >= segmentIndexes.length) {
217: return pathLength;
218: }
219: PathSegment seg = (PathSegment) segments
220: .get(segmentIndexes[index]);
221: return seg.getLength();
222: }
223:
224: /**
225: * Returns the index of the segment at the given distance along the path.
226: */
227: public int segmentAtLength(float length) {
228: int upperIndex = findUpperIndex(length);
229: if (upperIndex == -1) {
230: // Length is off the end of the path.
231: return -1;
232: }
233:
234: if (upperIndex == 0) {
235: // Length was probably zero, so return the upper segment.
236: PathSegment upper = (PathSegment) segments.get(upperIndex);
237: return upper.getIndex();
238: }
239:
240: PathSegment lower = (PathSegment) segments.get(upperIndex - 1);
241: return lower.getIndex();
242: }
243:
244: /**
245: * Returns the point that is the given proportion along the path segment
246: * given by the specified index.
247: */
248: public Point2D pointAtLength(int index, float proportion) {
249: if (!initialised) {
250: initialise();
251: }
252: if (index < 0 || index >= segmentIndexes.length) {
253: return null;
254: }
255: PathSegment seg = (PathSegment) segments
256: .get(segmentIndexes[index]);
257: float start = seg.getLength();
258: float end;
259: if (index == segmentIndexes.length - 1) {
260: end = pathLength;
261: } else {
262: seg = (PathSegment) segments.get(segmentIndexes[index + 1]);
263: end = seg.getLength();
264: }
265: return pointAtLength(start + (end - start) * proportion);
266: }
267:
268: /**
269: * Returns the point that is at the given length along the path.
270: * @param length The length along the path
271: * @return The point at the given length
272: */
273: public Point2D pointAtLength(float length) {
274: int upperIndex = findUpperIndex(length);
275: if (upperIndex == -1) {
276: // Length is off the end of the path.
277: return null;
278: }
279:
280: PathSegment upper = (PathSegment) segments.get(upperIndex);
281:
282: if (upperIndex == 0) {
283: // Length was probably zero, so return the upper point.
284: return new Point2D.Float(upper.getX(), upper.getY());
285: }
286:
287: PathSegment lower = (PathSegment) segments.get(upperIndex - 1);
288:
289: // Now work out where along the line would be the length.
290: float offset = length - lower.getLength();
291:
292: // Compute the slope.
293: double theta = Math.atan2(upper.getY() - lower.getY(), upper
294: .getX()
295: - lower.getX());
296:
297: float xPoint = (float) (lower.getX() + offset * Math.cos(theta));
298: float yPoint = (float) (lower.getY() + offset * Math.sin(theta));
299:
300: return new Point2D.Float(xPoint, yPoint);
301: }
302:
303: /**
304: * Returns the slope of the path at the specified length.
305: * @param index The segment number
306: * @param proportion The proportion along the given segment
307: * @return the angle in radians, in the range [-{@link Math#PI},
308: * {@link Math#PI}].
309: */
310: public float angleAtLength(int index, float proportion) {
311: if (!initialised) {
312: initialise();
313: }
314: if (index < 0 || index >= segmentIndexes.length) {
315: return 0f;
316: }
317: PathSegment seg = (PathSegment) segments
318: .get(segmentIndexes[index]);
319: float start = seg.getLength();
320: float end;
321: if (index == segmentIndexes.length - 1) {
322: end = pathLength;
323: } else {
324: seg = (PathSegment) segments.get(segmentIndexes[index + 1]);
325: end = seg.getLength();
326: }
327: return angleAtLength(start + (end - start) * proportion);
328: }
329:
330: /**
331: * Returns the slope of the path at the specified length.
332: * @param length The length along the path
333: * @return the angle in radians, in the range [-{@link Math#PI},
334: * {@link Math#PI}].
335: */
336: public float angleAtLength(float length) {
337: int upperIndex = findUpperIndex(length);
338: if (upperIndex == -1) {
339: // Length is off the end of the path.
340: return 0f;
341: }
342:
343: PathSegment upper = (PathSegment) segments.get(upperIndex);
344:
345: if (upperIndex == 0) {
346: // Length was probably zero, so return the angle between the first
347: // and second segments.
348: upperIndex = 1;
349: }
350:
351: PathSegment lower = (PathSegment) segments.get(upperIndex - 1);
352:
353: // Compute the slope.
354: return (float) Math.atan2(upper.getY() - lower.getY(), upper
355: .getX()
356: - lower.getX());
357: }
358:
359: /**
360: * Returns the index of the path segment that bounds the specified
361: * length along the path.
362: * @param length The length along the path
363: * @return The path segment index, or -1 if there is not such segment
364: */
365: public int findUpperIndex(float length) {
366: if (!initialised) {
367: initialise();
368: }
369:
370: if (length < 0 || length > pathLength) {
371: // Length is outside the path, so return -1.
372: return -1;
373: }
374:
375: // Find the two segments that are each side of the length.
376: int lb = 0;
377: int ub = segments.size() - 1;
378: while (lb != ub) {
379: int curr = (lb + ub) >> 1;
380: PathSegment ps = (PathSegment) segments.get(curr);
381: if (ps.getLength() >= length) {
382: ub = curr;
383: } else {
384: lb = curr + 1;
385: }
386: }
387: for (;;) {
388: PathSegment ps = (PathSegment) segments.get(ub);
389: if (ps.getSegType() != PathIterator.SEG_MOVETO
390: || ub == segments.size() - 1) {
391: break;
392: }
393: ub++;
394: }
395:
396: int upperIndex = -1;
397: int currentIndex = 0;
398: int numSegments = segments.size();
399: while (upperIndex <= 0 && currentIndex < numSegments) {
400: PathSegment ps = (PathSegment) segments.get(currentIndex);
401: if (ps.getLength() >= length
402: && ps.getSegType() != PathIterator.SEG_MOVETO) {
403: upperIndex = currentIndex;
404: }
405: currentIndex++;
406: }
407: return upperIndex;
408: }
409:
410: /**
411: * A {@link PathIterator} that returns only the next path segment from
412: * another {@link PathIterator}.
413: */
414: protected static class SingleSegmentPathIterator implements
415: PathIterator {
416:
417: /**
418: * The path iterator being wrapped.
419: */
420: protected PathIterator it;
421:
422: /**
423: * Whether the single segment has been passed.
424: */
425: protected boolean done;
426:
427: /**
428: * Whether the generated move command has been returned.
429: */
430: protected boolean moveDone;
431:
432: /**
433: * The x coordinate of the next move command.
434: */
435: protected double x;
436:
437: /**
438: * The y coordinate of the next move command.
439: */
440: protected double y;
441:
442: /**
443: * Sets the path iterator to use and the initial SEG_MOVETO command
444: * to return before it.
445: */
446: public void setPathIterator(PathIterator it, double x, double y) {
447: this .it = it;
448: this .x = x;
449: this .y = y;
450: done = false;
451: moveDone = false;
452: }
453:
454: public int currentSegment(double[] coords) {
455: int type = it.currentSegment(coords);
456: if (!moveDone) {
457: coords[0] = x;
458: coords[1] = y;
459: return SEG_MOVETO;
460: }
461: return type;
462: }
463:
464: public int currentSegment(float[] coords) {
465: int type = it.currentSegment(coords);
466: if (!moveDone) {
467: coords[0] = (float) x;
468: coords[1] = (float) y;
469: return SEG_MOVETO;
470: }
471: return type;
472: }
473:
474: public int getWindingRule() {
475: return it.getWindingRule();
476: }
477:
478: public boolean isDone() {
479: return done || it.isDone();
480: }
481:
482: public void next() {
483: if (!done) {
484: if (!moveDone) {
485: moveDone = true;
486: } else {
487: it.next();
488: done = true;
489: }
490: }
491: }
492: }
493:
494: /**
495: * A single path segment in the flattened version of the path.
496: * This is a local helper class. PathSegment-objects are stored in
497: * the {@link PathLength#segments} - list.
498: * This is used as an immutable value-object.
499: */
500: protected static class PathSegment {
501:
502: /**
503: * The path segment type.
504: */
505: protected final int segType;
506:
507: /**
508: * The x coordinate of the path segment.
509: */
510: protected float x;
511:
512: /**
513: * The y coordinate of the path segment.
514: */
515: protected float y;
516:
517: /**
518: * The length of the path segment, accumulated from the start.
519: */
520: protected float length;
521:
522: /**
523: * The index of the original path segment this flattened segment is a
524: * part of.
525: */
526: protected int index;
527:
528: /**
529: * Creates a new PathSegment with the specified parameters.
530: * @param segType The segment type
531: * @param x The x coordinate
532: * @param y The y coordinate
533: * @param len The segment length
534: * @param idx The index of the original path segment this flattened
535: * segment is a part of
536: */
537: PathSegment(int segType, float x, float y, float len, int idx) {
538: this .segType = segType;
539: this .x = x;
540: this .y = y;
541: this .length = len;
542: this .index = idx;
543: }
544:
545: /**
546: * Returns the segment type.
547: */
548: public int getSegType() {
549: return segType;
550: }
551:
552: /**
553: * Returns the x coordinate of the path segment.
554: */
555: public float getX() {
556: return x;
557: }
558:
559: /**
560: * Sets the x coordinate of the path segment.
561: */
562: public void setX(float v) {
563: x = v;
564: }
565:
566: /**
567: * Returns the y coordinate of the path segment.
568: */
569: public float getY() {
570: return y;
571: }
572:
573: /**
574: * Sets the y coordinate of the path segment.
575: */
576: public void setY(float v) {
577: y = v;
578: }
579:
580: /**
581: * Returns the length of the path segment.
582: */
583: public float getLength() {
584: return length;
585: }
586:
587: /**
588: * Sets the length of the path segment.
589: */
590: public void setLength(float v) {
591: length = v;
592: }
593:
594: /**
595: * Returns the segment index.
596: */
597: public int getIndex() {
598: return index;
599: }
600:
601: /**
602: * Sets the segment index.
603: */
604: public void setIndex(int v) {
605: index = v;
606: }
607: }
608: }
|