geometry/algorithms/correct.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2014-2024 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2017-2023.
0009 // Modifications copyright (c) 2017-2023 Oracle and/or its affiliates.
0010 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0011 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0012
0013 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0014 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0015
0016 // Use, modification and distribution is subject to the Boost Software License,
0017 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0018 // http://www.boost.org/LICENSE_1_0.txt)
0019
0020 #ifndef BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP
0021 #define BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP
0022
0023
0024 #include <algorithm>
0025 #include <functional>
0026
0027 #include <boost/range/begin.hpp>
0028 #include <boost/range/end.hpp>
0029
0030 #include <boost/geometry/algorithms/area.hpp>
0031 #include <boost/geometry/algorithms/correct_closure.hpp>
0032 #include <boost/geometry/algorithms/detail/multi_modify.hpp>
0033 #include <boost/geometry/algorithms/detail/visit.hpp>
0034
0035 #include <boost/geometry/core/exterior_ring.hpp>
0036 #include <boost/geometry/core/interior_rings.hpp>
0037 #include <boost/geometry/core/tags.hpp>
0038 #include <boost/geometry/core/visit.hpp>
0039
0040 #include <boost/geometry/geometries/adapted/boost_variant.hpp> // For backward compatibility
0041 #include <boost/geometry/geometries/concepts/check.hpp>
0042
0043 #include <boost/geometry/strategies/area/cartesian.hpp>
0044 #include <boost/geometry/strategies/area/geographic.hpp>
0045 #include <boost/geometry/strategies/area/spherical.hpp>
0046 #include <boost/geometry/strategies/detail.hpp>
0047
0048 #include <boost/geometry/util/algorithm.hpp>
0049
0050
0051 namespace boost { namespace geometry
0052 {
0053
0054 // Silence warning C4127: conditional expression is constant
0055 #if defined(_MSC_VER)
0056 #pragma warning(push)
0057 #pragma warning(disable : 4127)
0058 #endif
0059
0060 #ifndef DOXYGEN_NO_DETAIL
0061 namespace detail { namespace correct
0062 {
0063
0064 struct correct_nop
0065 {
0066     template <typename Geometry, typename Strategy>
0067     static inline void apply(Geometry& , Strategy const& )
0068     {}
0069 };
0070
0071
0072 // Correct a box: make min/max correct
0073 struct correct_box
0074 {
0075     template <typename Box, typename Strategy>
0076     static inline void apply(Box& box, Strategy const& )
0077     {
0078         // Currently only for Cartesian coordinates
0079         // (or spherical without crossing dateline)
0080         // Future version: adapt using strategies
0081         detail::for_each_dimension<Box>([&](auto dimension)
0082         {
0083             if (get<min_corner, dimension>(box) > get<max_corner, dimension>(box))
0084             {
0085                 // Swap the coordinates
0086                 auto max_value = get<min_corner, dimension>(box);
0087                 auto min_value = get<max_corner, dimension>(box);
0088                 set<min_corner, dimension>(box, min_value);
0089                 set<max_corner, dimension>(box, max_value);
0090             }
0091         });
0092     }
0093 };
0094
0095
0096 // Close a ring, if not closed
0097 template <typename Predicate = std::less<>>
0098 struct correct_ring
0099 {
0100     template <typename Ring, typename Strategy>
0101     static inline void apply(Ring& r, Strategy const& strategy)
0102     {
0103         // Correct closure if necessary
0104         detail::correct_closure::close_or_open_ring::apply(r);
0105
0106         // NOTE: calculate_point_order should probably be used here instead.
0107
0108         // Check area
0109         using area_t = typename area_result<Ring, Strategy>::type;
0110         area_t const zero = 0;
0111         if (Predicate()(detail::area::ring_area::apply(r, strategy), zero))
0112         {
0113             std::reverse(boost::begin(r), boost::end(r));
0114         }
0115     }
0116 };
0117
0118 // Correct a polygon: normalizes all rings, sets outer ring clockwise, sets all
0119 // inner rings counter clockwise (or vice versa depending on orientation)
0120 struct correct_polygon
0121 {
0122     template <typename Polygon, typename Strategy>
0123     static inline void apply(Polygon& poly, Strategy const& strategy)
0124     {
0125         correct_ring<std::less<>>::apply(exterior_ring(poly), strategy);
0126
0127         auto&& rings = interior_rings(poly);
0128         auto const end = boost::end(rings);
0129         for (auto it = boost::begin(rings); it != end; ++it)
0130         {
0131             correct_ring<std::greater<>>::apply(*it, strategy);
0132         }
0133     }
0134 };
0135
0136
0137 }} // namespace detail::correct
0138 #endif // DOXYGEN_NO_DETAIL
0139
0140
0141 #ifndef DOXYGEN_NO_DISPATCH
0142 namespace dispatch
0143 {
0144
0145 template <typename Geometry, typename Tag = tag_t<Geometry>>
0146 struct correct: not_implemented<Tag>
0147 {};
0148
0149 template <typename Point>
0150 struct correct<Point, point_tag>
0151     : detail::correct::correct_nop
0152 {};
0153
0154 template <typename LineString>
0155 struct correct<LineString, linestring_tag>
0156     : detail::correct::correct_nop
0157 {};
0158
0159 template <typename Segment>
0160 struct correct<Segment, segment_tag>
0161     : detail::correct::correct_nop
0162 {};
0163
0164
0165 template <typename Box>
0166 struct correct<Box, box_tag>
0167     : detail::correct::correct_box
0168 {};
0169
0170 template <typename Ring>
0171 struct correct<Ring, ring_tag>
0172     : detail::correct::correct_ring<>
0173 {};
0174
0175 template <typename Polygon>
0176 struct correct<Polygon, polygon_tag>
0177     : detail::correct::correct_polygon
0178 {};
0179
0180
0181 template <typename MultiPoint>
0182 struct correct<MultiPoint, multi_point_tag>
0183     : detail::correct::correct_nop
0184 {};
0185
0186
0187 template <typename MultiLineString>
0188 struct correct<MultiLineString, multi_linestring_tag>
0189     : detail::correct::correct_nop
0190 {};
0191
0192
0193 template <typename Geometry>
0194 struct correct<Geometry, multi_polygon_tag>
0195     : detail::multi_modify<detail::correct::correct_polygon>
0196 {};
0197
0198
0199 } // namespace dispatch
0200 #endif // DOXYGEN_NO_DISPATCH
0201
0202
0203 namespace resolve_strategy
0204 {
0205
0206 template
0207 <
0208     typename Strategy,
0209     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategy>::value
0210 >
0211 struct correct
0212 {
0213     template <typename Geometry>
0214     static inline void apply(Geometry& geometry, Strategy const& strategy)
0215     {
0216         dispatch::correct<Geometry>::apply(geometry, strategy);
0217     }
0218 };
0219
0220 template <typename Strategy>
0221 struct correct<Strategy, false>
0222 {
0223     template <typename Geometry>
0224     static inline void apply(Geometry& geometry, Strategy const& strategy)
0225     {
0226         // NOTE: calculate_point_order strategy should probably be used here instead.
0227         using geometry::strategies::area::services::strategy_converter;
0228         dispatch::correct<Geometry>::apply(geometry, strategy_converter<Strategy>::get(strategy));
0229     }
0230 };
0231
0232 template <>
0233 struct correct<default_strategy, false>
0234 {
0235     template <typename Geometry>
0236     static inline void apply(Geometry& geometry, default_strategy const& )
0237     {
0238         // NOTE: calculate_point_order strategy should probably be used here instead.
0239         using strategy_type = typename strategies::area::services::default_strategy
0240             <
0241                 Geometry
0242             >::type;
0243         dispatch::correct<Geometry>::apply(geometry, strategy_type());
0244     }
0245 };
0246
0247 } // namespace resolve_strategy
0248
0249
0250 namespace resolve_dynamic
0251 {
0252
0253 template <typename Geometry, typename Tag = tag_t<Geometry>>
0254 struct correct
0255 {
0256     template <typename Strategy>
0257     static inline void apply(Geometry& geometry, Strategy const& strategy)
0258     {
0259         concepts::check<Geometry>();
0260         resolve_strategy::correct<Strategy>::apply(geometry, strategy);
0261     }
0262 };
0263
0264 template <typename Geometry>
0265 struct correct<Geometry, dynamic_geometry_tag>
0266 {
0267     template <typename Strategy>
0268     static inline void apply(Geometry& geometry, Strategy const& strategy)
0269     {
0270         traits::visit<Geometry>::apply([&](auto & g)
0271         {
0272             correct<util::remove_cref_t<decltype(g)>>::apply(g, strategy);
0273         }, geometry);
0274     }
0275 };
0276
0277 template <typename Geometry>
0278 struct correct<Geometry, geometry_collection_tag>
0279 {
0280     template <typename Strategy>
0281     static inline void apply(Geometry& geometry, Strategy const& strategy)
0282     {
0283         detail::visit_breadth_first([&](auto & g)
0284         {
0285             correct<util::remove_cref_t<decltype(g)>>::apply(g, strategy);
0286             return true;
0287         }, geometry);
0288     }
0289 };
0290
0291
0292 } // namespace resolve_dynamic
0293
0294
0295 /*!
0296 \brief Corrects a geometry
0297 \details Corrects a geometry: all rings which are wrongly oriented with respect
0298     to their expected orientation are reversed. To all rings which do not have a
0299     closing point and are typed as they should have one, the first point is
0300     appended. Also boxes can be corrected.
0301 \ingroup correct
0302 \tparam Geometry \tparam_geometry
0303 \param geometry \param_geometry which will be corrected if necessary
0304
0305 \qbk{[include reference/algorithms/correct.qbk]}
0306 */
0307 template <typename Geometry>
0308 inline void correct(Geometry& geometry)
0309 {
0310     resolve_dynamic::correct<Geometry>::apply(geometry, default_strategy());
0311 }
0312
0313 /*!
0314 \brief Corrects a geometry
0315 \details Corrects a geometry: all rings which are wrongly oriented with respect
0316     to their expected orientation are reversed. To all rings which do not have a
0317     closing point and are typed as they should have one, the first point is
0318     appended. Also boxes can be corrected.
0319 \ingroup correct
0320 \tparam Geometry \tparam_geometry
0321 \tparam Strategy \tparam_strategy{Area}
0322 \param geometry \param_geometry which will be corrected if necessary
0323 \param strategy \param_strategy{area}
0324
0325 \qbk{distinguish,with strategy}
0326
0327 \qbk{[include reference/algorithms/correct.qbk]}
0328 */
0329 template <typename Geometry, typename Strategy>
0330 inline void correct(Geometry& geometry, Strategy const& strategy)
0331 {
0332     resolve_dynamic::correct<Geometry>::apply(geometry, strategy);
0333 }
0334
0335 #if defined(_MSC_VER)
0336 #pragma warning(pop)
0337 #endif
0338
0339 }} // namespace boost::geometry
0340
0341
0342 #endif // BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP