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