detail/overlay/colocate_clusters.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2023 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_COLOCATE_CLUSTERS_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COLOCATE_CLUSTERS_HPP
0011
0012 #include <boost/geometry/core/access.hpp>
0013 #include <boost/geometry/core/cs.hpp>
0014 #include <boost/geometry/core/coordinate_type.hpp>
0015 #include <boost/geometry/core/tags.hpp>
0016
0017 namespace boost { namespace geometry
0018 {
0019
0020 #ifndef DOXYGEN_NO_DETAIL
0021 namespace detail { namespace overlay
0022 {
0023
0024 // Default implementation, using the first point for all turns in the cluster.
0025 template
0026 <
0027     typename Point,
0028     typename CoordinateType = geometry::coordinate_type_t<Point>,
0029     typename CsTag = geometry::cs_tag_t<Point>,
0030     bool IsIntegral = std::is_integral<CoordinateType>::value
0031 >
0032 struct cluster_colocator
0033 {
0034     template <typename TurnIndices, typename Turns>
0035     static inline void apply(TurnIndices const& indices, Turns& turns)
0036     {
0037         // This approach works for all but one testcase (rt_p13)
0038         // The problem is fill_sbs, which uses sides and these sides might change slightly
0039         // depending on the exact location of the cluster.
0040         // Using the centroid is, on the average, a safer choice for sides.
0041         // Alternatively fill_sbs could be revised, but that requires a lot of work
0042         // and is outside current scope.
0043         // Integer coordinates are always colocated already and do not need centroid calculation.
0044         // Geographic/spherical coordinates might (in extremely rare cases) cross the date line
0045         // and therefore the first point is taken for them as well.
0046         auto it = indices.begin();
0047         auto const& first_point = turns[*it].point;
0048         for (++it; it != indices.end(); ++it)
0049         {
0050             turns[*it].point = first_point;
0051         }
0052     }
0053 };
0054
0055 // Specialization for non-integral cartesian coordinates, calculating
0056 // the centroid of the points of the turns in the cluster.
0057 template <typename Point, typename CoordinateType>
0058 struct cluster_colocator<Point, CoordinateType, geometry::cartesian_tag, false>
0059 {
0060     template <typename TurnIndices, typename Turns>
0061     static inline void apply(TurnIndices const& indices, Turns& turns)
0062     {
0063         CoordinateType centroid_0 = 0;
0064         CoordinateType centroid_1 = 0;
0065         for (auto const& index : indices)
0066         {
0067             centroid_0 += geometry::get<0>(turns[index].point);
0068             centroid_1 += geometry::get<1>(turns[index].point);
0069         }
0070         centroid_0 /= indices.size();
0071         centroid_1 /= indices.size();
0072         for (auto const& index : indices)
0073         {
0074             geometry::set<0>(turns[index].point, centroid_0);
0075             geometry::set<1>(turns[index].point, centroid_1);
0076         }
0077     }
0078 };
0079
0080 // Moves intersection points per cluster such that they are identical.
0081 // Because clusters are intersection close together, and
0082 // handled as one location. Then they should also have one location.
0083 // It is necessary to avoid artefacts and invalidities.
0084 template <typename Clusters, typename Turns>
0085 inline void colocate_clusters(Clusters const& clusters, Turns& turns)
0086 {
0087     for (auto const& pair : clusters)
0088     {
0089         auto const& turn_indices = pair.second.turn_indices;
0090         if (turn_indices.size() < 2)
0091         {
0092             // Defensive check
0093             continue;
0094         }
0095         using point_t = decltype(turns[*turn_indices.begin()].point);
0096         cluster_colocator<point_t>::apply(turn_indices, turns);
0097     }
0098 }
0099
0100
0101 }} // namespace detail::overlay
0102 #endif //DOXYGEN_NO_DETAIL
0103
0104
0105 }} // namespace boost::geometry
0106
0107 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COLOCATE_CLUSTERS_HPP