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