1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2014-2015, Oracle and/or its affiliates.
4
5 // Licensed under the Boost Software License version 1.0.
6 // http://www.boost.org/users/license.html
7
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
9
10 #include <iostream>
11
12 #ifndef BOOST_TEST_MODULE
13 #define BOOST_TEST_MODULE test_intersection_linear_linear
14 #endif
15
16 #ifdef BOOST_GEOMETRY_TEST_DEBUG
17 #define BOOST_GEOMETRY_DEBUG_TURNS
18 #define BOOST_GEOMETRY_DEBUG_SEGMENT_IDENTIFIER
19 #endif
20
21 #include <boost/test/included/unit_test.hpp>
22
23 #include "test_intersection_linear_linear.hpp"
24
25 #include <boost/geometry/geometries/linestring.hpp>
26 #include <boost/geometry/geometries/multi_linestring.hpp>
27 #include <boost/geometry/algorithms/intersection.hpp>
28
29 typedef bg::model::point<double,2,bg::cs::cartesian> point_type;
30 typedef bg::model::segment<point_type> segment_type;
31 typedef bg::model::linestring<point_type> linestring_type;
32 typedef bg::model::multi_linestring<linestring_type> multi_linestring_type;
33
34
35
36 //===========================================================================
37 //===========================================================================
38 //===========================================================================
39
40
BOOST_AUTO_TEST_CASE(test_intersection_linestring_linestring)41 BOOST_AUTO_TEST_CASE( test_intersection_linestring_linestring )
42 {
43 #ifdef BOOST_GEOMETRY_TEST_DEBUG
44 std::cout << std::endl << std::endl << std::endl;
45 std::cout << "*** LINESTRING / LINESTRING INTERSECTION ***" << std::endl;
46 std::cout << std::endl;
47 #endif
48
49 typedef linestring_type L;
50 typedef multi_linestring_type ML;
51
52 typedef test_intersection_of_geometries<L, L, ML> tester;
53
54 tester::apply
55 (from_wkt<L>("LINESTRING(0 0,1 1,2 1,3 2)"),
56 from_wkt<L>("LINESTRING(0 2,1 1,2 1,3 0)"),
57 from_wkt<ML>("MULTILINESTRING((1 1,2 1))"),
58 "lli00");
59
60 tester::apply
61 (from_wkt<L>("LINESTRING(0 0,5 0)"),
62 from_wkt<L>("LINESTRING(3 0,4 0)"),
63 from_wkt<ML>("MULTILINESTRING((3 0,4 0))"),
64 "lli01");
65
66 tester::apply
67 (from_wkt<L>("LINESTRING(0 0,4 0)"),
68 from_wkt<L>("LINESTRING(3 0,6 0)"),
69 from_wkt<ML>("MULTILINESTRING((3 0,4 0))"),
70 "lli01-2");
71
72 tester::apply
73 (from_wkt<L>("LINESTRING(0 0,6 0)"),
74 from_wkt<L>("LINESTRING(0 0,4 0)"),
75 from_wkt<ML>("MULTILINESTRING((0 0,4 0))"),
76 "lli01-4");
77
78 tester::apply
79 (from_wkt<L>("LINESTRING(0 0,20 0)"),
80 from_wkt<L>("LINESTRING(0 0,1 1,2 0,3 1,4 0,5 0,6 1,7 -1,8 0)"),
81 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
82 from_wkt<ML>("MULTILINESTRING((4 0,5 0))"),
83 #else
84 from_wkt<ML>("MULTILINESTRING((0 0),(2 0),(4 0,5 0),(6.5 0),(8 0))"),
85 #endif
86 "lli01-6");
87
88 tester::apply
89 (from_wkt<L>("LINESTRING(-20 0,20 0)"),
90 from_wkt<L>("LINESTRING(0 0,1 1,2 0,3 1,4 0,5 0,6 1,7 -1,8 0)"),
91 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
92 from_wkt<ML>("MULTILINESTRING((4 0,5 0))"),
93 #else
94 from_wkt<ML>("MULTILINESTRING((0 0),(2 0),(4 0,5 0),(6.5 0),(8 0))"),
95 #endif
96 "lli01-7");
97
98 tester::apply
99 (from_wkt<L>("LINESTRING(0 0,4 0)"),
100 from_wkt<L>("LINESTRING(2 0,4 0)"),
101 from_wkt<ML>("MULTILINESTRING((2 0,4 0))"),
102 "lli01-8");
103
104 tester::apply
105 (from_wkt<L>("LINESTRING(0 0,2 0)"),
106 from_wkt<L>("LINESTRING(4 0,5 0)"),
107 from_wkt<ML>("MULTILINESTRING()"),
108 "lli01-10");
109
110 tester::apply
111 (from_wkt<L>("LINESTRING(0 0,2 0)"),
112 from_wkt<L>("LINESTRING(2 0,5 0)"),
113 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
114 from_wkt<ML>("MULTILINESTRING()"),
115 #else
116 from_wkt<ML>("MULTILINESTRING((2 0))"),
117 #endif
118 "lli01-11");
119
120 tester::apply
121 (from_wkt<L>("LINESTRING(0 0,1 0,4 0)"),
122 from_wkt<L>("LINESTRING(3 0,5 0)"),
123 from_wkt<ML>("MULTILINESTRING((3 0,4 0))"),
124 "lli01-11a");
125
126 tester::apply
127 (from_wkt<L>("LINESTRING(0 0,1 0,4 0)"),
128 from_wkt<L>("LINESTRING(3 0,4 0,5 0)"),
129 from_wkt<ML>("MULTILINESTRING((3 0,4 0))"),
130 "lli01-11b");
131
132 tester::apply
133 (from_wkt<L>("LINESTRING(0 0,5 0,10 0)"),
134 from_wkt<L>("LINESTRING(2 0,6 0,8 0)"),
135 from_wkt<ML>("MULTILINESTRING((2 0,5 0,8 0))"),
136 from_wkt<ML>("MULTILINESTRING((2 0,6 0,8 0))"),
137 "lli01-11c");
138
139 tester::apply
140 (from_wkt<L>("LINESTRING(0 0,6 0)"),
141 from_wkt<L>("LINESTRING(2 0,4 0,5 0)"),
142 from_wkt<ML>("MULTILINESTRING((2 0,5 0))"),
143 from_wkt<ML>("MULTILINESTRING((2 0,4 0,5 0))"),
144 "lli01-12");
145
146 tester::apply
147 (from_wkt<L>("LINESTRING(0 0,1 0,5 5,10 5,15 0)"),
148 from_wkt<L>("LINESTRING(-1 6,0 5,15 5)"),
149 from_wkt<ML>("MULTILINESTRING((5 5,10 5))"),
150 "lli02");
151
152 tester::apply
153 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0)"),
154 from_wkt<L>("LINESTRING(-1 0,30 0)"),
155 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0))"),
156 "lli03");
157
158 tester::apply
159 (from_wkt<L>("LINESTRING(0 0,1 0,5 5,10 5,15 0,20 0)"),
160 from_wkt<L>("LINESTRING(-1 0,30 0)"),
161 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0))"),
162 "lli04");
163
164 tester::apply
165 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,25 1)"),
166 from_wkt<L>("LINESTRING(-1 0,30 0)"),
167 from_wkt<ML>("MULTILINESTRING((0 0,1 0)(15 0,20 0))"),
168 "lli05");
169
170 tester::apply
171 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,30 0)"),
172 from_wkt<L>("LINESTRING(-1 0,30 0)"),
173 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"),
174 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,30 0))"),
175 "lli05-1");
176
177 tester::apply
178 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,31 0)"),
179 from_wkt<L>("LINESTRING(-1 0,30 0)"),
180 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"),
181 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,30 0))"),
182 "lli06");
183
184 tester::apply
185 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,31 0)"),
186 from_wkt<L>("LINESTRING(-1 0,25 0,30 0)"),
187 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"),
188 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,25 0,30 0))"),
189 "lli07");
190
191 tester::apply
192 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,31 0)"),
193 from_wkt<L>("LINESTRING(-1 0,19 0,30 0)"),
194 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"),
195 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,19 0,30 0))"),
196 "lli08");
197
198 tester::apply
199 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,30 0,31 1)"),
200 from_wkt<L>("LINESTRING(-1 0,30 0)"),
201 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"),
202 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,30 0))"),
203 "lli09");
204
205 tester::apply
206 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,5 5,10 5,15 0,20 0,30 0,31 1)"),
207 from_wkt<L>("LINESTRING(-1 -1,0 0,1 0,2 1,3 0,30 0)"),
208 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,20 0,30 0))"),
209 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(15 0,30 0))"),
210 "lli10");
211
212 tester::apply
213 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,4 0,5 5,10 5,15 0,20 0,\
214 30 0,31 1)"),
215 from_wkt<L>("LINESTRING(-1 -1,0 0,1 0,2 0,2.5 1,3 0,30 0)"),
216 from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0),(3 0,4 0),\
217 (15 0,20 0,30 0))"),
218 from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0),(3 0,4 0),\
219 (15 0,30 0))"),
220 "lli11");
221
222 tester::apply
223 (from_wkt<L>("LINESTRING(-1 1,0 0,1 0,4 0,5 5,10 5,15 0,31 0)"),
224 from_wkt<L>("LINESTRING(-1 -1,0 0,1 0,2 0,2.5 1,3 0,30 0)"),
225 from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0),\
226 (3 0,4 0),(15 0,30 0))"),
227 "lli11-1");
228
229 tester::apply
230 (from_wkt<L>("LINESTRING(0 0,2 0,3 1)"),
231 from_wkt<L>("LINESTRING(0 0,2 0,3 1)"),
232 from_wkt<ML>("MULTILINESTRING((0 0,2 0,3 1))"),
233 "lli12");
234
235 tester::apply
236 (from_wkt<L>("LINESTRING(0 0,2 0,3 1)"),
237 from_wkt<L>("LINESTRING(3 1,2 0,0 0)"),
238 from_wkt<ML>("MULTILINESTRING((0 0,2 0,3 1))"),
239 from_wkt<ML>("MULTILINESTRING((3 1,2 0,0 0))"),
240 "lli12-1");
241
242 tester::apply
243 (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 5,4 0)"),
244 from_wkt<L>("LINESTRING(1 0,2 1,3 5,4 0,5 10)"),
245 from_wkt<ML>("MULTILINESTRING((1 0,2 1,3 5,4 0))"),
246 "lli13");
247
248 tester::apply
249 (from_wkt<L>("LINESTRING(0 0,1 0,2 0,2.5 0,3 1)"),
250 from_wkt<L>("LINESTRING(0 0,2 0,2.5 0,3 1)"),
251 from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0,2.5 0,3 1))"),
252 from_wkt<ML>("MULTILINESTRING((0 0,2 0,2.5 0,3 1))"),
253 "lli14");
254
255 tester::apply
256 (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 5,4 0)"),
257 from_wkt<L>("LINESTRING(1 0,2 1,3 5)"),
258 from_wkt<ML>("MULTILINESTRING((1 0,2 1,3 5))"),
259 "lli15");
260
261 tester::apply
262 (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 2)"),
263 from_wkt<L>("LINESTRING(0.5 0,1 0,3 2,4 5)"),
264 from_wkt<ML>("MULTILINESTRING((0.5 0,1 0,2 1,3 2))"),
265 from_wkt<ML>("MULTILINESTRING((0.5 0,1 0,3 2))"),
266 "lli16");
267
268 tester::apply
269 (from_wkt<L>("LINESTRING(0 0,1 0,2 1,3 2)"),
270 from_wkt<L>("LINESTRING(4 5,3 2,1 0,0.5 0)"),
271 from_wkt<ML>("MULTILINESTRING((0.5 0,1 0,2 1,3 2))"),
272 from_wkt<ML>("MULTILINESTRING((0.5 0,1 0,3 2))"),
273 "lli16-r");
274
275 tester::apply
276 (from_wkt<L>("LINESTRING(0 0,10 0,20 1,30 1)"),
277 from_wkt<L>("LINESTRING(1 1,2 0,3 1,20 1,25 1)"),
278 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
279 from_wkt<ML>("MULTILINESTRING((20 1,25 1))"),
280 #else
281 from_wkt<ML>("MULTILINESTRING((2 0),(20 1,25 1))"),
282 #endif
283 "lli17");
284
285 tester::apply
286 (from_wkt<L>("LINESTRING(0 0,10 0,20 1,21 0,30 0)"),
287 from_wkt<L>("LINESTRING(1 1,2 0,3 1,20 1,25 0)"),
288 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
289 from_wkt<ML>("MULTILINESTRING()"),
290 #else
291 from_wkt<ML>("MULTILINESTRING((2 0),(20 1),(25 0))"),
292 #endif
293 "lli18");
294
295 tester::apply
296 (from_wkt<L>("LINESTRING(0 0,30 0)"),
297 from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 1)"),
298 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
299 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
300 #else
301 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
302 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0))"),
303 #endif
304 "lli19");
305
306 tester::apply
307 (from_wkt<L>("LINESTRING(0 0,30 0)"),
308 from_wkt<L>("LINESTRING(5 1,4 0,4 1,20 1,5 0,1 0)"),
309 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
310 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
311 #else
312 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
313 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0))"),
314 #endif
315 "lli19-r");
316
317 tester::apply
318 (from_wkt<L>("LINESTRING(0 0,30 0)"),
319 from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0)"),
320 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
321 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
322 #else
323 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
324 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0))"),
325 #endif
326 "lli19a");
327
328 tester::apply
329 (from_wkt<L>("LINESTRING(0 0,30 0)"),
330 from_wkt<L>("LINESTRING(4 0,4 1,20 1,5 0,1 0)"),
331 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
332 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
333 #else
334 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
335 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0))"),
336 #endif
337 "lli19a-r");
338
339 tester::apply
340 (from_wkt<L>("LINESTRING(0 0,30 0)"),
341 from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 0)"),
342 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
343 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,5 0))"),
344 "lli19b");
345
346 tester::apply
347 (from_wkt<L>("LINESTRING(0 0,30 0)"),
348 from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 0,6 1)"),
349 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
350 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,5 0))"),
351 "lli19c");
352
353 tester::apply
354 (from_wkt<L>("LINESTRING(0 0,30 0)"),
355 from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,3 0)"),
356 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
357 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,3 0))"),
358 "lli19d");
359
360 tester::apply
361 (from_wkt<L>("LINESTRING(0 0,30 0)"),
362 from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,3 0,3 1)"),
363 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
364 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,3 0))"),
365 "lli19e");
366
367 tester::apply
368 (from_wkt<L>("LINESTRING(0 0,30 0)"),
369 from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,4 0,5 0,5 1)"),
370 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
371 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(4 0,5 0))"),
372 "lli19f");
373
374 tester::apply
375 (from_wkt<L>("LINESTRING(0 0,30 0)"),
376 from_wkt<L>("LINESTRING(5 1,5 0,4 0,4 1,20 1,5 0,1 0)"),
377 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
378 from_wkt<ML>("MULTILINESTRING((5 0,4 0),(5 0,1 0))"),
379 "lli19f-r");
380
381 tester::apply
382 (from_wkt<L>("LINESTRING(0 0,30 0)"),
383 from_wkt<L>("LINESTRING(1 0,5 0,20 1,4 1,5 0,5 1)"),
384 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
385 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
386 #else
387 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
388 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(5 0))"),
389 #endif
390 "lli19g");
391
392 tester::apply
393 (from_wkt<L>("LINESTRING(0 0,30 0)"),
394 from_wkt<L>("LINESTRING(5 1,5 0,4 1,20 1,5 0,1 0)"),
395 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
396 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
397 #else
398 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
399 from_wkt<ML>("MULTILINESTRING((1 0,5 0),(5 0))"),
400 #endif
401 "lli19g-r");
402
403 tester::apply
404 (from_wkt<L>("LINESTRING(0 0,30 0,30 30,10 30,10 -10,15 0,40 0)"),
405 from_wkt<L>("LINESTRING(5 5,10 0,10 30,20 0,25 0,25 25,50 0,35 0)"),
406 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
407 from_wkt<ML>("MULTILINESTRING((20 0,25 0),(10 30,10 0),\
408 (35 0,40 0),(20 0,25 0))"),
409 from_wkt<ML>("MULTILINESTRING((20 0,25 0),(10 0,10 30),\
410 (40 0,35 0))"),
411 #else
412 from_wkt<ML>("MULTILINESTRING((10 0),(20 0,25 0),(10 30,10 0),\
413 (30 20),(35 0,40 0),(20 0,25 0))"),
414 from_wkt<ML>("MULTILINESTRING((10 0),(20 0,25 0),(10 0,10 30),\
415 (30 20),(40 0,35 0))"),
416 #endif
417 "lli20");
418
419 tester::apply
420 (from_wkt<L>("LINESTRING(0 0,30 0,30 30,10 30,10 -10,15 0,40 0)"),
421 from_wkt<L>("LINESTRING(5 5,10 0,10 30,20 0,25 0,25 25,50 0,15 0)"),
422 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
423 from_wkt<ML>("MULTILINESTRING((15 0,30 0),(10 30,10 0),\
424 (15 0,40 0))"),
425 from_wkt<ML>("MULTILINESTRING((10 0,10 30),(20 0,25 0),(40 0,15 0))"),
426 #else
427 from_wkt<ML>("MULTILINESTRING((10 0),(15 0,30 0),(10 30,10 0),\
428 (30 20),(15 0,40 0))"),
429 from_wkt<ML>("MULTILINESTRING((10 0),(10 0,10 30),(20 0,25 0),\
430 (30 20),(40 0,15 0))"),
431 #endif
432 "lli20a");
433
434
435 tester::apply
436 (from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"),
437 from_wkt<L>("LINESTRING(2 2,5 -1,15 2,18 0,20 0)"),
438 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
439 from_wkt<ML>("MULTILINESTRING((18 0,19 0,20 0))"),
440 from_wkt<ML>("MULTILINESTRING((18 0,20 0))"),
441 #else
442 from_wkt<ML>("MULTILINESTRING((4 0),(8.33333333333333333 0),\
443 (18 0,19 0,20 0))"),
444 from_wkt<ML>("MULTILINESTRING((4 0),(8.33333333333333333 0),\
445 (18 0,20 0))"),
446 #endif
447 "lli21"
448 );
449
450 tester::apply
451 (from_wkt<L>("LINESTRING(0 0,10 0)"),
452 from_wkt<L>("LINESTRING(1 0,4 0,2 1,5 1,4 0,8 0)"),
453 from_wkt<ML>("MULTILINESTRING((1 0,4 0),(4 0,8 0))"),
454 "lli22"
455 );
456
457 tester::apply
458 (from_wkt<L>("LINESTRING(0 0,10 0)"),
459 from_wkt<L>("LINESTRING(4 0,5 0,5 1,1 1,1 0,4 0)"),
460 from_wkt<ML>("MULTILINESTRING((1 0,5 0))"),
461 from_wkt<ML>("MULTILINESTRING((1 0,4 0),(4 0,5 0))"),
462 "lli23"
463 );
464
465 // the following two tests have been discussed with by Adam
466 tester::apply
467 (from_wkt<L>("LINESTRING(1 0,1 1,2 1)"),
468 from_wkt<L>("LINESTRING(2 1,1 1,1 0)"),
469 from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"),
470 "lli24"
471 );
472
473 tester::apply
474 (from_wkt<L>("LINESTRING(1 0,1 1,2 1)"),
475 from_wkt<L>("LINESTRING(1 2,1 1,1 0)"),
476 from_wkt<ML>("MULTILINESTRING((1 0,1 1))"),
477 "lli25"
478 );
479 }
480
481
482
483
BOOST_AUTO_TEST_CASE(test_intersection_linestring_multilinestring)484 BOOST_AUTO_TEST_CASE( test_intersection_linestring_multilinestring )
485 {
486 #ifdef BOOST_GEOMETRY_TEST_DEBUG
487 std::cout << std::endl << std::endl << std::endl;
488 std::cout << "*** LINESTRING / MULTILINESTRING INTERSECTION ***"
489 << std::endl;
490 std::cout << std::endl;
491 #endif
492
493 typedef linestring_type L;
494 typedef multi_linestring_type ML;
495
496 typedef test_intersection_of_geometries<L, ML, ML> tester;
497
498 // the inertsection code automatically reverses the order of the
499 // geometries according to the geometry IDs.
500 // all calls below are actually reversed, and internally the
501 // intersection of the linestring with the multi-linestring is
502 // computed.
503
504 // disjoint linestrings
505 tester::apply
506 (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"),
507 from_wkt<ML>("MULTILINESTRING((1 1,2 2,4 3),(1 1,2 2,5 3))"),
508 from_wkt<ML>("MULTILINESTRING()"),
509 "lmli01"
510 );
511
512 tester::apply
513 (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"),
514 from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,4 0))"),
515 from_wkt<ML>("MULTILINESTRING((2 0,4 0))"),
516 "lmli02"
517 );
518
519 tester::apply
520 (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"),
521 from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,5 0))"),
522 from_wkt<ML>("MULTILINESTRING((2 0,5 0))"),
523 "lmli03"
524 );
525
526 tester::apply
527 (from_wkt<L>("LINESTRING(0 0,10 0,20 1)"),
528 from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0))"),
529 from_wkt<ML>("MULTILINESTRING((2 0,4 0))"),
530 "lmli04"
531 );
532
533 tester::apply
534 (from_wkt<L>("LINESTRING(0 0,101 0)"),
535 from_wkt<ML>("MULTILINESTRING((-1 -1,1 0,101 0,200 -1))"),
536 from_wkt<ML>("MULTILINESTRING((1 0,101 0))"),
537 "lmli07"
538 );
539
540 tester::apply
541 (from_wkt<L>("LINESTRING(-1 1,0 0,101 0)"),
542 from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\
543 (19 -1,20 0,101 0,200 -1))"),
544 from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
545 "lmli07a"
546 );
547
548 tester::apply
549 (from_wkt<L>("LINESTRING(0 0,101 0)"),
550 from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\
551 (19 -1,20 0,101 0,200 -1))"),
552 from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
553 "lmli07b"
554 );
555
556 tester::apply
557 (from_wkt<L>("LINESTRING(0 0,101 0)"),
558 from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0),\
559 (-1 -1,1 0,101 0,200 -1))"),
560 from_wkt<ML>("MULTILINESTRING((1 0,101 0))"),
561 "lmli08"
562 );
563
564 tester::apply
565 (from_wkt<L>("LINESTRING(0 0,1 0,2 0.5,3 0,101 0)"),
566 from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0.5),\
567 (-1 -1,1 0,101 0,200 -1))"),
568 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
569 from_wkt<ML>("MULTILINESTRING((3 0,101 0))"),
570 #else
571 from_wkt<ML>("MULTILINESTRING((1 0),(2 0.5),(3 0,101 0))"),
572 #endif
573 "lmli09"
574 );
575
576 tester::apply
577 (from_wkt<L>("LINESTRING(0 0,1 0,1.5 0,2 0.5,3 0,101 0)"),
578 from_wkt<ML>("MULTILINESTRING((0 1,1 1,1 0,2 0.5),\
579 (-1 -1,1 0,101 0,200 -1))"),
580 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
581 from_wkt<ML>("MULTILINESTRING((1 0,1.5 0),(3 0,101 0))"),
582 #else
583 from_wkt<ML>("MULTILINESTRING((1 0),(2 0.5),(1 0,1.5 0),(3 0,101 0))"),
584 #endif
585 "lmli10"
586 );
587
588 tester::apply
589 (from_wkt<L>("LINESTRING(0 0,20 0)"),
590 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
591 (1 1,2 0,18 0,19 1),(2 1,3 0,17 0,18 1),\
592 (3 1,4 0,16 0,17 1))"),
593 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
594 "lmli12"
595 );
596
597 tester::apply
598 (from_wkt<L>("LINESTRING(0 0,20 0)"),
599 from_wkt<ML>("MULTILINESTRING((1 0,19 0,20 1),\
600 (2 0,18 0,19 1),(3 0,17 0,18 1),\
601 (4 0,16 0,17 1))"),
602 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
603 "lmli13"
604 );
605
606 tester::apply
607 (from_wkt<L>("LINESTRING(0 0,20 0)"),
608 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1,19 1,18 0,2 0,\
609 1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1))"),
610 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
611 "lmli14"
612 );
613
614 tester::apply
615 (from_wkt<L>("LINESTRING(0 0,20 0)"),
616 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
617 (2 2,4 2,6 0))"),
618 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
619 "lmli15"
620 );
621
622 tester::apply
623 (from_wkt<L>("LINESTRING(0 0,20 0)"),
624 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
625 (6 0,4 2,2 2))"),
626 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
627 "lmli15a"
628 );
629
630 tester::apply
631 (from_wkt<L>("LINESTRING(0 0,20 0)"),
632 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
633 (2 2,4 2,5 0,6 0))"),
634 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
635 "lmli16"
636 );
637
638 tester::apply
639 (from_wkt<L>("LINESTRING(0 0,20 0)"),
640 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
641 (6 0,5 0,4 2,2 2))"),
642 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
643 "lmli16a"
644 );
645
646 tester::apply
647 (from_wkt<L>("LINESTRING(0 0,30 0)"),
648 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
649 (2 2,4 0,5 2,20 2,25 0))"),
650 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
651 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
652 #else
653 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(25 0))"),
654 #endif
655 "lmli17"
656 );
657
658 tester::apply
659 (from_wkt<L>("LINESTRING(0 0,30 0)"),
660 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
661 (2 2,4 0,5 2,20 2,25 0,26 2))"),
662 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
663 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
664 #else
665 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(25 0))"),
666 #endif
667 "lmli17a"
668 );
669
670 tester::apply
671 (from_wkt<L>("LINESTRING(0 0,30 0)"),
672 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
673 (2 2,5 -1,15 2,18 0))"),
674 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
675 "lmli18"
676 );
677
678 tester::apply
679 (from_wkt<L>("LINESTRING(0 0,18 0,19 0,30 0)"),
680 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
681 (2 2,5 -1,15 2,18 0))"),
682 from_wkt<ML>("MULTILINESTRING((1 0,18 0,19 0))"),
683 "lmli18a"
684 );
685 }
686
687
688
689
690
691
692 #ifndef BOOST_GEOMETRY_TEST_NO_DEGENERATE
BOOST_AUTO_TEST_CASE(test_intersection_l_ml_degenerate)693 BOOST_AUTO_TEST_CASE( test_intersection_l_ml_degenerate )
694 {
695 #ifdef BOOST_GEOMETRY_TEST_DEBUG
696 std::cout << std::endl << std::endl << std::endl;
697 std::cout << "*** LINESTRING / MULTILINESTRING INTERSECTION"
698 << " (DEGENERATE) ***"
699 << std::endl;
700 std::cout << std::endl;
701 #endif
702
703 typedef linestring_type L;
704 typedef multi_linestring_type ML;
705
706 typedef test_intersection_of_geometries<L, ML, ML> tester;
707
708 // the following test cases concern linestrings with duplicate
709 // points and possibly linestrings with zero length.
710
711 // no unique: (3 0) appears twice
712 tester::apply
713 (from_wkt<L>("LINESTRING(0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0)"),
714 from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
715 (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
716 (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
717 (4 0,4 10,4 10))"),
718 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
719 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"),
720 #else
721 from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),(4 0),\
722 (5 0,18 0,19 0,20 0))"),
723 #endif
724 "lmli20a"
725 );
726
727 // no unique: (3 0) appears twice
728 tester::apply
729 (from_wkt<L>("LINESTRING(0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0)"),
730 from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
731 (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
732 (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
733 (4 0,4 0,4 10,4 10))"),
734 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
735 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"),
736 #else
737 from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),(4 0),\
738 (5 0,18 0,19 0,20 0))"),
739 #endif
740 "lmli20b"
741 );
742
743 // no unique: (3 0) appears twice
744 tester::apply
745 (from_wkt<L>("LINESTRING(0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0)"),
746 from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
747 (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
748 (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
749 (30 0,30 0,30 0))"),
750 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
751 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"),
752 #else
753 from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\
754 (5 0,18 0,19 0,20 0),(30 0))"),
755 #endif
756 "lmli20c"
757 );
758
759 // no unique: (3 0) appears twice
760 tester::apply
761 (from_wkt<L>("LINESTRING(0 0,0 0,18 0,18 0,19 0,19 0,19 0,30 0,30 0)"),
762 from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
763 (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
764 (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
765 (30 0,30 0,31 0))"),
766 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
767 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"),
768 #else
769 from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\
770 (5 0,18 0,19 0,20 0),(30 0))"),
771 #endif
772 "lmli20d"
773 );
774 }
775 #endif // BOOST_GEOMETRY_TEST_NO_DEGENERATE
776
777
778
779
BOOST_AUTO_TEST_CASE(test_intersection_multilinestring_linestring)780 BOOST_AUTO_TEST_CASE( test_intersection_multilinestring_linestring )
781 {
782 #ifdef BOOST_GEOMETRY_TEST_DEBUG
783 std::cout << std::endl << std::endl << std::endl;
784 std::cout << "*** MULTILINESTRING / LINESTRING INTERSECTION ***"
785 << std::endl;
786 std::cout << std::endl;
787 #endif
788
789 typedef linestring_type L;
790 typedef multi_linestring_type ML;
791
792 typedef test_intersection_of_geometries<ML, L, ML> tester;
793
794 // the intersection code automatically reverses the order of the
795 // geometries according to the geometry IDs.
796 // all calls below are actually reversed, and internally the
797 // intersection of the linestring with the multi-linestring is
798 // computed.
799
800 // disjoint linestrings
801 tester::apply
802 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
803 from_wkt<L>("LINESTRING(1 1,2 2,4 3)"),
804 from_wkt<ML>("MULTILINESTRING()"),
805 "mlli01"
806 );
807
808 tester::apply
809 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
810 from_wkt<L>("LINESTRING(1 1,2 0,4 0)"),
811 from_wkt<ML>("MULTILINESTRING((2 0,4 0))"),
812 "mlli02"
813 );
814
815 tester::apply
816 (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
817 from_wkt<L>("LINESTRING(-1 -1,1 0,101 0,200 -1)"),
818 from_wkt<ML>("MULTILINESTRING((1 0,101 0))"),
819 "mlli03"
820 );
821
822 tester::apply
823 (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
824 from_wkt<L>("LINESTRING(0 1,1 0,19 0,20 1,19 1,18 0,2 0,\
825 1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1)"),
826 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(18 0,2 0),\
827 (3 0,17 0),(16 0,4 0))"),
828 "mlli04"
829 );
830 }
831
832
833
834
835
836
BOOST_AUTO_TEST_CASE(test_intersection_multilinestring_multilinestring)837 BOOST_AUTO_TEST_CASE( test_intersection_multilinestring_multilinestring )
838 {
839 #ifdef BOOST_GEOMETRY_TEST_DEBUG
840 std::cout << std::endl << std::endl << std::endl;
841 std::cout << "*** MULTILINESTRING / MULTILINESTRING INTERSECTION ***"
842 << std::endl;
843 std::cout << std::endl;
844 #endif
845
846 typedef multi_linestring_type ML;
847
848 typedef test_intersection_of_geometries<ML, ML, ML> tester;
849
850 // disjoint linestrings
851 tester::apply
852 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
853 from_wkt<ML>("MULTILINESTRING((1 1,2 2,4 3),(1 1,2 2,5 3))"),
854 from_wkt<ML>("MULTILINESTRING()"),
855 "mlmli01"
856 );
857
858 tester::apply
859 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
860 from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,4 0))"),
861 from_wkt<ML>("MULTILINESTRING((2 0,4 0),(2 0,4 0))"),
862 from_wkt<ML>("MULTILINESTRING((2 0,4 0),(3 0,4 0))"),
863 "mlmli02"
864 );
865
866 tester::apply
867 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
868 from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),(1 1,3 0,5 0))"),
869 from_wkt<ML>("MULTILINESTRING((2 0,5 0),(2 0,5 0))"),
870 from_wkt<ML>("MULTILINESTRING((2 0,4 0),(3 0,5 0))"),
871 "mlmli03"
872 );
873
874 tester::apply
875 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0))"),
876 from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0))"),
877 from_wkt<ML>("MULTILINESTRING((2 0,4 0),(2 0,4 0))"),
878 from_wkt<ML>("MULTILINESTRING((2 0,4 0))"),
879 "mlmli04"
880 );
881
882 tester::apply
883 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 1),(1 0,7 0),\
884 (10 10,20 10,30 20))"),
885 from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),\
886 (10 20,15 10,25 10,30 15))"),
887 from_wkt<ML>("MULTILINESTRING((2 0,4 0),(2 0,4 0),(15 10,20 10))"),
888 from_wkt<ML>("MULTILINESTRING((2 0,4 0),(15 10,20 10))"),
889 "mlmli05"
890 );
891
892 tester::apply
893 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,20 10),(1 0,7 0),\
894 (10 10,20 10,30 20))"),
895 from_wkt<ML>("MULTILINESTRING((1 1,2 0,4 0),\
896 (-1 -1,0 0,9 0,11 10,12 10,13 3,14 4,15 5),\
897 (10 20,15 10,25 10,30 15))"),
898 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
899 from_wkt<ML>("MULTILINESTRING((0 0,9 0),(13 3,15 5),\
900 (1 0,7 0),(11 10,12 10),(15 10,20 10))"),
901 from_wkt<ML>("MULTILINESTRING((2 0,4 0),(0 0,9 0),(13 3,14 4,15 5),\
902 (11 10,12 10),(15 10,20 10))"),
903 #else
904 from_wkt<ML>("MULTILINESTRING((0 0,9 0),(13 3,15 5),(20 10),\
905 (1 0,7 0),(11 10,12 10),(15 10,20 10))"),
906 from_wkt<ML>("MULTILINESTRING((2 0,4 0),(0 0,9 0),(13 3,14 4,15 5),\
907 (11 10,12 10),(15 10,20 10))"),
908 #endif
909 "mlmli06"
910 );
911
912 tester::apply
913 (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
914 from_wkt<ML>("MULTILINESTRING((-1 -1,1 0,101 0,200 -1))"),
915 from_wkt<ML>("MULTILINESTRING((1 0,101 0))"),
916 "mlmli07"
917 );
918
919 tester::apply
920 (from_wkt<ML>("MULTILINESTRING((-1 1,0 0,101 0))"),
921 from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\
922 (19 -1,20 0,101 0,200 -1))"),
923 from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
924 from_wkt<ML>("MULTILINESTRING((0 0,50 0),(20 0,101 0))"),
925 "mlmli07a"
926 );
927
928 tester::apply
929 (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
930 from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,50 0),\
931 (19 -1,20 0,101 0,200 -1))"),
932 from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
933 from_wkt<ML>("MULTILINESTRING((0 0,50 0),(20 0,101 0))"),
934 "mlmli07b"
935 );
936
937 tester::apply
938 (from_wkt<ML>("MULTILINESTRING((0 0,101 0))"),
939 from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0),\
940 (-1 -1,1 0,101 0,200 -1))"),
941 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
942 from_wkt<ML>("MULTILINESTRING((1 0,101 0))"),
943 #else
944 from_wkt<ML>("MULTILINESTRING((1 0,101 0))"),
945 from_wkt<ML>("MULTILINESTRING((2 0),(1 0,101 0))"),
946 #endif
947 "mlmli08"
948 );
949
950 tester::apply
951 (from_wkt<ML>("MULTILINESTRING((0 0,1 0,2 0.5,3 0,101 0))"),
952 from_wkt<ML>("MULTILINESTRING((0 1,1 1,2 0.5),\
953 (-1 -1,1 0,101 0,200 -1))"),
954 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
955 from_wkt<ML>("MULTILINESTRING((3 0,101 0))"),
956 #else
957 from_wkt<ML>("MULTILINESTRING((1 0),(2 0.5),(3 0,101 0))"),
958 #endif
959 "mlmli09"
960 );
961
962 tester::apply
963 (from_wkt<ML>("MULTILINESTRING((0 0,1 0,1.5 0,2 0.5,3 0,101 0))"),
964 from_wkt<ML>("MULTILINESTRING((0 1,1 1,1 0,2 0.5),\
965 (-1 -1,1 0,101 0,200 -1))"),
966 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
967 from_wkt<ML>("MULTILINESTRING((1 0,1.5 0),(3 0,101 0))"),
968 #else
969 from_wkt<ML>("MULTILINESTRING((1 0,1.5 0),(2 0.5),(3 0,101 0))"),
970 from_wkt<ML>("MULTILINESTRING((1 0),(1 0,1.5 0),(2 0.5),(3 0,101 0))"),
971 #endif
972 "mlmli10"
973 );
974
975 tester::apply
976 (from_wkt<ML>("MULTILINESTRING((0 0,1 1,100 1,101 0),\
977 (0 0,101 0))"),
978 from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1,3 0,4 0,5 1,6 1,\
979 7 0,8 0,9 1,10 1,11 0,12 0,13 1,14 1,15 0),\
980 (-1 -1,1 0,101 0,200 -1))"),
981 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
982 from_wkt<ML>("MULTILINESTRING((1 1,2 1),(5 1,6 1),(9 1,10 1),\
983 (13 1,14 1),(1 0,101 0))"),
984 from_wkt<ML>("MULTILINESTRING((1 1,2 1),(5 1,6 1),(9 1,10 1),\
985 (13 1,14 1),(3 0,4 0),(7 0,8 0),(11 0,12 0),\
986 (1 0,101 0))"),
987 #else
988 from_wkt<ML>("MULTILINESTRING((1 1,2 1),(5 1,6 1),(9 1,10 1),\
989 (13 1,14 1),(101 0),(1 0),(1 0,101 0))"),
990 from_wkt<ML>("MULTILINESTRING((1 0),(1 1,2 1),(5 1,6 1),(9 1,10 1),\
991 (13 1,14 1),(3 0,4 0),(7 0,8 0),(11 0,12 0),(15 0),\
992 (1 0,101 0))"),
993 #endif
994 "mlmli11"
995 );
996
997 tester::apply
998 (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
999 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1000 (1 1,2 0,18 0,19 1),(2 1,3 0,17 0,18 1),\
1001 (3 1,4 0,16 0,17 1))"),
1002 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1003 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(2 0,18 0),(3 0,17 0),\
1004 (4 0,16 0))"),
1005 "mlmli12"
1006 );
1007
1008 tester::apply
1009 (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1010 from_wkt<ML>("MULTILINESTRING((1 0,19 0,20 1),\
1011 (2 0,18 0,19 1),(3 0,17 0,18 1),\
1012 (4 0,16 0,17 1))"),
1013 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1014 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(2 0,18 0),(3 0,17 0),\
1015 (4 0,16 0))"),
1016 "mlmli13"
1017 );
1018
1019 tester::apply
1020 (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1021 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1,19 1,18 0,2 0,\
1022 1 1,2 1,3 0,17 0,18 1,17 1,16 0,4 0,3 1))"),
1023 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1024 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(18 0,2 0),\
1025 (3 0,17 0),(16 0,4 0))"),
1026 "mlmli14"
1027 );
1028
1029 tester::apply
1030 (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1031 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1032 (2 2,4 2,6 0))"),
1033 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1034 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1035 #else
1036 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1037 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(6 0))"),
1038 #endif
1039 "mlmli15"
1040 );
1041
1042 tester::apply
1043 (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1044 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1045 (6 0,4 2,2 2))"),
1046 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1047 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1048 #else
1049 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1050 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(6 0))"),
1051 #endif
1052 "mlmli15a"
1053 );
1054
1055 tester::apply
1056 (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1057 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1058 (2 2,4 2,5 0,6 0))"),
1059 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1060 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(5 0,6 0))"),
1061 "mlmli16"
1062 );
1063
1064 tester::apply
1065 (from_wkt<ML>("MULTILINESTRING((0 0,20 0))"),
1066 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1067 (6 0,5 0,4 2,2 2))"),
1068 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1069 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(6 0,5 0))"),
1070 "mlmli16a"
1071 );
1072
1073 tester::apply
1074 (from_wkt<ML>("MULTILINESTRING((0 0,30 0))"),
1075 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1076 (2 2,4 0,5 2,20 2,25 0))"),
1077 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1078 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1079 #else
1080 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(25 0))"),
1081 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(4 0),(25 0))"),
1082 #endif
1083 "mlmli17"
1084 );
1085
1086 tester::apply
1087 (from_wkt<ML>("MULTILINESTRING((0 0,30 0))"),
1088 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1089 (2 2,4 0,5 2,20 2,25 0,26 2))"),
1090 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1091 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1092 #else
1093 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(25 0))"),
1094 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(4 0),(25 0))"),
1095 #endif
1096 "mlmli17a"
1097 );
1098
1099 tester::apply
1100 (from_wkt<ML>("MULTILINESTRING((0 0,30 0))"),
1101 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1102 (2 2,5 -1,15 2,18 0))"),
1103 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1104 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1105 #else
1106 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1107 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(4 0),\
1108 (8.3333333333333333333 0),(18 0))"),
1109 #endif
1110 "mlmli18"
1111 );
1112
1113 tester::apply
1114 (from_wkt<ML>("MULTILINESTRING((0 0,18 0,19 0,30 0))"),
1115 from_wkt<ML>("MULTILINESTRING((0 1,1 0,19 0,20 1),\
1116 (2 2,5 -1,15 2,18 0))"),
1117 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1118 from_wkt<ML>("MULTILINESTRING((1 0,18 0,19 0))"),
1119 from_wkt<ML>("MULTILINESTRING((1 0,19 0))"),
1120 #else
1121 from_wkt<ML>("MULTILINESTRING((1 0,18 0,19 0))"),
1122 from_wkt<ML>("MULTILINESTRING((1 0,19 0),(4 0),\
1123 (8.3333333333333333333 0),(18 0))"),
1124 #endif
1125 "mlmli18a"
1126 );
1127 }
1128
1129
1130
1131
1132
1133
1134 #ifndef BOOST_GEOMETRY_TEST_NO_DEGENERATE
BOOST_AUTO_TEST_CASE(test_intersection_ml_ml_degenerate)1135 BOOST_AUTO_TEST_CASE( test_intersection_ml_ml_degenerate )
1136 {
1137 #ifdef BOOST_GEOMETRY_TEST_DEBUG
1138 std::cout << std::endl << std::endl << std::endl;
1139 std::cout << "*** MULTILINESTRING / MULTILINESTRING INTERSECTION"
1140 << " (DEGENERATE) ***"
1141 << std::endl;
1142 std::cout << std::endl;
1143 #endif
1144
1145 typedef multi_linestring_type ML;
1146
1147 typedef test_intersection_of_geometries<ML, ML, ML> tester;
1148
1149 // the following test cases concern linestrings with duplicate
1150 // points and possibly linestrings with zero length.
1151
1152 // no unique: (3 0) appears twice
1153 tester::apply
1154 (from_wkt<ML>("MULTILINESTRING((5 5,5 5),(0 0,18 0,18 0,\
1155 19 0,19 0,19 0,30 0),(2 0,2 0),(4 10,4 10))"),
1156 from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
1157 (1 1,2 2),(1 10,1 10,1 0,1 0,1 -10),\
1158 (2 0,2 0),(3 0,3 0,3 0),(0 0,0 10),\
1159 (4 0,4 10),(5 5,5 5))"),
1160 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1161 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"),
1162 from_wkt<ML>("MULTILINESTRING((5 0,20 0))"),
1163 #else
1164 from_wkt<ML>("MULTILINESTRING((5 5),(0 0),(1 0),(2 0),(3 0),\
1165 (4 0),(5 0,18 0,19 0,20 0),(2 0),(4 10))"),
1166 from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(2 0),(3 0),\
1167 (0 0),(4 0),(4 10),(5 5))"),
1168 #endif
1169 "mlmli20a"
1170 );
1171
1172 // no unique: (3 0) appears three times
1173 tester::apply
1174 (from_wkt<ML>("MULTILINESTRING((5 5,5 5),(0 0,0 0,18 0,18 0,\
1175 19 0,19 0,19 0,30 0,30 0),(2 0,2 0),(4 10,4 10))"),
1176 from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
1177 (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
1178 (2 0,2 0),(3 0,3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
1179 (4 0,4 10,4 10),(5 5,5 5))"),
1180 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1181 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"),
1182 from_wkt<ML>("MULTILINESTRING((5 0,20 0))"),
1183 #else
1184 from_wkt<ML>("MULTILINESTRING((5 5),(0 0),(1 0),(2 0),(3 0),(4 0),\
1185 (5 0,18 0,19 0,20 0),(2 0),(4 10))"),
1186 from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(2 0),\
1187 (3 0),(0 0),(4 0),(4 10),(5 5))"),
1188 #endif
1189 "mlmli20aa"
1190 );
1191
1192 // no unique: (3 0) appears twice
1193 tester::apply
1194 (from_wkt<ML>("MULTILINESTRING((5 5,5 5),(0 0,0 0,18 0,18 0,\
1195 19 0,19 0,19 0,30 0,30 0))"),
1196 from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
1197 (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
1198 (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
1199 (4 0,4 0,4 10,4 10),(0 5,15 5))"),
1200 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1201 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"),
1202 from_wkt<ML>("MULTILINESTRING((5 0,20 0))"),
1203 #else
1204 from_wkt<ML>("MULTILINESTRING((5 5),(0 0),(1 0),(2 0),(3 0),(4 0),\
1205 (5 0,18 0,19 0,20 0))"),
1206 from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(3 0),\
1207 (0 0),(4 0),(5 5))"),
1208 #endif
1209 "mlmli20b"
1210 );
1211
1212 // no unique: (3 0) and (30 0) appear twice
1213 tester::apply
1214 (from_wkt<ML>("MULTILINESTRING((0 0,0 0,18 0,18 0,\
1215 19 0,19 0,19 0,30 0,30 0))"),
1216 from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
1217 (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
1218 (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
1219 (30 0,30 0,30 0))"),
1220 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1221 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"),
1222 from_wkt<ML>("MULTILINESTRING((5 0,20 0))"),
1223 #else
1224 from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\
1225 (5 0,18 0,19 0,20 0),(30 0))"),
1226 from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(3 0),\
1227 (0 0),(30 0))"),
1228 #endif
1229 "mlmli20c"
1230 );
1231
1232 // no unique: (3 0) appears twice
1233 tester::apply
1234 (from_wkt<ML>("MULTILINESTRING((0 0,0 0,18 0,18 0,\
1235 19 0,19 0,19 0,30 0,30 0))"),
1236 from_wkt<ML>("MULTILINESTRING((-10 0,-9 0),(0 10,5 0,20 0,20 0,30 10),\
1237 (1 1,1 1,2 2,2 2),(1 10,1 10,1 0,1 0,1 -10),\
1238 (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
1239 (30 0,30 0,31 0))"),
1240 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1241 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,20 0))"),
1242 from_wkt<ML>("MULTILINESTRING((5 0,20 0))"),
1243 #else
1244 from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\
1245 (5 0,18 0,19 0,20 0),(30 0))"),
1246 from_wkt<ML>("MULTILINESTRING((5 0,20 0),(1 0),(2 0),(3 0),\
1247 (0 0),(30 0))"),
1248 #endif
1249 "mlmli20d"
1250 );
1251
1252 tester::apply
1253 (from_wkt<ML>("MULTILINESTRING((0 0,0 0,18 0,18 0,\
1254 19 0,19 0,19 0,30 0,30 0))"),
1255 from_wkt<ML>("MULTILINESTRING((0 10,5 0,20 0,20 0,30 0),\
1256 (1 10,1 10,1 0,1 0,1 -10),\
1257 (2 0,2 0),(3 0,3 0,3 0),(0 0,0 0,0 10,0 10),\
1258 (30 0,30 0,31 0,31 0))"),
1259 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1260 from_wkt<ML>("MULTILINESTRING((5 0,18 0,19 0,30 0))"),
1261 from_wkt<ML>("MULTILINESTRING((5 0,20 0,30 0))"),
1262 #else
1263 from_wkt<ML>("MULTILINESTRING((0 0),(1 0),(2 0),(3 0),\
1264 (5 0,18 0,19 0,30 0),(30 0))"),
1265 from_wkt<ML>("MULTILINESTRING((5 0,20 0,30 0),(1 0),(2 0),(3 0),\
1266 (0 0),(30 0))"),
1267 #endif
1268 "mlmli20e"
1269 );
1270
1271 tester::apply
1272 (from_wkt<ML>("MULTILINESTRING((1 5, -4.3 -.1), (0 6, 8.6 6, 189.7654 5, 1 3, 6 3, 3 5, 6 2.232432, 0 4), (-6 5, 1 2.232432), (3 -1032.34324, 9 0, 189.7654 1, -1.4 3, 3 189.7654, +.3 10.0002, 1 5, 6 3, 5 1, 9 1, 10.0002 -1032.34324, -0.7654 0, 5 3, 3 4), (2.232432 2.232432, 8.6 +.4, 0.0 2.232432, 4 0, -8.8 10.0002), (1 0, 6 6, 7 2, -0 8.4), (-0.7654 3, +.6 8, 4 -1032.34324, 1 6, 0 4), (0 7, 2 1, 8 -7, 7 -.7, -1032.34324 9), (5 0, 10.0002 4, 8 7, 3 3, -8.1 5))"),
1273 from_wkt<ML>("MULTILINESTRING((5 10.0002, 2 7, -0.7654 0, 5 3), (0 -0.7654, 4 10.0002, 4 +.1, -.8 3, -.1 8, 10.0002 2, +.9 -1032.34324))"),
1274 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1275 from_wkt<ML>("MULTILINESTRING((-0.7654 8.88178e-16,-0.7654 0,5 3))"),
1276 #else
1277 from_wkt<ML>("MULTILINESTRING((-0.756651 3.30964),(1.60494 6),\
1278 (2.51371 6),(3.26673 6),(4 6),(8.18862 3.07616),\
1279 (4 3.03179),(1.40063 3.00424),(1.39905 3),\
1280 (4 3),(5 3),(4 4.33333),(4 4.07748),\
1281 (4.41962 2.698),(4 2.82162),(1.59592 3.52985),\
1282 (0.729883 3.78498),(-0.532243 2.83823),\
1283 (0.235887 2.53454),(7.08745 -329.0674155),\
1284 (9.98265 0.00543606),(8.49103 2.89652),\
1285 (4.87386 2.93436),(4 2.9435),(1.38821 2.97083)\
1286 (0.412281 2.98104),(-0.789427 2.99361),\
1287 (0.641699 7.5594),(1.18124 4.9275),\
1288 (1.99437 4.60225),(4 3.8),(9.09826 -100.515944),\
1289 (5.06428 -559.024344),\
1290 (4 3.5),(3.06464 1.99294),(4 1.72377),\
1291 (4 1.38014),(2.50083 1.69957),(1.03214 2.01251),\
1292 (0.72677 2.07758),(0.10749 2.20953),\
1293 (0.0954852 2.17914),(0.92255 1.71755),\
1294 (1.70073 1.28324),(3.43534 0.441146),\
1295 (2.09493 1.48836),(1.12031 2.2498),\
1296 (0.358522 2.84496),(-0.705343 3.67612),\
1297 (2.06005 1.27206),(2.3516 1.62191),(4 3.6),\
1298 (5.09496 4.91395),(6.47672 4.09311),(4 4.74286),\
1299 (2.54193 6.07595),(1.87562 6.68515),\
1300 (1.43457 7.08839),(0.502294 7.64221),\
1301 (0.601362 7.58336),(0.614728 3.49349),\
1302 (0.619143 2.1426),(0.623165 0.911787),\
1303 (0.623783 0.722855),(3.16036 -775.427199),\
1304 (3.23365 -767.0972558),(1.01466 0.926246),\
1305 (1.01183 1.90535),(1.01168 1.95744),\
1306 (1.00439 4.47984),(0.91526 4.25422),\
1307 (1.36441 2.90677),(1.8713 1.38609),\
1308 (1.87531 1.37408),(0.0484053 -0.635122),\
1309 (8.5655 2.85228),(5.26567 4.81254),(4 3.8),\
1310 (1.4995 3.27036),(0.591231 3.43401),\
1311 (-0.706503 3.66784),\
1312 (-0.7654 8.88178e-16,-0.7654 0,5 3))"),
1313 from_wkt<ML>("MULTILINESTRING((1.87562 6.68515),(1.60494 6),\
1314 (1.18124 4.9275),(1.00439 4.47984),(0.91526 4.25422),\
1315 (0.729883 3.78498),(0.614728 3.49349),\
1316 (0.591231 3.43401),(0.412281 2.98104),\
1317 (0.358522 2.84496),(0.235887 2.53454),\
1318 (0.10749 2.20953),(0.0954852 2.17914),\
1319 (5 3),(0.0484053 -0.635122),(0.535994 0.677175),\
1320 (0.623165 0.911787),(0.92255 1.71755),\
1321 (1.01168 1.95744),(1.03214 2.01251),\
1322 (1.12031 2.2498),(1.36441 2.90677),\
1323 (1.38821 2.97083),(1.39905 3),(1.40063 3.00424),\
1324 (1.4995 3.27036),(1.59592 3.52985),\
1325 (1.99437 4.60225),(2.51371 6),(2.54193 6.07595),\
1326 (4 6),(4 4.74286),(4 4.33333),(4 4.07748),(4 3.8),\
1327 (4 3.8),(4 3.6),(4 3.5),(4 3.03179),(4 3),\
1328 (4 2.9435),(4 2.82162),(4 2.47965),(4 1.72377),\
1329 (4 1.38014),(3.43534 0.441146),(2.06005 1.27206),\
1330 (1.88383 1.37852),(1.8713 1.38609),\
1331 (1.01183 1.90535),(0.72677 2.07758),\
1332 (0.619143 2.1426),(-0.532243 2.83823),\
1333 (-0.789427 2.99361),(-0.756651 3.30964),\
1334 (-0.706503 3.66784),(-0.705343 3.67612),\
1335 (0.502294 7.64221),(0.601362 7.58336),\
1336 (0.641699 7.5594),(1.43457 7.08839),\
1337 (3.26673 6),(5.09496 4.91395),(5.26567 4.81254),\
1338 (6.47672 4.09311),(8.18862 3.07616),\
1339 (8.49103 2.89652),(8.5655 2.85228),\
1340 (9.98265 0.00543606),(9.09826 -100.515944),\
1341 (7.08745 -329.0674155),(5.06428 -559.024344),\
1342 (3.23365 -767.0972558),(3.16036 -775.427199),\
1343 (-0.7654 8.88178e-16,-0.7654 0,5 3))"),
1344 #endif
1345 "mlmli21",
1346 1e-4
1347 );
1348 }
1349 #endif // BOOST_GEOMETRY_TEST_NO_DEGENERATE
1350
1351
1352
1353
BOOST_AUTO_TEST_CASE(test_intersection_ml_ml_spikes)1354 BOOST_AUTO_TEST_CASE( test_intersection_ml_ml_spikes )
1355 {
1356 #ifdef BOOST_GEOMETRY_TEST_DEBUG
1357 std::cout << std::endl << std::endl << std::endl;
1358 std::cout << "*** MULTILINESTRING / MULTILINESTRING INTERSECTION"
1359 << " (WITH SPIKES) ***"
1360 << std::endl;
1361 std::cout << std::endl;
1362 #endif
1363
1364 typedef multi_linestring_type ML;
1365
1366 typedef test_intersection_of_geometries<ML, ML, ML> tester;
1367
1368 // the following test cases concern linestrings with spikes
1369
1370 tester::apply
1371 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1372 from_wkt<ML>("MULTILINESTRING((1 0,9 0,5 0))"),
1373 from_wkt<ML>("MULTILINESTRING((1 0,9 0))"),
1374 from_wkt<ML>("MULTILINESTRING((1 0,9 0,5 0))"),
1375 "mlmli-spikes-01"
1376 );
1377
1378 tester::apply
1379 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1380 from_wkt<ML>("MULTILINESTRING((9 0,1 0,5 0))"),
1381 from_wkt<ML>("MULTILINESTRING((1 0,9 0))"),
1382 from_wkt<ML>("MULTILINESTRING((9 0,1 0,5 0))"),
1383 "mlmli-spikes-02"
1384 );
1385
1386 tester::apply
1387 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1388 from_wkt<ML>("MULTILINESTRING((1 0,9 0,2 0,8 0,3 0,7 0,4 0,5 0))"),
1389 from_wkt<ML>("MULTILINESTRING((1 0,9 0))"),
1390 from_wkt<ML>("MULTILINESTRING((1 0,9 0,2 0,8 0,3 0,7 0,4 0,5 0))"),
1391 "mlmli-spikes-03"
1392 );
1393
1394 tester::apply
1395 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1396 from_wkt<ML>("MULTILINESTRING((1 0,3 0,2 0,4 0,3 0,5 0,4 0,6 0,\
1397 5 0,7 0,6 0,8 0,7 0,9 0))"),
1398 from_wkt<ML>("MULTILINESTRING((1 0,9 0))"),
1399 from_wkt<ML>("MULTILINESTRING((1 0,3 0,2 0,4 0,3 0,5 0,4 0,6 0,\
1400 5 0,7 0,6 0,8 0,7 0,9 0))"),
1401 "mlmli-spikes-04"
1402 );
1403
1404 tester::apply
1405 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1406 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),\
1407 (9 1,9 0,9 2))"),
1408 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1409 from_wkt<ML>("MULTILINESTRING((1 0,6 0),(7 0,8 0))"),
1410 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0))"),
1411 #else
1412 from_wkt<ML>("MULTILINESTRING((1 0,6 0),(7 0,8 0),(9 0))"),
1413 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),(9 0))"),
1414 #endif
1415 "mlmli-spikes-05"
1416 );
1417
1418 tester::apply
1419 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1420 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),\
1421 (9 0,9 2,9 1))"),
1422 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1423 from_wkt<ML>("MULTILINESTRING((1 0,6 0),(7 0,8 0))"),
1424 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0))"),
1425 #else
1426 from_wkt<ML>("MULTILINESTRING((1 0,6 0),(7 0,8 0),(9 0))"),
1427 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,7 0),(9 0))"),
1428 #endif
1429 "mlmli-spikes-05a"
1430 );
1431
1432 tester::apply
1433 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1434 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(9 0,6 0,8 0),\
1435 (11 0,8 0,12 0))"),
1436 from_wkt<ML>("MULTILINESTRING((1 0,6 0),(6 0,10 0))"),
1437 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(9 0,6 0,8 0),\
1438 (10 0,8 0,10 0))"),
1439 "mlmli-spikes-06"
1440 );
1441
1442 tester::apply
1443 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1444 from_wkt<ML>("MULTILINESTRING((-1 0,0 0,-2 0),(11 0,10 0,12 0))"),
1445 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1446 from_wkt<ML>("MULTILINESTRING()"),
1447 #else
1448 from_wkt<ML>("MULTILINESTRING((0 0),(10 0))"),
1449 #endif
1450 "mlmli-spikes-07"
1451 );
1452
1453 tester::apply
1454 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1455 from_wkt<ML>("MULTILINESTRING((-1 -1,0 0,-2 -2),(11 1,10 0,12 2))"),
1456 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1457 from_wkt<ML>("MULTILINESTRING()"),
1458 #else
1459 from_wkt<ML>("MULTILINESTRING((0 0),(10 0))"),
1460 #endif
1461 "mlmli-spikes-07a"
1462 );
1463
1464 tester::apply
1465 (from_wkt<ML>("MULTILINESTRING((0 0,10 0))"),
1466 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(11 0,10 0,12 0),\
1467 (7 5,7 0,8 0,6.5 0,8.5 0,8.5 5))"),
1468 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1469 from_wkt<ML>("MULTILINESTRING((1 0,6 0),(6.5 0,8.5 0))"),
1470 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,6.5 0,8.5 0))"),
1471 #else
1472 from_wkt<ML>("MULTILINESTRING((1 0,6 0),(6.5 0,8.5 0),(10 0))"),
1473 from_wkt<ML>("MULTILINESTRING((1 0,6 0,5 0),(7 0,8 0,6.5 0,8.5 0),(10 0))"),
1474 #endif
1475 "mlmli-spikes-08"
1476 );
1477
1478 // now the first geometry has a spike
1479 tester::apply
1480 (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"),
1481 from_wkt<ML>("MULTILINESTRING((1 0,8 0))"),
1482 from_wkt<ML>("MULTILINESTRING((1 0,7 0,4 0,8 0))"),
1483 from_wkt<ML>("MULTILINESTRING((1 0,8 0))"),
1484 "mlmli-spikes-09"
1485 );
1486
1487 tester::apply
1488 (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"),
1489 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0))"),
1490 from_wkt<ML>("MULTILINESTRING((0 0,1 0),(9 0,10 0))"),
1491 "mlmli-spikes-09a"
1492 );
1493
1494 tester::apply
1495 (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"),
1496 from_wkt<ML>("MULTILINESTRING((0 0,5 0),(9 0,10 0))"),
1497 from_wkt<ML>("MULTILINESTRING((0 0,5 0),(5 0,4 0,5 0),(9 0,10 0))"),
1498 from_wkt<ML>("MULTILINESTRING((0 0,5 0),(9 0,10 0))"),
1499 "mlmli-spikes-09b"
1500 );
1501
1502 tester::apply
1503 (from_wkt<ML>("MULTILINESTRING((0 0,7 0,4 0,10 0))"),
1504 from_wkt<ML>("MULTILINESTRING((0 0,5 0),(6 0,10 0))"),
1505 from_wkt<ML>("MULTILINESTRING((0 0,5 0),(6 0,7 0,6 0),(5 0,4 0,5 0),\
1506 (6 0,10 0))"),
1507 from_wkt<ML>("MULTILINESTRING((0 0,5 0),(6 0,10 0))"),
1508 "mlmli-spikes-09c"
1509 );
1510
1511 tester::apply
1512 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1513 from_wkt<ML>("MULTILINESTRING((1 0,8 0))"),
1514 from_wkt<ML>("MULTILINESTRING((1 0,8 0),(8 0,5 0))"),
1515 from_wkt<ML>("MULTILINESTRING((1 0,8 0))"),
1516 "mlmli-spikes-10"
1517 );
1518
1519 tester::apply
1520 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1521 from_wkt<ML>("MULTILINESTRING((1 0,8 0,4 0),(2 0,9 0,5 0))"),
1522 from_wkt<ML>("MULTILINESTRING((1 0,9 0),(9 0,5 0))"),
1523 from_wkt<ML>("MULTILINESTRING((1 0,8 0,4 0),(2 0,9 0,5 0))"),
1524 "mlmli-spikes-11"
1525 );
1526
1527 tester::apply
1528 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1529 from_wkt<ML>("MULTILINESTRING((11 1,10 0,12 2))"),
1530 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1531 from_wkt<ML>("MULTILINESTRING()"),
1532 #else
1533 from_wkt<ML>("MULTILINESTRING((10 0))"),
1534 #endif
1535 "mlmli-spikes-12"
1536 );
1537
1538 tester::apply
1539 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1540 from_wkt<ML>("MULTILINESTRING((11 -1,10 0,12 -2))"),
1541 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1542 from_wkt<ML>("MULTILINESTRING()"),
1543 #else
1544 from_wkt<ML>("MULTILINESTRING((10 0))"),
1545 #endif
1546 "mlmli-spikes-12a"
1547 );
1548
1549 tester::apply
1550 (from_wkt<ML>("MULTILINESTRING((0 0,10 0,5 0))"),
1551 from_wkt<ML>("MULTILINESTRING((11 0,10 0,12 0))"),
1552 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1553 from_wkt<ML>("MULTILINESTRING()"),
1554 #else
1555 from_wkt<ML>("MULTILINESTRING((10 0))"),
1556 #endif
1557 "mlmli-spikes-13"
1558 );
1559
1560 // the following three tests have been discussed with Adam
1561 tester::apply
1562 (from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"),
1563 from_wkt<ML>("MULTILINESTRING((1 2,1 1,1 2))"),
1564 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1565 from_wkt<ML>("MULTILINESTRING()"),
1566 #else
1567 from_wkt<ML>("MULTILINESTRING((1 1))"),
1568 #endif
1569 "mlmli-spikes-14"
1570 );
1571
1572 tester::apply
1573 (from_wkt<ML>("MULTILINESTRING((0 0,1 0,0 0))"),
1574 from_wkt<ML>("MULTILINESTRING((2 0,1 0,2 0))"),
1575 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1576 from_wkt<ML>("MULTILINESTRING()"),
1577 #else
1578 from_wkt<ML>("MULTILINESTRING((1 0))"),
1579 #endif
1580 "mlmli-spikes-15"
1581 );
1582
1583 tester::apply
1584 (from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"),
1585 from_wkt<ML>("MULTILINESTRING((2 0,1 1,2 0))"),
1586 #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
1587 from_wkt<ML>("MULTILINESTRING()"),
1588 #else
1589 from_wkt<ML>("MULTILINESTRING((1 1))"),
1590 #endif
1591 "mlmli-spikes-16"
1592 );
1593
1594 tester::apply
1595 (from_wkt<ML>("MULTILINESTRING((1 0,1 1,2 1))"),
1596 from_wkt<ML>("MULTILINESTRING((2 1,1 1,2 1))"),
1597 from_wkt<ML>("MULTILINESTRING((1 1,2 1))"),
1598 from_wkt<ML>("MULTILINESTRING((2 1,1 1,2 1))"),
1599 "mlmli-spikes-17"
1600 );
1601
1602 // test cases sent by Adam on the mailing list (equal slikes)
1603 tester::apply
1604 (from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"),
1605 from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"),
1606 from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"),
1607 "mlmli-spikes-18"
1608 );
1609
1610 tester::apply
1611 (from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"),
1612 from_wkt<ML>("MULTILINESTRING((1 1,0 0,1 1))"),
1613 from_wkt<ML>("MULTILINESTRING((0 0,1 1,0 0))"),
1614 from_wkt<ML>("MULTILINESTRING((1 1,0 0,1 1))"),
1615 "mlmli-spikes-19"
1616 );
1617 }
1618