ceph/src/boost/boost/geometry/algorithms/detail/intersection/multi.hpp

   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 <type_traits>
  18
  19 #include <boost/geometry/core/closure.hpp>
  20 #include <boost/geometry/core/geometry_id.hpp>
  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,
 127     overlay_type OverlayType,
 128     bool FollowIsolatedPoints
 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                 <
 152                     ReverseAreal, LineStringOut, OverlayType, FollowIsolatedPoints
 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,
 166     overlay_type OverlayType,
 167     bool FollowIsolatedPoints
 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             <
 184                 ReverseAreal, LineStringOut, OverlayType, FollowIsolatedPoints
 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,
 234     bool Reverse1, bool Reverse2
 235 >
 236 struct intersection_insert
 237     <
 238         MultiLinestring1, MultiLinestring2,
 239         GeometryOut,
 240         OverlayType,
 241         Reverse1, Reverse2,
 242         multi_linestring_tag, multi_linestring_tag, point_tag,
 243         linear_tag, linear_tag, pointlike_tag
 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,
 256     bool Reverse1, bool Reverse2
 257 >
 258 struct intersection_insert
 259     <
 260         Linestring, MultiLinestring,
 261         GeometryOut,
 262         OverlayType,
 263         Reverse1, Reverse2,
 264         linestring_tag, multi_linestring_tag, point_tag,
 265         linear_tag, linear_tag, pointlike_tag
 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,
 278     bool Reverse1, bool Reverse2
 279 >
 280 struct intersection_insert
 281     <
 282         MultiLinestring, Box,
 283         GeometryOut,
 284         OverlayType,
 285         Reverse1, Reverse2,
 286         multi_linestring_tag, box_tag, linestring_tag,
 287         linear_tag, areal_tag, linear_tag
 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,
 300     bool ReverseLinestring, bool ReverseMultiPolygon
 301 >
 302 struct intersection_insert
 303     <
 304         Linestring, MultiPolygon,
 305         GeometryOut,
 306         OverlayType,
 307         ReverseLinestring, ReverseMultiPolygon,
 308         linestring_tag, multi_polygon_tag, linestring_tag,
 309         linear_tag, areal_tag, linear_tag
 310     > : detail::intersection::intersection_of_linestring_with_areal
 311             <
 312                 ReverseMultiPolygon,
 313                 GeometryOut,
 314                 OverlayType,
 315                 false
 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,
 327     bool ReversePolygon, bool ReverseMultiLinestring
 328 >
 329 struct intersection_insert
 330     <
 331         Polygon, MultiLinestring,
 332         GeometryOut,
 333         OverlayType,
 334         ReversePolygon, ReverseMultiLinestring,
 335         polygon_tag, multi_linestring_tag, linestring_tag,
 336         areal_tag, linear_tag, linear_tag
 337     > : detail::intersection::intersection_of_areal_with_multi_linestring
 338             <
 339                 ReversePolygon,
 340                 GeometryOut,
 341                 OverlayType,
 342                 false
 343             >
 344 {};
 345
 346
 347 template
 348 <
 349     typename MultiLinestring, typename Ring,
 350     typename GeometryOut,
 351     overlay_type OverlayType,
 352     bool ReverseMultiLinestring, bool ReverseRing
 353 >
 354 struct intersection_insert
 355     <
 356         MultiLinestring, Ring,
 357         GeometryOut,
 358         OverlayType,
 359         ReverseMultiLinestring, ReverseRing,
 360         multi_linestring_tag, ring_tag, linestring_tag,
 361         linear_tag, areal_tag, linear_tag
 362     > : detail::intersection::intersection_of_multi_linestring_with_areal
 363             <
 364                 ReverseRing,
 365                 GeometryOut,
 366                 OverlayType,
 367                 false
 368             >
 369 {};
 370
 371 template
 372 <
 373     typename MultiLinestring, typename Polygon,
 374     typename GeometryOut,
 375     overlay_type OverlayType,
 376     bool ReverseMultiLinestring, bool ReversePolygon
 377 >
 378 struct intersection_insert
 379     <
 380         MultiLinestring, Polygon,
 381         GeometryOut,
 382         OverlayType,
 383         ReverseMultiLinestring, ReversePolygon,
 384         multi_linestring_tag, polygon_tag, linestring_tag,
 385         linear_tag, areal_tag, linear_tag
 386     > : detail::intersection::intersection_of_multi_linestring_with_areal
 387             <
 388                 ReversePolygon,
 389                 GeometryOut,
 390                 OverlayType,
 391                 false
 392             >
 393 {};
 394
 395
 396
 397 template
 398 <
 399     typename MultiLinestring, typename MultiPolygon,
 400     typename GeometryOut,
 401     overlay_type OverlayType,
 402     bool ReverseMultiLinestring, bool ReverseMultiPolygon
 403 >
 404 struct intersection_insert
 405     <
 406         MultiLinestring, MultiPolygon,
 407         GeometryOut,
 408         OverlayType,
 409         ReverseMultiLinestring, ReverseMultiPolygon,
 410         multi_linestring_tag, multi_polygon_tag, linestring_tag,
 411         linear_tag, areal_tag, linear_tag
 412     > : detail::intersection::intersection_of_multi_linestring_with_areal
 413             <
 414                 ReverseMultiPolygon,
 415                 GeometryOut,
 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,
 436         multi_linestring_tag, ring_tag, detail::tupled_output_tag,
 437         linear_tag, areal_tag, detail::tupled_output_tag
 438     > : detail::intersection::intersection_of_multi_linestring_with_areal
 439             <
 440                 ReverseRing,
 441                 TupledOut,
 442                 OverlayType,
 443                 true
 444             >
 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             >
 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,
 474         multi_linestring_tag, polygon_tag, detail::tupled_output_tag,
 475         linear_tag, areal_tag, detail::tupled_output_tag
 476     > : detail::intersection::intersection_of_multi_linestring_with_areal
 477             <
 478                 ReversePolygon,
 479                 TupledOut,
 480                 OverlayType,
 481                 true
 482             >
 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             >
 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,
 511         polygon_tag, multi_linestring_tag, detail::tupled_output_tag,
 512         areal_tag, linear_tag, detail::tupled_output_tag
 513     > : detail::intersection::intersection_of_areal_with_multi_linestring
 514             <
 515                 ReversePolygon,
 516                 TupledOut,
 517                 OverlayType,
 518                 true
 519             >
 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             >
 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,
 551         multi_linestring_tag, multi_polygon_tag, detail::tupled_output_tag,
 552         linear_tag, areal_tag, detail::tupled_output_tag
 553     > : detail::intersection::intersection_of_multi_linestring_with_areal
 554             <
 555                 ReverseMultiPolygon,
 556                 TupledOut,
 557                 OverlayType,
 558                 true
 559             >
 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             >
 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