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 2017, 2018. 6 // Modifications copyright (c) 2017-2018, Oracle and/or its affiliates. 7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 8 9 // Use, modification and distribution is subject to the Boost Software License, 10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 11 // http://www.boost.org/LICENSE_1_0.txt) 12 13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP 14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP 15 16 #include <cstddef> 17 18 #include <boost/range.hpp> 19 20 #include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp> 21 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> 22 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> 23 #include <boost/geometry/algorithms/detail/overlay/traversal.hpp> 24 #include <boost/geometry/algorithms/num_points.hpp> 25 #include <boost/geometry/core/access.hpp> 26 #include <boost/geometry/core/assert.hpp> 27 #include <boost/geometry/core/closure.hpp> 28 29 namespace boost { namespace geometry 30 { 31 32 #ifndef DOXYGEN_NO_DETAIL 33 namespace detail { namespace overlay 34 { 35 36 37 template 38 < 39 bool Reverse1, 40 bool Reverse2, 41 overlay_type OverlayType, 42 typename Geometry1, 43 typename Geometry2, 44 typename Turns, 45 typename TurnInfoMap, 46 typename Clusters, 47 typename IntersectionStrategy, 48 typename RobustPolicy, 49 typename Visitor, 50 typename Backtrack 51 > 52 struct traversal_ring_creator 53 { 54 typedef traversal 55 < 56 Reverse1, Reverse2, OverlayType, 57 Geometry1, Geometry2, Turns, Clusters, 58 RobustPolicy, typename IntersectionStrategy::side_strategy_type, 59 Visitor 60 > traversal_type; 61 62 typedef typename boost::range_value<Turns>::type turn_type; 63 typedef typename turn_type::turn_operation_type turn_operation_type; 64 65 static const operation_type target_operation 66 = operation_from_overlay<OverlayType>::value; 67 traversal_ring_creatorboost::geometry::detail::overlay::traversal_ring_creator68 inline traversal_ring_creator(Geometry1 const& geometry1, Geometry2 const& geometry2, 69 Turns& turns, TurnInfoMap& turn_info_map, 70 Clusters const& clusters, 71 IntersectionStrategy const& intersection_strategy, 72 RobustPolicy const& robust_policy, Visitor& visitor) 73 : m_trav(geometry1, geometry2, turns, clusters, 74 robust_policy, intersection_strategy.get_side_strategy(), 75 visitor) 76 , m_geometry1(geometry1) 77 , m_geometry2(geometry2) 78 , m_turns(turns) 79 , m_turn_info_map(turn_info_map) 80 , m_clusters(clusters) 81 , m_intersection_strategy(intersection_strategy) 82 , m_robust_policy(robust_policy) 83 , m_visitor(visitor) 84 { 85 } 86 87 template <typename Ring> travel_to_next_turnboost::geometry::detail::overlay::traversal_ring_creator88 inline traverse_error_type travel_to_next_turn(signed_size_type start_turn_index, 89 int start_op_index, 90 signed_size_type& turn_index, 91 int& op_index, 92 Ring& current_ring, 93 bool is_start) 94 { 95 int const previous_op_index = op_index; 96 signed_size_type const previous_turn_index = turn_index; 97 turn_type& previous_turn = m_turns[turn_index]; 98 turn_operation_type& previous_op = previous_turn.operations[op_index]; 99 segment_identifier previous_seg_id; 100 101 signed_size_type to_vertex_index = -1; 102 if (! m_trav.select_turn_from_enriched(turn_index, previous_seg_id, 103 to_vertex_index, start_turn_index, start_op_index, 104 previous_turn, previous_op, is_start)) 105 { 106 return is_start 107 ? traverse_error_no_next_ip_at_start 108 : traverse_error_no_next_ip; 109 } 110 if (to_vertex_index >= 0) 111 { 112 if (previous_op.seg_id.source_index == 0) 113 { 114 geometry::copy_segments<Reverse1>(m_geometry1, 115 previous_op.seg_id, to_vertex_index, 116 m_intersection_strategy.get_side_strategy(), 117 m_robust_policy, current_ring); 118 } 119 else 120 { 121 geometry::copy_segments<Reverse2>(m_geometry2, 122 previous_op.seg_id, to_vertex_index, 123 m_intersection_strategy.get_side_strategy(), 124 m_robust_policy, current_ring); 125 } 126 } 127 128 if (m_turns[turn_index].discarded) 129 { 130 return is_start 131 ? traverse_error_dead_end_at_start 132 : traverse_error_dead_end; 133 } 134 135 if (is_start) 136 { 137 // Register the start 138 previous_op.visited.set_started(); 139 m_visitor.visit_traverse(m_turns, previous_turn, previous_op, "Start"); 140 } 141 142 if (! m_trav.select_turn(start_turn_index, start_op_index, 143 turn_index, op_index, 144 previous_op_index, previous_turn_index, previous_seg_id, 145 is_start, current_ring.size() > 1)) 146 { 147 return is_start 148 ? traverse_error_no_next_ip_at_start 149 : traverse_error_no_next_ip; 150 } 151 152 { 153 // Check operation (TODO: this might be redundant or should be catched before) 154 const turn_type& current_turn = m_turns[turn_index]; 155 const turn_operation_type& op = current_turn.operations[op_index]; 156 if (op.visited.finalized() 157 || m_trav.is_visited(current_turn, op, turn_index, op_index)) 158 { 159 return traverse_error_visit_again; 160 } 161 } 162 163 // Update registration and append point 164 turn_type& current_turn = m_turns[turn_index]; 165 turn_operation_type& op = current_turn.operations[op_index]; 166 detail::overlay::append_no_collinear(current_ring, current_turn.point, 167 m_intersection_strategy.get_side_strategy(), 168 m_robust_policy); 169 170 // Register the visit 171 m_trav.set_visited(current_turn, op); 172 m_visitor.visit_traverse(m_turns, current_turn, op, "Visit"); 173 174 return traverse_error_none; 175 } 176 177 template <typename Ring> traverseboost::geometry::detail::overlay::traversal_ring_creator178 inline traverse_error_type traverse(Ring& ring, 179 signed_size_type start_turn_index, int start_op_index) 180 { 181 turn_type const& start_turn = m_turns[start_turn_index]; 182 turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index]; 183 184 detail::overlay::append_no_collinear(ring, start_turn.point, 185 m_intersection_strategy.get_side_strategy(), 186 m_robust_policy); 187 188 signed_size_type current_turn_index = start_turn_index; 189 int current_op_index = start_op_index; 190 191 traverse_error_type error = travel_to_next_turn(start_turn_index, 192 start_op_index, 193 current_turn_index, current_op_index, 194 ring, true); 195 196 if (error != traverse_error_none) 197 { 198 // This is not necessarily a problem, it happens for clustered turns 199 // which are "build in" or otherwise point inwards 200 return error; 201 } 202 203 if (current_turn_index == start_turn_index) 204 { 205 start_op.visited.set_finished(); 206 m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish"); 207 return traverse_error_none; 208 } 209 210 if (start_turn.is_clustered()) 211 { 212 turn_type& turn = m_turns[current_turn_index]; 213 turn_operation_type& op = turn.operations[current_op_index]; 214 if (turn.cluster_id == start_turn.cluster_id 215 && op.enriched.get_next_turn_index() == start_turn_index) 216 { 217 op.visited.set_finished(); 218 m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish (cluster)"); 219 return traverse_error_none; 220 } 221 } 222 223 std::size_t const max_iterations = 2 + 2 * m_turns.size(); 224 for (std::size_t i = 0; i <= max_iterations; i++) 225 { 226 // We assume clockwise polygons only, non self-intersecting, closed. 227 // However, the input might be different, and checking validity 228 // is up to the library user. 229 230 // Therefore we make here some sanity checks. If the input 231 // violates the assumptions, the output polygon will not be correct 232 // but the routine will stop and output the current polygon, and 233 // will continue with the next one. 234 235 // Below three reasons to stop. 236 error = travel_to_next_turn(start_turn_index, start_op_index, 237 current_turn_index, current_op_index, 238 ring, false); 239 240 if (error != traverse_error_none) 241 { 242 return error; 243 } 244 245 if (current_turn_index == start_turn_index 246 && current_op_index == start_op_index) 247 { 248 start_op.visited.set_finished(); 249 m_visitor.visit_traverse(m_turns, start_turn, start_op, "Finish"); 250 return traverse_error_none; 251 } 252 } 253 254 return traverse_error_endless_loop; 255 } 256 257 template <typename Rings> traverse_with_operationboost::geometry::detail::overlay::traversal_ring_creator258 void traverse_with_operation(turn_type const& start_turn, 259 std::size_t turn_index, int op_index, 260 Rings& rings, std::size_t& finalized_ring_size, 261 typename Backtrack::state_type& state) 262 { 263 typedef typename boost::range_value<Rings>::type ring_type; 264 265 turn_operation_type const& start_op = start_turn.operations[op_index]; 266 267 if (! start_op.visited.none() 268 || ! start_op.enriched.startable 269 || start_op.visited.rejected() 270 || ! (start_op.operation == target_operation 271 || start_op.operation == detail::overlay::operation_continue)) 272 { 273 return; 274 } 275 276 ring_type ring; 277 traverse_error_type traverse_error = traverse(ring, turn_index, op_index); 278 279 if (traverse_error == traverse_error_none) 280 { 281 std::size_t const min_num_points 282 = core_detail::closure::minimum_ring_size 283 < 284 geometry::closure<ring_type>::value 285 >::value; 286 287 if (geometry::num_points(ring) >= min_num_points) 288 { 289 clean_closing_dups_and_spikes(ring, 290 m_intersection_strategy.get_side_strategy(), 291 m_robust_policy); 292 rings.push_back(ring); 293 294 m_trav.finalize_visit_info(m_turn_info_map); 295 finalized_ring_size++; 296 } 297 } 298 else 299 { 300 Backtrack::apply( 301 finalized_ring_size, 302 rings, ring, m_turns, start_turn, 303 m_turns[turn_index].operations[op_index], 304 traverse_error, 305 m_geometry1, m_geometry2, 306 m_intersection_strategy, m_robust_policy, 307 state, m_visitor); 308 } 309 } 310 get_operation_indexboost::geometry::detail::overlay::traversal_ring_creator311 int get_operation_index(turn_type const& turn) const 312 { 313 // When starting with a continue operation, the one 314 // with the smallest (for intersection) or largest (for union) 315 // remaining distance (#8310b) 316 // Also to avoid skipping a turn in between, which can happen 317 // in rare cases (e.g. #130) 318 static const bool is_union 319 = operation_from_overlay<OverlayType>::value == operation_union; 320 321 turn_operation_type const& op0 = turn.operations[0]; 322 turn_operation_type const& op1 = turn.operations[1]; 323 return op0.remaining_distance <= op1.remaining_distance 324 ? (is_union ? 1 : 0) 325 : (is_union ? 0 : 1); 326 } 327 328 template <typename Rings> iterateboost::geometry::detail::overlay::traversal_ring_creator329 void iterate(Rings& rings, std::size_t& finalized_ring_size, 330 typename Backtrack::state_type& state) 331 { 332 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) 333 { 334 turn_type const& turn = m_turns[turn_index]; 335 336 if (turn.discarded || turn.blocked()) 337 { 338 // Skip discarded and blocked turns 339 continue; 340 } 341 342 if (turn.both(operation_continue)) 343 { 344 traverse_with_operation(turn, turn_index, 345 get_operation_index(turn), 346 rings, finalized_ring_size, state); 347 } 348 else 349 { 350 for (int op_index = 0; op_index < 2; op_index++) 351 { 352 traverse_with_operation(turn, turn_index, op_index, 353 rings, finalized_ring_size, state); 354 } 355 } 356 } 357 } 358 359 template <typename Rings> iterate_with_preferenceboost::geometry::detail::overlay::traversal_ring_creator360 void iterate_with_preference(std::size_t phase, 361 Rings& rings, std::size_t& finalized_ring_size, 362 typename Backtrack::state_type& state) 363 { 364 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) 365 { 366 turn_type const& turn = m_turns[turn_index]; 367 368 if (turn.discarded || turn.blocked()) 369 { 370 // Skip discarded and blocked turns 371 continue; 372 } 373 374 turn_operation_type const& op0 = turn.operations[0]; 375 turn_operation_type const& op1 = turn.operations[1]; 376 377 if (phase == 0) 378 { 379 if (! op0.enriched.prefer_start && ! op1.enriched.prefer_start) 380 { 381 // Not preferred, take next one 382 continue; 383 } 384 } 385 386 if (turn.both(operation_continue)) 387 { 388 traverse_with_operation(turn, turn_index, 389 get_operation_index(turn), 390 rings, finalized_ring_size, state); 391 } 392 else 393 { 394 bool const forward = op0.enriched.prefer_start; 395 396 int op_index = forward ? 0 : 1; 397 int const increment = forward ? 1 : -1; 398 399 for (int i = 0; i < 2; i++, op_index += increment) 400 { 401 traverse_with_operation(turn, turn_index, op_index, 402 rings, finalized_ring_size, state); 403 } 404 } 405 } 406 } 407 408 private: 409 traversal_type m_trav; 410 411 Geometry1 const& m_geometry1; 412 Geometry2 const& m_geometry2; 413 Turns& m_turns; 414 TurnInfoMap& m_turn_info_map; // contains turn-info information per ring 415 Clusters const& m_clusters; 416 IntersectionStrategy const& m_intersection_strategy; 417 RobustPolicy const& m_robust_policy; 418 Visitor& m_visitor; 419 }; 420 421 }} // namespace detail::overlay 422 #endif // DOXYGEN_NO_DETAIL 423 424 }} // namespace boost::geometry 425 426 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP 427