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