overlay/graph/get_tois.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_GET_TOIS_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TOIS_HPP
0011
0012 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
0013 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0014 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
0015 #include <boost/geometry/algorithms/detail/overlay/graph/is_operation_included.hpp>
0016 #include <boost/geometry/algorithms/detail/overlay/graph/node_util.hpp>
0017
0018 namespace boost { namespace geometry
0019 {
0020
0021 #ifndef DOXYGEN_NO_DETAIL
0022 namespace detail { namespace overlay
0023 {
0024
0025 template <operation_type TargetOperation, typename Turns, typename Clusters>
0026 void add_tois(Turns const& turns, Clusters const& clusters,
0027         signed_size_type source_node_id, signed_size_type target_node_id,
0028         set_of_tois& result)
0029 {
0030     using is_included = is_operation_included<TargetOperation>;
0031
0032     auto get_tois_from_turns = [&](std::size_t const source_index, std::size_t const target_index)
0033     {
0034         for (int i = 0; i < 2; i++)
0035         {
0036             auto const& op = turns[source_index].operations[i];
0037             if (op.enriched.travels_to_ip_index == static_cast<signed_size_type>(target_index)
0038                 && is_included::apply(op))
0039             {
0040                 turn_operation_id const toi{source_index, i};
0041                 if (is_target_operation<TargetOperation>(turns, toi))
0042                 {
0043                     result.insert(std::move(toi));
0044                 }
0045             }
0046         }
0047     };
0048
0049     constexpr bool allow_closed = TargetOperation == operation_intersection;
0050     if (source_node_id >= 0 && target_node_id >= 0)
0051     {
0052         get_tois_from_turns(source_node_id, target_node_id);
0053     }
0054     else if (source_node_id < 0 && target_node_id >= 0)
0055     {
0056         const auto source_turn_indices = get_turn_indices_by_node_id(turns, clusters,
0057                     source_node_id, allow_closed);
0058         for (auto source_turn_index : source_turn_indices)
0059         {
0060             get_tois_from_turns(source_turn_index, target_node_id);
0061         }
0062     }
0063     else if (source_node_id >= 0 && target_node_id < 0)
0064     {
0065         const auto target_turn_indices = get_turn_indices_by_node_id(turns, clusters,
0066                 target_node_id, allow_closed);
0067         for (auto target_turn_index : target_turn_indices)
0068         {
0069             get_tois_from_turns(source_node_id, target_turn_index);
0070         }
0071     }
0072     else
0073     {
0074         // Combine two sets together, quadratically
0075         const auto source_turn_indices = get_turn_indices_by_node_id(turns, clusters,
0076                 source_node_id, allow_closed);
0077         const auto target_turn_indices = get_turn_indices_by_node_id(turns, clusters,
0078                 target_node_id, allow_closed);
0079         for (auto source_turn_index : source_turn_indices)
0080         {
0081             for (auto target_turn_index : target_turn_indices)
0082             {
0083                 get_tois_from_turns(source_turn_index, target_turn_index);
0084             }
0085         }
0086 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
0087         // This happens, for example, in multi line cases where lines are on top of each other.
0088         // Then there will be many turns, and many clusters with many turns.
0089         // It gives listings like:
0090         //      quadratic: -272 -> -273 sizes 55 x 55 = 110
0091         // It is currently probably not worth to cache these cases, as these are rare cases.
0092         // In the bitset_grids robustness test, the clusters are small and the listings are like:
0093         //     quadratic: -5 -> -1 sizes 2 x 3 = 1
0094         std::cout << "quadratic: "
0095             << source_node_id << " -> " << target_node_id
0096             << " sizes " << source_turn_indices.size() << " x " << target_turn_indices.size()
0097             << " = " << result.size()
0098             << std::endl;
0099 #endif
0100     }
0101 }
0102
0103 // Variant with one node
0104 template <operation_type TargetOperation, typename Turns, typename Clusters>
0105 set_of_tois get_tois(Turns const& turns, Clusters const& clusters,
0106         signed_size_type source_node_id, signed_size_type target_node_id)
0107 {
0108     set_of_tois result;
0109     add_tois<TargetOperation>(turns, clusters, source_node_id, target_node_id, result);
0110     return result;
0111 }
0112
0113 // Variant with multiple target nodes
0114 template <operation_type TargetOperation, typename Turns, typename Clusters>
0115 set_of_tois get_tois(Turns const& turns, Clusters const& clusters,
0116         signed_size_type source_node_id, std::set<signed_size_type> const& target_node_ids)
0117 {
0118     set_of_tois result;
0119     for (auto const& target : target_node_ids)
0120     {
0121         add_tois<TargetOperation>(turns, clusters, source_node_id, target, result);
0122     }
0123     return result;
0124 }
0125
0126 }} // namespace detail::overlay
0127 #endif // DOXYGEN_NO_DETAIL
0128
0129 }} // namespace boost::geometry
0130
0131 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TOIS_HPP