]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
f67539c2 TL |
5 | // This file was modified by Oracle on 2014, 2020. |
6 | // Modifications copyright (c) 2014-2020, Oracle and/or its affiliates. | |
7c673cae FG |
7 | |
8 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
9 | ||
10 | // Use, modification and distribution is subject to the Boost Software License, | |
11 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
12 | // http://www.boost.org/LICENSE_1_0.txt) | |
13 | ||
14 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP | |
16 | ||
20effc67 TL |
17 | #include <type_traits> |
18 | ||
7c673cae FG |
19 | #include <boost/geometry/core/closure.hpp> |
20 | #include <boost/geometry/core/geometry_id.hpp> | |
7c673cae FG |
21 | #include <boost/geometry/core/point_order.hpp> |
22 | #include <boost/geometry/core/tags.hpp> | |
23 | #include <boost/geometry/geometries/concepts/check.hpp> | |
24 | ||
25 | // TODO: those headers probably may be removed | |
26 | #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp> | |
27 | #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp> | |
28 | #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> | |
29 | #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp> | |
30 | #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp> | |
31 | #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp> | |
32 | #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp> | |
33 | ||
34 | #include <boost/geometry/algorithms/detail/intersection/interface.hpp> | |
35 | ||
36 | #include <boost/geometry/algorithms/covered_by.hpp> | |
37 | #include <boost/geometry/algorithms/envelope.hpp> | |
38 | #include <boost/geometry/algorithms/num_points.hpp> | |
39 | ||
40 | ||
41 | namespace boost { namespace geometry | |
42 | { | |
43 | ||
44 | #ifndef DOXYGEN_NO_DETAIL | |
45 | namespace detail { namespace intersection | |
46 | { | |
47 | ||
48 | ||
49 | template <typename PointOut> | |
50 | struct intersection_multi_linestring_multi_linestring_point | |
51 | { | |
52 | template | |
53 | < | |
54 | typename MultiLinestring1, typename MultiLinestring2, | |
55 | typename RobustPolicy, | |
56 | typename OutputIterator, typename Strategy | |
57 | > | |
58 | static inline OutputIterator apply(MultiLinestring1 const& ml1, | |
59 | MultiLinestring2 const& ml2, | |
60 | RobustPolicy const& robust_policy, | |
61 | OutputIterator out, | |
62 | Strategy const& strategy) | |
63 | { | |
64 | // Note, this loop is quadratic w.r.t. number of linestrings per input. | |
65 | // Future Enhancement: first do the sections of each, then intersect. | |
66 | for (typename boost::range_iterator | |
67 | < | |
68 | MultiLinestring1 const | |
69 | >::type it1 = boost::begin(ml1); | |
70 | it1 != boost::end(ml1); | |
71 | ++it1) | |
72 | { | |
73 | for (typename boost::range_iterator | |
74 | < | |
75 | MultiLinestring2 const | |
76 | >::type it2 = boost::begin(ml2); | |
77 | it2 != boost::end(ml2); | |
78 | ++it2) | |
79 | { | |
80 | out = intersection_linestring_linestring_point<PointOut> | |
81 | ::apply(*it1, *it2, robust_policy, out, strategy); | |
82 | } | |
83 | } | |
84 | ||
85 | return out; | |
86 | } | |
87 | }; | |
88 | ||
89 | ||
90 | template <typename PointOut> | |
91 | struct intersection_linestring_multi_linestring_point | |
92 | { | |
93 | template | |
94 | < | |
95 | typename Linestring, typename MultiLinestring, | |
96 | typename RobustPolicy, | |
97 | typename OutputIterator, typename Strategy | |
98 | > | |
99 | static inline OutputIterator apply(Linestring const& linestring, | |
100 | MultiLinestring const& ml, | |
101 | RobustPolicy const& robust_policy, | |
102 | OutputIterator out, | |
103 | Strategy const& strategy) | |
104 | { | |
105 | for (typename boost::range_iterator | |
106 | < | |
107 | MultiLinestring const | |
108 | >::type it = boost::begin(ml); | |
109 | it != boost::end(ml); | |
110 | ++it) | |
111 | { | |
112 | out = intersection_linestring_linestring_point<PointOut> | |
113 | ::apply(linestring, *it, robust_policy, out, strategy); | |
114 | } | |
115 | ||
116 | return out; | |
117 | } | |
118 | }; | |
119 | ||
120 | ||
121 | // This loop is quite similar to the loop above, but beacuse the iterator | |
122 | // is second (above) or first (below) argument, it is not trivial to merge them. | |
123 | template | |
124 | < | |
125 | bool ReverseAreal, | |
126 | typename LineStringOut, | |
f67539c2 TL |
127 | overlay_type OverlayType, |
128 | bool FollowIsolatedPoints | |
7c673cae FG |
129 | > |
130 | struct intersection_of_multi_linestring_with_areal | |
131 | { | |
132 | template | |
133 | < | |
134 | typename MultiLinestring, typename Areal, | |
135 | typename RobustPolicy, | |
136 | typename OutputIterator, typename Strategy | |
137 | > | |
138 | static inline OutputIterator apply(MultiLinestring const& ml, Areal const& areal, | |
139 | RobustPolicy const& robust_policy, | |
140 | OutputIterator out, | |
141 | Strategy const& strategy) | |
142 | { | |
143 | for (typename boost::range_iterator | |
144 | < | |
145 | MultiLinestring const | |
146 | >::type it = boost::begin(ml); | |
147 | it != boost::end(ml); | |
148 | ++it) | |
149 | { | |
150 | out = intersection_of_linestring_with_areal | |
151 | < | |
f67539c2 | 152 | ReverseAreal, LineStringOut, OverlayType, FollowIsolatedPoints |
7c673cae FG |
153 | >::apply(*it, areal, robust_policy, out, strategy); |
154 | } | |
155 | ||
156 | return out; | |
157 | ||
158 | } | |
159 | }; | |
160 | ||
161 | // This one calls the one above with reversed arguments | |
162 | template | |
163 | < | |
164 | bool ReverseAreal, | |
165 | typename LineStringOut, | |
f67539c2 TL |
166 | overlay_type OverlayType, |
167 | bool FollowIsolatedPoints | |
7c673cae FG |
168 | > |
169 | struct intersection_of_areal_with_multi_linestring | |
170 | { | |
171 | template | |
172 | < | |
173 | typename Areal, typename MultiLinestring, | |
174 | typename RobustPolicy, | |
175 | typename OutputIterator, typename Strategy | |
176 | > | |
177 | static inline OutputIterator apply(Areal const& areal, MultiLinestring const& ml, | |
178 | RobustPolicy const& robust_policy, | |
179 | OutputIterator out, | |
180 | Strategy const& strategy) | |
181 | { | |
182 | return intersection_of_multi_linestring_with_areal | |
183 | < | |
f67539c2 | 184 | ReverseAreal, LineStringOut, OverlayType, FollowIsolatedPoints |
7c673cae FG |
185 | >::apply(ml, areal, robust_policy, out, strategy); |
186 | } | |
187 | }; | |
188 | ||
189 | ||
190 | ||
191 | template <typename LinestringOut> | |
192 | struct clip_multi_linestring | |
193 | { | |
194 | template | |
195 | < | |
196 | typename MultiLinestring, typename Box, | |
197 | typename RobustPolicy, | |
198 | typename OutputIterator, typename Strategy | |
199 | > | |
200 | static inline OutputIterator apply(MultiLinestring const& multi_linestring, | |
201 | Box const& box, | |
202 | RobustPolicy const& robust_policy, | |
203 | OutputIterator out, Strategy const& ) | |
204 | { | |
205 | typedef typename point_type<LinestringOut>::type point_type; | |
206 | strategy::intersection::liang_barsky<Box, point_type> lb_strategy; | |
207 | for (typename boost::range_iterator<MultiLinestring const>::type it | |
208 | = boost::begin(multi_linestring); | |
209 | it != boost::end(multi_linestring); ++it) | |
210 | { | |
211 | out = detail::intersection::clip_range_with_box | |
212 | <LinestringOut>(box, *it, robust_policy, out, lb_strategy); | |
213 | } | |
214 | return out; | |
215 | } | |
216 | }; | |
217 | ||
218 | ||
219 | }} // namespace detail::intersection | |
220 | #endif // DOXYGEN_NO_DETAIL | |
221 | ||
222 | ||
223 | #ifndef DOXYGEN_NO_DISPATCH | |
224 | namespace dispatch | |
225 | { | |
226 | ||
227 | ||
228 | // Linear | |
229 | template | |
230 | < | |
231 | typename MultiLinestring1, typename MultiLinestring2, | |
232 | typename GeometryOut, | |
233 | overlay_type OverlayType, | |
f67539c2 | 234 | bool Reverse1, bool Reverse2 |
7c673cae FG |
235 | > |
236 | struct intersection_insert | |
237 | < | |
238 | MultiLinestring1, MultiLinestring2, | |
239 | GeometryOut, | |
240 | OverlayType, | |
f67539c2 | 241 | Reverse1, Reverse2, |
7c673cae | 242 | multi_linestring_tag, multi_linestring_tag, point_tag, |
b32b8144 | 243 | linear_tag, linear_tag, pointlike_tag |
7c673cae FG |
244 | > : detail::intersection::intersection_multi_linestring_multi_linestring_point |
245 | < | |
246 | GeometryOut | |
247 | > | |
248 | {}; | |
249 | ||
250 | ||
251 | template | |
252 | < | |
253 | typename Linestring, typename MultiLinestring, | |
254 | typename GeometryOut, | |
255 | overlay_type OverlayType, | |
f67539c2 | 256 | bool Reverse1, bool Reverse2 |
7c673cae FG |
257 | > |
258 | struct intersection_insert | |
259 | < | |
260 | Linestring, MultiLinestring, | |
261 | GeometryOut, | |
262 | OverlayType, | |
f67539c2 | 263 | Reverse1, Reverse2, |
7c673cae | 264 | linestring_tag, multi_linestring_tag, point_tag, |
b32b8144 | 265 | linear_tag, linear_tag, pointlike_tag |
7c673cae FG |
266 | > : detail::intersection::intersection_linestring_multi_linestring_point |
267 | < | |
268 | GeometryOut | |
269 | > | |
270 | {}; | |
271 | ||
272 | ||
273 | template | |
274 | < | |
275 | typename MultiLinestring, typename Box, | |
276 | typename GeometryOut, | |
277 | overlay_type OverlayType, | |
f67539c2 | 278 | bool Reverse1, bool Reverse2 |
7c673cae FG |
279 | > |
280 | struct intersection_insert | |
281 | < | |
282 | MultiLinestring, Box, | |
283 | GeometryOut, | |
284 | OverlayType, | |
f67539c2 | 285 | Reverse1, Reverse2, |
7c673cae | 286 | multi_linestring_tag, box_tag, linestring_tag, |
b32b8144 | 287 | linear_tag, areal_tag, linear_tag |
7c673cae FG |
288 | > : detail::intersection::clip_multi_linestring |
289 | < | |
290 | GeometryOut | |
291 | > | |
292 | {}; | |
293 | ||
294 | ||
295 | template | |
296 | < | |
297 | typename Linestring, typename MultiPolygon, | |
298 | typename GeometryOut, | |
299 | overlay_type OverlayType, | |
f67539c2 | 300 | bool ReverseLinestring, bool ReverseMultiPolygon |
7c673cae FG |
301 | > |
302 | struct intersection_insert | |
303 | < | |
304 | Linestring, MultiPolygon, | |
305 | GeometryOut, | |
306 | OverlayType, | |
f67539c2 | 307 | ReverseLinestring, ReverseMultiPolygon, |
7c673cae | 308 | linestring_tag, multi_polygon_tag, linestring_tag, |
b32b8144 | 309 | linear_tag, areal_tag, linear_tag |
7c673cae FG |
310 | > : detail::intersection::intersection_of_linestring_with_areal |
311 | < | |
312 | ReverseMultiPolygon, | |
313 | GeometryOut, | |
f67539c2 TL |
314 | OverlayType, |
315 | false | |
7c673cae FG |
316 | > |
317 | {}; | |
318 | ||
319 | ||
320 | // Derives from areal/mls because runtime arguments are in that order. | |
321 | // areal/mls reverses it itself to mls/areal | |
322 | template | |
323 | < | |
324 | typename Polygon, typename MultiLinestring, | |
325 | typename GeometryOut, | |
326 | overlay_type OverlayType, | |
f67539c2 | 327 | bool ReversePolygon, bool ReverseMultiLinestring |
7c673cae FG |
328 | > |
329 | struct intersection_insert | |
330 | < | |
331 | Polygon, MultiLinestring, | |
332 | GeometryOut, | |
333 | OverlayType, | |
f67539c2 | 334 | ReversePolygon, ReverseMultiLinestring, |
7c673cae | 335 | polygon_tag, multi_linestring_tag, linestring_tag, |
b32b8144 | 336 | areal_tag, linear_tag, linear_tag |
7c673cae FG |
337 | > : detail::intersection::intersection_of_areal_with_multi_linestring |
338 | < | |
339 | ReversePolygon, | |
340 | GeometryOut, | |
f67539c2 TL |
341 | OverlayType, |
342 | false | |
7c673cae FG |
343 | > |
344 | {}; | |
345 | ||
346 | ||
347 | template | |
348 | < | |
349 | typename MultiLinestring, typename Ring, | |
350 | typename GeometryOut, | |
351 | overlay_type OverlayType, | |
f67539c2 | 352 | bool ReverseMultiLinestring, bool ReverseRing |
7c673cae FG |
353 | > |
354 | struct intersection_insert | |
355 | < | |
356 | MultiLinestring, Ring, | |
357 | GeometryOut, | |
358 | OverlayType, | |
f67539c2 | 359 | ReverseMultiLinestring, ReverseRing, |
7c673cae | 360 | multi_linestring_tag, ring_tag, linestring_tag, |
b32b8144 | 361 | linear_tag, areal_tag, linear_tag |
7c673cae FG |
362 | > : detail::intersection::intersection_of_multi_linestring_with_areal |
363 | < | |
364 | ReverseRing, | |
365 | GeometryOut, | |
f67539c2 TL |
366 | OverlayType, |
367 | false | |
7c673cae FG |
368 | > |
369 | {}; | |
370 | ||
371 | template | |
372 | < | |
373 | typename MultiLinestring, typename Polygon, | |
374 | typename GeometryOut, | |
375 | overlay_type OverlayType, | |
f67539c2 | 376 | bool ReverseMultiLinestring, bool ReversePolygon |
7c673cae FG |
377 | > |
378 | struct intersection_insert | |
379 | < | |
380 | MultiLinestring, Polygon, | |
381 | GeometryOut, | |
382 | OverlayType, | |
f67539c2 | 383 | ReverseMultiLinestring, ReversePolygon, |
7c673cae | 384 | multi_linestring_tag, polygon_tag, linestring_tag, |
b32b8144 | 385 | linear_tag, areal_tag, linear_tag |
7c673cae FG |
386 | > : detail::intersection::intersection_of_multi_linestring_with_areal |
387 | < | |
f67539c2 | 388 | ReversePolygon, |
7c673cae | 389 | GeometryOut, |
f67539c2 TL |
390 | OverlayType, |
391 | false | |
7c673cae FG |
392 | > |
393 | {}; | |
394 | ||
395 | ||
396 | ||
397 | template | |
398 | < | |
399 | typename MultiLinestring, typename MultiPolygon, | |
400 | typename GeometryOut, | |
401 | overlay_type OverlayType, | |
f67539c2 | 402 | bool ReverseMultiLinestring, bool ReverseMultiPolygon |
7c673cae FG |
403 | > |
404 | struct intersection_insert | |
405 | < | |
406 | MultiLinestring, MultiPolygon, | |
407 | GeometryOut, | |
408 | OverlayType, | |
f67539c2 | 409 | ReverseMultiLinestring, ReverseMultiPolygon, |
7c673cae | 410 | multi_linestring_tag, multi_polygon_tag, linestring_tag, |
b32b8144 | 411 | linear_tag, areal_tag, linear_tag |
7c673cae FG |
412 | > : detail::intersection::intersection_of_multi_linestring_with_areal |
413 | < | |
414 | ReverseMultiPolygon, | |
415 | GeometryOut, | |
f67539c2 TL |
416 | OverlayType, |
417 | false | |
418 | > | |
419 | {}; | |
420 | ||
421 | ||
422 | ||
423 | template | |
424 | < | |
425 | typename MultiLinestring, typename Ring, | |
426 | typename TupledOut, | |
427 | overlay_type OverlayType, | |
428 | bool ReverseMultiLinestring, bool ReverseRing | |
429 | > | |
430 | struct intersection_insert | |
431 | < | |
432 | MultiLinestring, Ring, | |
433 | TupledOut, | |
434 | OverlayType, | |
435 | ReverseMultiLinestring, ReverseRing, | |
20effc67 TL |
436 | multi_linestring_tag, ring_tag, detail::tupled_output_tag, |
437 | linear_tag, areal_tag, detail::tupled_output_tag | |
f67539c2 TL |
438 | > : detail::intersection::intersection_of_multi_linestring_with_areal |
439 | < | |
440 | ReverseRing, | |
441 | TupledOut, | |
442 | OverlayType, | |
443 | true | |
444 | > | |
20effc67 TL |
445 | , detail::expect_output |
446 | < | |
447 | MultiLinestring, Ring, TupledOut, | |
448 | // NOTE: points can be the result only in case of intersection. | |
449 | // TODO: union should require L and A | |
450 | std::conditional_t | |
451 | < | |
452 | (OverlayType == overlay_intersection), | |
453 | point_tag, | |
454 | void | |
455 | >, | |
456 | linestring_tag | |
457 | > | |
f67539c2 TL |
458 | {}; |
459 | ||
460 | ||
461 | template | |
462 | < | |
463 | typename MultiLinestring, typename Polygon, | |
464 | typename TupledOut, | |
465 | overlay_type OverlayType, | |
466 | bool ReverseMultiLinestring, bool ReversePolygon | |
467 | > | |
468 | struct intersection_insert | |
469 | < | |
470 | MultiLinestring, Polygon, | |
471 | TupledOut, | |
472 | OverlayType, | |
473 | ReverseMultiLinestring, ReversePolygon, | |
20effc67 TL |
474 | multi_linestring_tag, polygon_tag, detail::tupled_output_tag, |
475 | linear_tag, areal_tag, detail::tupled_output_tag | |
f67539c2 TL |
476 | > : detail::intersection::intersection_of_multi_linestring_with_areal |
477 | < | |
478 | ReversePolygon, | |
479 | TupledOut, | |
480 | OverlayType, | |
481 | true | |
482 | > | |
20effc67 TL |
483 | , detail::expect_output |
484 | < | |
485 | MultiLinestring, Polygon, TupledOut, | |
486 | // NOTE: points can be the result only in case of intersection. | |
487 | // TODO: union should require L and A | |
488 | std::conditional_t | |
489 | < | |
490 | (OverlayType == overlay_intersection), | |
491 | point_tag, | |
492 | void | |
493 | >, | |
494 | linestring_tag | |
495 | > | |
f67539c2 TL |
496 | {}; |
497 | ||
498 | template | |
499 | < | |
500 | typename Polygon, typename MultiLinestring, | |
501 | typename TupledOut, | |
502 | overlay_type OverlayType, | |
503 | bool ReversePolygon, bool ReverseMultiLinestring | |
504 | > | |
505 | struct intersection_insert | |
506 | < | |
507 | Polygon, MultiLinestring, | |
508 | TupledOut, | |
509 | OverlayType, | |
510 | ReversePolygon, ReverseMultiLinestring, | |
20effc67 TL |
511 | polygon_tag, multi_linestring_tag, detail::tupled_output_tag, |
512 | areal_tag, linear_tag, detail::tupled_output_tag | |
f67539c2 TL |
513 | > : detail::intersection::intersection_of_areal_with_multi_linestring |
514 | < | |
515 | ReversePolygon, | |
516 | TupledOut, | |
517 | OverlayType, | |
518 | true | |
519 | > | |
20effc67 TL |
520 | , detail::expect_output |
521 | < | |
522 | Polygon, MultiLinestring, TupledOut, | |
523 | // NOTE: points can be the result only in case of intersection. | |
524 | // TODO: union should require L and A | |
525 | // TODO: in general the result of difference should depend on the first argument | |
526 | // but this specialization calls L/A in reality so the first argument is linear. | |
527 | // So expect only L for difference? | |
528 | std::conditional_t | |
529 | < | |
530 | (OverlayType == overlay_intersection), | |
531 | point_tag, | |
532 | void | |
533 | >, | |
534 | linestring_tag | |
535 | > | |
f67539c2 TL |
536 | {}; |
537 | ||
538 | template | |
539 | < | |
540 | typename MultiLinestring, typename MultiPolygon, | |
541 | typename TupledOut, | |
542 | overlay_type OverlayType, | |
543 | bool ReverseMultiLinestring, bool ReverseMultiPolygon | |
544 | > | |
545 | struct intersection_insert | |
546 | < | |
547 | MultiLinestring, MultiPolygon, | |
548 | TupledOut, | |
549 | OverlayType, | |
550 | ReverseMultiLinestring, ReverseMultiPolygon, | |
20effc67 TL |
551 | multi_linestring_tag, multi_polygon_tag, detail::tupled_output_tag, |
552 | linear_tag, areal_tag, detail::tupled_output_tag | |
f67539c2 TL |
553 | > : detail::intersection::intersection_of_multi_linestring_with_areal |
554 | < | |
555 | ReverseMultiPolygon, | |
556 | TupledOut, | |
557 | OverlayType, | |
558 | true | |
7c673cae | 559 | > |
20effc67 TL |
560 | , detail::expect_output |
561 | < | |
562 | MultiLinestring, MultiPolygon, TupledOut, | |
563 | // NOTE: points can be the result only in case of intersection. | |
564 | // TODO: union should require L and A | |
565 | std::conditional_t | |
566 | < | |
567 | (OverlayType == overlay_intersection), | |
568 | point_tag, | |
569 | void | |
570 | >, | |
571 | linestring_tag | |
572 | > | |
7c673cae FG |
573 | {}; |
574 | ||
575 | ||
576 | } // namespace dispatch | |
577 | #endif | |
578 | ||
579 | }} // namespace boost::geometry | |
580 | ||
581 | ||
582 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP | |
583 |