PathLength


1   /*
2   
3      Copyright 2001,2003  The Apache Software Foundation 
4   
5      Licensed under the Apache License, Version 2.0 (the "License");
6      you may not use this file except in compliance with the License.
7      You may obtain a copy of the License at
8   
9          http://www.apache.org/licenses/LICENSE-2.0
10  
11     Unless required by applicable law or agreed to in writing, software
12     distributed under the License is distributed on an "AS IS" BASIS,
13     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14     See the License for the specific language governing permissions and
15     limitations under the License.
16  
17   */
18  package org.apache.batik.ext.awt.geom;
19  
20  import java.awt.Shape  ;
21  import java.awt.geom.AffineTransform  ;
22  import java.awt.geom.FlatteningPathIterator  ;
23  import java.awt.geom.GeneralPath  ;
24  import java.awt.geom.PathIterator  ;
25  import java.awt.geom.Point2D  ;
26  import java.util.Vector  ;
27  
28  /**
29   * PathLength is a utility class for calculating the length
30   * of a path, the location of a point at a particular length
31   * along the path, and the angle of the tangent to the path
32   * at a given length.
33   * <p>
34   * It uses a FlatteningPathIterator to create a flattened version
35   * of the Path. This means the values returned are not always
36   * exact (in fact, they rarely are), but in most cases they
37   * are reasonably accurate.
38   *
39   * @author <a HREF="mailto:dean.jackson@cmis.csiro.au">Dean Jackson</a>
40   * @version $Id: PathLength.java,v 1.8 2005/02/27 02:08:52 deweese Exp $
41   */
42  
43  public class PathLength {
44  
45      /**
46       * Construct a PathLength utility class to operate on the
47       * particular Shape.
48       *
49       * @param path The Path (or Shape) to use.
50       */
51  
52      public PathLength(Shape   path) {
53          setPath(path);
54      }
55  
56  
57      private Shape   path = null;
58  
59      /**
60       * Get the path to use in calculations.
61       * @return Path used in calculations.
62       */
63  
64      public Shape   getPath() {
65          return path;
66      }
67  
68      /**
69       * Set the path to use in calculations.
70       * @param v  Path to be used in calculations.
71       */
72  
73      public void setPath(Shape   v) {
74          this.path = v;
75          initialised = false;
76      }
77  
78      /**
79       * The list of flattened path segments.
80       */
81  
82      private Vector   segments = null;
83  
84      /**
85       * Cached copy of the path length.
86       */
87      private float pathLength = 0f;
88  
89      /**
90       * Has this path been flattened?
91       */
92      private boolean initialised = false;
93  
94  
95      /**
96       * Returns the length of the path used by this PathLength object.
97       *
98       * @return The length of the path.
99       */
100 
101     public float lengthOfPath() {
102 
103         if (!initialised) {
104             initialise();
105         }
106 
107         return pathLength;
108     }
109 
110 
111     protected void initialise() {
112 
113         pathLength = 0f;
114 
115         FlatteningPathIterator   fpi = new FlatteningPathIterator  (path.getPathIterator(new AffineTransform  ()), 0.01f);
116         segments = new Vector  (20);
117         float lastMoveX = 0f;
118         float lastMoveY = 0f;
119         float currentX = 0f;
120         float currentY = 0f;
121         float seg[] = new float[6];
122         int segType;
123 
124         segments.add(new PathSegment(PathIterator.SEG_MOVETO, 0f, 0f, 0f));
125 
126         while (!fpi.isDone()) {
127 
128             segType = fpi.currentSegment(seg);
129 
130             switch (segType) {
131 
132             case PathIterator.SEG_MOVETO:
133 
134                 // System.err.println("== MOVE TO " + seg[0] + " " + seg[1]);
135 
136                 segments.add(new PathSegment(segType, seg[0], seg[1], pathLength));
137                 currentX = seg[0];
138                 currentY = seg[1];
139                 lastMoveX = currentX;
140                 lastMoveY = currentY;
141 
142                 break;
143 
144             case PathIterator.SEG_LINETO:
145 
146                 // System.err.println("== LINE TO " + seg[0] + " " + seg[1]);
147 
148                 pathLength += Point2D.distance(currentX, currentY, seg[0], seg[1]);
149                 segments.add(new PathSegment(segType, seg[0], seg[1], pathLength));
150 
151                 currentX = seg[0];
152                 currentY = seg[1];
153 
154                 break;
155 
156             case PathIterator.SEG_CLOSE:
157 
158                 // System.err.println("== CLOSE TO " + lastMoveX + " " + lastMoveY);
159 
160                 pathLength += Point2D.distance(currentX, currentY, lastMoveX, lastMoveY);
161                 segments.add(new PathSegment(PathIterator.SEG_LINETO, lastMoveX, lastMoveY, pathLength));
162 
163                 currentX = lastMoveX;
164                 currentY = lastMoveY;
165 
166                 break;
167 
168             default:
169 
170                 // ouch, where have these come from
171                 System.out.println("Bad path segment types");
172 
173             }
174 
175             fpi.next();
176 
177         }
178 
179         initialised = true;
180 
181     }
182 
183 
184     /**
185      * Return the point that is at the given length
186      * along the path.
187      *
188      * @param length The length along the path
189      * @return The point at the given length
190      */
191 
192     public Point2D   pointAtLength(float length) {
193 
194         int upperIndex = findUpperIndex(length);
195 
196         if (upperIndex == -1) {
197             // length is off the end of the path
198             return null;
199         }
200 
201         PathSegment upper = (PathSegment) segments.elementAt(upperIndex);
202 
203         if (upperIndex == 0) {
204             // length was probably zero
205             // return the upper point
206             return new Point2D.Float  (upper.getX(), upper.getY());
207         }
208 
209         PathSegment lower = (PathSegment) segments.elementAt(upperIndex - 1);
210 
211         // now work out where along the line would be the length
212 
213         float offset = length - lower.getLength();
214 
215         // slope
216         double theta = Math.atan2(upper.getY() - lower.getY(), upper.getX() - lower.getX());
217 
218         float xPoint = (float) (lower.getX() + offset * Math.cos(theta));
219         float yPoint = (float) (lower.getY() + offset * Math.sin(theta));
220 
221         return new Point2D.Float  (xPoint, yPoint);
222 
223     }
224 
225     public float angleAtLength(float length) {
226 
227         int upperIndex = findUpperIndex(length);
228 
229         if (upperIndex == -1) {
230             // length is off the end of the path
231             // return 0f
232             return 0f;
233         }
234 
235         PathSegment upper = (PathSegment) segments.elementAt(upperIndex);
236 
237         if (upperIndex == 0) {
238             // length was probably zero
239             // return the angle between the first and second segments
240             //return new Point2D.Float(upper.getX(), upper.getY());
241             upperIndex = 1;
242         }
243 
244         PathSegment lower = (PathSegment) segments.elementAt(upperIndex - 1);
245 
246         // slope
247         float theta = (float) Math.atan2(upper.getY() - lower.getY(), upper.getX() - lower.getX());
248 
249         return theta;
250 
251     }
252 
253     public int findUpperIndex(float length) {
254         if (!initialised)
255             initialise();
256 
257         if (length < 0)         // length is before the start of the path
258             return -1;
259         if (length > pathLength) // length is after end of path
260             return -1;
261 
262         // find the two segments that are each side of the length
263 
264         int lb = 0, ub=segments.size()-1;
265         while (lb != ub) {
266             int curr = (lb+ub)>>1;
267             PathSegment ps = (PathSegment) segments.elementAt(curr);
268             if (ps.getLength() >= length) {
269                 ub = curr;
270             } else {
271                 lb = curr+1;
272             }
273         }
274         while (true) {
275             PathSegment ps = (PathSegment) segments.elementAt(ub);
276             if (ps.getSegType() != PathIterator.SEG_MOVETO)
277                 break;
278             if (ub == segments.size()-1) break;
279             ub++;
280         }
281 
282         int upperIndex = -1;
283         int currentIndex = 0;
284         int numSegments = segments.size();;
285         while (upperIndex <= 0 && currentIndex < numSegments) {
286 
287             PathSegment ps = (PathSegment) segments.elementAt(currentIndex);
288 
289             if (ps.getLength() >= length && ps.getSegType() != PathIterator.SEG_MOVETO) {
290                 upperIndex = currentIndex;
291             }
292             currentIndex++;
293         }
294         if (ub != upperIndex) {
295             System.err.println("UB: " + ub + " UI: " + upperIndex);
296         }
297         return upperIndex;
298     }
299 
300 
301     public static void main(String   args[]) {
302 
303         GeneralPath   path;
304 
305         PathLength pl;
306 
307         path = new GeneralPath  ();
308         path.moveTo(100f, 100f);
309         path.lineTo(200f, 150f);
310         path.closePath();
311         pl = new PathLength(path);
312 
313         System.out.println("New Path Length created");
314         System.out.println("Path Length = " + pl.lengthOfPath());
315         System.out.println("Point at 0 = " + pl.pointAtLength(0f));
316         System.out.println("Point at 10 = " + pl.pointAtLength(10f));
317         System.out.println("Point at 20 = " + pl.pointAtLength(20f));
318         System.out.println("Point at 300 = " + pl.pointAtLength(300f));
319         System.out.println("Point at 3000 = " + pl.pointAtLength(3000f));
320 
321         path = new GeneralPath  ();
322         path.moveTo(100f, 100f);
323         path.lineTo(200f, 150f);
324         path.quadTo(450f, 525f, 400f, 250f);
325         path.closePath();
326         pl = new PathLength(path);
327 
328         System.out.println("Path Length = " + pl.lengthOfPath());
329         System.out.println("Point at 0 = " + pl.pointAtLength(0f));
330         System.out.println("Point at 10 = " + pl.pointAtLength(10f));
331         System.out.println("Point at 20 = " + pl.pointAtLength(20f));
332         System.out.println("Point at 300 = " + pl.pointAtLength(300f));
333 
334         path = new GeneralPath  ();
335         path.moveTo(100f, 100f);
336         path.lineTo(200f, 150f);
337         path.quadTo(450f, 525f, 400f, 250f);
338         path.lineTo(300f, 200f);
339         path.closePath();
340 
341         pl = new PathLength(path);
342         System.out.println("Path Length = " + pl.lengthOfPath());
343         System.out.println("Point at 3000 = " + pl.pointAtLength(3000f));
344         System.out.println("Point at 300 = " + pl.pointAtLength(300f));
345         System.out.println("Point at 10 = " + pl.pointAtLength(10f));
346         System.out.println("Point at 0 = " + pl.pointAtLength(0f));
347 
348     }
349 
350 
351     protected class PathSegment {
352 
353 
354         public PathSegment(int a, float b, float c, float d) {
355             setSegType(a);
356             setX(b);
357             setY(c);
358             setLength(d);
359         }
360 
361         int segType;
362 
363         /**
364          * Get the value of segType.
365          * @return Value of segType.
366          */
367 
368         public int getSegType() {
369             return segType;
370         }
371 
372         /**
373          * Set the value of segType.
374          * @param v  Value to assign to segType.
375          */
376 
377         public void setSegType(int v) {
378             this.segType = v;
379         }
380 
381         float X;
382 
383         /**
384          * Get the value of X.
385          * @return Value of X.
386          */
387 
388         public float getX() {
389             return X;
390         }
391 
392         /**
393          * Set the value of X.
394          * @param v  Value to assign to X.
395          */
396 
397         public void setX(float v) {
398             this.X = v;
399         }
400 
401         float Y;
402 
403         /**
404          * Get the value of Y.
405          * @return Value of Y.
406          */
407 
408         public float getY() {
409             return Y;
410         }
411 
412         /**
413          * Set the value of Y.
414          * @param v  Value to assign to Y.
415          */
416 
417         public void setY(float v) {
418             this.Y = v;
419         }
420 
421         float length;
422 
423         /**
424          * Get the value of Length.
425          * @return Value of Length.
426          */
427 
428         public float getLength() {
429             return length;
430         }
431 
432         /**
433          * Set the value of Length.
434          * @param v  Value to assign to Length.
435          */
436 
437         public void setLength(float v) {
438             this.length = v;
439         }
440     }
441 }
442 
443 
444
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags