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