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