detail/overlay/handle_colocations.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2017-2024.
0007 // Modifications copyright (c) 2017-2024 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
0017
0018 #include <cstddef>
0019 #include <algorithm>
0020 #include <map>
0021 #include <vector>
0022
0023 #include <boost/core/ignore_unused.hpp>
0024 #include <boost/range/begin.hpp>
0025 #include <boost/range/end.hpp>
0026 #include <boost/range/value_type.hpp>
0027
0028 #include <boost/geometry/core/assert.hpp>
0029 #include <boost/geometry/core/point_order.hpp>
0030 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
0031 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
0032 #include <boost/geometry/algorithms/detail/overlay/colocate_clusters.hpp>
0033 #include <boost/geometry/algorithms/detail/overlay/get_clusters.hpp>
0034 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
0035 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
0036 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
0037 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0038 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
0039 #include <boost/geometry/util/constexpr.hpp>
0040
0041 #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
0042 #  include <iostream>
0043 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
0044 #  include <boost/geometry/io/wkt/wkt.hpp>
0045 #  define BOOST_GEOMETRY_DEBUG_IDENTIFIER
0046 #endif
0047
0048 namespace boost { namespace geometry
0049 {
0050
0051 #ifndef DOXYGEN_NO_DETAIL
0052 namespace detail { namespace overlay
0053 {
0054
0055 // Removes clusters which have only one point left, or are empty.
0056 template <typename Turns, typename Clusters>
0057 inline void remove_clusters(Turns& turns, Clusters& clusters)
0058 {
0059     auto it = clusters.begin();
0060     while (it != clusters.end())
0061     {
0062         // Hold iterator and increase. We can erase cit, this keeps the
0063         // iterator valid (cf The standard associative-container erase idiom)
0064         auto current_it = it;
0065         ++it;
0066
0067         auto const& turn_indices = current_it->second.turn_indices;
0068         if (turn_indices.size() == 1)
0069         {
0070             auto const turn_index = *turn_indices.begin();
0071             turns[turn_index].cluster_id = -1;
0072             clusters.erase(current_it);
0073         }
0074     }
0075 }
0076
0077 template <typename Turns, typename Clusters>
0078 inline void cleanup_clusters(Turns& turns, Clusters& clusters)
0079 {
0080     // Removes discarded turns from clusters
0081     for (auto& pair : clusters)
0082     {
0083         auto& cinfo = pair.second;
0084         auto& indices = cinfo.turn_indices;
0085         for (auto sit = indices.begin(); sit != indices.end(); /* no increment */)
0086         {
0087             auto current_it = sit;
0088             ++sit;
0089
0090             auto const turn_index = *current_it;
0091             if (turns[turn_index].discarded)
0092             {
0093                 indices.erase(current_it);
0094             }
0095         }
0096     }
0097
0098     remove_clusters(turns, clusters);
0099 }
0100
0101
0102 template
0103 <
0104     typename Turns,
0105     typename Clusters
0106 >
0107 inline void assign_cluster_ids(Turns& turns, Clusters const& clusters)
0108 {
0109     for (auto& turn : turns)
0110     {
0111         turn.cluster_id = -1;
0112     }
0113     for (auto const& kv : clusters)
0114     {
0115         for (auto const& index : kv.second.turn_indices)
0116         {
0117             turns[index].cluster_id = kv.first;
0118         }
0119     }
0120 }
0121
0122 // Get clusters and assign their ids
0123 template<typename Turns, typename Clusters>
0124 inline void handle_colocations(Turns& turns, Clusters& clusters)
0125 {
0126     get_clusters(turns, clusters);
0127     assign_cluster_ids(turns, clusters);
0128 }
0129
0130
0131 }} // namespace detail::overlay
0132 #endif //DOXYGEN_NO_DETAIL
0133
0134
0135 }} // namespace boost::geometry
0136
0137 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP