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