EIC code displayed by LXR master/​include/​boost/​geometry/​algorithms/​detail/​overlay/​graph/​assign_clustered_counts.hpp	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-08-21 08:45:50

  // Boost.Geometry
 
 // Copyright (c) 2025 Barend Gehrels, Amsterdam, the Netherlands.
 
 // Use, modification and distribution is subject to the Boost Software License,
 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
 // http://www.boost.org/LICENSE_1_0.txt)
 
 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_CLUSTERED_COUNTS_HPP
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_CLUSTERED_COUNTS_HPP
 
 #include <boost/geometry/algorithms/detail/position_code.hpp>
 #include <boost/geometry/algorithms/detail/overlay/approximately_equals.hpp>
 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
 #include <boost/geometry/algorithms/detail/overlay/get_distance_measure.hpp>
 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
 
 #include <set>
 #include <map>
 
 namespace boost { namespace geometry
 {
 
 #ifndef DOXYGEN_NO_DETAIL
 namespace detail { namespace overlay
 {
 
 // Indicating if the segment is incoming (to cluster) or outgoing (from cluster)
 enum class connection_type { unknown = -1, incoming = 0, outgoing = 1 };
 
 // A turn contains four connections to a cluster:
 // For both operations one incoming and one outgoing connection.
 // They are stored in a map, with the (segment id, connection type) as key.
 struct connection_key
 {
     segment_identifier seg_id;
     connection_type connection{connection_type::unknown};
 
     bool operator<(connection_key const& rhs) const
     {
         return std::tie(seg_id, connection) < std::tie(rhs.seg_id, rhs.connection);
     }
 };
 
 // Properties of a connection in a property map
 template <typename Point>
 struct connection_properties
 {
     // Assigned at construction time
     int position_code{0};
     Point point{};
     Point opposite_point{};
     bool is_shifted{false};
 
     // Assigned later
     std::size_t zone_count_left{0};
     std::size_t zone_count_right{0};
     std::size_t rank{0};
 };
 
 // Convenience structure to store connections in a vector
 template <typename Point>
 struct connection_item
 {
     connection_key key{};
     connection_properties<Point> properties{};
 };
 
 template <overlay_type OverlayType>
 struct is_corresponding_connection
 {
     static inline bool apply(connection_key const& left, connection_key const& right)
     {
         return left.seg_id.source_index == right.seg_id.source_index;
     }
 };
 
 template <>
 struct is_corresponding_connection<overlay_buffer>
 {
     static inline bool apply(connection_key const& left, connection_key const& right)
     {
         // For buffer, the source_index is always the same.
         // It needs to check where the incoming seg_id is outgoing.
         return left.seg_id == right.seg_id;
     }
 };
 
 template
 <
     bool Reverse1,
     bool Reverse2,
     overlay_type OverlayType,
     typename Geometry1,
     typename Geometry2,
     typename Turns,
     typename Clusters,
     typename Strategy
 >
 struct clustered_count_handler
 {
     using point_type = typename Turns::value_type::point_type;
     using connection_map_type = std::map<connection_key, connection_properties<point_type>>;
     using ct_type = typename geometry::select_most_precise
         <
             geometry::coordinate_type_t<point_type>,
             double
         >::type;
 
     clustered_count_handler(Geometry1 const& m_geometry1, Geometry2 const& m_geometry2,
         Turns& m_turns, Clusters& clusters,
         Strategy const& strategy)
         : m_geometry1(m_geometry1)
         , m_geometry2(m_geometry2)
         , m_turns(m_turns)
         , m_clusters(clusters)
         , m_intersection_strategy(strategy)
         , m_side_strategy(m_intersection_strategy.side())
     {}
 
     // Walks over a ring to get the point after the turn.
     // The turn can be located at the very end of a segment.
     // Therefore it can be the first point on the next segment.
     template <typename Operation>
     bool get_segment_points(Operation const& op, point_type const& point_turn,
         point_type& point_from, point_type& point_to)
     {
         // Use the coordinate type, but if it is too small (e.g. std::int16), use a double
         static const ct_type tolerance
             = common_approximately_equals_epsilon_multiplier<ct_type>::value();
 
         // For a defensive check.
         constexpr int max_iterations = 10;
 
         int from_offset = 0;
         do
         {
             geometry::copy_segment_point<Reverse1, Reverse2>(m_geometry1, m_geometry2,
                 op.seg_id, from_offset--, point_from);
         } while (approximately_equals(point_from, point_turn, tolerance) && from_offset > -max_iterations);
 
         int to_offset = 1;
         do
         {
             geometry::copy_segment_point<Reverse1, Reverse2>(m_geometry1, m_geometry2,
                 op.seg_id, to_offset++, point_to);
         } while (approximately_equals(point_to, point_turn, tolerance) && to_offset < max_iterations);
 
         return from_offset < -1 || to_offset > 2;
     }
 
     void get_connection_map(cluster_info const& cluster, point_type const& point_turn,
         connection_map_type& connection_map, point_type& point_origin)
     {
         auto const get_position_code = [&](point_type const& point)
         {
             return detail::get_position_code(point_origin, point_turn, point, m_side_strategy);
         };
 
         auto insert = [&connection_map](auto const& op,  connection_type conn,
                     auto const& point, int position_code, auto const& opposite_point, bool is_shifted)
         {
             connection_key const key{op.seg_id, conn};
             connection_properties<point_type> properties{position_code, point, opposite_point, is_shifted};
             connection_map.insert({key, properties});
         };
 
         // Add them to the set, which keeps them unique on (seg_id,from/to)
         bool first = true;
         for (std::size_t index : cluster.turn_indices)
         {
             auto const& turn = m_turns[index];
             for (auto const& op : turn.operations)
             {
                 point_type point_from, point_to;
                 bool const is_shifted = get_segment_points(op, point_turn, point_from, point_to);
 
                 if (first)
                 {
                     // One of the incoming points is the origin. For the algorithm,
                     // it does not matter which one.
                     first = false;
                     point_origin = point_from;
                 }
 
                 // Insert the four connections. Insert all operations (even if they are blocked).
                 insert(op, connection_type::incoming, point_from, get_position_code(point_from), point_to, is_shifted);
                 insert(op, connection_type::outgoing, point_to, get_position_code(point_to), point_from, is_shifted);
             }
         }
     }
 
     void sort(point_type const& point_turn, std::vector<connection_item<point_type>>& item_vector)
     {
         auto compare_by_connection = [](auto const& left, auto const& right)
         {
             // Reversing it gives only one failure in ticket_9942 (difference)...
             return left.key.connection > right.key.connection;
         };
 
         // Compare by side, then by connection.
         // Left-side (1) goes before right-side (-1).
         // Outgoing (1) goes before incoming (0).
         auto compare_by_side = [&](auto const& left, auto const& right)
         {
             int const side_left = m_side_strategy.apply(point_turn, right.properties.point, left.properties.point);
             int const side_right = m_side_strategy.apply(point_turn, left.properties.point, right.properties.point);
 
             if (side_right == side_left)
             {
                 return compare_by_connection(left, right);
             }
             return side_left < side_right;
         };
 
         std::sort(item_vector.begin(), item_vector.end(),
             [&](auto const& left, auto const& right)
             {
                 if (left.properties.position_code == right.properties.position_code)
                 {
                     if (left.properties.position_code == 1 || left.properties.position_code == 3)
                     {
                         // For collinear cases, side is be the same.
                         return compare_by_connection(left, right);
                     }
                     return compare_by_side(left, right);
                 }
                 return left.properties.position_code < right.properties.position_code;
             });
     }
 
     // Assign ranks, counter clockwise from the first incoming segment.
     void assign_ranks(point_type const& point_turn,
         std::vector<connection_item<point_type>>& item_vector)
     {
         std::size_t rank = 0;
         item_vector.front().properties.rank = 0;
         for (std::size_t i = 0; i + 1 < item_vector.size(); i++)
         {
             auto const& previous = item_vector[i];
             auto& item = item_vector[i + 1];
             if (item.properties.position_code != previous.properties.position_code)
             {
                 item.properties.rank = ++rank;
                 continue;
             }
 
             if (item.properties.position_code == 1 || item.properties.position_code == 3)
             {
                 // Collinear cases always get the same rank.
                 item.properties.rank = rank;
                 continue;
             }
 
             // If it is collinear, it gets the same rank.
             // In other cases the side should be 1 (left) because the connections
             // are sorted counter clockwise.
             int const side = m_side_strategy.apply(point_turn, previous.properties.point,
                 item.properties.point);
             item.properties.rank = side == 0 ? rank : ++rank;
         }
     }
 
     auto get_zone_counts(std::vector<connection_item<point_type>> const& item_vector,
         std::size_t rank_size)
     {
         std::size_t const vector_size = item_vector.size();
         auto get_next_item = [&vector_size](std::size_t counter)
         {
             return (counter + 1) % vector_size;
         };
 
         auto get_next_zone = [&rank_size](std::size_t counter)
         {
             return (counter + 1) % rank_size;
         };
 
         // Each segment occurs twice, once as from, once as to.
         // As soon as it comes in, increase the zone count, until it goes out.
         std::vector<std::size_t> zone_counts(rank_size, 0);
         for (std::size_t i = 0; i < item_vector.size(); i++)
         {
             auto const& item = item_vector[i];
             if (item.key.connection != connection_type::incoming)
             {
                 continue;
             }
 
             // Walk ahead, cyclic, to find the next item with the same seg_id.
             // The iteration is a defensive check.
             std::size_t end_rank = item.properties.rank;
             for (std::size_t j = get_next_item(i), iteration = 0; ; j = get_next_item(j), iteration++)
             {
                 if (iteration > vector_size)
                 {
 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
                     std::cerr << " *** ERROR: infinite loop in cluster" << std::endl;
 #endif                    
                     return zone_counts;
                 }
                 auto const& next = item_vector[j];
                 end_rank = next.properties.rank;
 
                 if (next.key.connection == connection_type::outgoing
                     && is_corresponding_connection<OverlayType>::apply(item.key, next.key))
                 {
                     // Found the corresponding outgoing segment for this incoming segment.
                     break;
                 }
             }
 
             // Assign the ring count to the zone_counts in the rank range.
             for (std::size_t r = item.properties.rank; r != end_rank; r = get_next_zone(r))
             {
                 zone_counts[r]++;
             }
         }
 
         return zone_counts;
     }
 
     void assign_zone_counts(std::vector<connection_item<point_type>>& item_vector,
         std::vector<std::size_t> const& zone_counts, std::size_t rank_size)
     {
         // The main goal is to get the number of polygons in the zone_counts.
         // The zone_counts on the right side of the seg_ids.
         for (auto& item : item_vector)
         {
             std::size_t const zone_right =
                 item.key.connection == connection_type::incoming
                 ? item.properties.rank
                 : (item.properties.rank + rank_size - 1) % rank_size;
 
             std::size_t const zone_left =
                 item.key.connection == connection_type::incoming
                 ? (item.properties.rank + rank_size - 1) % rank_size
                 : item.properties.rank;
 
             item.properties.zone_count_left = zone_counts[zone_left];
             item.properties.zone_count_right = zone_counts[zone_right];
         }
     }
 
     std::size_t get_open_count(std::vector<std::size_t> const& zone_counts, std::size_t rank_size)
     {
         std::size_t result = 0;
         for (std::size_t i = 0; i < rank_size; i++)
         {
             if (zone_counts[i] == 0)
             {
                 result++;
             }
         }
         return result;
     }
 
     // Get the number of spikes in a cluster, and mark them as spikes.
     void handle_spikes(cluster_info& cluster, std::vector<connection_item<point_type>>& item_vector)
     {
         for (std::size_t i = 0; i < item_vector.size(); i++)
         {
             auto const next_i = (i + 1) % item_vector.size();
             if (item_vector[i].key.connection == item_vector[next_i].key.connection)
             {
                 // The connection should be different
                 continue;
             }
             auto& current = item_vector[i].properties;
             auto& next = item_vector[next_i].properties;
             if (current.rank != next.rank
                 || current.zone_count_left != 1 || current.zone_count_right != 1
                 || next.zone_count_left != 1 || next.zone_count_right != 1)
             {
                 // The rank should be the same
                 // It should have one zone on either side
                 continue;
             }
 
             if (current.is_shifted || next.is_shifted) {
                 // The opposite point is shifted. Therefore a spike measurement
                 // cannot be done.
                 continue;
             }
 
             // Precise measurement, not from the turn, but over the whole intersecting segment.
             // If it is positive (on the left side), it is a spike.
             auto const dm = get_distance_measure(current.opposite_point, current.point, next.point,
                 m_intersection_strategy);
             if (dm.measure <= 0)
             {
                 continue;
             }
 
             // There is a small measurable difference.
             // Make the cluster open and adapt the counts.
             cluster.open_count++;
             current.zone_count_left = 0;
             next.zone_count_right = 0;
         }
     }
 
     void assign_turn_operations(cluster_info const& cluster,
         connection_map_type const& connection_map)
     {
         // Assign the items, per seg_id, back to the outgoing turn operations.
         for (std::size_t index : cluster.turn_indices)
         {
             auto& turn = m_turns[index];
             for (int i = 0; i < 2; i++)
             {
                 auto& op = turn.operations[i];
                 connection_key const key{op.seg_id, connection_type::outgoing};
                 auto const it = connection_map.find(key);
                 if (it != connection_map.end())
                 {
                     op.enriched.count_left = it->second.zone_count_left;
                     op.enriched.count_right = it->second.zone_count_right;
                     op.enriched.rank = it->second.rank;
                 }
             }
         }
     }
 
     // Currently necessary for some failing cases in buffer only, where due to floating point
     // precision the i/u turns get unexpected counts for left/right.
     // rt_w10, rt_w11, rt_w14, rt_w15
     // The original sides are measured over the two whole intersecting segments.
     // The sides in clusters are measured w.r.t. the turn point, which is the point of the first cluster.
     // This can differ.
     // It should be possible to fix it in another way.
     void change_reversed_operations(signed_size_type const cluster_id, cluster_info const& cluster,
             point_type const& point_turn, point_type const& point_origin)
     {
         std::set<std::size_t> reversed_indices;
         for (std::size_t index : cluster.turn_indices)
         {
             auto const& turn = m_turns[index];
             if (! turn.combination(operation_union, operation_intersection))
             {
                 continue;
             }
             int const union_index = turn.operations[0].operation == operation_union ? 0 : 1;
             auto const& op_u = turn.operations[union_index];
             auto const& op_i = turn.operations[1 - union_index];
             if (op_u.enriched.count_left > 0 && op_i.enriched.count_left == 0)
             {
                 reversed_indices.insert(index);
             }
         }
 
         if (reversed_indices.empty())
         {
             return;
         }
 
 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
         std::cout << " *** REVERSED OPERATIONS in cluster: " << cluster_id
             << " cluster size: " << cluster.turn_indices.size()
             << " reversed: " << reversed_indices.size()
             << std::endl;
 #endif
         for (std::size_t index : cluster.turn_indices)
         {
             auto& turn = m_turns[index];
             auto& op0 = turn.operations[0];
             auto& op1 = turn.operations[1];
 
             bool const is_same_target = op0.enriched.travels_to_ip_index == op1.enriched.travels_to_ip_index;
             if (is_same_target && reversed_indices.find(index) != reversed_indices.end())
             {
                 // Best choice: i/u are nearly collinear, so we can let them continue.
                 op0.operation = operation_continue;
                 op1.operation = operation_continue;
 
                 // Also adapt the left/right-counts, both should get the minimum of both.
                 op0.enriched.count_left = (std::min)(op0.enriched.count_left, op1.enriched.count_left);
                 op1.enriched.count_left = op0.enriched.count_left;
                 op0.enriched.count_right = (std::min)(op0.enriched.count_right, op1.enriched.count_right);
                 op1.enriched.count_right = op0.enriched.count_right;
             }
         }
     }
 
     template <typename Visitor>
     void apply(signed_size_type const cluster_id, cluster_info& cluster, Visitor& visitor)
     {
         if (cluster.turn_indices.empty())
         {
             // Defensive check.
             return;
         }
 
         point_type const& point_turn = m_turns[*cluster.turn_indices.begin()].point;
         point_type point_origin;
         connection_map_type connection_map;
         get_connection_map(cluster, point_turn, connection_map, point_origin);
 
         // Sort the items by position code, and if equal, by side.
         // For this they are copied into a vector.
         std::vector<connection_item<point_type>> item_vector;
         for (auto const& key_value : connection_map)
         {
             connection_item<point_type> item;
             item.key = key_value.first;
             item.properties = key_value.second;
             item_vector.push_back(std::move(item));
         }
 
         sort(point_turn, item_vector);
         assign_ranks(point_turn, item_vector);
 
         auto const rank_size = item_vector.back().properties.rank + 1;
         auto const zone_counts = get_zone_counts(item_vector, rank_size);
 
         assign_zone_counts(item_vector, zone_counts, rank_size);
 
         cluster.open_count = get_open_count(zone_counts, rank_size);
         if (cluster.open_count == 0)
         {
             handle_spikes(cluster, item_vector);
         }
 
         // Assign the updated properties back to the connection map
         for (auto const& item : item_vector)
         {
             connection_map[item.key] = item.properties;
         }
 
         assign_turn_operations(cluster, connection_map);
         change_reversed_operations(cluster_id, cluster, point_turn, point_origin);
 
 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE_GRAPH)
         // List the connections
         std::cout << "Cluster " << cluster_id << " size: " << cluster.turn_indices.size() << std::endl;
         for (auto const& item : item_vector)
         {
             std::cout << "  " << item.key.seg_id
                 << " " << (item.key.connection == connection_type::incoming ? " in" : "out")
                 << " " << item.properties.position_code
                 << " " << item.properties.rank
                 << " " << item.properties.zone_count_left
                 << " " << item.properties.zone_count_right
                 << std::endl;
         }
 #endif
 
         visitor.visit_cluster_connections(cluster_id, m_turns, cluster, item_vector);
     }
 
     template <typename Visitor>
     void apply(Visitor& visitor)
     {
         for (auto& key_value : m_clusters)
         {
             auto& cluster = key_value.second;
             if (cluster.turn_indices.empty())
             {
                 continue;
             }
 
             apply(key_value.first, cluster, visitor);
         }
     }
 
 private:
     Geometry1 const& m_geometry1;
     Geometry2 const& m_geometry2;
     Turns& m_turns;
     Clusters& m_clusters;
     Strategy const& m_intersection_strategy;
     decltype(m_intersection_strategy.side()) m_side_strategy;
 };
 
 }} // namespace detail::overlay
 #endif //DOXYGEN_NO_DETAIL
 
 }} // namespace boost::geometry
 
 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLUSTER_INFO_HPP

This page was automatically generated by the 2.3.7 LXR engine. The LXR team