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