detail/relate/follow_helpers.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2013-2022.
0006 // Modifications copyright (c) 2013-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
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP
0017
0018 #include <vector>
0019
0020 #include <boost/core/ignore_unused.hpp>
0021 #include <boost/range/size.hpp>
0022
0023 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp>
0024 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0025 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
0026 #include <boost/geometry/algorithms/detail/relate/boundary_checker.hpp>
0027 #include <boost/geometry/algorithms/not_implemented.hpp>
0028
0029 #include <boost/geometry/core/assert.hpp>
0030
0031 #include <boost/geometry/util/condition.hpp>
0032 #include <boost/geometry/util/range.hpp>
0033
0034 #include <type_traits>
0035
0036 namespace boost { namespace geometry
0037 {
0038
0039 #ifndef DOXYGEN_NO_DETAIL
0040 namespace detail { namespace relate {
0041
0042 // NOTE: This iterates through single geometries for which turns were not generated.
0043 //       It doesn't mean that the geometry is disjoint, only that no turns were detected.
0044
0045 template <std::size_t OpId,
0046           typename Geometry,
0047           typename Tag = typename geometry::tag<Geometry>::type,
0048           bool IsMulti = std::is_base_of<multi_tag, Tag>::value
0049 >
0050 struct for_each_disjoint_geometry_if
0051     : public not_implemented<Tag>
0052 {};
0053
0054 template <std::size_t OpId, typename Geometry, typename Tag>
0055 struct for_each_disjoint_geometry_if<OpId, Geometry, Tag, false>
0056 {
0057     template <typename TurnIt, typename Pred>
0058     static void apply(TurnIt first, TurnIt last, Geometry const& geometry, Pred & pred)
0059     {
0060         if (first == last)
0061         {
0062             pred(geometry);
0063         }
0064     }
0065 };
0066
0067 template <std::size_t OpId, typename Geometry, typename Tag>
0068 struct for_each_disjoint_geometry_if<OpId, Geometry, Tag, true>
0069 {
0070     template <typename TurnIt, typename Pred>
0071     static void apply(TurnIt first, TurnIt last, Geometry const& geometry, Pred & pred)
0072     {
0073         if (first == last)
0074         {
0075             for_empty(geometry, pred);
0076         }
0077         else
0078         {
0079             for_turns(first, last, geometry, pred);
0080         }
0081     }
0082
0083     template <typename Pred>
0084     static void for_empty(Geometry const& geometry, Pred & pred)
0085     {
0086         // O(N)
0087         // check predicate for each contained geometry without generated turn
0088         for (auto it = boost::begin(geometry); it != boost::end(geometry) ; ++it)
0089         {
0090             if (! pred(*it))
0091             {
0092                 break;
0093             }
0094         }
0095     }
0096
0097     template <typename TurnIt, typename Pred>
0098     static void for_turns(TurnIt first, TurnIt last, Geometry const& geometry, Pred & pred)
0099     {
0100         BOOST_GEOMETRY_ASSERT(first != last);
0101
0102         std::size_t const count = boost::size(geometry);
0103
0104         // O(I)
0105         // gather info about turns generated for contained geometries
0106         std::vector<bool> detected_intersections(count, false);
0107         for (TurnIt it = first; it != last; ++it)
0108         {
0109             signed_size_type multi_index = it->operations[OpId].seg_id.multi_index;
0110             BOOST_GEOMETRY_ASSERT(multi_index >= 0);
0111             std::size_t const index = static_cast<std::size_t>(multi_index);
0112             BOOST_GEOMETRY_ASSERT(index < count);
0113             detected_intersections[index] = true;
0114         }
0115
0116         // O(N)
0117         // check predicate for each contained geometry without generated turn
0118         for (std::size_t index = 0; index < detected_intersections.size(); ++index)
0119         {
0120             // if there were no intersections for this multi_index
0121             if (detected_intersections[index] == false)
0122             {
0123                 if (! pred(range::at(geometry, index)))
0124                 {
0125                     break;
0126                 }
0127             }
0128         }
0129     }
0130 };
0131
0132
0133 // WARNING! This class stores pointers!
0134 // Passing a reference to local variable will result in undefined behavior!
0135 template <typename Point>
0136 class point_info
0137 {
0138 public:
0139     point_info() : sid_ptr(NULL), pt_ptr(NULL) {}
0140     point_info(Point const& pt, segment_identifier const& sid)
0141         : sid_ptr(boost::addressof(sid))
0142         , pt_ptr(boost::addressof(pt))
0143     {}
0144     segment_identifier const& seg_id() const
0145     {
0146         BOOST_GEOMETRY_ASSERT(sid_ptr);
0147         return *sid_ptr;
0148     }
0149     Point const& point() const
0150     {
0151         BOOST_GEOMETRY_ASSERT(pt_ptr);
0152         return *pt_ptr;
0153     }
0154
0155     //friend bool operator==(point_identifier const& l, point_identifier const& r)
0156     //{
0157     //    return l.seg_id() == r.seg_id()
0158     //        && detail::equals::equals_point_point(l.point(), r.point());
0159     //}
0160
0161 private:
0162     const segment_identifier * sid_ptr;
0163     const Point * pt_ptr;
0164 };
0165
0166 // WARNING! This class stores pointers!
0167 // Passing a reference to local variable will result in undefined behavior!
0168 class same_single
0169 {
0170 public:
0171     same_single(segment_identifier const& sid)
0172         : sid_ptr(boost::addressof(sid))
0173     {}
0174
0175     bool operator()(segment_identifier const& sid) const
0176     {
0177         return sid.multi_index == sid_ptr->multi_index;
0178     }
0179
0180     template <typename Point>
0181     bool operator()(point_info<Point> const& pid) const
0182     {
0183         return operator()(pid.seg_id());
0184     }
0185
0186 private:
0187     const segment_identifier * sid_ptr;
0188 };
0189
0190 class same_ring
0191 {
0192 public:
0193     same_ring(segment_identifier const& sid)
0194         : sid_ptr(boost::addressof(sid))
0195     {}
0196
0197     bool operator()(segment_identifier const& sid) const
0198     {
0199         return sid.multi_index == sid_ptr->multi_index
0200             && sid.ring_index == sid_ptr->ring_index;
0201     }
0202
0203 private:
0204     const segment_identifier * sid_ptr;
0205 };
0206
0207 // WARNING! This class stores pointers!
0208 // Passing a reference to local variable will result in undefined behavior!
0209 template <typename SameRange = same_single>
0210 class segment_watcher
0211 {
0212 public:
0213     segment_watcher()
0214         : m_seg_id_ptr(NULL)
0215     {}
0216
0217     bool update(segment_identifier const& seg_id)
0218     {
0219         bool result = m_seg_id_ptr == 0 || !SameRange(*m_seg_id_ptr)(seg_id);
0220         m_seg_id_ptr = boost::addressof(seg_id);
0221         return result;
0222     }
0223
0224 private:
0225     const segment_identifier * m_seg_id_ptr;
0226 };
0227
0228 // WARNING! This class stores pointers!
0229 // Passing a reference to local variable will result in undefined behavior!
0230 template <typename TurnInfo, std::size_t OpId>
0231 class exit_watcher
0232 {
0233     static std::size_t const op_id = OpId;
0234     static std::size_t const other_op_id = (OpId + 1) % 2;
0235
0236     typedef typename TurnInfo::point_type point_type;
0237     typedef detail::relate::point_info<point_type> point_info;
0238
0239 public:
0240     exit_watcher()
0241         : m_exit_operation(overlay::operation_none)
0242         , m_exit_turn_ptr(NULL)
0243     {}
0244
0245     void enter(TurnInfo const& turn)
0246     {
0247         m_other_entry_points.push_back(
0248             point_info(turn.point, turn.operations[other_op_id].seg_id) );
0249     }
0250
0251     // TODO: exit_per_geometry parameter looks not very safe
0252     //       wrong value may be easily passed
0253
0254     void exit(TurnInfo const& turn, bool exit_per_geometry = true)
0255     {
0256         //segment_identifier const& seg_id = turn.operations[op_id].seg_id;
0257         segment_identifier const& other_id = turn.operations[other_op_id].seg_id;
0258         overlay::operation_type exit_op = turn.operations[op_id].operation;
0259
0260         // search for the entry point in the same range of other geometry
0261         auto entry_it = std::find_if(m_other_entry_points.begin(),
0262                                      m_other_entry_points.end(),
0263                                      same_single(other_id));
0264
0265         // this end point has corresponding entry point
0266         if ( entry_it != m_other_entry_points.end() )
0267         {
0268             // erase the corresponding entry point
0269             m_other_entry_points.erase(entry_it);
0270
0271             if ( exit_per_geometry || m_other_entry_points.empty() )
0272             {
0273                 // here we know that we possibly left LS
0274                 // we must still check if we didn't get back on the same point
0275                 m_exit_operation = exit_op;
0276                 m_exit_turn_ptr = boost::addressof(turn);
0277             }
0278         }
0279     }
0280
0281     bool is_outside() const
0282     {
0283         // if we didn't entered anything in the past, we're outside
0284         return m_other_entry_points.empty();
0285     }
0286
0287     bool is_outside(TurnInfo const& turn) const
0288     {
0289         return m_other_entry_points.empty()
0290             || std::none_of(m_other_entry_points.begin(),
0291                             m_other_entry_points.end(),
0292                             same_single(
0293                                 turn.operations[other_op_id].seg_id));
0294     }
0295
0296     overlay::operation_type get_exit_operation() const
0297     {
0298         return m_exit_operation;
0299     }
0300
0301     point_type const& get_exit_point() const
0302     {
0303         BOOST_GEOMETRY_ASSERT(m_exit_operation != overlay::operation_none);
0304         BOOST_GEOMETRY_ASSERT(m_exit_turn_ptr);
0305         return m_exit_turn_ptr->point;
0306     }
0307
0308     TurnInfo const& get_exit_turn() const
0309     {
0310         BOOST_GEOMETRY_ASSERT(m_exit_operation != overlay::operation_none);
0311         BOOST_GEOMETRY_ASSERT(m_exit_turn_ptr);
0312         return *m_exit_turn_ptr;
0313     }
0314
0315     void reset_detected_exit()
0316     {
0317         m_exit_operation = overlay::operation_none;
0318     }
0319
0320     void reset()
0321     {
0322         m_exit_operation = overlay::operation_none;
0323         m_other_entry_points.clear();
0324     }
0325
0326 private:
0327     overlay::operation_type m_exit_operation;
0328     const TurnInfo * m_exit_turn_ptr;
0329     std::vector<point_info> m_other_entry_points; // TODO: use map here or sorted vector?
0330 };
0331
0332 template <std::size_t OpId, typename Turn, typename Strategy>
0333 inline bool turn_on_the_same_ip(Turn const& prev_turn, Turn const& curr_turn,
0334                                 Strategy const& strategy)
0335 {
0336     segment_identifier const& prev_seg_id = prev_turn.operations[OpId].seg_id;
0337     segment_identifier const& curr_seg_id = curr_turn.operations[OpId].seg_id;
0338
0339     if ( prev_seg_id.multi_index != curr_seg_id.multi_index
0340       || prev_seg_id.ring_index != curr_seg_id.ring_index )
0341     {
0342         return false;
0343     }
0344
0345     // TODO: will this work if between segments there will be some number of degenerated ones?
0346
0347     if ( prev_seg_id.segment_index != curr_seg_id.segment_index
0348       && ( ! curr_turn.operations[OpId].fraction.is_zero()
0349         || prev_seg_id.segment_index + 1 != curr_seg_id.segment_index ) )
0350     {
0351         return false;
0352     }
0353
0354     return detail::equals::equals_point_point(prev_turn.point, curr_turn.point, strategy);
0355 }
0356
0357 template <typename IntersectionPoint, typename OperationInfo, typename BoundaryChecker>
0358 static inline bool is_ip_on_boundary(IntersectionPoint const& ip,
0359                                      OperationInfo const& operation_info,
0360                                      BoundaryChecker const& boundary_checker)
0361 {
0362     // IP on the first or the last point of the linestring
0363     return (operation_info.position == overlay::position_back
0364             || operation_info.position == overlay::position_front)
0365          // check if this point is a boundary
0366          ? boundary_checker.is_endpoint_boundary(ip)
0367          : false;
0368 }
0369
0370
0371 }} // namespace detail::relate
0372 #endif // DOXYGEN_NO_DETAIL
0373
0374 }} // namespace boost::geometry
0375
0376 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP