1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. 4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. 5 6 // This file was modified by Oracle on 2017, 2018. 7 // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates. 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 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP 15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP 16 17 #include <boost/core/ignore_unused.hpp> 18 #include <boost/range.hpp> 19 20 #include <boost/geometry/core/assert.hpp> 21 #include <boost/geometry/algorithms/equals.hpp> 22 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> 23 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> 24 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> 25 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp> 26 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp> 27 28 29 namespace boost { namespace geometry 30 { 31 32 33 #ifndef DOXYGEN_NO_DETAIL 34 namespace detail { namespace buffer 35 { 36 37 // Implements a unique_sub_range for a buffered piece, 38 // the range can return subsequent points 39 // known as "i", "j" and "k" (and further), indexed as 0,1,2,3 40 template <typename Ring> 41 struct unique_sub_range_from_piece 42 { 43 typedef typename boost::range_iterator<Ring const>::type iterator_type; 44 typedef typename geometry::point_type<Ring const>::type point_type; 45 unique_sub_range_from_pieceboost::geometry::detail::buffer::unique_sub_range_from_piece46 unique_sub_range_from_piece(Ring const& ring, 47 iterator_type iterator_at_i, iterator_type iterator_at_j) 48 : m_ring(ring) 49 , m_iterator_at_i(iterator_at_i) 50 , m_iterator_at_j(iterator_at_j) 51 , m_point_retrieved(false) 52 {} 53 is_first_segmentboost::geometry::detail::buffer::unique_sub_range_from_piece54 static inline bool is_first_segment() { return false; } is_last_segmentboost::geometry::detail::buffer::unique_sub_range_from_piece55 static inline bool is_last_segment() { return false; } 56 sizeboost::geometry::detail::buffer::unique_sub_range_from_piece57 static inline std::size_t size() { return 3u; } 58 atboost::geometry::detail::buffer::unique_sub_range_from_piece59 inline point_type const& at(std::size_t index) const 60 { 61 BOOST_GEOMETRY_ASSERT(index < size()); 62 switch (index) 63 { 64 case 0 : return *m_iterator_at_i; 65 case 1 : return *m_iterator_at_j; 66 case 2 : return get_point_k(); 67 default : return *m_iterator_at_i; 68 } 69 } 70 71 private : 72 get_point_kboost::geometry::detail::buffer::unique_sub_range_from_piece73 inline point_type const& get_point_k() const 74 { 75 if (! m_point_retrieved) 76 { 77 m_iterator_at_k = advance_one(m_iterator_at_j); 78 m_point_retrieved = true; 79 } 80 return *m_iterator_at_k; 81 } 82 circular_advance_oneboost::geometry::detail::buffer::unique_sub_range_from_piece83 inline void circular_advance_one(iterator_type& next) const 84 { 85 ++next; 86 if (next == boost::end(m_ring)) 87 { 88 next = boost::begin(m_ring) + 1; 89 } 90 } 91 advance_oneboost::geometry::detail::buffer::unique_sub_range_from_piece92 inline iterator_type advance_one(iterator_type it) const 93 { 94 iterator_type result = it; 95 circular_advance_one(result); 96 97 // TODO: we could also use piece-boundaries 98 // to check if the point equals the last one 99 while (geometry::equals(*it, *result)) 100 { 101 circular_advance_one(result); 102 } 103 return result; 104 } 105 106 Ring const& m_ring; 107 iterator_type m_iterator_at_i; 108 iterator_type m_iterator_at_j; 109 mutable iterator_type m_iterator_at_k; 110 mutable bool m_point_retrieved; 111 }; 112 113 template 114 < 115 typename Pieces, 116 typename Rings, 117 typename Turns, 118 typename IntersectionStrategy, 119 typename RobustPolicy 120 > 121 class piece_turn_visitor 122 { 123 Pieces const& m_pieces; 124 Rings const& m_rings; 125 Turns& m_turns; 126 IntersectionStrategy const& m_intersection_strategy; 127 RobustPolicy const& m_robust_policy; 128 129 template <typename Piece> is_adjacent(Piece const & piece1,Piece const & piece2) const130 inline bool is_adjacent(Piece const& piece1, Piece const& piece2) const 131 { 132 if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index) 133 { 134 return false; 135 } 136 137 return piece1.index == piece2.left_index 138 || piece1.index == piece2.right_index; 139 } 140 141 template <typename Piece> is_on_same_convex_ring(Piece const & piece1,Piece const & piece2) const142 inline bool is_on_same_convex_ring(Piece const& piece1, Piece const& piece2) const 143 { 144 if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index) 145 { 146 return false; 147 } 148 149 return ! m_rings[piece1.first_seg_id.multi_index].has_concave; 150 } 151 152 153 template <std::size_t Dimension, typename Iterator, typename Box> move_begin_iterator(Iterator & it_begin,Iterator it_beyond,signed_size_type & index,int dir,Box const & this_bounding_box,Box const & other_bounding_box)154 inline void move_begin_iterator(Iterator& it_begin, Iterator it_beyond, 155 signed_size_type& index, int dir, 156 Box const& this_bounding_box, 157 Box const& other_bounding_box) 158 { 159 for(; it_begin != it_beyond 160 && it_begin + 1 != it_beyond 161 && detail::section::preceding<Dimension>(dir, *(it_begin + 1), 162 this_bounding_box, 163 other_bounding_box, 164 m_robust_policy); 165 ++it_begin, index++) 166 {} 167 } 168 169 template <std::size_t Dimension, typename Iterator, typename Box> move_end_iterator(Iterator it_begin,Iterator & it_beyond,int dir,Box const & this_bounding_box,Box const & other_bounding_box)170 inline void move_end_iterator(Iterator it_begin, Iterator& it_beyond, 171 int dir, Box const& this_bounding_box, 172 Box const& other_bounding_box) 173 { 174 while (it_beyond != it_begin 175 && it_beyond - 1 != it_begin 176 && it_beyond - 2 != it_begin) 177 { 178 if (detail::section::exceeding<Dimension>(dir, *(it_beyond - 2), 179 this_bounding_box, other_bounding_box, m_robust_policy)) 180 { 181 --it_beyond; 182 } 183 else 184 { 185 return; 186 } 187 } 188 } 189 190 template <typename Piece, typename Section> calculate_turns(Piece const & piece1,Piece const & piece2,Section const & section1,Section const & section2)191 inline void calculate_turns(Piece const& piece1, Piece const& piece2, 192 Section const& section1, Section const& section2) 193 { 194 typedef typename boost::range_value<Rings const>::type ring_type; 195 typedef typename boost::range_value<Turns const>::type turn_type; 196 typedef typename boost::range_iterator<ring_type const>::type iterator; 197 198 signed_size_type const piece1_first_index = piece1.first_seg_id.segment_index; 199 signed_size_type const piece2_first_index = piece2.first_seg_id.segment_index; 200 if (piece1_first_index < 0 || piece2_first_index < 0) 201 { 202 return; 203 } 204 205 // Get indices of part of offsetted_rings for this monotonic section: 206 signed_size_type const sec1_first_index = piece1_first_index + section1.begin_index; 207 signed_size_type const sec2_first_index = piece2_first_index + section2.begin_index; 208 209 // index of last point in section, beyond-end is one further 210 signed_size_type const sec1_last_index = piece1_first_index + section1.end_index; 211 signed_size_type const sec2_last_index = piece2_first_index + section2.end_index; 212 213 // get geometry and iterators over these sections 214 ring_type const& ring1 = m_rings[piece1.first_seg_id.multi_index]; 215 iterator it1_first = boost::begin(ring1) + sec1_first_index; 216 iterator it1_beyond = boost::begin(ring1) + sec1_last_index + 1; 217 218 ring_type const& ring2 = m_rings[piece2.first_seg_id.multi_index]; 219 iterator it2_first = boost::begin(ring2) + sec2_first_index; 220 iterator it2_beyond = boost::begin(ring2) + sec2_last_index + 1; 221 222 // Set begin/end of monotonic ranges, in both x/y directions 223 signed_size_type index1 = sec1_first_index; 224 move_begin_iterator<0>(it1_first, it1_beyond, index1, 225 section1.directions[0], section1.bounding_box, section2.bounding_box); 226 move_end_iterator<0>(it1_first, it1_beyond, 227 section1.directions[0], section1.bounding_box, section2.bounding_box); 228 move_begin_iterator<1>(it1_first, it1_beyond, index1, 229 section1.directions[1], section1.bounding_box, section2.bounding_box); 230 move_end_iterator<1>(it1_first, it1_beyond, 231 section1.directions[1], section1.bounding_box, section2.bounding_box); 232 233 signed_size_type index2 = sec2_first_index; 234 move_begin_iterator<0>(it2_first, it2_beyond, index2, 235 section2.directions[0], section2.bounding_box, section1.bounding_box); 236 move_end_iterator<0>(it2_first, it2_beyond, 237 section2.directions[0], section2.bounding_box, section1.bounding_box); 238 move_begin_iterator<1>(it2_first, it2_beyond, index2, 239 section2.directions[1], section2.bounding_box, section1.bounding_box); 240 move_end_iterator<1>(it2_first, it2_beyond, 241 section2.directions[1], section2.bounding_box, section1.bounding_box); 242 243 turn_type the_model; 244 the_model.operations[0].piece_index = piece1.index; 245 the_model.operations[0].seg_id = piece1.first_seg_id; 246 the_model.operations[0].seg_id.segment_index = index1; // override 247 248 iterator it1 = it1_first; 249 for (iterator prev1 = it1++; 250 it1 != it1_beyond; 251 prev1 = it1++, the_model.operations[0].seg_id.segment_index++) 252 { 253 the_model.operations[1].piece_index = piece2.index; 254 the_model.operations[1].seg_id = piece2.first_seg_id; 255 the_model.operations[1].seg_id.segment_index = index2; // override 256 257 unique_sub_range_from_piece<ring_type> unique_sub_range1(ring1, prev1, it1); 258 259 iterator it2 = it2_first; 260 for (iterator prev2 = it2++; 261 it2 != it2_beyond; 262 prev2 = it2++, the_model.operations[1].seg_id.segment_index++) 263 { 264 unique_sub_range_from_piece<ring_type> unique_sub_range2(ring2, prev2, it2); 265 266 typedef detail::overlay::get_turn_info 267 < 268 detail::overlay::assign_null_policy 269 > turn_policy; 270 271 turn_policy::apply(unique_sub_range1, unique_sub_range2, 272 the_model, 273 m_intersection_strategy, 274 m_robust_policy, 275 std::back_inserter(m_turns)); 276 } 277 } 278 } 279 280 public: 281 piece_turn_visitor(Pieces const & pieces,Rings const & ring_collection,Turns & turns,IntersectionStrategy const & intersection_strategy,RobustPolicy const & robust_policy)282 piece_turn_visitor(Pieces const& pieces, 283 Rings const& ring_collection, 284 Turns& turns, 285 IntersectionStrategy const& intersection_strategy, 286 RobustPolicy const& robust_policy) 287 : m_pieces(pieces) 288 , m_rings(ring_collection) 289 , m_turns(turns) 290 , m_intersection_strategy(intersection_strategy) 291 , m_robust_policy(robust_policy) 292 {} 293 294 template <typename Section> apply(Section const & section1,Section const & section2,bool first=true)295 inline bool apply(Section const& section1, Section const& section2, 296 bool first = true) 297 { 298 boost::ignore_unused(first); 299 300 typedef typename boost::range_value<Pieces const>::type piece_type; 301 piece_type const& piece1 = m_pieces[section1.ring_id.source_index]; 302 piece_type const& piece2 = m_pieces[section2.ring_id.source_index]; 303 304 if ( piece1.index == piece2.index 305 || is_adjacent(piece1, piece2) 306 || is_on_same_convex_ring(piece1, piece2) 307 || detail::disjoint::disjoint_box_box(section1.bounding_box, 308 section2.bounding_box, 309 m_intersection_strategy.get_disjoint_box_box_strategy()) ) 310 { 311 return true; 312 } 313 314 calculate_turns(piece1, piece2, section1, section2); 315 316 return true; 317 } 318 }; 319 320 321 }} // namespace detail::buffer 322 #endif // DOXYGEN_NO_DETAIL 323 324 325 }} // namespace boost::geometry 326 327 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP 328