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-2020, Oracle and/or its affiliates.
0006
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     typedef following::action_selector<OverlayType, false> action;
0185
0186     typedef geometry::detail::output_geometry_access
0187         <
0188             GeometryOut, linestring_tag, linestring_tag
0189         > linear;
0190     typedef geometry::detail::output_geometry_access
0191         <
0192             GeometryOut, point_tag, linestring_tag
0193         > pointlike;
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         // We don't rescale linear/linear
0216         detail::no_rescale_policy robust_policy;
0217
0218         if ( is_entering(*it, *op_it) )
0219         {
0220             detail::turns::debug_turn(*it, *op_it, "-> Entering");
0221
0222             entered = true;
0223             if ( enter_count == 0 )
0224             {
0225                 action::enter(current_piece,
0226                               linestring,
0227                               current_segment_id,
0228                               op_it->seg_id.segment_index,
0229                               it->point, *op_it, strategy, robust_policy,
0230                               linear::get(oit));
0231             }
0232             ++enter_count;
0233         }
0234         else if ( is_leaving(*it, *op_it, entered) )
0235         {
0236             detail::turns::debug_turn(*it, *op_it, "-> Leaving");
0237
0238             --enter_count;
0239             if ( enter_count == 0 )
0240             {
0241                 entered = false;
0242                 action::leave(current_piece,
0243                               linestring,
0244                               current_segment_id,
0245                               op_it->seg_id.segment_index,
0246                               it->point, *op_it, strategy, robust_policy,
0247                               linear::get(oit));
0248             }
0249         }
0250         else if ( BOOST_GEOMETRY_CONDITION(FollowIsolatedPoints)
0251                   && is_isolated_point(*it, *op_it, entered) )
0252         {
0253             detail::turns::debug_turn(*it, *op_it, "-> Isolated point");
0254
0255             action::template isolated_point
0256                 <
0257                     typename pointlike::type
0258                 >(it->point, pointlike::get(oit));
0259         }
0260         else if ( BOOST_GEOMETRY_CONDITION(FollowContinueTurns)
0261                   && is_staying_inside(*it, *op_it, entered) )
0262         {
0263             detail::turns::debug_turn(*it, *op_it, "-> Staying inside");
0264
0265             entered = true;
0266         }
0267         return oit;
0268     }
0269
0270     template
0271     <
0272         typename SegmentIdentifier,
0273         typename LinestringOut,
0274         typename OutputIterator,
0275         typename SideStrategy
0276     >
0277     static inline OutputIterator
0278     process_end(bool entered,
0279                 Linestring const& linestring,
0280                 SegmentIdentifier const& current_segment_id,
0281                 LinestringOut& current_piece,
0282                 OutputIterator oit,
0283                 SideStrategy const& strategy)
0284     {
0285         if ( action::is_entered(entered) )
0286         {
0287             // We don't rescale linear/linear
0288             detail::no_rescale_policy robust_policy;
0289
0290             detail::copy_segments::copy_segments_linestring
0291                 <
0292                     false, false // do not reverse; do not remove spikes
0293                 >::apply(linestring,
0294                          current_segment_id,
0295                          static_cast<signed_size_type>(boost::size(linestring) - 1),
0296                          strategy,
0297                          robust_policy,
0298                          current_piece);
0299         }
0300
0301         // Output the last one, if applicable
0302         if (::boost::size(current_piece) > 1)
0303         {
0304             *linear::get(oit)++ = current_piece;
0305         }
0306
0307         return oit;
0308     }
0309
0310 public:
0311     template <typename TurnIterator, typename OutputIterator, typename SideStrategy>
0312     static inline OutputIterator
0313     apply(Linestring const& linestring, Linear const&,
0314           TurnIterator first, TurnIterator beyond,
0315           OutputIterator oit,
0316           SideStrategy const& strategy)
0317     {
0318         // Iterate through all intersection points (they are
0319         // ordered along the each line)
0320
0321         typename linear::type current_piece;
0322         geometry::segment_identifier current_segment_id(0, -1, -1, -1);
0323
0324         bool entered = false;
0325         std::size_t enter_count = 0;
0326
0327         for (TurnIterator it = first; it != beyond; ++it)
0328         {
0329             oit = process_turn(it, boost::begin(it->operations),
0330                                entered, enter_count,
0331                                linestring,
0332                                current_piece, current_segment_id,
0333                                oit,
0334                                strategy);
0335         }
0336
0337         if (enter_count != 0)
0338         {
0339            return oit;
0340         }
0341
0342         return process_end(entered, linestring,
0343                            current_segment_id, current_piece,
0344                            oit,
0345                            strategy);
0346     }
0347 };
0348
0349
0350
0351
0352 template
0353 <
0354     typename LinestringOut,
0355     typename MultiLinestring,
0356     typename Linear,
0357     overlay_type OverlayType,
0358     bool FollowIsolatedPoints,
0359     bool FollowContinueTurns
0360 >
0361 class follow_multilinestring_linear
0362     : follow_linestring_linear
0363         <
0364             LinestringOut,
0365             typename boost::range_value<MultiLinestring>::type,
0366             Linear,
0367             OverlayType,
0368             FollowIsolatedPoints,
0369             FollowContinueTurns
0370         >
0371 {
0372 protected:
0373     typedef typename boost::range_value<MultiLinestring>::type Linestring;
0374
0375     typedef follow_linestring_linear
0376         <
0377             LinestringOut, Linestring, Linear,
0378             OverlayType, FollowIsolatedPoints, FollowContinueTurns
0379         > Base;
0380
0381     typedef following::action_selector<OverlayType> action;
0382
0383     typedef typename boost::range_iterator
0384         <
0385             MultiLinestring const
0386         >::type linestring_iterator;
0387
0388
0389     template <typename OutputIt, overlay_type OT>
0390     struct copy_linestrings_in_range
0391     {
0392         static inline OutputIt
0393         apply(linestring_iterator, linestring_iterator, OutputIt oit)
0394         {
0395             return oit;
0396         }
0397     };
0398
0399     template <typename OutputIt>
0400     struct copy_linestrings_in_range<OutputIt, overlay_difference>
0401     {
0402         static inline OutputIt
0403         apply(linestring_iterator first, linestring_iterator beyond,
0404               OutputIt oit)
0405         {
0406             for (linestring_iterator ls_it = first; ls_it != beyond; ++ls_it)
0407             {
0408                 LinestringOut line_out;
0409                 geometry::convert(*ls_it, line_out);
0410                 *oit++ = line_out;
0411             }
0412             return oit;
0413         }
0414     };
0415
0416     template <typename TurnIterator>
0417     static inline signed_size_type get_multi_index(TurnIterator it)
0418     {
0419         return boost::begin(it->operations)->seg_id.multi_index;
0420     }
0421
0422     class has_other_multi_id
0423     {
0424     private:
0425         signed_size_type m_multi_id;
0426
0427     public:
0428         has_other_multi_id(signed_size_type multi_id)
0429             : m_multi_id(multi_id) {}
0430
0431         template <typename Turn>
0432         bool operator()(Turn const& turn) const
0433         {
0434             return boost::begin(turn.operations)->seg_id.multi_index
0435                 != m_multi_id;
0436         }
0437     };
0438
0439 public:
0440     template <typename TurnIterator, typename OutputIterator, typename SideStrategy>
0441     static inline OutputIterator
0442     apply(MultiLinestring const& multilinestring, Linear const& linear,
0443           TurnIterator first, TurnIterator beyond,
0444           OutputIterator oit,
0445           SideStrategy const& strategy)
0446     {
0447         BOOST_GEOMETRY_ASSERT( first != beyond );
0448
0449         typedef copy_linestrings_in_range
0450             <
0451                 OutputIterator, OverlayType
0452             > copy_linestrings;
0453
0454         linestring_iterator ls_first = boost::begin(multilinestring);
0455         linestring_iterator ls_beyond = boost::end(multilinestring);
0456
0457         // Iterate through all intersection points (they are
0458         // ordered along the each linestring)
0459
0460         signed_size_type current_multi_id = get_multi_index(first);
0461
0462         oit = copy_linestrings::apply(ls_first,
0463                                       ls_first + current_multi_id,
0464                                       oit);
0465
0466         TurnIterator per_ls_next = first;
0467         do {
0468             TurnIterator per_ls_current = per_ls_next;
0469
0470             // find turn with different multi-index
0471             per_ls_next = std::find_if(per_ls_current, beyond,
0472                                        has_other_multi_id(current_multi_id));
0473
0474             oit = Base::apply(*(ls_first + current_multi_id),
0475                               linear, per_ls_current, per_ls_next, oit, strategy);
0476
0477             signed_size_type next_multi_id = -1;
0478             linestring_iterator ls_next = ls_beyond;
0479             if ( per_ls_next != beyond )
0480             {
0481                 next_multi_id = get_multi_index(per_ls_next);
0482                 ls_next = ls_first + next_multi_id;
0483             }
0484             oit = copy_linestrings::apply(ls_first + current_multi_id + 1,
0485                                           ls_next,
0486                                           oit);
0487
0488             current_multi_id = next_multi_id;
0489         }
0490         while ( per_ls_next != beyond );
0491
0492         return oit;
0493     }
0494 };
0495
0496
0497
0498
0499
0500
0501 template
0502 <
0503     typename LinestringOut,
0504     typename Geometry1,
0505     typename Geometry2,
0506     overlay_type OverlayType,
0507     bool FollowIsolatedPoints,
0508     bool FollowContinueTurns,
0509     typename TagIn1 = typename tag<Geometry1>::type
0510 >
0511 struct follow
0512     : not_implemented<Geometry1>
0513 {};
0514
0515
0516
0517 template
0518 <
0519     typename LinestringOut,
0520     typename Linestring,
0521     typename Linear,
0522     overlay_type OverlayType,
0523     bool FollowIsolatedPoints,
0524     bool FollowContinueTurns
0525 >
0526 struct follow
0527     <
0528         LinestringOut, Linestring, Linear,
0529         OverlayType, FollowIsolatedPoints, FollowContinueTurns,
0530         linestring_tag
0531     > : follow_linestring_linear
0532         <
0533             LinestringOut, Linestring, Linear,
0534             OverlayType, FollowIsolatedPoints, FollowContinueTurns
0535         >
0536 {};
0537
0538
0539 template
0540 <
0541     typename LinestringOut,
0542     typename MultiLinestring,
0543     typename Linear,
0544     overlay_type OverlayType,
0545     bool FollowIsolatedPoints,
0546     bool FollowContinueTurns
0547 >
0548 struct follow
0549     <
0550         LinestringOut, MultiLinestring, Linear,
0551         OverlayType, FollowIsolatedPoints, FollowContinueTurns,
0552         multi_linestring_tag
0553     > : follow_multilinestring_linear
0554         <
0555             LinestringOut, MultiLinestring, Linear,
0556             OverlayType, FollowIsolatedPoints, FollowContinueTurns
0557         >
0558 {};
0559
0560
0561
0562 }} // namespace following::linear
0563
0564 }} // namespace detail::overlay
0565 #endif // DOXYGEN_NO_DETAIL
0566
0567 }} // namespace boost::geometry
0568
0569
0570 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP