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