detail/overlay/traversal_ring_creator.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2017-2020.
0006 // Modifications copyright (c) 2017-2020, Oracle and/or its affiliates.
0007 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0008
0009 // Use, modification and distribution is subject to the Boost Software License,
0010 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0011 // http://www.boost.org/LICENSE_1_0.txt)
0012
0013 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP
0014 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP
0015
0016 #include <cstddef>
0017
0018 #include <boost/range/value_type.hpp>
0019 #include <boost/range/size.hpp>
0020
0021 #include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp>
0022 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
0023 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0024 #include <boost/geometry/algorithms/detail/overlay/traversal.hpp>
0025 #include <boost/geometry/algorithms/num_points.hpp>
0026 #include <boost/geometry/core/assert.hpp>
0027 #include <boost/geometry/core/closure.hpp>
0028
0029 namespace boost { namespace geometry
0030 {
0031
0032 #ifndef DOXYGEN_NO_DETAIL
0033 namespace detail { namespace overlay
0034 {
0035
0036
0037 template
0038 <
0039     bool Reverse1,
0040     bool Reverse2,
0041     overlay_type OverlayType,
0042     typename Geometry1,
0043     typename Geometry2,
0044     typename Turns,
0045     typename TurnInfoMap,
0046     typename Clusters,
0047     typename Strategy,
0048     typename RobustPolicy,
0049     typename Visitor,
0050     typename Backtrack
0051 >
0052 struct traversal_ring_creator
0053 {
0054     typedef traversal
0055             <
0056                 Reverse1, Reverse2, OverlayType,
0057                 Geometry1, Geometry2, Turns, Clusters,
0058                 RobustPolicy,
0059                 decltype(std::declval<Strategy>().side()),
0060                 Visitor
0061             > traversal_type;
0062
0063     typedef typename boost::range_value<Turns>::type turn_type;
0064     typedef typename turn_type::turn_operation_type turn_operation_type;
0065
0066     static const operation_type target_operation
0067         = operation_from_overlay<OverlayType>::value;
0068
0069     inline traversal_ring_creator(Geometry1 const& geometry1, Geometry2 const& geometry2,
0070             Turns& turns, TurnInfoMap& turn_info_map,
0071             Clusters const& clusters,
0072             Strategy const& strategy,
0073             RobustPolicy const& robust_policy, Visitor& visitor)
0074         : m_trav(geometry1, geometry2, turns, clusters,
0075                  robust_policy, strategy.side(), visitor)
0076         , m_geometry1(geometry1)
0077         , m_geometry2(geometry2)
0078         , m_turns(turns)
0079         , m_turn_info_map(turn_info_map)
0080         , m_clusters(clusters)
0081         , m_strategy(strategy)
0082         , m_robust_policy(robust_policy)
0083         , m_visitor(visitor)
0084     {
0085     }
0086
0087     template <typename Ring>
0088     inline traverse_error_type travel_to_next_turn(signed_size_type start_turn_index,
0089                 int start_op_index,
0090                 signed_size_type& turn_index,
0091                 int& op_index,
0092                 Ring& current_ring,
0093                 bool is_start)
0094     {
0095         int const previous_op_index = op_index;
0096         signed_size_type const previous_turn_index = turn_index;
0097         turn_type& previous_turn = m_turns[turn_index];
0098         turn_operation_type& previous_op = previous_turn.operations[op_index];
0099         segment_identifier previous_seg_id;
0100
0101         signed_size_type to_vertex_index = -1;
0102         if (! m_trav.select_turn_from_enriched(turn_index, previous_seg_id,
0103                           to_vertex_index, start_turn_index, start_op_index,
0104                           previous_turn, previous_op, is_start))
0105         {
0106             return is_start
0107                     ? traverse_error_no_next_ip_at_start
0108                     : traverse_error_no_next_ip;
0109         }
0110         if (to_vertex_index >= 0)
0111         {
0112             if (previous_op.seg_id.source_index == 0)
0113             {
0114                 geometry::copy_segments<Reverse1>(m_geometry1,
0115                         previous_op.seg_id, to_vertex_index,
0116                         m_strategy, m_robust_policy, current_ring);
0117             }
0118             else
0119             {
0120                 geometry::copy_segments<Reverse2>(m_geometry2,
0121                         previous_op.seg_id, to_vertex_index,
0122                         m_strategy, m_robust_policy, current_ring);
0123             }
0124         }
0125
0126         if (m_turns[turn_index].discarded)
0127         {
0128             return is_start
0129                 ? traverse_error_dead_end_at_start
0130                 : traverse_error_dead_end;
0131         }
0132
0133         if (is_start)
0134         {
0135             // Register the start
0136             previous_op.visited.set_started();
0137             m_visitor.visit_traverse(m_turns, previous_turn, previous_op, "Start");
0138         }
0139
0140         if (! m_trav.select_turn(start_turn_index, start_op_index,
0141                 turn_index, op_index,
0142                 previous_op_index, previous_turn_index, previous_seg_id,
0143                 is_start, boost::size(current_ring) > 1))
0144         {
0145             return is_start
0146                 ? traverse_error_no_next_ip_at_start
0147                 : traverse_error_no_next_ip;
0148         }
0149
0150         {
0151             // Check operation (TODO: this might be redundant or should be catched before)
0152             turn_type const& current_turn = m_turns[turn_index];
0153             turn_operation_type const& op = current_turn.operations[op_index];
0154             if (op.visited.finalized()
0155                 || m_trav.is_visited(current_turn, op, turn_index, op_index))
0156             {
0157                 return traverse_error_visit_again;
0158             }
0159         }
0160
0161         // Update registration and append point
0162         turn_type& current_turn = m_turns[turn_index];
0163         turn_operation_type& op = current_turn.operations[op_index];
0164         detail::overlay::append_no_collinear(current_ring, current_turn.point,
0165                                              m_strategy, m_robust_policy);
0166
0167         // Register the visit
0168         m_trav.set_visited(current_turn, op);
0169         m_visitor.visit_traverse(m_turns, current_turn, op, "Visit");
0170
0171         return traverse_error_none;
0172     }
0173
0174     template <typename Ring>
0175     inline traverse_error_type traverse(Ring& ring,
0176             signed_size_type start_turn_index, int start_op_index)
0177     {
0178         turn_type const& start_turn = m_turns[start_turn_index];
0179         turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index];
0180
0181         detail::overlay::append_no_collinear(ring, start_turn.point,
0182                                              m_strategy, m_robust_policy);
0183
0184         signed_size_type current_turn_index = start_turn_index;
0185         int current_op_index = start_op_index;
0186
0187         traverse_error_type error = travel_to_next_turn(start_turn_index,
0188                     start_op_index,
0189                     current_turn_index, current_op_index,
0190                     ring, true);
0191
0192         if (error != traverse_error_none)
0193         {
0194             // This is not necessarily a problem, it happens for clustered turns
0195             // which are "build in" or otherwise point inwards
0196             return error;
0197         }
0198
0199         if (current_turn_index == start_turn_index)
0200         {
0201             start_op.visited.set_finished();
0202             m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish");
0203             return traverse_error_none;
0204         }
0205
0206         if (start_turn.is_clustered())
0207         {
0208             turn_type& turn = m_turns[current_turn_index];
0209             turn_operation_type& op = turn.operations[current_op_index];
0210             if (turn.cluster_id == start_turn.cluster_id
0211                 && op.enriched.get_next_turn_index() == start_turn_index)
0212             {
0213                 op.visited.set_finished();
0214                 m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish (cluster)");
0215                 return traverse_error_none;
0216             }
0217         }
0218
0219         std::size_t const max_iterations = 2 + 2 * m_turns.size();
0220         for (std::size_t i = 0; i <= max_iterations; i++)
0221         {
0222             // We assume clockwise polygons only, non self-intersecting, closed.
0223             // However, the input might be different, and checking validity
0224             // is up to the library user.
0225
0226             // Therefore we make here some sanity checks. If the input
0227             // violates the assumptions, the output polygon will not be correct
0228             // but the routine will stop and output the current polygon, and
0229             // will continue with the next one.
0230
0231             // Below three reasons to stop.
0232             error = travel_to_next_turn(start_turn_index, start_op_index,
0233                     current_turn_index, current_op_index,
0234                     ring, false);
0235
0236             if (error != traverse_error_none)
0237             {
0238                 return error;
0239             }
0240
0241             if (current_turn_index == start_turn_index
0242                     && current_op_index == start_op_index)
0243             {
0244                 start_op.visited.set_finished();
0245                 m_visitor.visit_traverse(m_turns, start_turn, start_op, "Finish");
0246                 return traverse_error_none;
0247             }
0248         }
0249
0250         return traverse_error_endless_loop;
0251     }
0252
0253     template <typename Rings>
0254     void traverse_with_operation(turn_type const& start_turn,
0255             std::size_t turn_index, int op_index,
0256             Rings& rings, std::size_t& finalized_ring_size,
0257             typename Backtrack::state_type& state)
0258     {
0259         typedef typename boost::range_value<Rings>::type ring_type;
0260
0261         turn_operation_type const& start_op = start_turn.operations[op_index];
0262
0263         if (! start_op.visited.none()
0264             || ! start_op.enriched.startable
0265             || start_op.visited.rejected()
0266             || ! (start_op.operation == target_operation
0267                 || start_op.operation == detail::overlay::operation_continue))
0268         {
0269             return;
0270         }
0271
0272         ring_type ring;
0273         traverse_error_type traverse_error = traverse(ring, turn_index, op_index);
0274
0275         if (traverse_error == traverse_error_none)
0276         {
0277             remove_spikes_at_closure(ring, m_strategy, m_robust_policy);
0278             fix_closure(ring, m_strategy);
0279
0280             std::size_t const min_num_points
0281                     = core_detail::closure::minimum_ring_size
0282                             <
0283                                 geometry::closure<ring_type>::value
0284                             >::value;
0285
0286             if (geometry::num_points(ring) >= min_num_points)
0287             {
0288                 rings.push_back(ring);
0289
0290                 m_trav.finalize_visit_info(m_turn_info_map);
0291                 finalized_ring_size++;
0292             }
0293         }
0294         else
0295         {
0296             Backtrack::apply(finalized_ring_size,
0297                              rings, ring, m_turns, start_turn,
0298                              m_turns[turn_index].operations[op_index],
0299                              traverse_error,
0300                              m_geometry1, m_geometry2,
0301                              m_strategy, m_robust_policy,
0302                              state, m_visitor);
0303         }
0304     }
0305
0306     int get_operation_index(turn_type const& turn) const
0307     {
0308         // When starting with a continue operation, the one
0309         // with the smallest (for intersection) or largest (for union)
0310         // remaining distance (#8310b)
0311         // Also to avoid skipping a turn in between, which can happen
0312         // in rare cases (e.g. #130)
0313         static const bool is_union
0314             = operation_from_overlay<OverlayType>::value == operation_union;
0315
0316         turn_operation_type const& op0 = turn.operations[0];
0317         turn_operation_type const& op1 = turn.operations[1];
0318         return op0.remaining_distance <= op1.remaining_distance
0319                 ? (is_union ? 1 : 0)
0320                 : (is_union ? 0 : 1);
0321     }
0322
0323     template <typename Rings>
0324     void iterate(Rings& rings, std::size_t& finalized_ring_size,
0325                  typename Backtrack::state_type& state)
0326     {
0327         for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
0328         {
0329             turn_type const& turn = m_turns[turn_index];
0330
0331             if (turn.discarded || turn.blocked())
0332             {
0333                 // Skip discarded and blocked turns
0334                 continue;
0335             }
0336
0337             if (turn.both(operation_continue))
0338             {
0339                 traverse_with_operation(turn, turn_index,
0340                         get_operation_index(turn),
0341                         rings, finalized_ring_size, state);
0342             }
0343             else
0344             {
0345                 for (int op_index = 0; op_index < 2; op_index++)
0346                 {
0347                     traverse_with_operation(turn, turn_index, op_index,
0348                             rings, finalized_ring_size, state);
0349                 }
0350             }
0351         }
0352     }
0353
0354     template <typename Rings>
0355     void iterate_with_preference(std::size_t phase,
0356                  Rings& rings, std::size_t& finalized_ring_size,
0357                  typename Backtrack::state_type& state)
0358     {
0359         for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
0360         {
0361             turn_type const& turn = m_turns[turn_index];
0362
0363             if (turn.discarded || turn.blocked())
0364             {
0365                 // Skip discarded and blocked turns
0366                 continue;
0367             }
0368
0369             turn_operation_type const& op0 = turn.operations[0];
0370             turn_operation_type const& op1 = turn.operations[1];
0371
0372             if (phase == 0)
0373             {
0374                 if (! op0.enriched.prefer_start && ! op1.enriched.prefer_start)
0375                 {
0376                     // Not preferred, take next one
0377                     continue;
0378                 }
0379             }
0380
0381             if (turn.both(operation_continue))
0382             {
0383                 traverse_with_operation(turn, turn_index,
0384                         get_operation_index(turn),
0385                         rings, finalized_ring_size, state);
0386             }
0387             else
0388             {
0389                 bool const forward = op0.enriched.prefer_start;
0390
0391                 int op_index = forward ? 0 : 1;
0392                 int const increment = forward ? 1 : -1;
0393
0394                 for (int i = 0; i < 2; i++, op_index += increment)
0395                 {
0396                     traverse_with_operation(turn, turn_index, op_index,
0397                             rings, finalized_ring_size, state);
0398                 }
0399             }
0400         }
0401     }
0402
0403 private:
0404     traversal_type m_trav;
0405
0406     Geometry1 const& m_geometry1;
0407     Geometry2 const& m_geometry2;
0408     Turns& m_turns;
0409     TurnInfoMap& m_turn_info_map; // contains turn-info information per ring
0410     Clusters const& m_clusters;
0411     Strategy const& m_strategy;
0412     RobustPolicy const& m_robust_policy;
0413     Visitor& m_visitor;
0414 };
0415
0416 }} // namespace detail::overlay
0417 #endif // DOXYGEN_NO_DETAIL
0418
0419 }} // namespace boost::geometry
0420
0421 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP