detail/overlay/follow.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2014-2024.
0007 // Modifications copyright (c) 2014-2024 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0009 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011
0012 // Use, modification and distribution is subject to the Boost Software License,
0013 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0014 // http://www.boost.org/LICENSE_1_0.txt)
0015
0016 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
0017 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
0018
0019 #include <cstddef>
0020 #include <type_traits>
0021
0022 #include <boost/range/begin.hpp>
0023 #include <boost/range/end.hpp>
0024 #include <boost/range/size.hpp>
0025 #include <boost/range/value_type.hpp>
0026
0027 #include <boost/geometry/algorithms/clear.hpp>
0028 #include <boost/geometry/algorithms/detail/covered_by/implementation.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
0030 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
0031 #include <boost/geometry/algorithms/detail/overlay/debug_traverse.hpp>
0032 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0033 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
0034 #include <boost/geometry/algorithms/detail/relate/turns.hpp>
0035 #include <boost/geometry/algorithms/detail/tupled_output.hpp>
0036 #include <boost/geometry/core/static_assert.hpp>
0037 #include <boost/geometry/util/condition.hpp>
0038
0039 namespace boost { namespace geometry
0040 {
0041
0042
0043 #ifndef DOXYGEN_NO_DETAIL
0044 namespace detail { namespace overlay
0045 {
0046
0047 namespace following
0048 {
0049
0050 template <typename Turn, typename Operation>
0051 inline bool is_entering(Turn const& /* TODO remove this parameter */, Operation const& op)
0052 {
0053     // (Blocked means: blocked for polygon/polygon intersection, because
0054     // they are reversed. But for polygon/line it is similar to continue)
0055     return op.operation == operation_intersection
0056         || op.operation == operation_continue
0057         || op.operation == operation_blocked
0058         ;
0059 }
0060
0061 template
0062 <
0063     typename Turn,
0064     typename Operation,
0065     typename LineString,
0066     typename Polygon,
0067     typename Strategy
0068 >
0069 inline bool last_covered_by(Turn const& /*turn*/, Operation const& op,
0070                 LineString const& linestring, Polygon const& polygon,
0071                 Strategy const& strategy)
0072 {
0073     return geometry::covered_by(range::at(linestring, op.seg_id.segment_index), polygon, strategy);
0074 }
0075
0076
0077 template
0078 <
0079     typename Turn,
0080     typename Operation,
0081     typename LineString,
0082     typename Polygon,
0083     typename Strategy
0084 >
0085 inline bool is_leaving(Turn const& turn, Operation const& op,
0086                 bool entered, bool first,
0087                 LineString const& linestring, Polygon const& polygon,
0088                 Strategy const& strategy)
0089 {
0090     if (op.operation == operation_union)
0091     {
0092         return entered
0093             || turn.method == method_crosses
0094             || (first
0095                 && op.position != position_front
0096                 && last_covered_by(turn, op, linestring, polygon, strategy))
0097             ;
0098     }
0099     return false;
0100 }
0101
0102
0103 template
0104 <
0105     typename Turn,
0106     typename Operation,
0107     typename LineString,
0108     typename Polygon,
0109     typename Strategy
0110 >
0111 inline bool is_staying_inside(Turn const& turn, Operation const& op,
0112                 bool entered, bool first,
0113                 LineString const& linestring, Polygon const& polygon,
0114                 Strategy const& strategy)
0115 {
0116     if (turn.method == method_crosses)
0117     {
0118         // The normal case, this is completely covered with entering/leaving
0119         // so stay out of this time consuming "covered_by"
0120         return false;
0121     }
0122
0123     if (is_entering(turn, op))
0124     {
0125         return entered || (first && last_covered_by(turn, op, linestring, polygon, strategy));
0126     }
0127
0128     return false;
0129 }
0130
0131 template
0132 <
0133     typename Turn,
0134     typename Operation,
0135     typename Linestring,
0136     typename Polygon,
0137     typename Strategy
0138 >
0139 inline bool was_entered(Turn const& turn, Operation const& op, bool first,
0140                 Linestring const& linestring, Polygon const& polygon,
0141                 Strategy const& strategy)
0142 {
0143     if (first && (turn.method == method_collinear || turn.method == method_equal))
0144     {
0145         return last_covered_by(turn, op, linestring, polygon, strategy);
0146     }
0147     return false;
0148 }
0149
0150 template
0151 <
0152     typename Turn,
0153     typename Operation
0154 >
0155 inline bool is_touching(Turn const& turn, Operation const& op,
0156                         bool entered)
0157 {
0158     return (op.operation == operation_union || op.operation == operation_blocked)
0159         && (turn.method == method_touch || turn.method == method_touch_interior)
0160         && !entered
0161         && !op.is_collinear;
0162 }
0163
0164
0165 template
0166 <
0167     typename GeometryOut,
0168     typename Tag = geometry::tag_t<GeometryOut>
0169 >
0170 struct add_isolated_point
0171 {};
0172
0173 template <typename LineStringOut>
0174 struct add_isolated_point<LineStringOut, linestring_tag>
0175 {
0176     template <typename Point, typename OutputIterator>
0177     static inline void apply(Point const& point, OutputIterator& out)
0178     {
0179         LineStringOut isolated_point_ls;
0180         geometry::append(isolated_point_ls, point);
0181
0182 #ifndef BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
0183         geometry::append(isolated_point_ls, point);
0184 #endif // BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
0185
0186         *out++ = isolated_point_ls;
0187     }
0188 };
0189
0190 template <typename PointOut>
0191 struct add_isolated_point<PointOut, point_tag>
0192 {
0193     template <typename Point, typename OutputIterator>
0194     static inline void apply(Point const& point, OutputIterator& out)
0195     {
0196         PointOut isolated_point;
0197
0198         geometry::detail::conversion::convert_point_to_point(point, isolated_point);
0199
0200         *out++ = isolated_point;
0201     }
0202 };
0203
0204
0205 // Template specialization structure to call the right actions for the right type
0206 template <overlay_type OverlayType, bool RemoveSpikes = true>
0207 struct action_selector
0208 {
0209     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0210         "If you get here the overlay type is not intersection or difference.",
0211         std::integral_constant<overlay_type, OverlayType>);
0212 };
0213
0214 // Specialization for intersection, containing the implementation
0215 template <bool RemoveSpikes>
0216 struct action_selector<overlay_intersection, RemoveSpikes>
0217 {
0218     template
0219     <
0220         typename OutputIterator,
0221         typename LineStringOut,
0222         typename LineString,
0223         typename Point,
0224         typename Operation,
0225         typename Strategy
0226     >
0227     static inline void enter(LineStringOut& current_piece,
0228                 LineString const& ,
0229                 segment_identifier& segment_id,
0230                 signed_size_type , Point const& point,
0231                 Operation const& operation,
0232                 Strategy const& strategy,
0233                 OutputIterator& )
0234     {
0235         // On enter, append the intersection point and remember starting point
0236         // TODO: we don't check on spikes for linestrings (?). Consider this.
0237         detail::overlay::append_no_duplicates(current_piece, point, strategy);
0238         segment_id = operation.seg_id;
0239     }
0240
0241     template
0242     <
0243         typename OutputIterator,
0244         typename LineStringOut,
0245         typename LineString,
0246         typename Point,
0247         typename Operation,
0248         typename Strategy
0249     >
0250     static inline void leave(LineStringOut& current_piece,
0251                 LineString const& linestring,
0252                 segment_identifier& segment_id,
0253                 signed_size_type index, Point const& point,
0254                 Operation const& ,
0255                 Strategy const& strategy,
0256                 OutputIterator& out)
0257     {
0258         // On leave, copy all segments from starting point, append the intersection point
0259         // and add the output piece
0260         detail::copy_segments::copy_segments_linestring
0261             <
0262                 false, RemoveSpikes
0263             >::apply(linestring, segment_id, index, strategy, current_piece);
0264         detail::overlay::append_no_duplicates(current_piece, point, strategy);
0265         if (::boost::size(current_piece) > 1)
0266         {
0267             *out++ = current_piece;
0268         }
0269
0270         geometry::clear(current_piece);
0271     }
0272
0273     template
0274     <
0275         typename LineStringOrPointOut,
0276         typename Point,
0277         typename OutputIterator
0278     >
0279     static inline void isolated_point(Point const& point,
0280                                       OutputIterator& out)
0281     {
0282         add_isolated_point<LineStringOrPointOut>::apply(point, out);
0283     }
0284
0285     static inline bool is_entered(bool entered)
0286     {
0287         return entered;
0288     }
0289
0290     static inline bool included(int inside_value)
0291     {
0292         return inside_value >= 0; // covered_by
0293     }
0294
0295 };
0296
0297 // Specialization for difference, which reverses these actions
0298 template <bool RemoveSpikes>
0299 struct action_selector<overlay_difference, RemoveSpikes>
0300 {
0301     using normal_action = action_selector<overlay_intersection, RemoveSpikes>;
0302
0303     template
0304     <
0305         typename OutputIterator,
0306         typename LineStringOut,
0307         typename LineString,
0308         typename Point,
0309         typename Operation,
0310         typename Strategy
0311     >
0312     static inline void enter(LineStringOut& current_piece,
0313                 LineString const& linestring,
0314                 segment_identifier& segment_id,
0315                 signed_size_type index, Point const& point,
0316                 Operation const& operation,
0317                 Strategy const& strategy,
0318                 OutputIterator& out)
0319     {
0320         normal_action::leave(current_piece, linestring, segment_id, index,
0321                     point, operation, strategy, out);
0322     }
0323
0324     template
0325     <
0326         typename OutputIterator,
0327         typename LineStringOut,
0328         typename LineString,
0329         typename Point,
0330         typename Operation,
0331         typename Strategy
0332     >
0333     static inline void leave(LineStringOut& current_piece,
0334                 LineString const& linestring,
0335                 segment_identifier& segment_id,
0336                 signed_size_type index, Point const& point,
0337                 Operation const& operation,
0338                 Strategy const& strategy,
0339                 OutputIterator& out)
0340     {
0341         normal_action::enter(current_piece, linestring, segment_id, index,
0342                     point, operation, strategy, out);
0343     }
0344
0345     template
0346     <
0347         typename LineStringOrPointOut,
0348         typename Point,
0349         typename OutputIterator
0350     >
0351     static inline void isolated_point(Point const&,
0352                                       OutputIterator const&)
0353     {
0354     }
0355
0356     static inline bool is_entered(bool entered)
0357     {
0358         return ! normal_action::is_entered(entered);
0359     }
0360
0361     static inline bool included(int inside_value)
0362     {
0363         return ! normal_action::included(inside_value);
0364     }
0365
0366 };
0367
0368 } // namespace following
0369
0370 /*!
0371 \brief Follows a linestring from intersection point to intersection point, outputting which
0372     is inside, or outside, a ring or polygon
0373 \ingroup overlay
0374  */
0375 template
0376 <
0377     typename GeometryOut,
0378     typename LineString,
0379     typename Polygon,
0380     overlay_type OverlayType,
0381     bool RemoveSpikes,
0382     bool FollowIsolatedPoints
0383 >
0384 class follow
0385 {
0386     using linear = geometry::detail::output_geometry_access
0387         <
0388             GeometryOut, linestring_tag, linestring_tag
0389         >;
0390     using pointlike = geometry::detail::output_geometry_access
0391         <
0392             GeometryOut, point_tag, linestring_tag
0393         >;
0394
0395 public :
0396
0397     static inline bool included(int inside_value)
0398     {
0399         return following::action_selector
0400             <
0401                 OverlayType, RemoveSpikes
0402             >::included(inside_value);
0403     }
0404
0405     template
0406     <
0407         typename Turns,
0408         typename OutputIterator,
0409         typename Strategy
0410     >
0411     static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
0412                 detail::overlay::operation_type ,  // TODO: this parameter might be redundant
0413                 Turns& turns,
0414                 OutputIterator out,
0415                 Strategy const& strategy)
0416     {
0417         using action = following::action_selector<OverlayType, RemoveSpikes>;
0418
0419         // Sort intersection points on segments-along-linestring, and distance
0420         // (like in enrich is done for poly/poly)
0421         // sort turns by Linear seg_id, then by fraction, then
0422         // for same ring id: x, u, i, c
0423         // for different ring id: c, i, u, x
0424         using turn_less = relate::turns::less
0425             <
0426                 0, relate::turns::less_op_linear_areal_single<0>, Strategy
0427             >;
0428         std::sort(boost::begin(turns), boost::end(turns), turn_less());
0429
0430         typename linear::type current_piece;
0431         geometry::segment_identifier current_segment_id(0, -1, -1, -1);
0432
0433         // Iterate through all intersection points (they are ordered along the line)
0434         bool entered = false;
0435         bool first = true;
0436         for (auto const& turn : turns)
0437         {
0438             auto const& op = turn.operations[0];
0439
0440             if (following::was_entered(turn, op, first, linestring, polygon, strategy))
0441             {
0442                 debug_traverse(turn, op, "-> Was entered");
0443                 entered = true;
0444             }
0445
0446             if (following::is_staying_inside(turn, op, entered, first, linestring, polygon, strategy))
0447             {
0448                 debug_traverse(turn, op, "-> Staying inside");
0449
0450                 entered = true;
0451             }
0452             else if (following::is_entering(turn, op))
0453             {
0454                 debug_traverse(turn, op, "-> Entering");
0455
0456                 entered = true;
0457                 action::enter(current_piece, linestring, current_segment_id,
0458                     op.seg_id.segment_index, turn.point, op,
0459                     strategy,
0460                     linear::get(out));
0461             }
0462             else if (following::is_leaving(turn, op, entered, first, linestring, polygon, strategy))
0463             {
0464                 debug_traverse(turn, op, "-> Leaving");
0465
0466                 entered = false;
0467                 action::leave(current_piece, linestring, current_segment_id,
0468                     op.seg_id.segment_index, turn.point, op,
0469                     strategy,
0470                     linear::get(out));
0471             }
0472             else if (BOOST_GEOMETRY_CONDITION(FollowIsolatedPoints)
0473                   && following::is_touching(turn, op, entered))
0474             {
0475                 debug_traverse(turn, op, "-> Isolated point");
0476
0477                 action::template isolated_point
0478                     <
0479                         typename pointlike::type
0480                     >(turn.point, pointlike::get(out));
0481             }
0482
0483             first = false;
0484         }
0485
0486         if (action::is_entered(entered))
0487         {
0488             detail::copy_segments::copy_segments_linestring
0489                 <
0490                     false, RemoveSpikes
0491                 >::apply(linestring,
0492                          current_segment_id,
0493                          static_cast<signed_size_type>(boost::size(linestring) - 1),
0494                          strategy,
0495                          current_piece);
0496         }
0497
0498         // Output the last one, if applicable
0499         std::size_t current_piece_size = ::boost::size(current_piece);
0500         if (current_piece_size > 1)
0501         {
0502             *linear::get(out)++ = current_piece;
0503         }
0504         else if (BOOST_GEOMETRY_CONDITION(FollowIsolatedPoints)
0505               && current_piece_size == 1)
0506         {
0507             action::template isolated_point
0508                 <
0509                     typename pointlike::type
0510                 >(range::front(current_piece), pointlike::get(out));
0511         }
0512
0513         return out;
0514     }
0515
0516 };
0517
0518
0519 }} // namespace detail::overlay
0520 #endif // DOXYGEN_NO_DETAIL
0521
0522
0523 }} // namespace boost::geometry
0524
0525
0526 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP