View Javadoc

1   /* File CurveArray2D.java 
2    *
3    * Project : geometry
4    *
5    * ===========================================
6    * 
7    * This library is free software; you can redistribute it and/or modify it 
8    * under the terms of the GNU Lesser General Public License as published by
9    * the Free Software Foundation, either version 2.1 of the License, or (at
10   * your option) any later version.
11   *
12   * This library is distributed in the hope that it will be useful, but 
13   * WITHOUT ANY WARRANTY, without even the implied warranty of MERCHANTABILITY
14   * or FITNESS FOR A PARTICULAR PURPOSE.
15   *
16   * See the GNU Lesser General Public License for more details.
17   *
18   * You should have received a copy of the GNU Lesser General Public License
19   * along with this library. if not, write to :
20   * The Free Software Foundation, Inc., 59 Temple Place, Suite 330,
21   * Boston, MA 02111-1307, USA.
22   */
23  
24  package math.geom2d.curve;
25  
26  import java.awt.Graphics2D;
27  import java.awt.Shape;
28  import java.util.ArrayList;
29  import java.util.Collection;
30  import java.util.Iterator;
31  
32  import math.geom2d.AffineTransform2D;
33  import math.geom2d.Box2D;
34  import math.geom2d.Point2D;
35  import math.geom2d.Shape2D;
36  import math.geom2d.line.LinearShape2D;
37  
38  /**
39   * <p>
40   * A parameterized set of curves. A curve cannot be included twice in a
41   * CurveArray2D.
42   * </p>
43   * <p>
44   * The k-th curve contains points with positions between 2*k and 2*k+1. This
45   * allows to differentiate extremities of contiguous curves. The points with
46   * positions t between 2*k+1 and 2*k+2 belong to the curve k if t<2*k+1.5, or
47   * to the curve k+1 if t>2*k+1.5
48   * </p>
49   * 
50   * @author Legland
51   */
52  public class CurveArray2D<T extends Curve2D> extends CurveSet2D<T> 
53  implements Iterable<T>, Cloneable {
54  
55  //    /** The inner array of curves */
56  //    protected ArrayList<T> curves;
57  
58      // ===================================================================
59      // Constructors
60  
61      /**
62       * Empty constructor. Initializes an empty array of curves.
63       */
64      @SuppressWarnings("deprecation")
65  	public CurveArray2D() {
66      	this.curves = new ArrayList<T>();
67      }
68  
69      /**
70       * Empty constructor. Initializes an empty array of curves, 
71       * with a given size for allocating memory.
72       */
73      public CurveArray2D(int n) {
74      	this();
75      	this.curves = new ArrayList<T>(n);
76      }
77  
78      /**
79       * Constructor from an array of curves.
80       * 
81       * @param curves the array of curves in the set
82       */
83      public CurveArray2D(T[] curves) {
84      	this();
85      	this.curves = new ArrayList<T>(curves.length);
86          for (T element : curves)
87              this.addCurve(element);
88      }
89  
90      /**
91       * Constructor from a collection of curves. The curves are added to the
92       * inner collection of curves.
93       * 
94       * @param curves the collection of curves to add to the set
95       */
96      public CurveArray2D(Collection<? extends T> curves) {
97      	this();
98      	this.curves = new ArrayList<T>(curves.size());
99          this.curves.addAll(curves);
100     }
101 
102     
103     // ===================================================================
104     // static methods
105 
106 //    /**
107 //     * Static factory for creating a new CurveArray2D from a collection of
108 //     * curves.
109 //     * @since 0.8.1
110 //     */
111 //    public static <T extends Curve2D> CurveArray2D<T> create(
112 //    		Collection<T> curves) {
113 //    	return new CurveArray2D<T>(curves);
114 //    }
115 //    
116 //    /**
117 //     * Static factory for creating a new CurveArray2D from an array of
118 //     * curves.
119 //     * @since 0.8.1
120 //     */
121 //    public static <T extends Curve2D> CurveArray2D<T> create(
122 //    		T[] curves) {
123 //    	return new CurveArray2D<T>(curves);
124 //    }
125     
126     
127     // ===================================================================
128     // methods specific to CurveArray2D
129 
130     /**
131      * Converts the position on the curve set, which is comprised between 0 and
132      * 2*Nc-1 with Nc being the number of curves, to the position on the curve
133      * which contains the position. The result is comprised between the t0 and
134      * the t1 of the child curve.
135      * 
136      * @see #getGlobalPosition(int, double)
137      * @see #getCurveIndex(double)
138      * @param t the position on the curve set
139      * @return the position on the subcurve
140      */
141     @Override
142 	public double getLocalPosition(double t) {
143         int i = this.getCurveIndex(t);
144         T curve = curves.get(i);
145         double t0 = curve.getT0();
146         double t1 = curve.getT1();
147         return Curve2DUtils.fromUnitSegment(t-2*i, t0, t1);
148     }
149 
150     /**
151      * Converts a position on a curve (between t0 and t1 of the curve) to the
152      * position on the curve set (between 0 and 2*Nc-1).
153      * 
154      * @see #getLocalPosition(double)
155      * @see #getCurveIndex(double)
156      * @param i the index of the curve to consider
157      * @param t the position on the curve
158      * @return the position on the curve set, between 0 and 2*Nc-1
159      */
160     @Override
161 	public double getGlobalPosition(int i, double t) {
162         T curve = curves.get(i);
163         double t0 = curve.getT0();
164         double t1 = curve.getT1();
165         return Curve2DUtils.toUnitSegment(t, t0, t1)+i*2;
166     }
167 
168     /**
169      * Returns the index of the curve corresponding to a given position.
170      * 
171      * @param t the position on the set of curves, between 0 and twice the
172      *            number of curves minus 1
173      * @return the index of the curve which contains position t
174      */
175     @Override
176 	public int getCurveIndex(double t) {
177 
178         // check bounds
179         if (curves.size()==0)
180             return 0;
181         if (t>curves.size()*2-1)
182             return curves.size()-1;
183 
184         // curve index
185         int nc = (int) Math.floor(t);
186 
187         // check index if even-> corresponds to a curve
188         int indc = (int) Math.floor(nc/2);
189         if (indc*2==nc)
190             return indc;
191         else
192             return t-nc<.5 ? indc : indc+1;
193     }
194 
195     // ===================================================================
196     // Management of curves
197 
198     /**
199      * Adds the curve to the curve set, if it does not already belongs to the
200      * set.
201      * 
202      * @param curve the curve to add
203      */
204     @Override
205 	public void addCurve(T curve) {
206         if (!curves.contains(curve))
207             curves.add(curve);
208     }
209 
210     /**
211      * Removes the specified curve from the curve set.
212      * 
213      * @param curve the curve to remove
214      */
215     @Override
216 	public void removeCurve(T curve) {
217         curves.remove(curve);
218     }
219 
220     /**
221      * Checks if the curve set contains the given curve.
222      */
223     @Override
224 	public boolean containsCurve(Curve2D curve) {
225     	return curves.contains(curve);
226     }
227     
228     /**
229      * Clears the inner curve collection.
230      */
231     @Override
232 	public void clearCurves() {
233         curves.clear();
234     }
235 
236     /**
237      * Returns the collection of curves
238      * 
239      * @return the inner collection of curves
240      */
241     @Override
242 	public Collection<T> getCurves() {
243         return curves;
244     }
245 
246     /**
247      * Returns the inner curve corresponding to the given index.
248      * 
249      * @param index index of the curve
250      * @return the i-th inner curve
251      * @since 0.6.3
252      */
253     @Override
254 	public T getCurve(int index) {
255         return curves.get(index);
256     }
257 
258     /**
259      * Returns the child curve corresponding to a given position.
260      * 
261      * @param t the position on the set of curves, between 0 and twice the
262      *            number of curves
263      * @return the curve corresponding to the position.
264      * @since 0.6.3
265      */
266     @Override
267 	public T getChildCurve(double t) {
268         if (curves.size()==0)
269             return null;
270         return curves.get(getCurveIndex(t));
271     }
272 
273     /**
274      * Returns the first curve of the collection if it exists, null otherwise.
275      * 
276      * @return the first curve of the collection
277      */
278     @Override
279 	public T getFirstCurve() {
280         if (curves.size()==0)
281             return null;
282         return curves.get(0);
283     }
284 
285     /**
286      * Returns the last curve of the collection if it exists, null otherwise.
287      * 
288      * @return the last curve of the collection
289      */
290     @Override
291 	public T getLastCurve() {
292         if (curves.size()==0)
293             return null;
294         return curves.get(curves.size()-1);
295     }
296 
297     /**
298      * Returns the number of curves in the collection
299      * 
300      * @return the number of curves in the collection
301      */
302     @Override
303 	public int getCurveNumber() {
304         return curves.size();
305     }
306 
307     /**
308      * Returns true if the CurveSet does not contain any curve.
309      */
310     @Override
311 	public boolean isEmpty() {
312         return curves.size()==0;
313     }
314 
315     // ===================================================================
316     // methods inherited from interface Curve2D
317 
318     @Override
319 	public Collection<Point2D> getIntersections(LinearShape2D line) {
320         ArrayList<Point2D> intersect = new ArrayList<Point2D>();
321 
322         // add intersections with each curve
323         for (Curve2D curve : curves)
324             intersect.addAll(curve.getIntersections(line));
325 
326         return intersect;
327     }
328 
329     @Override
330 	public double getT0() {
331         return 0;
332     }
333 
334     @Override
335 	public double getT1() {
336         return Math.max(curves.size()*2-1, 0);
337     }
338 
339     /*
340      * (non-Javadoc)
341      * 
342      * @see math.geom2d.Curve2D#getPoint(double)
343      */
344     @Override
345 	public Point2D getPoint(double t) {
346         if (curves.size()==0)
347             return null;
348         if (t<getT0())
349             return this.getFirstCurve().getFirstPoint();
350         if (t>getT1())
351             return this.getLastCurve().getLastPoint();
352 
353         // curve index
354         int nc = (int) Math.floor(t);
355 
356         // check index if even-> corresponds to a curve
357         int indc = (int) Math.floor(nc/2);
358         if (indc*2==nc) {
359             Curve2D curve = curves.get(indc);
360             double pos = Curve2DUtils.fromUnitSegment(t-nc, 
361             		curve.getT0(), curve.getT1());
362             return curve.getPoint(pos);
363         } else {
364             // return either last point of preceding curve,
365             // or first point of next curve
366             if (t-nc<.5)
367                 return curves.get(indc).getLastPoint();
368             else
369                 return curves.get(indc+1).getFirstPoint();
370         }
371     }
372 
373     /**
374      * Get the first point of the curve.
375      * 
376      * @return the first point of the curve
377      */
378     @Override
379 	public Point2D getFirstPoint() {
380         if (curves.size()==0)
381             return null;
382         return getFirstCurve().getFirstPoint();
383     }
384 
385     /**
386      * Get the last point of the curve.
387      * 
388      * @return the last point of the curve.
389      */
390     @Override
391 	public Point2D getLastPoint() {
392         if (curves.size()==0)
393             return null;
394         return getLastCurve().getLastPoint();
395     }
396 
397     /**
398      * Computes the set of singular points as the set of singular points
399      * of each curve, plus the extremities of each curve.
400      * Each point is referenced only once.
401      */
402     @Override
403 	public Collection<Point2D> getSingularPoints() {
404     	// create array for result
405     	ArrayList<Point2D> points = new ArrayList<Point2D>();
406     	
407     	// iterate on curves composing the array
408         for (Curve2D curve : curves){
409         	// Add singular points inside curve
410             for (Point2D point : curve.getSingularPoints())
411                 if (!points.contains(point))
412                 	points.add(point);
413             
414             // add first point
415             if(!Curve2DUtils.isLeftInfinite(curve)){
416             	Point2D point = curve.getFirstPoint();
417             	if (!points.contains(point))
418                 	points.add(point);
419             }
420             
421             // add last point
422             if(!Curve2DUtils.isRightInfinite(curve)){
423             	Point2D point = curve.getLastPoint();
424             	if (!points.contains(point))
425                 	points.add(point);
426             }
427         }
428         // return the set of singular points
429         return points;
430     }
431 
432     @Override
433 	public boolean isSingular(double pos) {
434         if (Math.abs(pos-Math.round(pos))<Shape2D.ACCURACY)
435             return true;
436 
437         int nc = this.getCurveIndex(pos);
438         // int nc = (int) Math.floor(pos);
439         if (nc-Math.floor(pos/2.0)>0)
440             return true; // if is between 2
441         // curves
442 
443         Curve2D curve = curves.get(nc);
444         // double pos2 = fromUnitSegment(pos-2*nc, curve.getT0(),
445         // curve.getT1());
446         return curve.isSingular(this.getLocalPosition(pos));
447     }
448 
449     @Override
450 	public double getPosition(java.awt.geom.Point2D point) {
451         double minDist = Double.MAX_VALUE, dist = minDist;
452         double x = point.getX(), y = point.getY();
453         double pos = 0, t0, t1;
454 
455         int i = 0;
456         for (Curve2D curve : curves) {
457             dist = curve.getDistance(x, y);
458             if (dist<minDist) {
459                 minDist = dist;
460                 pos = curve.getPosition(point);
461                 // format position
462                 t0 = curve.getT0();
463                 t1 = curve.getT1();
464                 pos = Curve2DUtils.toUnitSegment(pos, t0, t1)+i*2;
465             }
466             i++;
467         }
468         return pos;
469     }
470 
471     @Override
472 	public double project(java.awt.geom.Point2D point) {
473         double minDist = Double.MAX_VALUE, dist = minDist;
474         double x = point.getX(), y = point.getY();
475         double pos = 0, t0, t1;
476 
477         int i = 0;
478         for (Curve2D curve : curves) {
479             dist = curve.getDistance(x, y);
480             if (dist<minDist) {
481                 minDist = dist;
482                 pos = curve.project(point);
483                 // format position
484                 t0 = curve.getT0();
485                 t1 = curve.getT1();
486                 pos = Curve2DUtils.toUnitSegment(pos, t0, t1)+i*2;
487             }
488             i++;
489         }
490         return pos;
491     }
492 
493     @Override
494 	public Curve2D getReverseCurve() {
495     	int n = curves.size();
496         // create array of reversed curves
497         Curve2D[] curves2 = new Curve2D[n];
498         
499         // reverse each curve
500         for (int i = 0; i<n; i++)
501             curves2[i] = curves.get(n-1-i).getReverseCurve();
502         
503         // create the reversed final curve
504         return new CurveArray2D<Curve2D>(curves2);
505     }
506 
507     /**
508      * Return an instance of CurveArray2D.
509      */
510     @Override
511 	public CurveSet2D<? extends Curve2D> getSubCurve(double t0, double t1) {
512         // number of curves in the set
513         int nc = curves.size();
514 
515         // create a new empty curve set
516         CurveArray2D<Curve2D> res = new CurveArray2D<Curve2D>();
517         Curve2D curve;
518 
519         // format to ensure t is between T0 and T1
520         t0 = Math.min(Math.max(t0, 0), nc*2-.6);
521         t1 = Math.min(Math.max(t1, 0), nc*2-.6);
522 
523         // find curves index
524         double t0f = Math.floor(t0);
525         double t1f = Math.floor(t1);
526 
527         // indices of curves supporting points
528         int ind0 = (int) Math.floor(t0f/2);
529         int ind1 = (int) Math.floor(t1f/2);
530 
531         // case of t a little bit after a curve
532         if (t0-2*ind0>1.5)
533             ind0++;
534         if (t1-2*ind1>1.5)
535             ind1++;
536 
537         // start at the beginning of a curve
538         t0f = 2*ind0;
539         t1f = 2*ind1;
540 
541         double pos0, pos1;
542 
543         // need to subdivide only one curve
544         if (ind0==ind1&&t0<t1) {
545             curve = curves.get(ind0);
546             pos0 = Curve2DUtils.fromUnitSegment(t0-t0f, 
547             		curve.getT0(), curve.getT1());
548             pos1 = Curve2DUtils.fromUnitSegment(t1-t1f, 
549             		curve.getT0(), curve.getT1());
550             res.addCurve(curve.getSubCurve(pos0, pos1));
551             return res;
552         }
553 
554         // add the end of the curve containing first cut
555         curve = curves.get(ind0);
556         pos0 = Curve2DUtils.fromUnitSegment(t0-t0f, 
557         		curve.getT0(), curve.getT1());
558         res.addCurve(curve.getSubCurve(pos0, curve.getT1()));
559 
560         if (ind1>ind0) {
561             // add all the whole curves between the 2 cuts
562             for (int n = ind0+1; n<ind1; n++)
563                 res.addCurve(curves.get(n));
564         } else {
565             // add all curves until the end of the set
566             for (int n = ind0+1; n<nc; n++)
567                 res.addCurve(curves.get(n));
568 
569             // add all curves from the beginning of the set
570             for (int n = 0; n<ind1; n++)
571                 res.addCurve(curves.get(n));
572         }
573 
574         // add the beginning of the last cut curve
575         curve = curves.get(ind1);
576         pos1 = Curve2DUtils.fromUnitSegment(t1-t1f, 
577         		curve.getT0(), curve.getT1());
578         res.addCurve(curve.getSubCurve(curve.getT0(), pos1));
579 
580         // return the curve set
581         return res;
582     }
583 
584     // ===================================================================
585     // methods inherited from interface Shape2D
586 
587     @Override
588 	public double getDistance(java.awt.geom.Point2D p) {
589         return getDistance(p.getX(), p.getY());
590     }
591 
592     @Override
593 	public double getDistance(double x, double y) {
594         double dist = Double.POSITIVE_INFINITY;
595         for (Curve2D curve : curves)
596             dist = Math.min(dist, curve.getDistance(x, y));
597         return dist;
598     }
599 
600     /**
601      * return true, if all curve pieces are bounded
602      */
603     @Override
604 	public boolean isBounded() {
605         for (Curve2D curve : curves)
606             if (!curve.isBounded())
607                 return false;
608         return true;
609     }
610 
611     /**
612      * Clips a curve, and return a CurveArray2D. If the curve is totally outside
613      * the box, return a CurveArray2D with 0 curves inside. If the curve is
614      * totally inside the box, return a CurveArray2D with only one curve, which is
615      * the original curve.
616      */
617     @Override
618 	public CurveSet2D<? extends Curve2D> clip(Box2D box) {
619     	// Simply calls the generic method in Curve2DUtils
620     	return Curve2DUtils.clipCurveSet(this, box);
621     }
622 
623     /**
624      * Returns bounding box for the CurveArray2D.
625      */
626     @Override
627 	public Box2D getBoundingBox() {
628         double xmin = Double.MAX_VALUE;
629         double ymin = Double.MAX_VALUE;
630         double xmax = Double.MIN_VALUE;
631         double ymax = Double.MIN_VALUE;
632 
633         Box2D box;
634         for (Curve2D curve : curves) {
635             box = curve.getBoundingBox();
636             xmin = Math.min(xmin, box.getMinX());
637             ymin = Math.min(ymin, box.getMinY());
638             xmax = Math.max(xmax, box.getMaxX());
639             ymax = Math.max(ymax, box.getMaxY());
640         }
641 
642         return new Box2D(xmin, xmax, ymin, ymax);
643     }
644 
645     /**
646      * Transforms each curve, and build a new CurveArray2D with the set of
647      * transformed curves.
648      */
649     @Override
650 	public CurveArray2D<? extends Curve2D> transform(AffineTransform2D trans) {
651     	// Allocate array for result
652         CurveArray2D<Curve2D> result = new CurveArray2D<Curve2D>(curves.size());
653         
654         // add each transformed curve
655         for (Curve2D curve : curves)
656             result.addCurve(curve.transform(trans));
657         return result;
658     }
659 
660     @Override
661 	public Collection<? extends ContinuousCurve2D> getContinuousCurves() {
662     	// create array for storing result
663         ArrayList<ContinuousCurve2D> continuousCurves = 
664         	new ArrayList<ContinuousCurve2D>();
665 
666         // Iterate on curves, and add either the curve itself, or the set of
667         // continuous curves making the curve
668         for (Curve2D curve : curves) {
669             if (curve instanceof ContinuousCurve2D) {
670                 continuousCurves.add((ContinuousCurve2D) curve);
671             } else {
672                 continuousCurves.addAll(curve.getContinuousCurves());
673             }
674         }
675 
676         return continuousCurves;
677     }
678 
679     // ===================================================================
680     // methods inherited from interface Shape2D
681 
682     /** Returns true if one of the curves contains the point */
683     @Override
684 	public boolean contains(java.awt.geom.Point2D p) {
685         return contains(p.getX(), p.getY());
686     }
687 
688     /** Returns true if one of the curves contains the point */
689     @Override
690 	public boolean contains(double x, double y) {
691         for (Curve2D curve : curves) {
692             if (curve.contains(x, y))
693                 return true;
694         }
695         return false;
696     }
697 
698     @Override
699 	public java.awt.geom.GeneralPath getGeneralPath() {
700         // create new path
701         java.awt.geom.GeneralPath path = new java.awt.geom.GeneralPath();
702 
703         // check case of empty curve set
704         if (curves.size()==0)
705             return path;
706 
707         // move to the first point of the first curves
708         Point2D point;
709         for (ContinuousCurve2D curve : this.getContinuousCurves()) {
710             point = curve.getFirstPoint();
711             path.moveTo((float) point.getX(), (float) point.getY());
712             path = curve.appendPath(path);
713         }
714 
715         // return the final path
716         return path;
717     }
718 
719     /* (non-Javadoc)
720      * @see math.geom2d.curve.Curve2D#getAsAWTShape()
721      */
722     @Override
723 	public Shape getAsAWTShape() {
724         return this.getGeneralPath();
725     }
726 
727     @Override
728 	public void draw(Graphics2D g2) {
729     	for(Curve2D curve : curves)
730     		curve.draw(g2);
731     }
732 
733     // ===================================================================
734     // methods inherited from interface Object
735 
736     /**
737      * Returns true if obj is a CurveArray2D with the same number of curves, and
738      * such that each curve belongs to both objects.
739      */
740     @Override
741     public boolean equals(Object obj) {
742         // check class, and cast type
743         if (!(obj instanceof CurveArray2D))
744             return false;
745         CurveArray2D<?> curveSet = (CurveArray2D<?>) obj;
746 
747         // check the number of curves in each set
748         if (this.getCurveNumber()!=curveSet.getCurveNumber())
749             return false;
750 
751         // return false if at least one couple of curves does not match
752         for(int i=0; i<curves.size(); i++)
753             if(!curves.get(i).equals(curveSet.curves.get(i)))
754                 return false;
755         
756         // otherwise return true
757         return true;
758     }
759 
760     @Override
761     public CurveArray2D<? extends Curve2D> clone() {
762         ArrayList<Curve2D> array = new ArrayList<Curve2D>(curves.size());
763         for(T curve : curves)
764             array.add(curve);
765         return new CurveArray2D<Curve2D>(array);
766     }
767     
768     // ===================================================================
769     // methods implementing the Iterable interface
770 
771    /*
772      * (non-Javadoc)
773      * 
774      * @see java.lang.Iterable#iterator()
775      */
776     @Override
777 	public Iterator<T> iterator() {
778         return curves.iterator();
779     }
780 }