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-2014 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/condition.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         typedef typename point_type<Range>::type point_type;
0072
0073         std::size_t n = boost::size(range);
0074         std::size_t const min_num_points = core_detail::closure::minimum_ring_size
0075             <
0076                 geometry::closure<Range>::value
0077             >::value - 1; // subtract one: a polygon with only one spike should result into one point
0078         if (n < min_num_points)
0079         {
0080             return;
0081         }
0082
0083         std::vector<point_type> cleaned;
0084         cleaned.reserve(n);
0085
0086         for (auto const& p : range)
0087         {
0088             // Add point
0089             cleaned.push_back(p);
0090
0091             while(cleaned.size() >= 3
0092                   && detail::is_spike_or_equal(range::at(cleaned, cleaned.size() - 3),
0093                                                range::at(cleaned, cleaned.size() - 2),
0094                                                range::back(cleaned),
0095                                                strategy))
0096             {
0097                 // Remove pen-ultimate point causing the spike (or which was equal)
0098                 cleaned.erase(cleaned.end() - 2);
0099             }
0100         }
0101
0102         auto cleaned_b = cleaned.begin();
0103         auto cleaned_e = cleaned.end();
0104         std::size_t cleaned_count = cleaned.size();
0105
0106         // For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent
0107         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
0108         {
0109             --cleaned_e;
0110             --cleaned_count;
0111         }
0112
0113         bool found = false;
0114         do
0115         {
0116             found = false;
0117             // Check for spike in first point
0118             while(cleaned_count >= 3
0119                   && detail::is_spike_or_equal(*(cleaned_e - 2), // prev
0120                                                *(cleaned_e - 1), // back
0121                                                *(cleaned_b),     // front
0122                                                strategy))
0123             {
0124                 --cleaned_e;
0125                 --cleaned_count;
0126                 found = true;
0127             }
0128             // Check for spike in second point
0129             while(cleaned_count >= 3
0130                   && detail::is_spike_or_equal(*(cleaned_e - 1), // back
0131                                                *(cleaned_b),     // front
0132                                                *(cleaned_b + 1), // next
0133                                                strategy))
0134             {
0135                 ++cleaned_b;
0136                 --cleaned_count;
0137                 found = true;
0138             }
0139         }
0140         while (found);
0141
0142         if (cleaned_count == 2)
0143         {
0144             // Ticket #9871: open polygon with only two points.
0145             // the second point forms, by definition, a spike
0146             --cleaned_e;
0147             //--cleaned_count;
0148         }
0149
0150         // Close if necessary
0151         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
0152         {
0153             BOOST_GEOMETRY_ASSERT(cleaned_e != cleaned.end());
0154             *cleaned_e = *cleaned_b;
0155             ++cleaned_e;
0156             //++cleaned_count;
0157         }
0158
0159         // Copy output
0160         geometry::clear(range);
0161         std::copy(cleaned_b, cleaned_e, range::back_inserter(range));
0162     }
0163 };
0164
0165
0166 struct polygon_remove_spikes
0167 {
0168     template <typename Polygon, typename SideStrategy>
0169     static inline void apply(Polygon& polygon, SideStrategy const& strategy)
0170     {
0171         typedef range_remove_spikes per_range;
0172         per_range::apply(exterior_ring(polygon), strategy);
0173
0174         auto&& rings = interior_rings(polygon);
0175
0176         for (auto it = boost::begin(rings); it != boost::end(rings); ++it)
0177         {
0178             per_range::apply(*it, strategy);
0179         }
0180     }
0181 };
0182
0183
0184 template <typename SingleVersion>
0185 struct multi_remove_spikes
0186 {
0187     template <typename MultiGeometry, typename SideStrategy>
0188     static inline void apply(MultiGeometry& multi, SideStrategy const& strategy)
0189     {
0190         for (auto it = boost::begin(multi); it != boost::end(multi); ++it)
0191         {
0192             SingleVersion::apply(*it, strategy);
0193         }
0194     }
0195 };
0196
0197
0198 }} // namespace detail::remove_spikes
0199 #endif // DOXYGEN_NO_DETAIL
0200
0201
0202
0203 #ifndef DOXYGEN_NO_DISPATCH
0204 namespace dispatch
0205 {
0206
0207
0208 template
0209 <
0210     typename Geometry,
0211     typename Tag = typename tag<Geometry>::type
0212 >
0213 struct remove_spikes
0214 {
0215     template <typename SideStrategy>
0216     static inline void apply(Geometry&, SideStrategy const&)
0217     {}
0218 };
0219
0220
0221 template <typename Ring>
0222 struct remove_spikes<Ring, ring_tag>
0223     : detail::remove_spikes::range_remove_spikes
0224 {};
0225
0226
0227
0228 template <typename Polygon>
0229 struct remove_spikes<Polygon, polygon_tag>
0230     : detail::remove_spikes::polygon_remove_spikes
0231 {};
0232
0233
0234 template <typename MultiPolygon>
0235 struct remove_spikes<MultiPolygon, multi_polygon_tag>
0236     : detail::remove_spikes::multi_remove_spikes
0237         <
0238             detail::remove_spikes::polygon_remove_spikes
0239         >
0240 {};
0241
0242
0243 } // namespace dispatch
0244 #endif
0245
0246
0247 namespace resolve_variant {
0248
0249 template <typename Geometry>
0250 struct remove_spikes
0251 {
0252     template <typename Strategy>
0253     static void apply(Geometry& geometry, Strategy const& strategy)
0254     {
0255         concepts::check<Geometry>();
0256         dispatch::remove_spikes<Geometry>::apply(geometry, strategy);
0257     }
0258
0259     static void apply(Geometry& geometry, geometry::default_strategy const&)
0260     {
0261         typedef typename strategy::side::services::default_strategy
0262             <
0263                 typename cs_tag<Geometry>::type
0264             >::type side_strategy;
0265
0266         apply(geometry, side_strategy());
0267     }
0268 };
0269
0270 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
0271 struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
0272 {
0273     template <typename Strategy>
0274     struct visitor: boost::static_visitor<void>
0275     {
0276         Strategy const& m_strategy;
0277
0278         visitor(Strategy const& strategy) : m_strategy(strategy) {}
0279
0280         template <typename Geometry>
0281         void operator()(Geometry& geometry) const
0282         {
0283             remove_spikes<Geometry>::apply(geometry, m_strategy);
0284         }
0285     };
0286
0287     template <typename Strategy>
0288     static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry,
0289                              Strategy const& strategy)
0290     {
0291         boost::apply_visitor(visitor<Strategy>(strategy), geometry);
0292     }
0293 };
0294
0295 } // namespace resolve_variant
0296
0297
0298 /*!
0299     \ingroup remove_spikes
0300     \tparam Geometry geometry type
0301     \param geometry the geometry to make remove_spikes
0302 */
0303 template <typename Geometry>
0304 inline void remove_spikes(Geometry& geometry)
0305 {
0306     resolve_variant::remove_spikes<Geometry>::apply(geometry, geometry::default_strategy());
0307 }
0308
0309 /*!
0310     \ingroup remove_spikes
0311     \tparam Geometry geometry type
0312     \tparam Strategy side strategy type
0313     \param geometry the geometry to make remove_spikes
0314     \param strategy the side strategy used by the algorithm
0315 */
0316 template <typename Geometry, typename Strategy>
0317 inline void remove_spikes(Geometry& geometry, Strategy const& strategy)
0318 {
0319     resolve_variant::remove_spikes<Geometry>::apply(geometry, strategy);
0320 }
0321
0322
0323 }} // namespace boost::geometry
0324
0325
0326 #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP