overlay/graph/traverse_graph.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2025 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // Use, modification and distribution is subject to the Boost Software License,
0006 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_GRAPH_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_GRAPH_HPP
0011
0012 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
0013 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
0014 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0015 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0016 #include <boost/geometry/algorithms/detail/overlay/graph/is_operation_included.hpp>
0017 #include <boost/geometry/algorithms/detail/overlay/graph/get_tois.hpp>
0018 #include <boost/geometry/algorithms/detail/overlay/graph/node_util.hpp>
0019 #include <boost/geometry/algorithms/detail/overlay/graph/select_edge.hpp>
0020 #include <boost/geometry/algorithms/num_points.hpp>
0021 #include <boost/geometry/core/closure.hpp>
0022
0023 #include <boost/assert.hpp>
0024
0025 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0026 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0027 #include <boost/geometry/io/wkt/wkt.hpp>
0028 #endif
0029
0030 namespace boost { namespace geometry
0031 {
0032
0033 #ifndef DOXYGEN_NO_DETAIL
0034 namespace detail { namespace overlay
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 Clusters,
0046     typename Strategy
0047 >
0048 struct traverse_graph
0049 {
0050     static constexpr operation_type target_operation = operation_from_overlay<OverlayType>::value;
0051     static constexpr bool allow_closed = target_operation == operation_intersection;
0052     static constexpr bool is_buffer = OverlayType == overlay_buffer;
0053
0054     using turn_type = typename boost::range_value<Turns>::type;
0055     using is_included = is_operation_included<target_operation>;
0056     using point_type = typename turn_type::point_type;
0057     using toi_set = std::set<turn_operation_id>;
0058
0059     inline traverse_graph(Geometry1 const& geometry1, Geometry2 const& geometry2,
0060             Turns& turns, Clusters const& clusters,
0061             Strategy const& strategy)
0062         : m_edge_selector(geometry1, geometry2, turns, clusters, strategy)
0063         , m_geometry1(geometry1)
0064         , m_geometry2(geometry2)
0065         , m_turns(turns)
0066         , m_clusters(clusters)
0067         , m_strategy(strategy)
0068     {
0069     }
0070
0071     template <typename Ring>
0072     void copy_segments(Ring& ring, turn_operation_id const& toi) const
0073     {
0074         auto const& op = m_turns[toi.turn_index].operations[toi.operation_index];
0075         auto const to_vertex_index = op.enriched.travels_to_vertex_index;
0076         if (op.seg_id.source_index == 0)
0077         {
0078             geometry::copy_segments<Reverse1>(m_geometry1,
0079                     op.seg_id, to_vertex_index,
0080                     m_strategy, ring);
0081         }
0082         else
0083         {
0084             geometry::copy_segments<Reverse2>(m_geometry2,
0085                     op.seg_id, to_vertex_index,
0086                     m_strategy, ring);
0087         }
0088
0089     }
0090
0091     template <typename Ring>
0092     void use_vertices(Ring& ring, turn_operation_id const& toi, bool is_round_trip = false) const
0093     {
0094         auto const& op = m_turns[toi.turn_index].operations[toi.operation_index];
0095         auto const to_vertex_index = op.enriched.travels_to_vertex_index;
0096
0097         if (to_vertex_index < 0)
0098         {
0099             return;
0100         }
0101
0102 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0103         std::cout << "At : " << toi << std::endl;
0104 #endif
0105
0106
0107         if (op.seg_id.segment_index == to_vertex_index && ! is_round_trip)
0108         {
0109             auto const& next_turn = m_turns[op.enriched.travels_to_ip_index];
0110
0111             bool allow = false;
0112
0113             for (int j = 0; j < 2; j++)
0114             {
0115                 auto const& next_op = next_turn.operations[j];
0116                 if (next_op.seg_id == op.seg_id)
0117                 {
0118                     // It is on the same segment. Determine if it is located before or after
0119                     if (next_op.fraction < op.fraction)
0120                     {
0121                         // It is before, so we can continue
0122                         allow = true;
0123                     }
0124                 }
0125             }
0126
0127             if (! allow)
0128             {
0129                 return;
0130             }
0131         }
0132
0133         copy_segments(ring, toi);
0134     }
0135
0136     // Set the turn operation as visited.
0137     void set_visited(turn_operation_id const& toi)
0138     {
0139         // std::cout << "Set visited: " << toi << std::endl;
0140         m_visited_tois.insert(toi);
0141
0142         // From the same cluster, set other operations with the same segment id,
0143         // going to the same target, as visited as well.
0144         auto const& turn = m_turns[toi.turn_index];
0145         if (! turn.is_clustered())
0146         {
0147             return;
0148         }
0149         auto cluster_it = m_clusters.find(turn.cluster_id);
0150         if (cluster_it == m_clusters.end())
0151         {
0152             return;
0153         }
0154         auto const& cluster = cluster_it->second;
0155
0156         auto const& op = turn.operations[toi.operation_index];
0157
0158         for (std::size_t turn_index : cluster.turn_indices)
0159         {
0160             if (turn_index == toi.turn_index)
0161             {
0162                 continue;
0163             }
0164             auto const& other_turn = m_turns[turn_index];
0165             for (int j = 0; j < 2; j++)
0166             {
0167                 auto const& other_op = other_turn.operations[j];
0168                 if (other_op.enriched.travels_to_ip_index == op.enriched.travels_to_ip_index
0169                     && other_op.seg_id == op.seg_id)
0170                 {
0171                     m_visited_tois.insert({turn_index, j});
0172                 }
0173             }
0174         }
0175     }
0176
0177     template <typename Ring>
0178     bool continue_traverse(Ring& ring,
0179             signed_size_type component_id,
0180             signed_size_type start_node_id,
0181             signed_size_type target_node_id)
0182     {
0183         signed_size_type current_node_id = target_node_id;
0184
0185         std::size_t iteration_count = 0;
0186
0187         // Keep traversing until it finds the start (successful finish), or it is stuck,
0188         // or it find an already visited node during traversal.
0189         // The iteration count is a defensive check to prevent endless loops and not iterate
0190         // more than times there are turns (this should not happen).
0191         while (iteration_count < m_turns.size())
0192         {
0193             auto const current_turn_indices = get_turn_indices_by_node_id(m_turns, m_clusters,
0194                     current_node_id, allow_closed);
0195
0196             // Any valid node should always deliver at least one turn
0197             BOOST_ASSERT(! current_turn_indices.empty());
0198
0199             auto const next_target_nodes = get_target_nodes<target_operation>(m_turns, m_clusters,
0200                     current_turn_indices, component_id);
0201
0202             if (next_target_nodes.empty())
0203             {
0204 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0205                 std::cout << "Stuck, start: " << start_node_id
0206                     << " stuck: " << current_node_id
0207                     << " (no targets) " << std::endl;
0208 #endif
0209                 return false;
0210             }
0211
0212             auto const tois = get_tois<target_operation>(m_turns, m_clusters,
0213                     current_node_id, next_target_nodes);
0214
0215             if (tois.empty())
0216             {
0217                 return false;
0218             }
0219
0220             auto const& turn_point = m_turns[*current_turn_indices.begin()].point;
0221
0222             auto toi = *tois.begin();
0223
0224             if (tois.size() > 1)
0225             {
0226                 // Select the best target edge, using the last point of the ring and the turn point
0227                 // for side calculations (if any).
0228                 toi = m_edge_selector.select_target_edge(tois, ring.back(), turn_point);
0229             }
0230
0231             if (m_visited_tois.count(toi) > 0 || m_finished_tois.count(toi) > 0)
0232             {
0233 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0234                 std::cout << "ALREADY visited, turn " << toi
0235                     << " in {" << current_node_id
0236                     << " -> size " << next_target_nodes.size() << "}" << std::endl;
0237 #endif
0238                 return false;
0239             }
0240
0241             detail::overlay::append_no_collinear(ring, turn_point, m_strategy);
0242
0243             set_visited(toi);
0244             use_vertices(ring, toi);
0245
0246             auto const& selected_op = m_turns[toi.turn_index].operations[toi.operation_index];
0247             auto const next_target_node_id = get_node_id(m_turns,
0248                 selected_op.enriched.travels_to_ip_index);
0249             if (next_target_node_id == start_node_id)
0250             {
0251 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0252                 std::cout << "Finished at: " << next_target_node_id << std::endl;
0253 #endif
0254                 return true;
0255             }
0256
0257             current_node_id = next_target_node_id;
0258             ++iteration_count;
0259         }
0260 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0261         std::cout << "Cancelled at: " << iteration_count << std::endl;
0262 #endif
0263         return false;
0264     }
0265
0266     template <typename Rings>
0267     void start_traverse(Rings& rings, point_type const& start_point,
0268             signed_size_type component_id,
0269             signed_size_type start_node_id,
0270             signed_size_type target_node_id)
0271     {
0272         // Select the first toi which is not yet visited and has the requested component.
0273         // If all tois are visited, not having the same component, it is not possible to continue,
0274         // and it returns an invalid toi.
0275         auto select_first_toi = [&](auto const& tois)
0276         {
0277             for (auto const& toi : tois)
0278             {
0279                 if (m_finished_tois.count(toi) > 0)
0280                 {
0281                     // Visited in the meantime
0282                     continue;
0283                 }
0284                 auto const& op = m_turns[toi.turn_index].operations[toi.operation_index];
0285                 if (op.enriched.component_id != component_id)
0286                 {
0287                     continue;
0288                 }
0289
0290                 return toi;
0291             }
0292             return turn_operation_id{0, -1};
0293         };
0294
0295         auto const toi = select_first_toi(get_tois<target_operation>(m_turns, m_clusters,
0296                 start_node_id, target_node_id));
0297         if (toi.operation_index < 0)
0298         {
0299             return;
0300         }
0301
0302 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0303         std::cout << "\n" << "-> Start traversing component " << component_id
0304             << " at: " << toi
0305             << " to " << target_node_id << std::endl;
0306 #endif
0307
0308
0309         using ring_type = typename boost::range_value<Rings>::type;
0310
0311         constexpr std::size_t min_size
0312                 = core_detail::closure::minimum_ring_size
0313                         <
0314                             geometry::closure<ring_type>::value
0315                         >::value;
0316
0317         ring_type ring;
0318         detail::overlay::append_no_collinear(ring, start_point, m_strategy);
0319
0320         m_visited_tois.clear();
0321         set_visited(toi);
0322
0323         bool const is_round_trip = start_node_id == target_node_id;
0324         use_vertices(ring, toi, is_round_trip);
0325
0326         // Traverse the graph. If the target is at the start, it is a round trip,
0327         // and it is finished immediately.
0328         // The continuation could fail (no target nodes, or no target edges).
0329         bool const is_finished = is_round_trip
0330             || continue_traverse(ring, component_id, start_node_id, target_node_id);
0331
0332         if (! is_finished)
0333         {
0334             return;
0335         }
0336
0337         detail::overlay::append_no_collinear(ring, start_point, m_strategy);
0338         remove_spikes_at_closure(ring, m_strategy);
0339         fix_closure(ring, m_strategy);
0340
0341         if (geometry::num_points(ring) >= min_size)
0342         {
0343         #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0344             std::cout << "Add ring: " << geometry::wkt(ring) << std::endl;
0345         #endif
0346             rings.push_back(std::move(ring));
0347         }
0348         m_finished_tois.insert(m_visited_tois.begin(), m_visited_tois.end());
0349     }
0350
0351     void update_administration()
0352     {
0353         for (auto const& toi : m_finished_tois)
0354         {
0355             auto& op = m_turns[toi.turn_index].operations[toi.operation_index];
0356             op.enriched.is_traversed = true;
0357         }
0358     }
0359
0360     template <typename Rings>
0361     void iterate(Rings& rings, std::size_t turn_index)
0362     {
0363         auto const& turn = m_turns[turn_index];
0364         if (turn.discarded)
0365         {
0366             return;
0367         }
0368         auto const source_node_id = get_node_id(m_turns, turn_index);
0369         auto const turn_indices = get_turn_indices_by_node_id(m_turns, m_clusters,
0370                 source_node_id, allow_closed);
0371
0372         for (int j = 0; j < 2; j++)
0373         {
0374             auto const& op = turn.operations[j];
0375             if (! op.enriched.startable || ! is_included::apply(op))
0376             {
0377                 continue;
0378             }
0379
0380             turn_operation_id const toi{turn_index, j};
0381             if (m_finished_tois.count(toi) > 0
0382                 || ! is_target_operation<target_operation>(m_turns, toi))
0383             {
0384                 continue;
0385             }
0386
0387             auto const component_id = op.enriched.component_id;
0388             auto const target_nodes = get_target_nodes<target_operation>(m_turns, m_clusters,
0389                     turn_indices, component_id);
0390
0391             for (auto const target_node_id : target_nodes)
0392             {
0393                 auto const start = std::make_tuple(source_node_id, target_node_id, component_id);
0394                 if (m_starts.count(start) > 0)
0395                 {
0396                     // Don't repeat earlier or finished trials. This speeds up some cases by 1.5x
0397                     continue;
0398                 }
0399                 m_starts.insert(start);
0400
0401     #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0402                 std::cout << "\n" << "Traversing component " << component_id
0403                     << " from " << source_node_id << " to " << target_node_id << std::endl;
0404     #endif
0405                 start_traverse(rings, turn.point, component_id, source_node_id, target_node_id);
0406             }
0407         }
0408     }
0409
0410     template <typename Rings>
0411     void iterate(Rings& rings)
0412     {
0413         for (std::size_t i = 0; i < m_turns.size(); i++)
0414         {
0415             iterate(rings, i);
0416         }
0417
0418         update_administration();
0419     }
0420
0421 private:
0422
0423     edge_selector
0424         <
0425             Reverse1, Reverse2, OverlayType,
0426             Geometry1, Geometry2,
0427             Turns, Clusters,
0428             Strategy
0429         > m_edge_selector;
0430
0431     Geometry1 const& m_geometry1;
0432     Geometry2 const& m_geometry2;
0433     Turns& m_turns;
0434     Clusters const& m_clusters;
0435     Strategy const& m_strategy;
0436
0437     // Visited turn operations on currenly traversed ring - they are either
0438     // inserted into the final set, or cleared before the next trial.
0439     toi_set m_visited_tois;
0440
0441     // Visited turn operations after a ring is added
0442     toi_set m_finished_tois;
0443
0444     // Keep track of started combinations (either finished, or stuck)
0445     std::set<std::tuple<signed_size_type, signed_size_type, signed_size_type>> m_starts;
0446 };
0447
0448 }} // namespace detail::overlay
0449 #endif // DOXYGEN_NO_DETAIL
0450
0451 }} // namespace boost::geometry
0452
0453 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_GRAPH_HPP