1 /**
2 *
3 */
4
5 package math.geom2d.polygon;
6
7 import java.util.ArrayList;
8 import java.util.Collection;
9 import java.util.Iterator;
10
11 import math.geom2d.Angle2D;
12 import math.geom2d.Point2D;
13 import math.geom2d.conic.Circle2D;
14 import math.geom2d.conic.CircleArc2D;
15 import math.geom2d.domain.BoundaryPolyCurve2D;
16 import math.geom2d.domain.PolyOrientedCurve2D;
17 import math.geom2d.domain.SmoothOrientedCurve2D;
18 import math.geom2d.line.LineSegment2D;
19 import math.geom2d.line.StraightLine2D;
20
21 /**
22 * Some utility functions for manipulating Polyline2D.
23 *
24 * @author dlegland
25 * @since 0.6.3
26 */
27 public abstract class Polyline2DUtils {
28
29 /**
30 * Creates a curve parallel to the given polyline, at a distance d. The
31 * resulting curve is continuous, but can self-intersect. It is composed of
32 * line segments, and circle arcs.
33 *
34 * @param polyline the source curve
35 * @param d the signed distance between the original curve and its parallel
36 * @return the curve parallel to the original curve at a distance d
37 */
38 public final static PolyOrientedCurve2D<SmoothOrientedCurve2D>
39 createParallel(Polyline2D polyline, double d) {
40
41 // Collection of parallel curves
42 PolyOrientedCurve2D<SmoothOrientedCurve2D> result =
43 new PolyOrientedCurve2D<SmoothOrientedCurve2D>();
44 result.setClosed(polyline instanceof LinearRing2D);
45
46 // evacuate degenerate case.
47 if (polyline.getVertices().size()<2)
48 return result;
49
50 // ----- declarations -----
51
52 // vertices of the current edge
53 Point2D v1, v2;
54
55 // The corresponding parallel points, and the intersection point
56 // for first curve
57 Point2D p1, p2, p0 = null;
58
59 // The line parallel to the previous and current line segments
60 StraightLine2D line0, line;
61
62 // Circle located at corners
63 Circle2D circle;
64
65 Iterator<Point2D> iterator;
66
67 // ----- Initializations -----
68
69 if (polyline instanceof LinearRing2D) {
70 // Add eventually a circle arc, and the first line segment.
71
72 // Extract parallel to last edge
73 LineSegment2D lastEdge = polyline.getLastEdge();
74 line0 = StraightLine2D.createParallel(lastEdge, d);
75
76 v2 = lastEdge.getLastPoint();
77 p0 = line0.getProjectedPoint(v2);
78
79 // extract current vertices, and current parallel
80 iterator = polyline.getVertices().iterator();
81 v1 = iterator.next();
82 v2 = iterator.next();
83 line = new StraightLine2D(v1, v2).getParallel(d);
84
85 // Check angle of the 2 lines
86 p1 = line.getProjectedPoint(v1);
87 if (Angle2D.getAngle(line0, line)>Math.PI^d<0) {
88 // Line is going to the right -> next line segment will be
89 // truncated
90 p1 = line.getIntersection(line0);
91 p0 = p1;
92 } else {
93 // line is going to the left -> add a circle arc
94 circle = new Circle2D(v1, Math.abs(d));
95 result.addCurve(new CircleArc2D(v1, Math.abs(d), circle
96 .getPosition(p0), circle.getPosition(p1), d>0));
97 }
98
99 p2 = line.getProjectedPoint(v2);
100 line0 = line;
101 } else {
102 // extract current vertices
103 iterator = polyline.getVertices().iterator();
104 v1 = iterator.next();
105 v2 = iterator.next();
106
107 // current parallel
108 line0 = new StraightLine2D(v1, v2).getParallel(d);
109 p1 = line0.getProjectedPoint(v1);
110 p2 = line0.getProjectedPoint(v2);
111 }
112
113 // ----- Main loop -----
114
115 // Main iteration on vertices
116 while (iterator.hasNext()) {
117 // Compute line parallel to current line segment
118 v1 = v2;
119 v2 = iterator.next();
120 line = new StraightLine2D(v1, v2).getParallel(d);
121
122 // Check angle of the 2 lines
123 if (Angle2D.getAngle(line0, line)>Math.PI^d<0) {
124 // Line is going to the right -> add the previous line segment
125 // truncated at corner
126 p2 = line.getIntersection(line0);
127 // TODO: need mode precise control
128 result.addCurve(new LineSegment2D(p1, p2));
129 p1 = p2;
130 } else {
131 // line is going to the left -> add the complete line segment
132 // and a circle arc
133 result.addCurve(new LineSegment2D(p1, p2));
134 p1 = line.getProjectedPoint(v1);
135 circle = new Circle2D(v1, Math.abs(d));
136 result.addCurve(new CircleArc2D(v1, Math.abs(d), circle
137 .getPosition(p2), circle.getPosition(p1), d>0));
138 }
139
140 // Prepare for next iteration
141 p2 = line.getProjectedPoint(v2);
142 line0 = line;
143 }
144
145 // ----- Post processing -----
146
147 if (polyline instanceof LinearRing2D) {
148 // current line segment join the last point to the first point
149 iterator = polyline.getVertices().iterator();
150 v1 = v2;
151 v2 = iterator.next();
152 line = new StraightLine2D(v1, v2).getParallel(d);
153
154 // Check angle of the 2 lines
155 if (Angle2D.getAngle(line0, line)>Math.PI^d<0) {
156 // Line is going to the right -> add the previous line segment
157 // truncated at corner
158 p2 = line.getIntersection(line0);
159 // TODO: need mode precise control
160 result.addCurve(new LineSegment2D(p1, p2));
161 p1 = p2;
162 } else {
163 // line is going to the left -> add the complete line segment
164 // and a circle arc
165 result.addCurve(new LineSegment2D(p1, p2));
166 p1 = line.getProjectedPoint(v1);
167 circle = new Circle2D(v1, Math.abs(d));
168 result.addCurve(new CircleArc2D(v1, Math.abs(d), circle
169 .getPosition(p2), circle.getPosition(p1), d>0));
170 }
171
172 // Add the last line segment
173 result.addCurve(new LineSegment2D(p1, p0));
174 } else {
175 // Add the last line segment
176 result.addCurve(new LineSegment2D(p1, p2));
177 }
178
179 // Return the resulting curve
180 return result;
181 }
182
183 /**
184 * Creates a curve parallel to the given polyline, at a distance d. The
185 * resulting curve is continuous, but can self-intersect. It is composed of
186 * line segments, and circle arcs.
187 *
188 * @param polyline the source curve
189 * @param d the signed distance between the original curve and its parallel
190 * @return the curve parallel to the original curve at a distance d
191 */
192 public final static BoundaryPolyCurve2D<SmoothOrientedCurve2D>
193 createClosedParallel(LinearRing2D polyline, double d) {
194
195 // Collection of parallel curves
196 BoundaryPolyCurve2D<SmoothOrientedCurve2D> result =
197 new BoundaryPolyCurve2D<SmoothOrientedCurve2D>();
198 result.setClosed(true);
199
200 // evacuate degenerate case.
201 if (polyline.getVertices().size()<2)
202 return result;
203
204 // ----- declarations -----
205
206 // vertices of the current edge
207 Point2D v1, v2;
208
209 // The corresponding parallel points, and the intersection point
210 // for first curve
211 Point2D p1, p2, p0 = null;
212
213 // The line parallel to the previous and current line segments
214 StraightLine2D line0, line;
215
216 // Circle located at corners
217 Circle2D circle;
218
219 Iterator<Point2D> iterator;
220
221 // ----- Initializations -----
222
223 // Add eventually a circle arc, and the first line segment.
224
225 // Extract parallel to last edge
226 LineSegment2D lastEdge = polyline.getLastEdge();
227 line0 = StraightLine2D.createParallel(lastEdge, d);
228
229 v2 = lastEdge.getLastPoint();
230 p0 = line0.getProjectedPoint(v2);
231
232 // extract current vertices, and current parallel
233 iterator = polyline.getVertices().iterator();
234 v1 = iterator.next();
235 v2 = iterator.next();
236 line = new StraightLine2D(v1, v2).getParallel(d);
237
238 // Check angle of the 2 lines
239 p1 = line.getProjectedPoint(v1);
240 if (Angle2D.getAngle(line0, line)>Math.PI^d<0) {
241 // Line is going to the right -> next line segment will be
242 // truncated
243 p1 = line.getIntersection(line0);
244 p0 = p1;
245 } else {
246 // line is going to the left -> add a circle arc
247 circle = new Circle2D(v1, Math.abs(d));
248 result.addCurve(new CircleArc2D(v1, Math.abs(d), circle
249 .getPosition(p0), circle.getPosition(p1), d>0));
250 }
251
252 p2 = line.getProjectedPoint(v2);
253 line0 = line;
254
255 // ----- Main loop -----
256
257 // Main iteration on vertices
258 while (iterator.hasNext()) {
259 // Compute line parallel to current line segment
260 v1 = v2;
261 v2 = iterator.next();
262 line = new StraightLine2D(v1, v2).getParallel(d);
263
264 // Check angle of the 2 lines
265 if (Angle2D.getAngle(line0, line)>Math.PI^d<0) {
266 // Line is going to the right -> add the previous line segment
267 // truncated at corner
268 p2 = line.getIntersection(line0);
269 // TODO: need mode precise control
270 result.addCurve(new LineSegment2D(p1, p2));
271 p1 = p2;
272 } else {
273 // line is going to the left -> add the complete line segment
274 // and a circle arc
275 result.addCurve(new LineSegment2D(p1, p2));
276 p1 = line.getProjectedPoint(v1);
277 circle = new Circle2D(v1, Math.abs(d));
278 result.addCurve(new CircleArc2D(v1, Math.abs(d), circle
279 .getPosition(p2), circle.getPosition(p1), d>0));
280 }
281
282 // Prepare for next iteration
283 p2 = line.getProjectedPoint(v2);
284 line0 = line;
285 }
286
287 // ----- Post processing -----
288
289 // current line segment join the last point to the first point
290 iterator = polyline.getVertices().iterator();
291 v1 = v2;
292 v2 = iterator.next();
293 line = new StraightLine2D(v1, v2).getParallel(d);
294
295 // Check angle of the 2 lines
296 if (Angle2D.getAngle(line0, line)>Math.PI^d<0) {
297 // Line is going to the right -> add the previous line segment
298 // truncated at corner
299 p2 = line.getIntersection(line0);
300 // TODO: need mode precise control
301 result.addCurve(new LineSegment2D(p1, p2));
302 p1 = p2;
303 } else {
304 // line is going to the left -> add the complete line segment
305 // and a circle arc
306 result.addCurve(new LineSegment2D(p1, p2));
307 p1 = line.getProjectedPoint(v1);
308 circle = new Circle2D(v1, Math.abs(d));
309 result.addCurve(new CircleArc2D(v1, Math.abs(d), circle
310 .getPosition(p2), circle.getPosition(p1), d>0));
311 }
312
313 // Add the last line segment
314 result.addCurve(new LineSegment2D(p1, p0));
315
316 // Return the resulting curve
317 return result;
318 }
319
320 /**
321 * Return all intersection points between the 2 polylines.
322 * @param poly1 a polyline
323 * @param poly2 a polyline
324 * @return the set of intersection points
325 */
326 public final static Collection<Point2D> intersect(
327 Polyline2D poly1, Polyline2D poly2) {
328 ArrayList<Point2D> points = new ArrayList<Point2D>();
329
330 Point2D point;
331 for(LineSegment2D edge1 : poly1.getEdges()){
332 for(LineSegment2D edge2 : poly2.getEdges()){
333 point = edge1.getIntersection(edge2);
334 if(point!=null)
335 points.add(point);
336 }
337 }
338
339 return points;
340 }
341 }