detail/overlay/follow_linear_linear.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
0004
0005 // Copyright (c) 2014-2024, Oracle and/or its affiliates.
0006 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0007 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Licensed under the Boost Software License version 1.0.
0011 // http://www.boost.org/users/license.html
0012
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP
0016
0017 #include <cstddef>
0018 #include <algorithm>
0019 #include <iterator>
0020
0021 #include <boost/range/begin.hpp>
0022 #include <boost/range/end.hpp>
0023 #include <boost/range/size.hpp>
0024 #include <boost/range/value_type.hpp>
0025 #include <boost/throw_exception.hpp>
0026
0027 #include <boost/geometry/core/assert.hpp>
0028 #include <boost/geometry/core/tag.hpp>
0029 #include <boost/geometry/core/tags.hpp>
0030
0031 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
0032 #include <boost/geometry/algorithms/detail/overlay/follow.hpp>
0033 #include <boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp>
0034 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0035 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
0036 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0037
0038 #include <boost/geometry/algorithms/detail/turns/debug_turn.hpp>
0039
0040 #include <boost/geometry/algorithms/detail/tupled_output.hpp>
0041
0042 #include <boost/geometry/algorithms/convert.hpp>
0043 #include <boost/geometry/algorithms/not_implemented.hpp>
0044
0045 #include <boost/geometry/util/condition.hpp>
0046
0047 namespace boost { namespace geometry
0048 {
0049
0050 #ifndef DOXYGEN_NO_DETAIL
0051 namespace detail { namespace overlay
0052 {
0053
0054 namespace following { namespace linear
0055 {
0056
0057
0058
0059
0060 // follower for linear/linear geometries set operations
0061
0062 template <typename Turn, typename Operation>
0063 static inline bool is_entering(Turn const& turn,
0064                                Operation const& operation)
0065 {
0066     if ( turn.method != method_touch && turn.method != method_touch_interior )
0067     {
0068         return false;
0069     }
0070     return operation.operation == operation_intersection;
0071 }
0072
0073
0074
0075 template <typename Turn, typename Operation>
0076 static inline bool is_staying_inside(Turn const& turn,
0077                                      Operation const& operation,
0078                                      bool entered)
0079 {
0080     if ( !entered )
0081     {
0082         return false;
0083     }
0084
0085     if ( turn.method != method_equal && turn.method != method_collinear )
0086     {
0087         return false;
0088     }
0089     return operation.operation == operation_continue;
0090 }
0091
0092
0093
0094 template <typename Turn, typename Operation>
0095 static inline bool is_leaving(Turn const& turn,
0096                               Operation const& operation,
0097                               bool entered)
0098 {
0099     if ( !entered )
0100     {
0101         return false;
0102     }
0103
0104     if ( turn.method != method_touch
0105          && turn.method != method_touch_interior
0106          && turn.method != method_equal
0107          && turn.method != method_collinear )
0108     {
0109         return false;
0110     }
0111
0112     if ( operation.operation == operation_blocked )
0113     {
0114         return true;
0115     }
0116
0117     if ( operation.operation != operation_union )
0118     {
0119         return false;
0120     }
0121
0122     return operation.is_collinear;
0123 }
0124
0125
0126
0127 template <typename Turn, typename Operation>
0128 static inline bool is_isolated_point(Turn const& turn,
0129                                      Operation const& operation,
0130                                      bool entered)
0131 {
0132     if ( entered )
0133     {
0134         return false;
0135     }
0136
0137     if ( turn.method == method_none )
0138     {
0139         BOOST_GEOMETRY_ASSERT( operation.operation == operation_continue );
0140         return true;
0141     }
0142
0143     if ( turn.method == method_crosses )
0144     {
0145         return true;
0146     }
0147
0148     if ( turn.method != method_touch && turn.method != method_touch_interior )
0149     {
0150         return false;
0151     }
0152
0153     if ( operation.operation == operation_blocked )
0154     {
0155         return true;
0156     }
0157
0158     if ( operation.operation != operation_union )
0159     {
0160         return false;
0161     }
0162
0163     return !operation.is_collinear;
0164 }
0165
0166
0167
0168
0169
0170 // GeometryOut - linestring or tuple of at least point and linestring
0171 template
0172 <
0173     typename GeometryOut,
0174     typename Linestring,
0175     typename Linear,
0176     overlay_type OverlayType,
0177     bool FollowIsolatedPoints,
0178     bool FollowContinueTurns
0179 >
0180 class follow_linestring_linear
0181 {
0182 protected:
0183     // allow spikes (false indicates: do not remove spikes)
0184     using action = following::action_selector<OverlayType, false>;
0185
0186     using linear = geometry::detail::output_geometry_access
0187         <
0188             GeometryOut, linestring_tag, linestring_tag
0189         >;
0190     using pointlike = geometry::detail::output_geometry_access
0191         <
0192             GeometryOut, point_tag, linestring_tag
0193         >;
0194
0195     template
0196     <
0197         typename TurnIterator,
0198         typename TurnOperationIterator,
0199         typename LinestringOut,
0200         typename SegmentIdentifier,
0201         typename OutputIterator,
0202         typename SideStrategy
0203     >
0204     static inline OutputIterator
0205     process_turn(TurnIterator it,
0206                  TurnOperationIterator op_it,
0207                  bool& entered,
0208                  std::size_t& enter_count,
0209                  Linestring const& linestring,
0210                  LinestringOut& current_piece,
0211                  SegmentIdentifier& current_segment_id,
0212                  OutputIterator oit,
0213                  SideStrategy const& strategy)
0214     {
0215         if ( is_entering(*it, *op_it) )
0216         {
0217             detail::turns::debug_turn(*it, *op_it, "-> Entering");
0218
0219             entered = true;
0220             if ( enter_count == 0 )
0221             {
0222                 action::enter(current_piece,
0223                               linestring,
0224                               current_segment_id,
0225                               op_it->seg_id.segment_index,
0226                               it->point, *op_it, strategy,
0227                               linear::get(oit));
0228             }
0229             ++enter_count;
0230         }
0231         else if ( is_leaving(*it, *op_it, entered) )
0232         {
0233             detail::turns::debug_turn(*it, *op_it, "-> Leaving");
0234
0235             --enter_count;
0236             if ( enter_count == 0 )
0237             {
0238                 entered = false;
0239                 action::leave(current_piece,
0240                               linestring,
0241                               current_segment_id,
0242                               op_it->seg_id.segment_index,
0243                               it->point, *op_it, strategy,
0244                               linear::get(oit));
0245             }
0246         }
0247         else if ( BOOST_GEOMETRY_CONDITION(FollowIsolatedPoints)
0248                   && is_isolated_point(*it, *op_it, entered) )
0249         {
0250             detail::turns::debug_turn(*it, *op_it, "-> Isolated point");
0251
0252             action::template isolated_point
0253                 <
0254                     typename pointlike::type
0255                 >(it->point, pointlike::get(oit));
0256         }
0257         else if ( BOOST_GEOMETRY_CONDITION(FollowContinueTurns)
0258                   && is_staying_inside(*it, *op_it, entered) )
0259         {
0260             detail::turns::debug_turn(*it, *op_it, "-> Staying inside");
0261
0262             entered = true;
0263         }
0264         return oit;
0265     }
0266
0267     template
0268     <
0269         typename SegmentIdentifier,
0270         typename LinestringOut,
0271         typename OutputIterator,
0272         typename SideStrategy
0273     >
0274     static inline OutputIterator
0275     process_end(bool entered,
0276                 Linestring const& linestring,
0277                 SegmentIdentifier const& current_segment_id,
0278                 LinestringOut& current_piece,
0279                 OutputIterator oit,
0280                 SideStrategy const& strategy)
0281     {
0282         if ( action::is_entered(entered) )
0283         {
0284             detail::copy_segments::copy_segments_linestring
0285                 <
0286                     false, false // do not reverse; do not remove spikes
0287                 >::apply(linestring,
0288                          current_segment_id,
0289                          static_cast<signed_size_type>(boost::size(linestring) - 1),
0290                          strategy,
0291                          current_piece);
0292         }
0293
0294         // Output the last one, if applicable
0295         if (::boost::size(current_piece) > 1)
0296         {
0297             *linear::get(oit)++ = current_piece;
0298         }
0299
0300         return oit;
0301     }
0302
0303 public:
0304     template <typename TurnIterator, typename OutputIterator, typename SideStrategy>
0305     static inline OutputIterator
0306     apply(Linestring const& linestring, Linear const&,
0307           TurnIterator first, TurnIterator beyond,
0308           OutputIterator oit,
0309           SideStrategy const& strategy)
0310     {
0311         // Iterate through all intersection points (they are
0312         // ordered along the each line)
0313
0314         typename linear::type current_piece;
0315         geometry::segment_identifier current_segment_id(0, -1, -1, -1);
0316
0317         bool entered = false;
0318         std::size_t enter_count = 0;
0319
0320         for (TurnIterator it = first; it != beyond; ++it)
0321         {
0322             oit = process_turn(it, boost::begin(it->operations),
0323                                entered, enter_count,
0324                                linestring,
0325                                current_piece, current_segment_id,
0326                                oit,
0327                                strategy);
0328         }
0329
0330         if (enter_count != 0)
0331         {
0332            return oit;
0333         }
0334
0335         return process_end(entered, linestring,
0336                            current_segment_id, current_piece,
0337                            oit,
0338                            strategy);
0339     }
0340 };
0341
0342
0343
0344
0345 template
0346 <
0347     typename LinestringOut,
0348     typename MultiLinestring,
0349     typename Linear,
0350     overlay_type OverlayType,
0351     bool FollowIsolatedPoints,
0352     bool FollowContinueTurns
0353 >
0354 class follow_multilinestring_linear
0355     : follow_linestring_linear
0356         <
0357             LinestringOut,
0358             typename boost::range_value<MultiLinestring>::type,
0359             Linear,
0360             OverlayType,
0361             FollowIsolatedPoints,
0362             FollowContinueTurns
0363         >
0364 {
0365 protected:
0366     using linestring_t = typename boost::range_value<MultiLinestring>::type;
0367
0368     using base_t = follow_linestring_linear
0369         <
0370             LinestringOut, linestring_t, Linear,
0371             OverlayType, FollowIsolatedPoints, FollowContinueTurns
0372         >;
0373
0374     using action = following::action_selector<OverlayType>;
0375
0376     using linestring_iterator = typename boost::range_iterator
0377         <
0378             MultiLinestring const
0379         >::type;
0380
0381
0382     template <typename OutputIt, overlay_type OT>
0383     struct copy_linestrings_in_range
0384     {
0385         static inline OutputIt
0386         apply(linestring_iterator, linestring_iterator, OutputIt oit)
0387         {
0388             return oit;
0389         }
0390     };
0391
0392     template <typename OutputIt>
0393     struct copy_linestrings_in_range<OutputIt, overlay_difference>
0394     {
0395         static inline OutputIt
0396         apply(linestring_iterator first, linestring_iterator beyond,
0397               OutputIt oit)
0398         {
0399             for (linestring_iterator ls_it = first; ls_it != beyond; ++ls_it)
0400             {
0401                 LinestringOut line_out;
0402                 geometry::convert(*ls_it, line_out);
0403                 *oit++ = line_out;
0404             }
0405             return oit;
0406         }
0407     };
0408
0409     template <typename TurnIterator>
0410     static inline signed_size_type get_multi_index(TurnIterator it)
0411     {
0412         return boost::begin(it->operations)->seg_id.multi_index;
0413     }
0414
0415     class has_other_multi_id
0416     {
0417     private:
0418         signed_size_type m_multi_id;
0419
0420     public:
0421         has_other_multi_id(signed_size_type multi_id)
0422             : m_multi_id(multi_id) {}
0423
0424         template <typename Turn>
0425         bool operator()(Turn const& turn) const
0426         {
0427             return boost::begin(turn.operations)->seg_id.multi_index
0428                 != m_multi_id;
0429         }
0430     };
0431
0432 public:
0433     template <typename TurnIterator, typename OutputIterator, typename SideStrategy>
0434     static inline OutputIterator
0435     apply(MultiLinestring const& multilinestring, Linear const& linear,
0436           TurnIterator first, TurnIterator beyond,
0437           OutputIterator oit,
0438           SideStrategy const& strategy)
0439     {
0440         BOOST_GEOMETRY_ASSERT( first != beyond );
0441
0442         using copy_linestrings = copy_linestrings_in_range
0443             <
0444                 OutputIterator, OverlayType
0445             >;
0446
0447         linestring_iterator ls_first = boost::begin(multilinestring);
0448         linestring_iterator ls_beyond = boost::end(multilinestring);
0449
0450         // Iterate through all intersection points (they are
0451         // ordered along the each linestring)
0452
0453         signed_size_type current_multi_id = get_multi_index(first);
0454
0455         oit = copy_linestrings::apply(ls_first,
0456                                       ls_first + current_multi_id,
0457                                       oit);
0458
0459         TurnIterator per_ls_next = first;
0460         do {
0461             TurnIterator per_ls_current = per_ls_next;
0462
0463             // find turn with different multi-index
0464             per_ls_next = std::find_if(per_ls_current, beyond,
0465                                        has_other_multi_id(current_multi_id));
0466
0467             oit = base_t::apply(*(ls_first + current_multi_id),
0468                               linear, per_ls_current, per_ls_next, oit, strategy);
0469
0470             signed_size_type next_multi_id = -1;
0471             linestring_iterator ls_next = ls_beyond;
0472             if ( per_ls_next != beyond )
0473             {
0474                 next_multi_id = get_multi_index(per_ls_next);
0475                 ls_next = ls_first + next_multi_id;
0476             }
0477             oit = copy_linestrings::apply(ls_first + current_multi_id + 1,
0478                                           ls_next,
0479                                           oit);
0480
0481             current_multi_id = next_multi_id;
0482         }
0483         while ( per_ls_next != beyond );
0484
0485         return oit;
0486     }
0487 };
0488
0489
0490
0491
0492
0493
0494 template
0495 <
0496     typename LinestringOut,
0497     typename Geometry1,
0498     typename Geometry2,
0499     overlay_type OverlayType,
0500     bool FollowIsolatedPoints,
0501     bool FollowContinueTurns,
0502     typename TagIn1 = tag_t<Geometry1>
0503 >
0504 struct follow
0505     : not_implemented<Geometry1>
0506 {};
0507
0508
0509
0510 template
0511 <
0512     typename LinestringOut,
0513     typename Linestring,
0514     typename Linear,
0515     overlay_type OverlayType,
0516     bool FollowIsolatedPoints,
0517     bool FollowContinueTurns
0518 >
0519 struct follow
0520     <
0521         LinestringOut, Linestring, Linear,
0522         OverlayType, FollowIsolatedPoints, FollowContinueTurns,
0523         linestring_tag
0524     > : follow_linestring_linear
0525         <
0526             LinestringOut, Linestring, Linear,
0527             OverlayType, FollowIsolatedPoints, FollowContinueTurns
0528         >
0529 {};
0530
0531
0532 template
0533 <
0534     typename LinestringOut,
0535     typename MultiLinestring,
0536     typename Linear,
0537     overlay_type OverlayType,
0538     bool FollowIsolatedPoints,
0539     bool FollowContinueTurns
0540 >
0541 struct follow
0542     <
0543         LinestringOut, MultiLinestring, Linear,
0544         OverlayType, FollowIsolatedPoints, FollowContinueTurns,
0545         multi_linestring_tag
0546     > : follow_multilinestring_linear
0547         <
0548             LinestringOut, MultiLinestring, Linear,
0549             OverlayType, FollowIsolatedPoints, FollowContinueTurns
0550         >
0551 {};
0552
0553
0554
0555 }} // namespace following::linear
0556
0557 }} // namespace detail::overlay
0558 #endif // DOXYGEN_NO_DETAIL
0559
0560 }} // namespace boost::geometry
0561
0562
0563 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP