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 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 if (t<=t0)
41 return 0;
42 if (t>=t1)
43 return 1;
44
45 if (t0==Double.NEGATIVE_INFINITY&&t1==Double.POSITIVE_INFINITY)
46 return Math.atan(t)/Math.PI+.5;
47
48 if (t0==Double.NEGATIVE_INFINITY)
49 return Math.atan(t-t1)*2/Math.PI+1;
50
51 if (t1==Double.POSITIVE_INFINITY)
52 return Math.atan(t-t0)*2/Math.PI;
53
54 // t0 and t1 are both finite
55 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 if (t<=0)
69 return t0;
70 if (t>=1)
71 return t1;
72
73 if (t0==Double.NEGATIVE_INFINITY&&t1==Double.POSITIVE_INFINITY)
74 return Math.tan((t-.5)*Math.PI);
75
76 if (t0==Double.NEGATIVE_INFINITY)
77 return Math.tan((t-1)*Math.PI/2)+t1;
78
79 if (t1==Double.POSITIVE_INFINITY)
80 return Math.tan(t*Math.PI/2)+t0;
81
82 // t0 and t1 are both finite
83 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 if (curve instanceof ContinuousCurve2D)
97 return new CurveArray2D<Curve2D>(Curve2DUtils.clipContinuousCurve(
98 (ContinuousCurve2D) curve, box).getCurves());
99
100 // case of a CurveSet2D
101 if (curve instanceof CurveSet2D)
102 return Curve2DUtils.clipCurveSet((CurveSet2D<?>) curve, box);
103
104 // Unknown case
105 System.err.println("Unknown curve class in Box2D.clipCurve()");
106 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 CurveArray2D<Curve2D> result = new CurveArray2D<Curve2D>();
116 CurveSet2D<?> clipped;
117
118 // a clipped parts of current curve to the result
119 for (Curve2D curve : curveSet) {
120 clipped = Curve2DUtils.clipCurve(curve, box);
121 for (Curve2D clippedPart : clipped)
122 result.addCurve(clippedPart);
123 }
124
125 // return a set of curves
126 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 CurveArray2D<ContinuousCurve2D> res =
156 new CurveArray2D<ContinuousCurve2D>();
157
158 // ------ Compute ordered list of intersections
159
160 // create array of intersection points
161 ArrayList<Point2D> points = new ArrayList<Point2D>();
162
163 // add all the intersections with edges of the box boundary
164 for (LinearShape2D edge : box.getEdges())
165 points.addAll(curve.getIntersections(edge));
166
167 // convert list to point array, sorted wrt to their position on the
168 // curve
169 SortedSet<Double> set = new TreeSet<Double>();
170 for (Point2D p : points)
171 set.add(new Double(curve.getPosition(p)));
172
173 // iterator on the intersection positions
174 Iterator<Double> iter = set.iterator();
175
176 // ----- remove intersections which do not cross the boundary
177
178 // init arrays
179 int nInter = set.size();
180 double[] positions = new double[nInter+2];
181 double[] between = new double[nInter+1];
182
183 // fill up array of positions, with extreme positions of curve
184 positions[0] = curve.getT0();
185 for (int i = 0; i<nInter; i++)
186 positions[i+1] = iter.next();
187 positions[nInter+1] = curve.getT1();
188
189 // compute positions of points between intersections
190 for (int i = 0; i<nInter+1; i++)
191 between[i] = choosePosition(positions[i], positions[i+1]);
192
193 // array of positions to remove
194 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 for (int i = 0; i<nInter; i++) {
199 Point2D p1 = curve.getPoint(between[i]);
200 Point2D p2 = curve.getPoint(between[i+1]);
201 boolean b1 = box.contains(p1);
202 boolean b2 = box.contains(p2);
203 if (b1==b2)
204 toRemove.add(positions[i+1]);
205 }
206
207 // remove unnecessary intersections
208 set.removeAll(toRemove);
209
210 // iterator on the intersection positions
211 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 if (set.size()==0) {
218 // compute position of an arbitrary point on the curve
219 Point2D point;
220 if (curve.isBounded()) {
221 point = curve.getFirstPoint();
222 } else {
223 double pos = choosePosition(curve.getT0(), curve.getT1());
224 point = curve.getPoint(pos);
225 }
226
227 // if the box contains a point, it contains the whole curve
228 if (box.contains(point))
229 res.addCurve(curve);
230 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 boolean inside = false;
237 boolean touch = false;
238
239 // different behavior if curve is bounded or not
240 double t0 = curve.getT0();
241 if (isLeftInfinite(curve)) {
242 // choose point between -infinite and first intersection
243 double pos = choosePosition(t0, set.iterator().next());
244 inside = box.contains(curve.getPoint(pos));
245 } else {
246 // extract first point of the curve
247 Point2D point = curve.getFirstPoint();
248 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 if (box.getBoundary().contains(point)) {
253 touch = true;
254
255 double pos = choosePosition(t0, iter.next());
256 while (Math.abs(pos-t0)<Shape2D.ACCURACY&&iter.hasNext())
257 pos = choosePosition(t0, iter.next());
258 if (Math.abs(pos-t0)<Shape2D.ACCURACY)
259 pos = choosePosition(t0, curve.getT1());
260 point = curve.getPoint(pos);
261
262 // remove the first point from the list of intersections
263 set.remove(t0);
264
265 // if inside, adds the first portion of the curve,
266 // and remove next intersection
267 if (box.contains(point)) {
268 pos = set.iterator().next();
269 res.addCurve((ContinuousCurve2D)curve.getSubCurve(t0, pos));
270 set.remove(pos);
271 }
272
273 // update iterator
274 iter = set.iterator();
275
276 inside = false;
277 }
278 }
279
280 // different behavior depending if first point lies inside the box
281 double pos0 = Double.NaN;
282 if (inside&&!touch)
283 if (curve.isClosed())
284 pos0 = iter.next();
285 else
286 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 while (iter.hasNext()) {
292 pos1 = iter.next().doubleValue();
293 if (iter.hasNext())
294 pos2 = iter.next().doubleValue();
295 else
296 pos2 = curve.isClosed()&&!touch ? pos0 : curve.getT1();
297 res.addCurve((ContinuousCurve2D)curve.getSubCurve(pos1, pos2));
298 }
299
300 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 CurveArray2D<SmoothCurve2D> result = new CurveArray2D<SmoothCurve2D>();
310 for (ContinuousCurve2D cont : Curve2DUtils.clipContinuousCurve(curve,
311 box))
312 if (cont instanceof SmoothCurve2D)
313 result.addCurve((SmoothCurve2D) cont);
314
315 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 ArrayList<Point2D> list = new ArrayList<Point2D>();
327 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 SortedSet<java.lang.Double> set = new TreeSet<java.lang.Double>();
333 double position;
334 Vector2D vector = line.getVector();
335 for (Point2D point : list) {
336 // get position of intersection on the curve (use project to avoid
337 // round-off problems)
338 position = curve.project(point);
339
340 // Condition of colinearity with direction vector of line
341 Vector2D tangent = curve.getTangent(position);
342 if (Vector2D.isColinear(tangent, vector)) {
343 // condition on the curvature (close to zero = cusp point)
344 double curv = curve.getCurvature(position);
345 if (Math.abs(curv)>Shape2D.ACCURACY)
346 continue;
347 }
348 set.add(new java.lang.Double(position));
349 }
350
351 // Create CurveSet2D for storing the result
352 CurveArray2D<SmoothCurve2D> res = new CurveArray2D<SmoothCurve2D>();
353
354 // extract first point of the curve, or a point arbitrarily far
355 Point2D point1;
356 if (Double.isInfinite(curve.getT0()))
357 point1 = curve.getPoint(-1000);
358 else
359 point1 = curve.getFirstPoint();
360
361 // Extract first valid intersection point, if it exists
362 double pos1, pos2;
363 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 if (!iter.hasNext()) {
368 // Find a point on the curve and not on the line
369 // First tries with first point
370 double t0 = curve.getT0();
371 if (t0==Double.NEGATIVE_INFINITY)
372 t0 = -100;
373 while (line.contains(point1)) {
374 double t1 = curve.getT1();
375 if (t1==Double.POSITIVE_INFINITY)
376 t1 = +100;
377 t0 = (t0+t1)/2;
378 point1 = curve.getPoint(t0);
379 }
380 if (line.getSignedDistance(point1)<0)
381 res.addCurve(curve);
382 return res;
383 }
384
385 // different behavior depending if first point lies inside the box
386 if (line.getSignedDistance(point1)<0&&!line.contains(point1)) {
387 pos1 = iter.next().doubleValue();
388 res.addCurve((SmoothCurve2D)curve.getSubCurve(curve.getT0(), pos1));
389 }
390
391 // add the portions of curve between couples of intersections
392 while (iter.hasNext()) {
393 pos1 = iter.next().doubleValue();
394 if (iter.hasNext())
395 pos2 = iter.next().doubleValue();
396 else
397 pos2 = curve.getT1();
398 res.addCurve((SmoothCurve2D)curve.getSubCurve(pos1, pos2));
399 }
400
401 return res;
402 }
403
404 public final static int findNextCurveIndex(double[] positions, double pos) {
405 int ind = -1;
406 double posMin = java.lang.Double.MAX_VALUE;
407 for (int i = 0; i<positions.length; i++) {
408 // avoid NaN
409 if (java.lang.Double.isNaN(positions[i]))
410 continue;
411 // avoid values before
412 if (positions[i]-pos<Shape2D.ACCURACY)
413 continue;
414
415 // test if closer that other points
416 if (positions[i]<posMin) {
417 ind = i;
418 posMin = positions[i];
419 }
420 }
421
422 if (ind!=-1)
423 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 for (int i = 0; i<positions.length; i++) {
428 if (java.lang.Double.isNaN(positions[i]))
429 continue;
430 if (positions[i]-posMin<Shape2D.ACCURACY) {
431 ind = i;
432 posMin = positions[i];
433 }
434 }
435 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 if (Double.isInfinite(t0)) {
448 if (Double.isInfinite(t1))
449 return 0;
450 return t1-10;
451 }
452
453 if (Double.isInfinite(t1))
454 return t0+10;
455
456 return (t0+t1)/2;
457 }
458
459 public final static boolean isLeftInfinite(Curve2D curve) {
460 // basic check
461 if(curve.isBounded()) return false;
462
463 // extract the first smooth curve
464 ContinuousCurve2D cont = curve.getContinuousCurves().iterator().next();
465 SmoothCurve2D smooth = cont.getSmoothPieces().iterator().next();
466
467 // check first position of first curve
468 return Double.isInfinite(smooth.getT0());
469 }
470
471 public final static boolean isRightInfinite(Curve2D curve) {
472 // basic check
473 if(curve.isBounded()) return false;
474
475 // extract the first smooth curve
476 SmoothCurve2D lastCurve = null;
477 for(ContinuousCurve2D cont : curve.getContinuousCurves())
478 for(SmoothCurve2D smooth : cont.getSmoothPieces())
479 lastCurve = smooth;
480
481 // check last position of last curve
482 return Double.isInfinite(lastCurve.getT1());
483 }
484 }