geometry/algorithms/remove_spikes.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2013 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2013 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2013 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2013-2023 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 // Use, modification and distribution is subject to the Boost Software License,
0014 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0015 // http://www.boost.org/LICENSE_1_0.txt)
0016
0017 #ifndef BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
0018 #define BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
0019
0020 #include <boost/range/begin.hpp>
0021 #include <boost/range/end.hpp>
0022 #include <boost/range/size.hpp>
0023
0024 #include <boost/variant/apply_visitor.hpp>
0025 #include <boost/variant/static_visitor.hpp>
0026 #include <boost/variant/variant_fwd.hpp>
0027
0028 #include <boost/geometry/core/closure.hpp>
0029 #include <boost/geometry/core/cs.hpp>
0030 #include <boost/geometry/core/interior_rings.hpp>
0031 #include <boost/geometry/core/tags.hpp>
0032
0033 #include <boost/geometry/geometries/concepts/check.hpp>
0034
0035 #include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp>
0036 #include <boost/geometry/algorithms/clear.hpp>
0037
0038 #include <boost/geometry/strategies/default_strategy.hpp>
0039
0040 #include <boost/geometry/util/constexpr.hpp>
0041 #include <boost/geometry/util/range.hpp>
0042
0043
0044 /*
0045 Remove spikes from a ring/polygon.
0046 Ring (having 8 vertices, including closing vertex)
0047 +------+
0048 |      |
0049 |      +--+
0050 |      |  ^this "spike" is removed, can be located outside/inside the ring
0051 +------+
0052 (the actualy determination if it is removed is done by a strategy)
0053
0054 */
0055
0056
0057 namespace boost { namespace geometry
0058 {
0059
0060
0061 #ifndef DOXYGEN_NO_DETAIL
0062 namespace detail { namespace remove_spikes
0063 {
0064
0065
0066 struct range_remove_spikes
0067 {
0068     template <typename Range, typename SideStrategy>
0069     static inline void apply(Range& range, SideStrategy const& strategy)
0070     {
0071         std::size_t const n = boost::size(range);
0072         std::size_t const min_num_points = core_detail::closure::minimum_ring_size
0073             <
0074                 geometry::closure<Range>::value
0075             >::value - 1; // subtract one: a polygon with only one spike should result into one point
0076         if (n < min_num_points)
0077         {
0078             return;
0079         }
0080
0081         std::vector<point_type_t<Range>> cleaned;
0082         cleaned.reserve(n);
0083
0084         for (auto const& p : range)
0085         {
0086             // Add point
0087             cleaned.push_back(p);
0088
0089             while(cleaned.size() >= 3
0090                   && detail::is_spike_or_equal(range::at(cleaned, cleaned.size() - 3),
0091                                                range::at(cleaned, cleaned.size() - 2),
0092                                                range::back(cleaned),
0093                                                strategy))
0094             {
0095                 // Remove pen-ultimate point causing the spike (or which was equal)
0096                 cleaned.erase(cleaned.end() - 2);
0097             }
0098         }
0099
0100         auto cleaned_b = cleaned.begin();
0101         auto cleaned_e = cleaned.end();
0102         std::size_t cleaned_count = cleaned.size();
0103
0104         // For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent
0105         if BOOST_GEOMETRY_CONSTEXPR (geometry::closure<Range>::value == geometry::closed)
0106         {
0107             --cleaned_e;
0108             --cleaned_count;
0109         }
0110
0111         bool found = false;
0112         do
0113         {
0114             found = false;
0115             // Check for spike in first point
0116             while(cleaned_count >= 3
0117                   && detail::is_spike_or_equal(*(cleaned_e - 2), // prev
0118                                                *(cleaned_e - 1), // back
0119                                                *(cleaned_b),     // front
0120                                                strategy))
0121             {
0122                 --cleaned_e;
0123                 --cleaned_count;
0124                 found = true;
0125             }
0126             // Check for spike in second point
0127             while(cleaned_count >= 3
0128                   && detail::is_spike_or_equal(*(cleaned_e - 1), // back
0129                                                *(cleaned_b),     // front
0130                                                *(cleaned_b + 1), // next
0131                                                strategy))
0132             {
0133                 ++cleaned_b;
0134                 --cleaned_count;
0135                 found = true;
0136             }
0137         }
0138         while (found);
0139
0140         if (cleaned_count == 2)
0141         {
0142             // Ticket #9871: open polygon with only two points.
0143             // the second point forms, by definition, a spike
0144             --cleaned_e;
0145             //--cleaned_count;
0146         }
0147
0148         // Close if necessary
0149         if BOOST_GEOMETRY_CONSTEXPR (geometry::closure<Range>::value == geometry::closed)
0150         {
0151             BOOST_GEOMETRY_ASSERT(cleaned_e != cleaned.end());
0152             *cleaned_e = *cleaned_b;
0153             ++cleaned_e;
0154             //++cleaned_count;
0155         }
0156
0157         // Copy output
0158         geometry::clear(range);
0159         std::copy(cleaned_b, cleaned_e, range::back_inserter(range));
0160     }
0161 };
0162
0163
0164 struct polygon_remove_spikes
0165 {
0166     template <typename Polygon, typename SideStrategy>
0167     static inline void apply(Polygon& polygon, SideStrategy const& strategy)
0168     {
0169         typedef range_remove_spikes per_range;
0170         per_range::apply(exterior_ring(polygon), strategy);
0171
0172         auto&& rings = interior_rings(polygon);
0173
0174         for (auto it = boost::begin(rings); it != boost::end(rings); ++it)
0175         {
0176             per_range::apply(*it, strategy);
0177         }
0178     }
0179 };
0180
0181
0182 template <typename SingleVersion>
0183 struct multi_remove_spikes
0184 {
0185     template <typename MultiGeometry, typename SideStrategy>
0186     static inline void apply(MultiGeometry& multi, SideStrategy const& strategy)
0187     {
0188         for (auto it = boost::begin(multi); it != boost::end(multi); ++it)
0189         {
0190             SingleVersion::apply(*it, strategy);
0191         }
0192     }
0193 };
0194
0195
0196 }} // namespace detail::remove_spikes
0197 #endif // DOXYGEN_NO_DETAIL
0198
0199
0200
0201 #ifndef DOXYGEN_NO_DISPATCH
0202 namespace dispatch
0203 {
0204
0205
0206 template
0207 <
0208     typename Geometry,
0209     typename Tag = tag_t<Geometry>
0210 >
0211 struct remove_spikes
0212 {
0213     template <typename SideStrategy>
0214     static inline void apply(Geometry&, SideStrategy const&)
0215     {}
0216 };
0217
0218
0219 template <typename Ring>
0220 struct remove_spikes<Ring, ring_tag>
0221     : detail::remove_spikes::range_remove_spikes
0222 {};
0223
0224
0225
0226 template <typename Polygon>
0227 struct remove_spikes<Polygon, polygon_tag>
0228     : detail::remove_spikes::polygon_remove_spikes
0229 {};
0230
0231
0232 template <typename MultiPolygon>
0233 struct remove_spikes<MultiPolygon, multi_polygon_tag>
0234     : detail::remove_spikes::multi_remove_spikes
0235         <
0236             detail::remove_spikes::polygon_remove_spikes
0237         >
0238 {};
0239
0240
0241 } // namespace dispatch
0242 #endif
0243
0244
0245 namespace resolve_variant {
0246
0247 template <typename Geometry>
0248 struct remove_spikes
0249 {
0250     template <typename Strategy>
0251     static void apply(Geometry& geometry, Strategy const& strategy)
0252     {
0253         concepts::check<Geometry>();
0254         dispatch::remove_spikes<Geometry>::apply(geometry, strategy);
0255     }
0256
0257     static void apply(Geometry& geometry, geometry::default_strategy const&)
0258     {
0259         using side_strategy = typename strategy::side::services::default_strategy
0260             <
0261                 cs_tag_t<Geometry>
0262             >::type;
0263
0264         apply(geometry, side_strategy());
0265     }
0266 };
0267
0268 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
0269 struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
0270 {
0271     template <typename Strategy>
0272     struct visitor: boost::static_visitor<void>
0273     {
0274         Strategy const& m_strategy;
0275
0276         visitor(Strategy const& strategy) : m_strategy(strategy) {}
0277
0278         template <typename Geometry>
0279         void operator()(Geometry& geometry) const
0280         {
0281             remove_spikes<Geometry>::apply(geometry, m_strategy);
0282         }
0283     };
0284
0285     template <typename Strategy>
0286     static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry,
0287                              Strategy const& strategy)
0288     {
0289         boost::apply_visitor(visitor<Strategy>(strategy), geometry);
0290     }
0291 };
0292
0293 } // namespace resolve_variant
0294
0295
0296 /*!
0297     \ingroup remove_spikes
0298     \tparam Geometry geometry type
0299     \param geometry the geometry to make remove_spikes
0300 */
0301 template <typename Geometry>
0302 inline void remove_spikes(Geometry& geometry)
0303 {
0304     resolve_variant::remove_spikes<Geometry>::apply(geometry, geometry::default_strategy());
0305 }
0306
0307 /*!
0308     \ingroup remove_spikes
0309     \tparam Geometry geometry type
0310     \tparam Strategy side strategy type
0311     \param geometry the geometry to make remove_spikes
0312     \param strategy the side strategy used by the algorithm
0313 */
0314 template <typename Geometry, typename Strategy>
0315 inline void remove_spikes(Geometry& geometry, Strategy const& strategy)
0316 {
0317     resolve_variant::remove_spikes<Geometry>::apply(geometry, strategy);
0318 }
0319
0320
0321 }} // namespace boost::geometry
0322
0323
0324 #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP