Coverage Report

Coverage Report - math.geom2d.curve.Curve2DUtils

Classes in this File

0/190

0/136

 /**
  * 
  */
 
 package math.geom2d.curve;
 
 import java.util.ArrayList;
 import java.util.Iterator;
 import java.util.SortedSet;
 import java.util.TreeSet;
 
 import math.geom2d.Box2D;
 import math.geom2d.Point2D;
 import math.geom2d.Shape2D;
 import math.geom2d.Vector2D;
 import math.geom2d.line.StraightLine2D;
 import math.geom2d.line.LinearShape2D;
 
 /**
  * Collects some useful methods for clipping curves.
  * 
  * @author dlegland
  */
 public abstract class Curve2DUtils {
 
     // ===================================================================
     // static methods
 
     /**
      * Mapping of the parameter t, relative to the local curve, into the
      * interval [0 1], [0 1[, ]0 1], or ]0 1[, depending on the values of t0 and
      * t1.
      * 
      * @param t a value between t0 and t1
      * @param t0 the lower bound of parameterization domain
      * @param t1 the upper bound of parameterization domain
      * @return a value between 0 and 1
      */
     public final static double toUnitSegment(double t, double t0, double t1) {
         if (t<=t0)
             return 0;
         if (t>=t1)
             return 1;
 
         if (t0==Double.NEGATIVE_INFINITY&&t1==Double.POSITIVE_INFINITY)
             return Math.atan(t)/Math.PI+.5;
 
         if (t0==Double.NEGATIVE_INFINITY)
             return Math.atan(t-t1)*2/Math.PI+1;
 
         if (t1==Double.POSITIVE_INFINITY)
             return Math.atan(t-t0)*2/Math.PI;
 
         // t0 and t1 are both finite
         return (t-t0)/(t1-t0);
     }
 
     /**
      * Transforms the value t between 0 and 1 in a value comprised between t0
      * and t1.
      * 
      * @param t a value between 0 and 1
      * @param t0 the lower bound of parameterization domain
      * @param t1 the upper bound of parameterization domain
      * @return a value between t0 and t1
      */
     public final static double fromUnitSegment(double t, double t0, double t1) {
         if (t<=0)
             return t0;
         if (t>=1)
             return t1;
 
         if (t0==Double.NEGATIVE_INFINITY&&t1==Double.POSITIVE_INFINITY)
             return Math.tan((t-.5)*Math.PI);
 
         if (t0==Double.NEGATIVE_INFINITY)
             return Math.tan((t-1)*Math.PI/2)+t1;
 
         if (t1==Double.POSITIVE_INFINITY)
             return Math.tan(t*Math.PI/2)+t0;
 
         // t0 and t1 are both finite
         return t*(t1-t0)+t0;
     }
 
     /**
      * Clip a curve, and return a CurveSet2D. If the curve is totally outside
      * the box, return a CurveSet2D with 0 curves inside. If the curve is
      * totally inside the box, return a CurveSet2D with only one curve, which is
      * the original curve.
      */
     public final static CurveSet2D<? extends Curve2D>
     clipCurve(Curve2D curve, Box2D box) {
         // Case of continuous curve:
         // convert the result of ClipContinuousCurve to CurveSet of Curve2D
         if (curve instanceof ContinuousCurve2D)
             return new CurveArray2D<Curve2D>(Curve2DUtils.clipContinuousCurve(
                     (ContinuousCurve2D) curve, box).getCurves());
 
         // case of a CurveSet2D
         if (curve instanceof CurveSet2D)
             return Curve2DUtils.clipCurveSet((CurveSet2D<?>) curve, box);
 
         // Unknown case
         System.err.println("Unknown curve class in Box2D.clipCurve()");
         return new CurveArray2D<Curve2D>();
     }
 
     /**
      * clip a CurveSet2D.
      */
     public final static CurveSet2D<? extends Curve2D> clipCurveSet(
             CurveSet2D<?> curveSet, Box2D box) {
         // Clip the current curve
             CurveArray2D<Curve2D> result = new CurveArray2D<Curve2D>();
         CurveSet2D<?> clipped;
 
         // a clipped parts of current curve to the result
         for (Curve2D curve : curveSet) {
             clipped = Curve2DUtils.clipCurve(curve, box);
             for (Curve2D clippedPart : clipped)
                 result.addCurve(clippedPart);
         }
 
         // return a set of curves
         return result;
     }
 
     /**
      * <p>
      * Clips a continuous curve and returns a set of continuous curves.
      * </p>
      * <p>
      * Algorithm is the following one:
      * <ul>
      * <li>Compute intersections between curve and box boundary</li>
      * <li>Sort intersections according to their position on the curve</li>
      * <li>Remove intersections which do not cross (they only touch) the box
      * boundary </li>
      * <li>Add portions of curves located between two intersections and inside
      * of the box</li>
      * </ul>
      * </p>
      * <p>
      * Special processing is added when the first point of the curve lies on the
      * boundary of the box, and when the curve is closed (when the first point
      * of the curve is inside the box, the method return a portion of curve
      * between the last intersection and the first intersection).
      * </p>
      */
     public final static CurveSet2D<ContinuousCurve2D> clipContinuousCurve(
             ContinuousCurve2D curve, Box2D box) {
 
         // Create CurveSet2D for storing the result
             CurveArray2D<ContinuousCurve2D> res = 
                     new CurveArray2D<ContinuousCurve2D>();
 
         // ------ Compute ordered list of intersections
 
         // create array of intersection points
         ArrayList<Point2D> points = new ArrayList<Point2D>();
 
         // add all the intersections with edges of the box boundary
         for (LinearShape2D edge : box.getEdges())
             points.addAll(curve.getIntersections(edge));
 
         // convert list to point array, sorted wrt to their position on the
         // curve
         SortedSet<Double> set = new TreeSet<Double>();
         for (Point2D p : points)
             set.add(new Double(curve.getPosition(p)));
 
         // iterator on the intersection positions
         Iterator<Double> iter = set.iterator();
 
         // ----- remove intersections which do not cross the boundary
 
         // init arrays
         int nInter = set.size();
         double[] positions = new double[nInter+2];
         double[] between = new double[nInter+1];
 
         // fill up array of positions, with extreme positions of curve
         positions[0] = curve.getT0();
         for (int i = 0; i<nInter; i++)
             positions[i+1] = iter.next();
         positions[nInter+1] = curve.getT1();
 
         // compute positions of points between intersections
         for (int i = 0; i<nInter+1; i++)
             between[i] = choosePosition(positions[i], positions[i+1]);
 
         // array of positions to remove
         ArrayList<Double> toRemove = new ArrayList<Double>();
 
         // remove an intersection point if the curve portions before and after
         // are both either inside or outside of the box.
         for (int i = 0; i<nInter; i++) {
             Point2D p1 = curve.getPoint(between[i]);
             Point2D p2 = curve.getPoint(between[i+1]);
             boolean b1 = box.contains(p1);
             boolean b2 = box.contains(p2);
             if (b1==b2)
                 toRemove.add(positions[i+1]);
         }
 
         // remove unnecessary intersections
         set.removeAll(toRemove);
 
         // iterator on the intersection positions
         iter = set.iterator();
 
         // ----- Check case of no intersection point
 
         // if no intersection point, the curve is totally either inside or
         // outside the box
         if (set.size()==0) {
             // compute position of an arbitrary point on the curve
             Point2D point;
             if (curve.isBounded()) {
                 point = curve.getFirstPoint();
             } else {
                 double pos = choosePosition(curve.getT0(), curve.getT1());
                 point = curve.getPoint(pos);
             }
 
             // if the box contains a point, it contains the whole curve
             if (box.contains(point))
                 res.addCurve(curve);
             return res;
         }
 
         // ----- Check if the curve starts inside of the box
 
         // the flag for a curve that starts inside the box
         boolean inside = false;
         boolean touch = false;
 
         // different behavior if curve is bounded or not
         double t0 = curve.getT0();
         if (isLeftInfinite(curve)) {
             // choose point between -infinite and first intersection
             double pos = choosePosition(t0, set.iterator().next());
             inside = box.contains(curve.getPoint(pos));
         } else {
             // extract first point of the curve
             Point2D point = curve.getFirstPoint();
             inside = box.contains(point);
 
             // if first point is on the boundary, then choose another point
             // located between first point and first intersection
             if (box.getBoundary().contains(point)) {
                 touch = true;
 
                 double pos = choosePosition(t0, iter.next());
                 while (Math.abs(pos-t0)<Shape2D.ACCURACY&&iter.hasNext())
                     pos = choosePosition(t0, iter.next());
                 if (Math.abs(pos-t0)<Shape2D.ACCURACY)
                     pos = choosePosition(t0, curve.getT1());
                 point = curve.getPoint(pos);
 
                 // remove the first point from the list of intersections
                 set.remove(t0);
 
                 // if inside, adds the first portion of the curve,
                 // and remove next intersection
                 if (box.contains(point)) {
                     pos = set.iterator().next();
                     res.addCurve((ContinuousCurve2D)curve.getSubCurve(t0, pos));
                     set.remove(pos);
                 }
 
                 // update iterator
                 iter = set.iterator();
 
                 inside = false;
             }
         }
 
         // different behavior depending if first point lies inside the box
         double pos0 = Double.NaN;
         if (inside&&!touch)
             if (curve.isClosed())
                 pos0 = iter.next();
             else
                 res.addCurve((ContinuousCurve2D)curve.getSubCurve(curve.getT0(), iter.next()));
 
         // ----- add portions of curve between each couple of intersections
 
         double pos1, pos2;
         while (iter.hasNext()) {
             pos1 = iter.next().doubleValue();
             if (iter.hasNext())
                 pos2 = iter.next().doubleValue();
             else
                 pos2 = curve.isClosed()&&!touch ? pos0 : curve.getT1();
             res.addCurve((ContinuousCurve2D)curve.getSubCurve(pos1, pos2));
         }
 
         return res;
     }
 
     /**
      * Clip a continuous smooth curve. Currently just call the static method
      * clipContinuousCurve, and cast clipped curves.
      */
     public final static CurveSet2D<SmoothCurve2D> clipSmoothCurve(
             SmoothCurve2D curve, Box2D box) {
             CurveArray2D<SmoothCurve2D> result = new CurveArray2D<SmoothCurve2D>();
         for (ContinuousCurve2D cont : Curve2DUtils.clipContinuousCurve(curve,
                 box))
             if (cont instanceof SmoothCurve2D)
                 result.addCurve((SmoothCurve2D) cont);
 
         return result;
     }
 
     /**
      * Clip a continuous smooth curve by the half-plane defined by a line. This
      * method is mainly used to help debugging when implementing curves.
      */
     public final static CurveSet2D<SmoothCurve2D> clipSmoothCurve(
             SmoothCurve2D curve, StraightLine2D line) {
 
         // get the list of intersections with the line
         ArrayList<Point2D> list = new ArrayList<Point2D>();
         list.addAll(curve.getIntersections(line));
 
         // convert list to point array, sorted with respect to their position
         // on the curve, but do not add tangent points with curvature greater
         // than 0
         SortedSet<java.lang.Double> set = new TreeSet<java.lang.Double>();
         double position;
         Vector2D vector = line.getVector();
         for (Point2D point : list) {
             // get position of intersection on the curve (use project to avoid
             // round-off problems)
             position = curve.project(point);
 
             // Condition of colinearity with direction vector of line
             Vector2D tangent = curve.getTangent(position);
             if (Vector2D.isColinear(tangent, vector)) {
                 // condition on the curvature (close to zero = cusp point)
                 double curv = curve.getCurvature(position);
                 if (Math.abs(curv)>Shape2D.ACCURACY)
                     continue;
             }
             set.add(new java.lang.Double(position));
         }
 
         // Create CurveSet2D for storing the result
         CurveArray2D<SmoothCurve2D> res = new CurveArray2D<SmoothCurve2D>();
 
         // extract first point of the curve, or a point arbitrarily far
         Point2D point1;
         if (Double.isInfinite(curve.getT0()))
             point1 = curve.getPoint(-1000);
         else
             point1 = curve.getFirstPoint();
 
         // Extract first valid intersection point, if it exists
         double pos1, pos2;
         Iterator<java.lang.Double> iter = set.iterator();
 
         // if no intersection point, the curve is either totally inside
         // or totally outside the box
         if (!iter.hasNext()) {
             // Find a point on the curve and not on the line
             // First tries with first point
             double t0 = curve.getT0();
             if (t0==Double.NEGATIVE_INFINITY)
                 t0 = -100;
             while (line.contains(point1)) {
                 double t1 = curve.getT1();
                 if (t1==Double.POSITIVE_INFINITY)
                     t1 = +100;
                 t0 = (t0+t1)/2;
                 point1 = curve.getPoint(t0);
             }
             if (line.getSignedDistance(point1)<0)
                 res.addCurve(curve);
             return res;
         }
 
         // different behavior depending if first point lies inside the box
         if (line.getSignedDistance(point1)<0&&!line.contains(point1)) {
             pos1 = iter.next().doubleValue();
             res.addCurve((SmoothCurve2D)curve.getSubCurve(curve.getT0(), pos1));
         }
 
         // add the portions of curve between couples of intersections
         while (iter.hasNext()) {
             pos1 = iter.next().doubleValue();
             if (iter.hasNext())
                 pos2 = iter.next().doubleValue();
             else
                 pos2 = curve.getT1();
             res.addCurve((SmoothCurve2D)curve.getSubCurve(pos1, pos2));
         }
 
         return res;
     }
 
     public final static int findNextCurveIndex(double[] positions, double pos) {
         int ind = -1;
         double posMin = java.lang.Double.MAX_VALUE;
         for (int i = 0; i<positions.length; i++) {
             // avoid NaN
             if (java.lang.Double.isNaN(positions[i]))
                 continue;
             // avoid values before
             if (positions[i]-pos<Shape2D.ACCURACY)
                 continue;
 
             // test if closer that other points
             if (positions[i]<posMin) {
                 ind = i;
                 posMin = positions[i];
             }
         }
 
         if (ind!=-1)
             return ind;
 
         // if not found, return index of smallest value (mean that pos is last
         // point on the boundary, so we need to start at the beginning).
         for (int i = 0; i<positions.length; i++) {
             if (java.lang.Double.isNaN(positions[i]))
                 continue;
             if (positions[i]-posMin<Shape2D.ACCURACY) {
                 ind = i;
                 posMin = positions[i];
             }
         }
         return ind;
     }
 
     /**
      * Choose an arbitrary position between positions t0 and t1, which can be
      * infinite.
      * 
      * @param t0 the first bound of a curve parameterization
      * @param t1 the second bound of a curve parameterization
      * @return a position located between t0 and t1
      */
     public final static double choosePosition(double t0, double t1) {
         if (Double.isInfinite(t0)) {
             if (Double.isInfinite(t1))
                 return 0;
             return t1-10;
         }
 
         if (Double.isInfinite(t1))
             return t0+10;
 
         return (t0+t1)/2;
     }
     
         public final static boolean isLeftInfinite(Curve2D curve) {
                 // basic check
                 if(curve.isBounded()) return false;
                 
                 // extract the first smooth curve
                 ContinuousCurve2D cont = curve.getContinuousCurves().iterator().next();
                 SmoothCurve2D smooth = cont.getSmoothPieces().iterator().next();
                 
                 // check first position of first curve
                 return Double.isInfinite(smooth.getT0());
         }
         
         public final static boolean isRightInfinite(Curve2D curve) {
                 // basic check
                 if(curve.isBounded()) return false;
                 
                 // extract the first smooth curve
                 SmoothCurve2D lastCurve = null;
                 for(ContinuousCurve2D cont : curve.getContinuousCurves())
                         for(SmoothCurve2D smooth : cont.getSmoothPieces())
                                 lastCurve = smooth;
                 
                 // check last position of last curve
                 return Double.isInfinite(lastCurve.getT1());
         }    
 }

1		/**
2		*
3		*/
4
5		package math.geom2d.curve;
6
7		import java.util.ArrayList;
8		import java.util.Iterator;
9		import java.util.SortedSet;
10		import java.util.TreeSet;
11
12		import math.geom2d.Box2D;
13		import math.geom2d.Point2D;
14		import math.geom2d.Shape2D;
15		import math.geom2d.Vector2D;
16		import math.geom2d.line.StraightLine2D;
17		import math.geom2d.line.LinearShape2D;
18
19		/**
20		* Collects some useful methods for clipping curves.
21		*
22		* @author dlegland
23		*/
24	0	public abstract class Curve2DUtils {
25
26		// ===================================================================
27		// static methods
28
29		/**
30		* Mapping of the parameter t, relative to the local curve, into the
31		* interval [0 1], [0 1[, ]0 1], or ]0 1[, depending on the values of t0 and
32		* t1.
33		*
34		* @param t a value between t0 and t1
35		* @param t0 the lower bound of parameterization domain
36		* @param t1 the upper bound of parameterization domain
37		* @return a value between 0 and 1
38		*/
39		public final static double toUnitSegment(double t, double t0, double t1) {
40	0	if (t<=t0)
41	0	return 0;
42	0	if (t>=t1)
43	0	return 1;
44
45	0	if (t0==Double.NEGATIVE_INFINITY&&t1==Double.POSITIVE_INFINITY)
46	0	return Math.atan(t)/Math.PI+.5;
47
48	0	if (t0==Double.NEGATIVE_INFINITY)
49	0	return Math.atan(t-t1)*2/Math.PI+1;
50
51	0	if (t1==Double.POSITIVE_INFINITY)
52	0	return Math.atan(t-t0)*2/Math.PI;
53
54		// t0 and t1 are both finite
55	0	return (t-t0)/(t1-t0);
56		}
57
58		/**
59		* Transforms the value t between 0 and 1 in a value comprised between t0
60		* and t1.
61		*
62		* @param t a value between 0 and 1
63		* @param t0 the lower bound of parameterization domain
64		* @param t1 the upper bound of parameterization domain
65		* @return a value between t0 and t1
66		*/
67		public final static double fromUnitSegment(double t, double t0, double t1) {
68	0	if (t<=0)
69	0	return t0;
70	0	if (t>=1)
71	0	return t1;
72
73	0	if (t0==Double.NEGATIVE_INFINITY&&t1==Double.POSITIVE_INFINITY)
74	0	return Math.tan((t-.5)*Math.PI);
75
76	0	if (t0==Double.NEGATIVE_INFINITY)
77	0	return Math.tan((t-1)*Math.PI/2)+t1;
78
79	0	if (t1==Double.POSITIVE_INFINITY)
80	0	return Math.tan(t*Math.PI/2)+t0;
81
82		// t0 and t1 are both finite
83	0	return t*(t1-t0)+t0;
84		}
85
86		/**
87		* Clip a curve, and return a CurveSet2D. If the curve is totally outside
88		* the box, return a CurveSet2D with 0 curves inside. If the curve is
89		* totally inside the box, return a CurveSet2D with only one curve, which is
90		* the original curve.
91		*/
92		public final static CurveSet2D<? extends Curve2D>
93		clipCurve(Curve2D curve, Box2D box) {
94		// Case of continuous curve:
95		// convert the result of ClipContinuousCurve to CurveSet of Curve2D
96	0	if (curve instanceof ContinuousCurve2D)
97	0	return new CurveArray2D<Curve2D>(Curve2DUtils.clipContinuousCurve(
98		(ContinuousCurve2D) curve, box).getCurves());
99
100		// case of a CurveSet2D
101	0	if (curve instanceof CurveSet2D)
102	0	return Curve2DUtils.clipCurveSet((CurveSet2D<?>) curve, box);
103
104		// Unknown case
105	0	System.err.println("Unknown curve class in Box2D.clipCurve()");
106	0	return new CurveArray2D<Curve2D>();
107		}
108
109		/**
110		* clip a CurveSet2D.
111		*/
112		public final static CurveSet2D<? extends Curve2D> clipCurveSet(
113		CurveSet2D<?> curveSet, Box2D box) {
114		// Clip the current curve
115	0	CurveArray2D<Curve2D> result = new CurveArray2D<Curve2D>();
116		CurveSet2D<?> clipped;
117
118		// a clipped parts of current curve to the result
119	0	for (Curve2D curve : curveSet) {
120	0	clipped = Curve2DUtils.clipCurve(curve, box);
121	0	for (Curve2D clippedPart : clipped)
122	0	result.addCurve(clippedPart);
123	0	}
124
125		// return a set of curves
126	0	return result;
127		}
128
129		/**
130		* <p>
131		* Clips a continuous curve and returns a set of continuous curves.
132		* </p>
133		* <p>
134		* Algorithm is the following one:
135		* <ul>
136		* <li>Compute intersections between curve and box boundary</li>
137		* <li>Sort intersections according to their position on the curve</li>
138		* <li>Remove intersections which do not cross (they only touch) the box
139		* boundary </li>
140		* <li>Add portions of curves located between two intersections and inside
141		* of the box</li>
142		* </ul>
143		* </p>
144		* <p>
145		* Special processing is added when the first point of the curve lies on the
146		* boundary of the box, and when the curve is closed (when the first point
147		* of the curve is inside the box, the method return a portion of curve
148		* between the last intersection and the first intersection).
149		* </p>
150		*/
151		public final static CurveSet2D<ContinuousCurve2D> clipContinuousCurve(
152		ContinuousCurve2D curve, Box2D box) {
153
154		// Create CurveSet2D for storing the result
155	0	CurveArray2D<ContinuousCurve2D> res =
156		new CurveArray2D<ContinuousCurve2D>();
157
158		// ------ Compute ordered list of intersections
159
160		// create array of intersection points
161	0	ArrayList<Point2D> points = new ArrayList<Point2D>();
162
163		// add all the intersections with edges of the box boundary
164	0	for (LinearShape2D edge : box.getEdges())
165	0	points.addAll(curve.getIntersections(edge));
166
167		// convert list to point array, sorted wrt to their position on the
168		// curve
169	0	SortedSet<Double> set = new TreeSet<Double>();
170	0	for (Point2D p : points)
171	0	set.add(new Double(curve.getPosition(p)));
172
173		// iterator on the intersection positions
174	0	Iterator<Double> iter = set.iterator();
175
176		// ----- remove intersections which do not cross the boundary
177
178		// init arrays
179	0	int nInter = set.size();
180	0	double[] positions = new double[nInter+2];
181	0	double[] between = new double[nInter+1];
182
183		// fill up array of positions, with extreme positions of curve
184	0	positions[0] = curve.getT0();
185	0	for (int i = 0; i<nInter; i++)
186	0	positions[i+1] = iter.next();
187	0	positions[nInter+1] = curve.getT1();
188
189		// compute positions of points between intersections
190	0	for (int i = 0; i<nInter+1; i++)
191	0	between[i] = choosePosition(positions[i], positions[i+1]);
192
193		// array of positions to remove
194	0	ArrayList<Double> toRemove = new ArrayList<Double>();
195
196		// remove an intersection point if the curve portions before and after
197		// are both either inside or outside of the box.
198	0	for (int i = 0; i<nInter; i++) {
199	0	Point2D p1 = curve.getPoint(between[i]);
200	0	Point2D p2 = curve.getPoint(between[i+1]);
201	0	boolean b1 = box.contains(p1);
202	0	boolean b2 = box.contains(p2);
203	0	if (b1==b2)
204	0	toRemove.add(positions[i+1]);
205		}
206
207		// remove unnecessary intersections
208	0	set.removeAll(toRemove);
209
210		// iterator on the intersection positions
211	0	iter = set.iterator();
212
213		// ----- Check case of no intersection point
214
215		// if no intersection point, the curve is totally either inside or
216		// outside the box
217	0	if (set.size()==0) {
218		// compute position of an arbitrary point on the curve
219		Point2D point;
220	0	if (curve.isBounded()) {
221	0	point = curve.getFirstPoint();
222		} else {
223	0	double pos = choosePosition(curve.getT0(), curve.getT1());
224	0	point = curve.getPoint(pos);
225		}
226
227		// if the box contains a point, it contains the whole curve
228	0	if (box.contains(point))
229	0	res.addCurve(curve);
230	0	return res;
231		}
232
233		// ----- Check if the curve starts inside of the box
234
235		// the flag for a curve that starts inside the box
236	0	boolean inside = false;
237	0	boolean touch = false;
238
239		// different behavior if curve is bounded or not
240	0	double t0 = curve.getT0();
241	0	if (isLeftInfinite(curve)) {
242		// choose point between -infinite and first intersection
243	0	double pos = choosePosition(t0, set.iterator().next());
244	0	inside = box.contains(curve.getPoint(pos));
245	0	} else {
246		// extract first point of the curve
247	0	Point2D point = curve.getFirstPoint();
248	0	inside = box.contains(point);
249
250		// if first point is on the boundary, then choose another point
251		// located between first point and first intersection
252	0	if (box.getBoundary().contains(point)) {
253	0	touch = true;
254
255	0	double pos = choosePosition(t0, iter.next());
256	0	while (Math.abs(pos-t0)<Shape2D.ACCURACY&&iter.hasNext())
257	0	pos = choosePosition(t0, iter.next());
258	0	if (Math.abs(pos-t0)<Shape2D.ACCURACY)
259	0	pos = choosePosition(t0, curve.getT1());
260	0	point = curve.getPoint(pos);
261
262		// remove the first point from the list of intersections
263	0	set.remove(t0);
264
265		// if inside, adds the first portion of the curve,
266		// and remove next intersection
267	0	if (box.contains(point)) {
268	0	pos = set.iterator().next();
269	0	res.addCurve((ContinuousCurve2D)curve.getSubCurve(t0, pos));
270	0	set.remove(pos);
271		}
272
273		// update iterator
274	0	iter = set.iterator();
275
276	0	inside = false;
277		}
278		}
279
280		// different behavior depending if first point lies inside the box
281	0	double pos0 = Double.NaN;
282	0	if (inside&&!touch)
283	0	if (curve.isClosed())
284	0	pos0 = iter.next();
285		else
286	0	res.addCurve((ContinuousCurve2D)curve.getSubCurve(curve.getT0(), iter.next()));
287
288		// ----- add portions of curve between each couple of intersections
289
290		double pos1, pos2;
291	0	while (iter.hasNext()) {
292	0	pos1 = iter.next().doubleValue();
293	0	if (iter.hasNext())
294	0	pos2 = iter.next().doubleValue();
295		else
296	0	pos2 = curve.isClosed()&&!touch ? pos0 : curve.getT1();
297	0	res.addCurve((ContinuousCurve2D)curve.getSubCurve(pos1, pos2));
298		}
299
300	0	return res;
301		}
302
303		/**
304		* Clip a continuous smooth curve. Currently just call the static method
305		* clipContinuousCurve, and cast clipped curves.
306		*/
307		public final static CurveSet2D<SmoothCurve2D> clipSmoothCurve(
308		SmoothCurve2D curve, Box2D box) {
309	0	CurveArray2D<SmoothCurve2D> result = new CurveArray2D<SmoothCurve2D>();
310	0	for (ContinuousCurve2D cont : Curve2DUtils.clipContinuousCurve(curve,
311		box))
312	0	if (cont instanceof SmoothCurve2D)
313	0	result.addCurve((SmoothCurve2D) cont);
314
315	0	return result;
316		}
317
318		/**
319		* Clip a continuous smooth curve by the half-plane defined by a line. This
320		* method is mainly used to help debugging when implementing curves.
321		*/
322		public final static CurveSet2D<SmoothCurve2D> clipSmoothCurve(
323		SmoothCurve2D curve, StraightLine2D line) {
324
325		// get the list of intersections with the line
326	0	ArrayList<Point2D> list = new ArrayList<Point2D>();
327	0	list.addAll(curve.getIntersections(line));
328
329		// convert list to point array, sorted with respect to their position
330		// on the curve, but do not add tangent points with curvature greater
331		// than 0
332	0	SortedSet<java.lang.Double> set = new TreeSet<java.lang.Double>();
333		double position;
334	0	Vector2D vector = line.getVector();
335	0	for (Point2D point : list) {
336		// get position of intersection on the curve (use project to avoid
337		// round-off problems)
338	0	position = curve.project(point);
339
340		// Condition of colinearity with direction vector of line
341	0	Vector2D tangent = curve.getTangent(position);
342	0	if (Vector2D.isColinear(tangent, vector)) {
343		// condition on the curvature (close to zero = cusp point)
344	0	double curv = curve.getCurvature(position);
345	0	if (Math.abs(curv)>Shape2D.ACCURACY)
346	0	continue;
347		}
348	0	set.add(new java.lang.Double(position));
349	0	}
350
351		// Create CurveSet2D for storing the result
352	0	CurveArray2D<SmoothCurve2D> res = new CurveArray2D<SmoothCurve2D>();
353
354		// extract first point of the curve, or a point arbitrarily far
355		Point2D point1;
356	0	if (Double.isInfinite(curve.getT0()))
357	0	point1 = curve.getPoint(-1000);
358		else
359	0	point1 = curve.getFirstPoint();
360
361		// Extract first valid intersection point, if it exists
362		double pos1, pos2;
363	0	Iterator<java.lang.Double> iter = set.iterator();
364
365		// if no intersection point, the curve is either totally inside
366		// or totally outside the box
367	0	if (!iter.hasNext()) {
368		// Find a point on the curve and not on the line
369		// First tries with first point
370	0	double t0 = curve.getT0();
371	0	if (t0==Double.NEGATIVE_INFINITY)
372	0	t0 = -100;
373	0	while (line.contains(point1)) {
374	0	double t1 = curve.getT1();
375	0	if (t1==Double.POSITIVE_INFINITY)
376	0	t1 = +100;
377	0	t0 = (t0+t1)/2;
378	0	point1 = curve.getPoint(t0);
379	0	}
380	0	if (line.getSignedDistance(point1)<0)
381	0	res.addCurve(curve);
382	0	return res;
383		}
384
385		// different behavior depending if first point lies inside the box
386	0	if (line.getSignedDistance(point1)<0&&!line.contains(point1)) {
387	0	pos1 = iter.next().doubleValue();
388	0	res.addCurve((SmoothCurve2D)curve.getSubCurve(curve.getT0(), pos1));
389		}
390
391		// add the portions of curve between couples of intersections
392	0	while (iter.hasNext()) {
393	0	pos1 = iter.next().doubleValue();
394	0	if (iter.hasNext())
395	0	pos2 = iter.next().doubleValue();
396		else
397	0	pos2 = curve.getT1();
398	0	res.addCurve((SmoothCurve2D)curve.getSubCurve(pos1, pos2));
399		}
400
401	0	return res;
402		}
403
404		public final static int findNextCurveIndex(double[] positions, double pos) {
405	0	int ind = -1;
406	0	double posMin = java.lang.Double.MAX_VALUE;
407	0	for (int i = 0; i<positions.length; i++) {
408		// avoid NaN
409	0	if (java.lang.Double.isNaN(positions[i]))
410	0	continue;
411		// avoid values before
412	0	if (positions[i]-pos<Shape2D.ACCURACY)
413	0	continue;
414
415		// test if closer that other points
416	0	if (positions[i]<posMin) {
417	0	ind = i;
418	0	posMin = positions[i];
419		}
420		}
421
422	0	if (ind!=-1)
423	0	return ind;
424
425		// if not found, return index of smallest value (mean that pos is last
426		// point on the boundary, so we need to start at the beginning).
427	0	for (int i = 0; i<positions.length; i++) {
428	0	if (java.lang.Double.isNaN(positions[i]))
429	0	continue;
430	0	if (positions[i]-posMin<Shape2D.ACCURACY) {
431	0	ind = i;
432	0	posMin = positions[i];
433		}
434		}
435	0	return ind;
436		}
437
438		/**
439		* Choose an arbitrary position between positions t0 and t1, which can be
440		* infinite.
441		*
442		* @param t0 the first bound of a curve parameterization
443		* @param t1 the second bound of a curve parameterization
444		* @return a position located between t0 and t1
445		*/
446		public final static double choosePosition(double t0, double t1) {
447	0	if (Double.isInfinite(t0)) {
448	0	if (Double.isInfinite(t1))
449	0	return 0;
450	0	return t1-10;
451		}
452
453	0	if (Double.isInfinite(t1))
454	0	return t0+10;
455
456	0	return (t0+t1)/2;
457		}
458
459		public final static boolean isLeftInfinite(Curve2D curve) {
460		// basic check
461	0	if(curve.isBounded()) return false;
462
463		// extract the first smooth curve
464	0	ContinuousCurve2D cont = curve.getContinuousCurves().iterator().next();
465	0	SmoothCurve2D smooth = cont.getSmoothPieces().iterator().next();
466
467		// check first position of first curve
468	0	return Double.isInfinite(smooth.getT0());
469		}
470
471		public final static boolean isRightInfinite(Curve2D curve) {
472		// basic check
473	0	if(curve.isBounded()) return false;
474
475		// extract the first smooth curve
476	0	SmoothCurve2D lastCurve = null;
477	0	for(ContinuousCurve2D cont : curve.getContinuousCurves())
478	0	for(SmoothCurve2D smooth : cont.getSmoothPieces())
479	0	lastCurve = smooth;
480
481		// check last position of last curve
482	0	return Double.isInfinite(lastCurve.getT1());
483		}
484		}