1 /**
2 *
3 */
4
5 package math.geom2d.domain;
6
7 import java.util.ArrayList;
8 import java.util.Collection;
9 import java.util.Iterator;
10
11 import math.geom2d.Box2D;
12 import math.geom2d.Point2D;
13 import math.geom2d.Shape2D;
14 import math.geom2d.UnboundedShapeException;
15 import math.geom2d.curve.ContinuousCurve2D;
16 import math.geom2d.curve.Curve2D;
17 import math.geom2d.curve.CurveArray2D;
18 import math.geom2d.curve.CurveSet2D;
19 import math.geom2d.curve.Curve2DUtils;
20 import math.geom2d.polygon.Polyline2D;
21
22 /**
23 * Collects some useful methods for clipping curves.
24 *
25 * @author dlegland
26 */
27 public abstract class Boundary2DUtils {
28
29 /**
30 * Clip a curve, and return a CurveSet2D. If the curve is totally outside
31 * the box, return a CurveSet2D with 0 curves inside. If the curve is
32 * totally inside the box, return a CurveSet2D with only one curve, which is
33 * the original curve.
34 */
35 public final static CurveSet2D<ContinuousOrientedCurve2D> clipContinuousOrientedCurve(
36 ContinuousOrientedCurve2D curve, Box2D box) {
37
38 CurveArray2D<ContinuousOrientedCurve2D> result =
39 new CurveArray2D<ContinuousOrientedCurve2D>();
40 for (ContinuousCurve2D cont :
41 Curve2DUtils.clipContinuousCurve(curve, box))
42 if (cont instanceof ContinuousOrientedCurve2D)
43 result.addCurve((ContinuousOrientedCurve2D) cont);
44
45 return result;
46
47 // // create array of points
48 // ArrayList<Point2D> points = new ArrayList<Point2D>();
49 //
50 // // add the intersections with edges of the box boundary
51 // for(StraightObject2D edge : box.getEdges())
52 // points.addAll(curve.getIntersections(edge));
53 //
54 // // convert list to point array, sorted wrt to their position on the
55 // curve
56 // SortedSet<java.lang.Double> set = new TreeSet<java.lang.Double>();
57 // for(Point2D p : points)
58 // set.add(new java.lang.Double(curve.getPosition(p)));
59 //
60 // // Create curveset for storing the result
61 // CurveSet2D<ContinuousOrientedCurve2D> res =
62 // new CurveSet2D<ContinuousOrientedCurve2D>();
63 //
64 // // extract first point of the curve
65 // Point2D point1 = curve.getFirstPoint();
66 //
67 // // case of empty curve set, for example
68 // if(point1==null)
69 // return res;
70 //
71 // // if no intersection point, the curve is totally either inside or
72 // outside the box
73 // if(set.size()==0){
74 // if(box.contains(point1))
75 // res.addCurve(curve);
76 // return res;
77 // }
78 //
79 // double pos1, pos2;
80 // Iterator<java.lang.Double> iter = set.iterator();
81 //
82 // double pos0=0;
83 //
84 // // different behavior depending if first point lies inside the box
85 // if(box.contains(point1) && !box.getBoundary().contains(point1))
86 // pos0 = iter.next().doubleValue();
87 //
88 //
89 // // add the portions of curve between couples of intersections
90 // while(iter.hasNext()){
91 // pos1 = iter.next().doubleValue();
92 // if(iter.hasNext())
93 // pos2 = iter.next().doubleValue();
94 // else
95 // pos2 = pos0;
96 // res.addCurve(curve.getSubCurve(pos1, pos2));
97 // }
98 //
99 // return res;
100 }
101
102 /**
103 * Clips a boundary and closes the result curve. Return an instance of
104 * BoundarySet2D.
105 */
106 public final static BoundarySet2D<ContinuousBoundary2D> clipBoundary(
107 Boundary2D boundary, Box2D box) {
108
109 if (!box.isBounded())
110 throw new UnboundedShapeException();
111
112 // iteration variable
113 ContinuousOrientedCurve2D curve;
114
115 // The set of boundary curves. Each curve of this set is either a
116 // curve of the original boundary, or a composition of a portion of
117 // original boundary with a portion of the box.
118 BoundarySet2D<ContinuousBoundary2D> res =
119 new BoundarySet2D<ContinuousBoundary2D>();
120
121 // to store result of curve clipping
122 CurveSet2D<ContinuousOrientedCurve2D> clipped;
123
124 // to store set of all clipped curves
125 CurveArray2D<ContinuousOrientedCurve2D> curveSet =
126 new CurveArray2D<ContinuousOrientedCurve2D>();
127
128 // extract the oriented curves which constitutes the boundary
129 Collection<? extends ContinuousBoundary2D> boundaryCurves =
130 boundary.getBoundaryCurves();
131
132 // Iterate on boundary curves: extract current curve (continuous and
133 // oriented), clip it with box, and add clipped curves to the array
134 // 'curveSet'
135 for (ContinuousBoundary2D boundaryCurve : boundaryCurves) {
136 clipped = Boundary2DUtils.clipContinuousOrientedCurve(
137 boundaryCurve, box);
138
139 for (ContinuousOrientedCurve2D clip : clipped)
140 curveSet.addCurve(clip);
141 }
142
143 // array of position on the box for first and last point of each curve
144 int nc = curveSet.getCurveNumber();
145 double[] startPositions = new double[nc];
146 double[] endPositions = new double[nc];
147
148 // Flag indicating if the curve intersects the boundary of the box
149 boolean intersect = false;
150
151 // also create array of curves
152 ContinuousOrientedCurve2D[] curves =
153 new ContinuousOrientedCurve2D[nc];
154
155 // boundary of the box
156 Curve2D boxBoundary = box.getBoundary();
157
158 // compute position on the box for first and last point of each curve
159 Iterator<ContinuousOrientedCurve2D> iter = curveSet.getCurves()
160 .iterator();
161
162 for (int i = 0; i<nc; i++) {
163 // save current curve
164 curve = iter.next();
165 curves[i] = curve;
166
167 if (curve.isClosed()) {
168 startPositions[i] = java.lang.Double.NaN;
169 endPositions[i] = java.lang.Double.NaN;
170 continue;
171 }
172
173 // compute positions of first point and last point on box boundary
174 startPositions[i] = boxBoundary.getPosition(curve.getFirstPoint());
175 endPositions[i] = boxBoundary.getPosition(curve.getLastPoint());
176
177 // set up the flag
178 intersect = true;
179 }
180
181 // theoretical number of boundary curves. Set to the number of clipped
182 // curves, but total number can be reduced if several clipped curves
183 // belong to the same boundary curve.
184 int nb = nc;
185
186 // current index of curve
187 int c = 0;
188
189 // iterate while there are boundary curve to build
190 while (c<nb) {
191 int ind = c;
192 // find the current curve (used curves are removed from array)
193 while (curves[ind]==null)
194 ind++;
195
196 // current curve
197 curve = curves[ind];
198
199 // if curve is closed, we can switch to next curve
200 if (curve.isClosed()) {
201 // Add current boundary to the set of boundary curves
202 if (curve instanceof ContinuousBoundary2D) {
203 res.addCurve((ContinuousBoundary2D) curve);
204 } else {
205 BoundaryPolyCurve2D<ContinuousOrientedCurve2D> bnd =
206 new BoundaryPolyCurve2D<ContinuousOrientedCurve2D>();
207 bnd.addCurve(curve);
208 res.addCurve(bnd);
209 }
210 curves[ind] = null;
211
212 // switch to next curve
213 c++;
214 continue;
215 }
216
217 // create a new Boundary curve
218 BoundaryPolyCurve2D<ContinuousOrientedCurve2D> boundary0 =
219 new BoundaryPolyCurve2D<ContinuousOrientedCurve2D>();
220
221 // add current curve to boundary curve
222 boundary0.addCurve(curve);
223
224 // get last points (to add a line with next curve)
225 Point2D p0 = curve.getFirstPoint();
226 Point2D p1 = curve.getLastPoint();
227
228 // index of first curve, used as a stop flag
229 int ind0 = ind;
230
231 // store indices of curves, to remove them later
232 ArrayList<Integer> indices = new ArrayList<Integer>();
233 indices.add(new Integer(ind));
234
235 // position of last point of current curve on box boundary
236 ind = findNextCurveIndex(startPositions, endPositions[ind0]);
237
238 // iterate while we don't come back to first point
239 while (ind!=ind0) {
240 // find the curve whose first point is just after last point
241 // of current curve on box boundary
242 curve = curves[ind];
243
244 // add a link between previous curve and current curve
245 boundary0.addCurve(getBoundaryPortion(box, p1, curve
246 .getFirstPoint()));
247
248 // add to current boundary
249 boundary0.addCurve(curve);
250
251 indices.add(new Integer(ind));
252
253 // find index and position of next curve
254 ind = findNextCurveIndex(startPositions, endPositions[ind]);
255
256 // get last points
257 p1 = curve.getLastPoint();
258
259 // decrease total number of boundary curves
260 nb--;
261 }
262
263 // add a line from last point to first point
264 boundary0.addCurve(getBoundaryPortion(box, p1, p0));
265
266 // Add current boundary to the set of boundary curves
267 res.addCurve(boundary0);
268
269 // remove curves from array
270 Iterator<Integer> iter2 = indices.iterator();
271 while (iter2.hasNext())
272 curves[iter2.next().intValue()] = null;
273
274 // next curve !
275 c++;
276 }
277
278 // Add processing when the box boundary does not intersect the curve.
279 // In this case add the boundary of the box to the resulting boundary
280 // set.
281 if (!intersect) {
282 Point2D vertex = box.getVertices().iterator().next();
283 if (boundary.isInside(vertex))
284 res.addCurve(box.getAsRectangle().getBoundary().getFirstCurve());
285 }
286
287 // return the result
288 return res;
289 }
290
291 public final static int findNextCurveIndex(double[] positions, double pos) {
292 int ind = -1;
293 double posMin = java.lang.Double.MAX_VALUE;
294 for (int i = 0; i<positions.length; i++) {
295 // avoid NaN
296 if (java.lang.Double.isNaN(positions[i]))
297 continue;
298 // avoid values before
299 if (positions[i]-pos<Shape2D.ACCURACY)
300 continue;
301
302 // test if closer that other points
303 if (positions[i]<posMin) {
304 ind = i;
305 posMin = positions[i];
306 }
307 }
308
309 if (ind!=-1)
310 return ind;
311
312 // if not found, return index of smallest value (mean that pos is last
313 // point on the boundary, so we need to start at the beginning).
314 for (int i = 0; i<positions.length; i++) {
315 if (java.lang.Double.isNaN(positions[i]))
316 continue;
317 if (positions[i]-posMin<Shape2D.ACCURACY) {
318 ind = i;
319 posMin = positions[i];
320 }
321 }
322 return ind;
323 }
324
325 /**
326 * Extracts a portion of the boundary of a bounded box.
327 *
328 * @param box the box from which one extract a portion of boundary
329 * @param p0 the first point of the portion
330 * @param p1 the last point of the portion
331 * @return the portion of the bounding box boundary as a Polyline2D
332 */
333 public final static Polyline2D getBoundaryPortion(Box2D box, Point2D p0,
334 Point2D p1) {
335 Boundary2D boundary = box.getBoundary();
336
337 // position of start and end points
338 double t0 = boundary.getPosition(p0);
339 double t1 = boundary.getPosition(p1);
340
341 // curve index of each point
342 int ind0 = (int) Math.floor(t0);
343 int ind1 = (int) Math.floor(t1);
344
345 // Simple case: returns a polyline with only 2 vertices
346 if (ind0==ind1&&t0<t1)
347 return new Polyline2D(new Point2D[] { p0, p1 });
348
349 // Create an array to store vertices
350 // Array can contain at most 6 vertices: 4 for the box corners,
351 // and 2 for curve extremities.
352 ArrayList<Point2D> vertices = new ArrayList<Point2D>(6);
353
354 // add the first point.
355 vertices.add(p0);
356
357 // compute index of first box boundary edge
358 int ind = (ind0+1)%4;
359
360 // add all vertices segments between the 2 end points
361 while (ind!=ind1) {
362 vertices.add(boundary.getPoint(ind));
363 ind = (ind+1)%4;
364 }
365 vertices.add(boundary.getPoint(ind));
366
367 // add the last line segment
368 vertices.add(p1);
369
370 return new Polyline2D(vertices);
371 }
372 }