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. 6 // Modifications copyright (c) 2017, 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/copy_segments.hpp> 21 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> 22 #include <boost/geometry/algorithms/detail/overlay/traversal.hpp> 23 #include <boost/geometry/algorithms/num_points.hpp> 24 #include <boost/geometry/core/access.hpp> 25 #include <boost/geometry/core/assert.hpp> 26 #include <boost/geometry/core/closure.hpp> 27 28 namespace boost { namespace geometry 29 { 30 31 #ifndef DOXYGEN_NO_DETAIL 32 namespace detail { namespace overlay 33 { 34 35 36 template 37 < 38 bool Reverse1, 39 bool Reverse2, 40 overlay_type OverlayType, 41 typename Geometry1, 42 typename Geometry2, 43 typename Turns, 44 typename Clusters, 45 typename IntersectionStrategy, 46 typename RobustPolicy, 47 typename Visitor, 48 typename Backtrack 49 > 50 struct traversal_ring_creator 51 { 52 typedef traversal 53 < 54 Reverse1, Reverse2, OverlayType, 55 Geometry1, Geometry2, Turns, Clusters, 56 RobustPolicy, typename IntersectionStrategy::side_strategy_type, 57 Visitor 58 > traversal_type; 59 60 typedef typename boost::range_value<Turns>::type turn_type; 61 typedef typename turn_type::turn_operation_type turn_operation_type; 62 63 static const operation_type target_operation 64 = operation_from_overlay<OverlayType>::value; 65 traversal_ring_creatorboost::geometry::detail::overlay::traversal_ring_creator66 inline traversal_ring_creator(Geometry1 const& geometry1, Geometry2 const& geometry2, 67 Turns& turns, Clusters const& clusters, 68 IntersectionStrategy const& intersection_strategy, 69 RobustPolicy const& robust_policy, Visitor& visitor) 70 : m_trav(geometry1, geometry2, turns, clusters, 71 robust_policy, intersection_strategy.get_side_strategy(), 72 visitor) 73 , m_geometry1(geometry1) 74 , m_geometry2(geometry2) 75 , m_turns(turns) 76 , m_clusters(clusters) 77 , m_intersection_strategy(intersection_strategy) 78 , m_robust_policy(robust_policy) 79 , m_visitor(visitor) 80 { 81 } 82 83 template <typename Ring> travel_to_next_turnboost::geometry::detail::overlay::traversal_ring_creator84 inline traverse_error_type travel_to_next_turn(signed_size_type start_turn_index, 85 int start_op_index, 86 signed_size_type& turn_index, 87 int& op_index, 88 Ring& current_ring, 89 bool is_start) 90 { 91 int const previous_op_index = op_index; 92 signed_size_type const previous_turn_index = turn_index; 93 turn_type& previous_turn = m_turns[turn_index]; 94 turn_operation_type& previous_op = previous_turn.operations[op_index]; 95 segment_identifier previous_seg_id; 96 97 signed_size_type to_vertex_index = -1; 98 if (! m_trav.select_turn_from_enriched(turn_index, previous_seg_id, 99 to_vertex_index, start_turn_index, start_op_index, 100 previous_turn, previous_op, is_start)) 101 { 102 return is_start 103 ? traverse_error_no_next_ip_at_start 104 : traverse_error_no_next_ip; 105 } 106 if (to_vertex_index >= 0) 107 { 108 if (previous_op.seg_id.source_index == 0) 109 { 110 geometry::copy_segments<Reverse1>(m_geometry1, 111 previous_op.seg_id, to_vertex_index, 112 m_intersection_strategy.get_side_strategy(), 113 m_robust_policy, current_ring); 114 } 115 else 116 { 117 geometry::copy_segments<Reverse2>(m_geometry2, 118 previous_op.seg_id, to_vertex_index, 119 m_intersection_strategy.get_side_strategy(), 120 m_robust_policy, current_ring); 121 } 122 } 123 124 if (m_turns[turn_index].discarded) 125 { 126 return is_start 127 ? traverse_error_dead_end_at_start 128 : traverse_error_dead_end; 129 } 130 131 if (is_start) 132 { 133 // Register the start 134 previous_op.visited.set_started(); 135 m_visitor.visit_traverse(m_turns, previous_turn, previous_op, "Start"); 136 } 137 138 if (! m_trav.select_turn(start_turn_index, start_op_index, 139 turn_index, op_index, 140 previous_op_index, previous_turn_index, previous_seg_id, 141 is_start)) 142 { 143 return is_start 144 ? traverse_error_no_next_ip_at_start 145 : traverse_error_no_next_ip; 146 } 147 148 { 149 // Check operation (TODO: this might be redundant or should be catched before) 150 const turn_type& current_turn = m_turns[turn_index]; 151 const turn_operation_type& op = current_turn.operations[op_index]; 152 if (op.visited.finalized() 153 || m_trav.is_visited(current_turn, op, turn_index, op_index)) 154 { 155 return traverse_error_visit_again; 156 } 157 } 158 159 // Update registration and append point 160 turn_type& current_turn = m_turns[turn_index]; 161 turn_operation_type& op = current_turn.operations[op_index]; 162 detail::overlay::append_no_dups_or_spikes(current_ring, current_turn.point, 163 m_intersection_strategy.get_side_strategy(), 164 m_robust_policy); 165 166 // Register the visit 167 m_trav.set_visited(current_turn, op); 168 m_visitor.visit_traverse(m_turns, current_turn, op, "Visit"); 169 170 return traverse_error_none; 171 } 172 173 template <typename Ring> traverseboost::geometry::detail::overlay::traversal_ring_creator174 inline traverse_error_type traverse(Ring& ring, 175 signed_size_type start_turn_index, int start_op_index) 176 { 177 turn_type const& start_turn = m_turns[start_turn_index]; 178 turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index]; 179 180 detail::overlay::append_no_dups_or_spikes(ring, start_turn.point, 181 m_intersection_strategy.get_side_strategy(), 182 m_robust_policy); 183 184 signed_size_type current_turn_index = start_turn_index; 185 int current_op_index = start_op_index; 186 187 traverse_error_type error = travel_to_next_turn(start_turn_index, 188 start_op_index, 189 current_turn_index, current_op_index, 190 ring, true); 191 192 if (error != traverse_error_none) 193 { 194 // This is not necessarily a problem, it happens for clustered turns 195 // which are "build in" or otherwise point inwards 196 return error; 197 } 198 199 if (current_turn_index == start_turn_index) 200 { 201 start_op.visited.set_finished(); 202 m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish"); 203 return traverse_error_none; 204 } 205 206 if (start_turn.cluster_id >= 0) 207 { 208 turn_type const& turn = m_turns[current_turn_index]; 209 if (turn.cluster_id == start_turn.cluster_id) 210 { 211 turn_operation_type& op = m_turns[start_turn_index].operations[current_op_index]; 212 op.visited.set_finished(); 213 m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish (cluster)"); 214 return traverse_error_none; 215 } 216 } 217 218 std::size_t const max_iterations = 2 + 2 * m_turns.size(); 219 for (std::size_t i = 0; i <= max_iterations; i++) 220 { 221 // We assume clockwise polygons only, non self-intersecting, closed. 222 // However, the input might be different, and checking validity 223 // is up to the library user. 224 225 // Therefore we make here some sanity checks. If the input 226 // violates the assumptions, the output polygon will not be correct 227 // but the routine will stop and output the current polygon, and 228 // will continue with the next one. 229 230 // Below three reasons to stop. 231 error = travel_to_next_turn(start_turn_index, start_op_index, 232 current_turn_index, current_op_index, 233 ring, false); 234 235 if (error != traverse_error_none) 236 { 237 return error; 238 } 239 240 if (current_turn_index == start_turn_index 241 && current_op_index == start_op_index) 242 { 243 start_op.visited.set_finished(); 244 m_visitor.visit_traverse(m_turns, start_turn, start_op, "Finish"); 245 return traverse_error_none; 246 } 247 } 248 249 return traverse_error_endless_loop; 250 } 251 252 template <typename Rings> traverse_with_operationboost::geometry::detail::overlay::traversal_ring_creator253 void traverse_with_operation(turn_type const& start_turn, 254 std::size_t turn_index, int op_index, 255 Rings& rings, std::size_t& finalized_ring_size, 256 typename Backtrack::state_type& state) 257 { 258 typedef typename boost::range_value<Rings>::type ring_type; 259 260 turn_operation_type const& start_op = start_turn.operations[op_index]; 261 262 if (! start_op.visited.none() 263 || ! start_op.enriched.startable 264 || start_op.visited.rejected() 265 || ! (start_op.operation == target_operation 266 || start_op.operation == detail::overlay::operation_continue)) 267 { 268 return; 269 } 270 271 ring_type ring; 272 traverse_error_type traverse_error = traverse(ring, turn_index, op_index); 273 274 if (traverse_error == traverse_error_none) 275 { 276 std::size_t const min_num_points 277 = core_detail::closure::minimum_ring_size 278 < 279 geometry::closure<ring_type>::value 280 >::value; 281 282 if (geometry::num_points(ring) >= min_num_points) 283 { 284 clean_closing_dups_and_spikes(ring, 285 m_intersection_strategy.get_side_strategy(), 286 m_robust_policy); 287 rings.push_back(ring); 288 289 m_trav.finalize_visit_info(); 290 finalized_ring_size++; 291 } 292 } 293 else 294 { 295 Backtrack::apply( 296 finalized_ring_size, 297 rings, ring, m_turns, start_turn, 298 m_turns[turn_index].operations[op_index], 299 traverse_error, 300 m_geometry1, m_geometry2, 301 m_intersection_strategy, m_robust_policy, 302 state, m_visitor); 303 } 304 } 305 306 template <typename Rings> iterateboost::geometry::detail::overlay::traversal_ring_creator307 void iterate(Rings& rings, std::size_t& finalized_ring_size, 308 typename Backtrack::state_type& state) 309 { 310 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) 311 { 312 turn_type const& turn = m_turns[turn_index]; 313 314 if (turn.discarded || turn.blocked()) 315 { 316 // Skip discarded and blocked turns 317 continue; 318 } 319 320 if (turn.both(operation_continue)) 321 { 322 // Traverse only one turn, the one with the SMALLEST remaining distance 323 // to avoid skipping a turn in between, which can happen in rare cases 324 // (e.g. #130) 325 turn_operation_type const& op0 = turn.operations[0]; 326 turn_operation_type const& op1 = turn.operations[1]; 327 int const op_index 328 = op0.remaining_distance <= op1.remaining_distance ? 0 : 1; 329 330 traverse_with_operation(turn, turn_index, op_index, 331 rings, finalized_ring_size, state); 332 } 333 else 334 { 335 for (int op_index = 0; op_index < 2; op_index++) 336 { 337 traverse_with_operation(turn, turn_index, op_index, 338 rings, finalized_ring_size, state); 339 } 340 } 341 } 342 } 343 344 private: 345 traversal_type m_trav; 346 347 Geometry1 const& m_geometry1; 348 Geometry2 const& m_geometry2; 349 Turns& m_turns; 350 Clusters const& m_clusters; 351 IntersectionStrategy const& m_intersection_strategy; 352 RobustPolicy const& m_robust_policy; 353 Visitor& m_visitor; 354 }; 355 356 }} // namespace detail::overlay 357 #endif // DOXYGEN_NO_DETAIL 358 359 }} // namespace boost::geometry 360 361 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP 362