detail/intersection/multi.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2014-2024.
0006 // Modifications copyright (c) 2014-2024, Oracle and/or its affiliates.
0007 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
0016
0017 #include <type_traits>
0018
0019 #include <boost/geometry/core/closure.hpp>
0020 #include <boost/geometry/core/geometry_id.hpp>
0021 #include <boost/geometry/core/point_order.hpp>
0022 #include <boost/geometry/core/tags.hpp>
0023 #include <boost/geometry/geometries/concepts/check.hpp>
0024
0025 #include <boost/geometry/algorithms/detail/covered_by/implementation.hpp>
0026
0027 // TODO: those headers probably may be removed
0028 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
0030 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
0031 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
0032 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
0033 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
0034 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
0035
0036 #include <boost/geometry/algorithms/detail/intersection/interface.hpp>
0037
0038 #include <boost/geometry/algorithms/envelope.hpp>
0039 #include <boost/geometry/algorithms/num_points.hpp>
0040
0041
0042 namespace boost { namespace geometry
0043 {
0044
0045 #ifndef DOXYGEN_NO_DETAIL
0046 namespace detail { namespace intersection
0047 {
0048
0049
0050 template <typename PointOut>
0051 struct intersection_multi_linestring_multi_linestring_point
0052 {
0053     template
0054     <
0055         typename MultiLinestring1, typename MultiLinestring2,
0056         typename OutputIterator, typename Strategy
0057     >
0058     static inline OutputIterator apply(MultiLinestring1 const& ml1,
0059             MultiLinestring2 const& ml2,
0060             OutputIterator out,
0061             Strategy const& strategy)
0062     {
0063         // Note, this loop is quadratic w.r.t. number of linestrings per input.
0064         // Future Enhancement: first do the sections of each, then intersect.
0065         for (auto it1 = boost::begin(ml1); it1 != boost::end(ml1); ++it1)
0066         {
0067             for (auto it2 = boost::begin(ml2); it2 != boost::end(ml2); ++it2)
0068             {
0069                 out = intersection_linestring_linestring_point<PointOut>
0070                       ::apply(*it1, *it2, out, strategy);
0071             }
0072         }
0073
0074         return out;
0075     }
0076 };
0077
0078
0079 template <typename PointOut>
0080 struct intersection_linestring_multi_linestring_point
0081 {
0082     template
0083     <
0084         typename Linestring, typename MultiLinestring,
0085         typename OutputIterator, typename Strategy
0086     >
0087     static inline OutputIterator apply(Linestring const& linestring,
0088             MultiLinestring const& ml,
0089             OutputIterator out,
0090             Strategy const& strategy)
0091     {
0092         for (auto it = boost::begin(ml); it != boost::end(ml); ++it)
0093         {
0094             out = intersection_linestring_linestring_point<PointOut>
0095                   ::apply(linestring, *it, out, strategy);
0096         }
0097
0098         return out;
0099     }
0100 };
0101
0102
0103 // This loop is quite similar to the loop above, but beacuse the iterator
0104 // is second (above) or first (below) argument, it is not trivial to merge them.
0105 template
0106 <
0107     bool ReverseAreal,
0108     typename LineStringOut,
0109     overlay_type OverlayType,
0110     bool FollowIsolatedPoints
0111 >
0112 struct intersection_of_multi_linestring_with_areal
0113 {
0114     template
0115     <
0116         typename MultiLinestring, typename Areal,
0117         typename OutputIterator, typename Strategy
0118     >
0119     static inline OutputIterator apply(MultiLinestring const& ml, Areal const& areal,
0120             OutputIterator out,
0121             Strategy const& strategy)
0122     {
0123         for (auto it = boost::begin(ml); it != boost::end(ml); ++it)
0124         {
0125             out = intersection_of_linestring_with_areal
0126                 <
0127                     ReverseAreal, LineStringOut, OverlayType, FollowIsolatedPoints
0128                 >::apply(*it, areal, out, strategy);
0129         }
0130
0131         return out;
0132
0133     }
0134 };
0135
0136 // This one calls the one above with reversed arguments
0137 template
0138 <
0139     bool ReverseAreal,
0140     typename LineStringOut,
0141     overlay_type OverlayType,
0142     bool FollowIsolatedPoints
0143 >
0144 struct intersection_of_areal_with_multi_linestring
0145 {
0146     template
0147     <
0148         typename Areal, typename MultiLinestring,
0149         typename OutputIterator, typename Strategy
0150     >
0151     static inline OutputIterator apply(Areal const& areal, MultiLinestring const& ml,
0152             OutputIterator out,
0153             Strategy const& strategy)
0154     {
0155         return intersection_of_multi_linestring_with_areal
0156             <
0157                 ReverseAreal, LineStringOut, OverlayType, FollowIsolatedPoints
0158             >::apply(ml, areal, out, strategy);
0159     }
0160 };
0161
0162
0163
0164 template <typename LinestringOut>
0165 struct clip_multi_linestring
0166 {
0167     template
0168     <
0169         typename MultiLinestring, typename Box,
0170         typename OutputIterator, typename Strategy
0171     >
0172     static inline OutputIterator apply(MultiLinestring const& multi_linestring,
0173             Box const& box,
0174             OutputIterator out, Strategy const& )
0175     {
0176         strategy::intersection::liang_barsky<Box, point_type_t<LinestringOut>> lb_strategy;
0177         for (auto it = boost::begin(multi_linestring); it != boost::end(multi_linestring); ++it)
0178         {
0179             out = detail::intersection::clip_range_with_box
0180                 <LinestringOut>(box, *it, out, lb_strategy);
0181         }
0182         return out;
0183     }
0184 };
0185
0186
0187 }} // namespace detail::intersection
0188 #endif // DOXYGEN_NO_DETAIL
0189
0190
0191 #ifndef DOXYGEN_NO_DISPATCH
0192 namespace dispatch
0193 {
0194
0195
0196 // Linear
0197 template
0198 <
0199     typename MultiLinestring1, typename MultiLinestring2,
0200     typename GeometryOut,
0201     overlay_type OverlayType,
0202     bool Reverse1, bool Reverse2
0203 >
0204 struct intersection_insert
0205     <
0206         MultiLinestring1, MultiLinestring2,
0207         GeometryOut,
0208         OverlayType,
0209         Reverse1, Reverse2,
0210         multi_linestring_tag, multi_linestring_tag, point_tag,
0211         linear_tag, linear_tag, pointlike_tag
0212     > : detail::intersection::intersection_multi_linestring_multi_linestring_point
0213             <
0214                 GeometryOut
0215             >
0216 {};
0217
0218
0219 template
0220 <
0221     typename Linestring, typename MultiLinestring,
0222     typename GeometryOut,
0223     overlay_type OverlayType,
0224     bool Reverse1, bool Reverse2
0225 >
0226 struct intersection_insert
0227     <
0228         Linestring, MultiLinestring,
0229         GeometryOut,
0230         OverlayType,
0231         Reverse1, Reverse2,
0232         linestring_tag, multi_linestring_tag, point_tag,
0233         linear_tag, linear_tag, pointlike_tag
0234     > : detail::intersection::intersection_linestring_multi_linestring_point
0235             <
0236                 GeometryOut
0237             >
0238 {};
0239
0240
0241 template
0242 <
0243     typename MultiLinestring, typename Box,
0244     typename GeometryOut,
0245     overlay_type OverlayType,
0246     bool Reverse1, bool Reverse2
0247 >
0248 struct intersection_insert
0249     <
0250         MultiLinestring, Box,
0251         GeometryOut,
0252         OverlayType,
0253         Reverse1, Reverse2,
0254         multi_linestring_tag, box_tag, linestring_tag,
0255         linear_tag, areal_tag, linear_tag
0256     > : detail::intersection::clip_multi_linestring
0257             <
0258                 GeometryOut
0259             >
0260 {};
0261
0262
0263 template
0264 <
0265     typename Linestring, typename MultiPolygon,
0266     typename GeometryOut,
0267     overlay_type OverlayType,
0268     bool ReverseLinestring, bool ReverseMultiPolygon
0269 >
0270 struct intersection_insert
0271     <
0272         Linestring, MultiPolygon,
0273         GeometryOut,
0274         OverlayType,
0275         ReverseLinestring, ReverseMultiPolygon,
0276         linestring_tag, multi_polygon_tag, linestring_tag,
0277         linear_tag, areal_tag, linear_tag
0278     > : detail::intersection::intersection_of_linestring_with_areal
0279             <
0280                 ReverseMultiPolygon,
0281                 GeometryOut,
0282                 OverlayType,
0283                 false
0284             >
0285 {};
0286
0287
0288 // Derives from areal/mls because runtime arguments are in that order.
0289 // areal/mls reverses it itself to mls/areal
0290 template
0291 <
0292     typename Polygon, typename MultiLinestring,
0293     typename GeometryOut,
0294     overlay_type OverlayType,
0295     bool ReversePolygon, bool ReverseMultiLinestring
0296 >
0297 struct intersection_insert
0298     <
0299         Polygon, MultiLinestring,
0300         GeometryOut,
0301         OverlayType,
0302         ReversePolygon, ReverseMultiLinestring,
0303         polygon_tag, multi_linestring_tag, linestring_tag,
0304         areal_tag, linear_tag, linear_tag
0305     > : detail::intersection::intersection_of_areal_with_multi_linestring
0306             <
0307                 ReversePolygon,
0308                 GeometryOut,
0309                 OverlayType,
0310                 false
0311             >
0312 {};
0313
0314
0315 template
0316 <
0317     typename MultiLinestring, typename Ring,
0318     typename GeometryOut,
0319     overlay_type OverlayType,
0320     bool ReverseMultiLinestring, bool ReverseRing
0321 >
0322 struct intersection_insert
0323     <
0324         MultiLinestring, Ring,
0325         GeometryOut,
0326         OverlayType,
0327         ReverseMultiLinestring, ReverseRing,
0328         multi_linestring_tag, ring_tag, linestring_tag,
0329         linear_tag, areal_tag, linear_tag
0330     > : detail::intersection::intersection_of_multi_linestring_with_areal
0331             <
0332                 ReverseRing,
0333                 GeometryOut,
0334                 OverlayType,
0335                 false
0336             >
0337 {};
0338
0339 template
0340 <
0341     typename MultiLinestring, typename Polygon,
0342     typename GeometryOut,
0343     overlay_type OverlayType,
0344     bool ReverseMultiLinestring, bool ReversePolygon
0345 >
0346 struct intersection_insert
0347     <
0348         MultiLinestring, Polygon,
0349         GeometryOut,
0350         OverlayType,
0351         ReverseMultiLinestring, ReversePolygon,
0352         multi_linestring_tag, polygon_tag, linestring_tag,
0353         linear_tag, areal_tag, linear_tag
0354     > : detail::intersection::intersection_of_multi_linestring_with_areal
0355             <
0356                 ReversePolygon,
0357                 GeometryOut,
0358                 OverlayType,
0359                 false
0360             >
0361 {};
0362
0363
0364
0365 template
0366 <
0367     typename MultiLinestring, typename MultiPolygon,
0368     typename GeometryOut,
0369     overlay_type OverlayType,
0370     bool ReverseMultiLinestring, bool ReverseMultiPolygon
0371 >
0372 struct intersection_insert
0373     <
0374         MultiLinestring, MultiPolygon,
0375         GeometryOut,
0376         OverlayType,
0377         ReverseMultiLinestring, ReverseMultiPolygon,
0378         multi_linestring_tag, multi_polygon_tag, linestring_tag,
0379         linear_tag, areal_tag, linear_tag
0380     > : detail::intersection::intersection_of_multi_linestring_with_areal
0381             <
0382                 ReverseMultiPolygon,
0383                 GeometryOut,
0384                 OverlayType,
0385                 false
0386             >
0387 {};
0388
0389
0390
0391 template
0392 <
0393     typename MultiLinestring, typename Ring,
0394     typename TupledOut,
0395     overlay_type OverlayType,
0396     bool ReverseMultiLinestring, bool ReverseRing
0397 >
0398 struct intersection_insert
0399     <
0400         MultiLinestring, Ring,
0401         TupledOut,
0402         OverlayType,
0403         ReverseMultiLinestring, ReverseRing,
0404         multi_linestring_tag, ring_tag, detail::tupled_output_tag,
0405         linear_tag, areal_tag, detail::tupled_output_tag
0406     > : detail::intersection::intersection_of_multi_linestring_with_areal
0407             <
0408                 ReverseRing,
0409                 TupledOut,
0410                 OverlayType,
0411                 true
0412             >
0413       , detail::expect_output
0414             <
0415                 MultiLinestring, Ring, TupledOut,
0416                 // NOTE: points can be the result only in case of intersection.
0417                 // TODO: union should require L and A
0418                 std::conditional_t
0419                     <
0420                         (OverlayType == overlay_intersection),
0421                         point_tag,
0422                         void
0423                     >,
0424                 linestring_tag
0425             >
0426 {};
0427
0428
0429 template
0430 <
0431     typename MultiLinestring, typename Polygon,
0432     typename TupledOut,
0433     overlay_type OverlayType,
0434     bool ReverseMultiLinestring, bool ReversePolygon
0435 >
0436 struct intersection_insert
0437     <
0438         MultiLinestring, Polygon,
0439         TupledOut,
0440         OverlayType,
0441         ReverseMultiLinestring, ReversePolygon,
0442         multi_linestring_tag, polygon_tag, detail::tupled_output_tag,
0443         linear_tag, areal_tag, detail::tupled_output_tag
0444     > : detail::intersection::intersection_of_multi_linestring_with_areal
0445             <
0446                 ReversePolygon,
0447                 TupledOut,
0448                 OverlayType,
0449                 true
0450             >
0451       , detail::expect_output
0452             <
0453                 MultiLinestring, Polygon, TupledOut,
0454                 // NOTE: points can be the result only in case of intersection.
0455                 // TODO: union should require L and A
0456                 std::conditional_t
0457                     <
0458                         (OverlayType == overlay_intersection),
0459                         point_tag,
0460                         void
0461                     >,
0462                 linestring_tag
0463             >
0464 {};
0465
0466 template
0467 <
0468     typename Polygon, typename MultiLinestring,
0469     typename TupledOut,
0470     overlay_type OverlayType,
0471     bool ReversePolygon, bool ReverseMultiLinestring
0472 >
0473 struct intersection_insert
0474     <
0475         Polygon, MultiLinestring,
0476         TupledOut,
0477         OverlayType,
0478         ReversePolygon, ReverseMultiLinestring,
0479         polygon_tag, multi_linestring_tag, detail::tupled_output_tag,
0480         areal_tag, linear_tag, detail::tupled_output_tag
0481     > : detail::intersection::intersection_of_areal_with_multi_linestring
0482             <
0483                 ReversePolygon,
0484                 TupledOut,
0485                 OverlayType,
0486                 true
0487             >
0488       , detail::expect_output
0489             <
0490                 Polygon, MultiLinestring, TupledOut,
0491                 // NOTE: points can be the result only in case of intersection.
0492                 // TODO: union should require L and A
0493                 // TODO: in general the result of difference should depend on the first argument
0494                 //       but this specialization calls L/A in reality so the first argument is linear.
0495                 //       So expect only L for difference?
0496                 std::conditional_t
0497                     <
0498                         (OverlayType == overlay_intersection),
0499                         point_tag,
0500                         void
0501                     >,
0502                 linestring_tag
0503             >
0504 {};
0505
0506 template
0507 <
0508     typename Linestring, typename MultiPolygon,
0509     typename TupledOut,
0510     overlay_type OverlayType,
0511     bool ReverseMultiLinestring, bool ReverseMultiPolygon
0512 >
0513 struct intersection_insert
0514     <
0515         Linestring, MultiPolygon,
0516         TupledOut,
0517         OverlayType,
0518         ReverseMultiLinestring, ReverseMultiPolygon,
0519         linestring_tag, multi_polygon_tag, detail::tupled_output_tag,
0520         linear_tag, areal_tag, detail::tupled_output_tag
0521     > : detail::intersection::intersection_of_linestring_with_areal
0522             <
0523                 ReverseMultiPolygon, TupledOut, OverlayType, true
0524             >
0525       , detail::expect_output
0526             <
0527                 Linestring, MultiPolygon, TupledOut,
0528                 // NOTE: points can be the result only in case of intersection.
0529                 // TODO: union should require L and A
0530                 std::conditional_t
0531                     <
0532                         (OverlayType == overlay_intersection),
0533                         point_tag,
0534                         void
0535                     >,
0536                 linestring_tag
0537             >
0538 {};
0539
0540 template
0541 <
0542     typename MultiLinestring, typename MultiPolygon,
0543     typename TupledOut,
0544     overlay_type OverlayType,
0545     bool ReverseMultiLinestring, bool ReverseMultiPolygon
0546 >
0547 struct intersection_insert
0548     <
0549         MultiLinestring, MultiPolygon,
0550         TupledOut,
0551         OverlayType,
0552         ReverseMultiLinestring, ReverseMultiPolygon,
0553         multi_linestring_tag, multi_polygon_tag, detail::tupled_output_tag,
0554         linear_tag, areal_tag, detail::tupled_output_tag
0555     > : detail::intersection::intersection_of_multi_linestring_with_areal
0556             <
0557                 ReverseMultiPolygon,
0558                 TupledOut,
0559                 OverlayType,
0560                 true
0561             >
0562       , detail::expect_output
0563             <
0564                 MultiLinestring, MultiPolygon, TupledOut,
0565                 // NOTE: points can be the result only in case of intersection.
0566                 // TODO: union should require L and A
0567                 std::conditional_t
0568                     <
0569                         (OverlayType == overlay_intersection),
0570                         point_tag,
0571                         void
0572                     >,
0573                 linestring_tag
0574             >
0575 {};
0576
0577
0578 } // namespace dispatch
0579 #endif
0580
0581 }} // namespace boost::geometry
0582
0583
0584 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_INTERSECTION_MULTI_HPP
0585