ceph/src/boost/boost/geometry/algorithms/detail/relate/follow_helpers.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2013, 2014.
   6 // Modifications copyright (c) 2013-2014 Oracle and/or its affiliates.
   7
   8 // Use, modification and distribution is subject to the Boost Software License,
   9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  10 // http://www.boost.org/LICENSE_1_0.txt)
  11
  12 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP
  16
  17 #include <boost/geometry/core/assert.hpp>
  18
  19 #include <boost/geometry/util/condition.hpp>
  20 #include <boost/geometry/util/range.hpp>
  21 //#include <boost/geometry/algorithms/detail/sub_range.hpp>
  22
  23 namespace boost { namespace geometry
  24 {
  25
  26 #ifndef DOXYGEN_NO_DETAIL
  27 namespace detail { namespace relate {
  28
  29 // NOTE: This iterates through single geometries for which turns were not generated.
  30 //       It doesn't mean that the geometry is disjoint, only that no turns were detected.
  31
  32 template <std::size_t OpId,
  33           typename Geometry,
  34           typename Tag = typename geometry::tag<Geometry>::type,
  35           bool IsMulti = boost::is_base_of<multi_tag, Tag>::value
  36 >
  37 struct for_each_disjoint_geometry_if
  38     : public not_implemented<Tag>
  39 {};
  40
  41 template <std::size_t OpId, typename Geometry, typename Tag>
  42 struct for_each_disjoint_geometry_if<OpId, Geometry, Tag, false>
  43 {
  44     template <typename TurnIt, typename Pred>
  45     static inline bool apply(TurnIt first, TurnIt last,
  46                              Geometry const& geometry,
  47                              Pred & pred)
  48     {
  49         if ( first != last )
  50             return false;
  51         pred(geometry);
  52         return true;
  53     }
  54 };
  55
  56 template <std::size_t OpId, typename Geometry, typename Tag>
  57 struct for_each_disjoint_geometry_if<OpId, Geometry, Tag, true>
  58 {
  59     template <typename TurnIt, typename Pred>
  60     static inline bool apply(TurnIt first, TurnIt last,
  61                              Geometry const& geometry,
  62                              Pred & pred)
  63     {
  64         if ( first != last )
  65             return for_turns(first, last, geometry, pred);
  66         else
  67             return for_empty(geometry, pred);
  68     }
  69
  70     template <typename Pred>
  71     static inline bool for_empty(Geometry const& geometry,
  72                                  Pred & pred)
  73     {
  74         typedef typename boost::range_iterator<Geometry const>::type iterator;
  75
  76         // O(N)
  77         // check predicate for each contained geometry without generated turn
  78         for ( iterator it = boost::begin(geometry) ;
  79               it != boost::end(geometry) ; ++it )
  80         {
  81             bool cont = pred(*it);
  82             if ( !cont )
  83                 break;
  84         }
  85
  86         return !boost::empty(geometry);
  87     }
  88
  89     template <typename TurnIt, typename Pred>
  90     static inline bool for_turns(TurnIt first, TurnIt last,
  91                                  Geometry const& geometry,
  92                                  Pred & pred)
  93     {
  94         BOOST_GEOMETRY_ASSERT(first != last);
  95
  96         const std::size_t count = boost::size(geometry);
  97         boost::ignore_unused_variable_warning(count);
  98
  99         // O(I)
 100         // gather info about turns generated for contained geometries
 101         std::vector<bool> detected_intersections(count, false);
 102         for ( TurnIt it = first ; it != last ; ++it )
 103         {
 104             signed_size_type multi_index = it->operations[OpId].seg_id.multi_index;
 105             BOOST_GEOMETRY_ASSERT(multi_index >= 0);
 106             std::size_t const index = static_cast<std::size_t>(multi_index);
 107             BOOST_GEOMETRY_ASSERT(index < count);
 108             detected_intersections[index] = true;
 109         }
 110
 111         bool found = false;
 112
 113         // O(N)
 114         // check predicate for each contained geometry without generated turn
 115         for ( std::vector<bool>::iterator it = detected_intersections.begin() ;
 116               it != detected_intersections.end() ; ++it )
 117         {
 118             // if there were no intersections for this multi_index
 119             if ( *it == false )
 120             {
 121                 found = true;
 122                 std::size_t const index = std::size_t(std::distance(detected_intersections.begin(), it));
 123                 bool cont = pred(range::at(geometry, index));
 124                 if ( !cont )
 125                     break;
 126             }
 127         }
 128
 129         return found;
 130     }
 131 };
 132
 133 // WARNING! This class stores pointers!
 134 // Passing a reference to local variable will result in undefined behavior!
 135 template <typename Point>
 136 class point_info
 137 {
 138 public:
 139     point_info() : sid_ptr(NULL), pt_ptr(NULL) {}
 140     point_info(Point const& pt, segment_identifier const& sid)
 141         : sid_ptr(boost::addressof(sid))
 142         , pt_ptr(boost::addressof(pt))
 143     {}
 144     segment_identifier const& seg_id() const
 145     {
 146         BOOST_GEOMETRY_ASSERT(sid_ptr);
 147         return *sid_ptr;
 148     }
 149     Point const& point() const
 150     {
 151         BOOST_GEOMETRY_ASSERT(pt_ptr);
 152         return *pt_ptr;
 153     }
 154
 155     //friend bool operator==(point_identifier const& l, point_identifier const& r)
 156     //{
 157     //    return l.seg_id() == r.seg_id()
 158     //        && detail::equals::equals_point_point(l.point(), r.point());
 159     //}
 160
 161 private:
 162     const segment_identifier * sid_ptr;
 163     const Point * pt_ptr;
 164 };
 165
 166 // WARNING! This class stores pointers!
 167 // Passing a reference to local variable will result in undefined behavior!
 168 class same_single
 169 {
 170 public:
 171     same_single(segment_identifier const& sid)
 172         : sid_ptr(boost::addressof(sid))
 173     {}
 174
 175     bool operator()(segment_identifier const& sid) const
 176     {
 177         return sid.multi_index == sid_ptr->multi_index;
 178     }
 179
 180     template <typename Point>
 181     bool operator()(point_info<Point> const& pid) const
 182     {
 183         return operator()(pid.seg_id());
 184     }
 185
 186 private:
 187     const segment_identifier * sid_ptr;
 188 };
 189
 190 class same_ring
 191 {
 192 public:
 193     same_ring(segment_identifier const& sid)
 194         : sid_ptr(boost::addressof(sid))
 195     {}
 196
 197     bool operator()(segment_identifier const& sid) const
 198     {
 199         return sid.multi_index == sid_ptr->multi_index
 200             && sid.ring_index == sid_ptr->ring_index;
 201     }
 202
 203 private:
 204     const segment_identifier * sid_ptr;
 205 };
 206
 207 // WARNING! This class stores pointers!
 208 // Passing a reference to local variable will result in undefined behavior!
 209 template <typename SameRange = same_single>
 210 class segment_watcher
 211 {
 212 public:
 213     segment_watcher()
 214         : m_seg_id_ptr(NULL)
 215     {}
 216
 217     bool update(segment_identifier const& seg_id)
 218     {
 219         bool result = m_seg_id_ptr == 0 || !SameRange(*m_seg_id_ptr)(seg_id);
 220         m_seg_id_ptr = boost::addressof(seg_id);
 221         return result;
 222     }
 223
 224 private:
 225     const segment_identifier * m_seg_id_ptr;
 226 };
 227
 228 // WARNING! This class stores pointers!
 229 // Passing a reference to local variable will result in undefined behavior!
 230 template <typename TurnInfo, std::size_t OpId>
 231 class exit_watcher
 232 {
 233     static const std::size_t op_id = OpId;
 234     static const std::size_t other_op_id = (OpId + 1) % 2;
 235
 236     typedef typename TurnInfo::point_type point_type;
 237     typedef detail::relate::point_info<point_type> point_info;
 238
 239 public:
 240     exit_watcher()
 241         : m_exit_operation(overlay::operation_none)
 242         , m_exit_turn_ptr(NULL)
 243     {}
 244
 245     void enter(TurnInfo const& turn)
 246     {
 247         m_other_entry_points.push_back(
 248             point_info(turn.point, turn.operations[other_op_id].seg_id) );
 249     }
 250
 251     // TODO: exit_per_geometry parameter looks not very safe
 252     //       wrong value may be easily passed
 253
 254     void exit(TurnInfo const& turn, bool exit_per_geometry = true)
 255     {
 256         //segment_identifier const& seg_id = turn.operations[op_id].seg_id;
 257         segment_identifier const& other_id = turn.operations[other_op_id].seg_id;
 258         overlay::operation_type exit_op = turn.operations[op_id].operation;
 259
 260         typedef typename std::vector<point_info>::iterator point_iterator;
 261         // search for the entry point in the same range of other geometry
 262         point_iterator entry_it = std::find_if(m_other_entry_points.begin(),
 263                                                m_other_entry_points.end(),
 264                                                same_single(other_id));
 265
 266         // this end point has corresponding entry point
 267         if ( entry_it != m_other_entry_points.end() )
 268         {
 269             // erase the corresponding entry point
 270             m_other_entry_points.erase(entry_it);
 271
 272             if ( exit_per_geometry || m_other_entry_points.empty() )
 273             {
 274                 // here we know that we possibly left LS
 275                 // we must still check if we didn't get back on the same point
 276                 m_exit_operation = exit_op;
 277                 m_exit_turn_ptr = boost::addressof(turn);
 278             }
 279         }
 280     }
 281
 282     bool is_outside() const
 283     {
 284         // if we didn't entered anything in the past, we're outside
 285         return m_other_entry_points.empty();
 286     }
 287
 288     bool is_outside(TurnInfo const& turn) const
 289     {
 290         return m_other_entry_points.empty()
 291             || std::find_if(m_other_entry_points.begin(),
 292                             m_other_entry_points.end(),
 293                             same_single(
 294                                 turn.operations[other_op_id].seg_id))
 295                     == m_other_entry_points.end();
 296     }
 297
 298     overlay::operation_type get_exit_operation() const
 299     {
 300         return m_exit_operation;
 301     }
 302
 303     point_type const& get_exit_point() const
 304     {
 305         BOOST_GEOMETRY_ASSERT(m_exit_operation != overlay::operation_none);
 306         BOOST_GEOMETRY_ASSERT(m_exit_turn_ptr);
 307         return m_exit_turn_ptr->point;
 308     }
 309
 310     TurnInfo const& get_exit_turn() const
 311     {
 312         BOOST_GEOMETRY_ASSERT(m_exit_operation != overlay::operation_none);
 313         BOOST_GEOMETRY_ASSERT(m_exit_turn_ptr);
 314         return *m_exit_turn_ptr;
 315     }
 316
 317     void reset_detected_exit()
 318     {
 319         m_exit_operation = overlay::operation_none;
 320     }
 321
 322     void reset()
 323     {
 324         m_exit_operation = overlay::operation_none;
 325         m_other_entry_points.clear();
 326     }
 327
 328 private:
 329     overlay::operation_type m_exit_operation;
 330     const TurnInfo * m_exit_turn_ptr;
 331     std::vector<point_info> m_other_entry_points; // TODO: use map here or sorted vector?
 332 };
 333
 334 template <std::size_t OpId, typename Turn>
 335 inline bool turn_on_the_same_ip(Turn const& prev_turn, Turn const& curr_turn)
 336 {
 337     segment_identifier const& prev_seg_id = prev_turn.operations[OpId].seg_id;
 338     segment_identifier const& curr_seg_id = curr_turn.operations[OpId].seg_id;
 339
 340     if ( prev_seg_id.multi_index != curr_seg_id.multi_index
 341       || prev_seg_id.ring_index != curr_seg_id.ring_index )
 342     {
 343         return false;
 344     }
 345
 346     // TODO: will this work if between segments there will be some number of degenerated ones?
 347
 348     if ( prev_seg_id.segment_index != curr_seg_id.segment_index
 349       && ( ! curr_turn.operations[OpId].fraction.is_zero()
 350         || prev_seg_id.segment_index + 1 != curr_seg_id.segment_index ) )
 351     {
 352         return false;
 353     }
 354
 355     return detail::equals::equals_point_point(prev_turn.point, curr_turn.point);
 356 }
 357
 358 template <boundary_query BoundaryQuery,
 359           typename Point,
 360           typename BoundaryChecker>
 361 static inline bool is_endpoint_on_boundary(Point const& pt,
 362                                            BoundaryChecker & boundary_checker)
 363 {
 364     return boundary_checker.template is_endpoint_boundary<BoundaryQuery>(pt);
 365 }
 366
 367 template <boundary_query BoundaryQuery,
 368           typename IntersectionPoint,
 369           typename OperationInfo,
 370           typename BoundaryChecker>
 371 static inline bool is_ip_on_boundary(IntersectionPoint const& ip,
 372                                      OperationInfo const& operation_info,
 373                                      BoundaryChecker & boundary_checker,
 374                                      segment_identifier const& seg_id)
 375 {
 376     boost::ignore_unused_variable_warning(seg_id);
 377
 378     bool res = false;
 379
 380     // IP on the last point of the linestring
 381     if ( BOOST_GEOMETRY_CONDITION(BoundaryQuery == boundary_back || BoundaryQuery == boundary_any)
 382       && operation_info.position == overlay::position_back )
 383     {
 384         // check if this point is a boundary
 385         res = boundary_checker.template is_endpoint_boundary<boundary_back>(ip);
 386     }
 387     // IP on the last point of the linestring
 388     else if ( BOOST_GEOMETRY_CONDITION(BoundaryQuery == boundary_front || BoundaryQuery == boundary_any)
 389            && operation_info.position == overlay::position_front )
 390     {
 391         // check if this point is a boundary
 392         res = boundary_checker.template is_endpoint_boundary<boundary_front>(ip);
 393     }
 394
 395     return res;
 396 }
 397
 398
 399 }} // namespace detail::relate
 400 #endif // DOXYGEN_NO_DETAIL
 401
 402 }} // namespace boost::geometry
 403
 404 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_FOLLOW_HELPERS_HPP