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 }