ceph/src/boost/boost/geometry/algorithms/remove_spikes.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2013 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2013 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2013 Mateusz Loskot, London, UK.
   6 // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // This file was modified by Oracle on 2017.
   9 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
  10
  11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  12
  13 // Use, modification and distribution is subject to the Boost Software License,
  14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  15 // http://www.boost.org/LICENSE_1_0.txt)
  16
  17 #ifndef BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
  18 #define BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
  19
  20 #include <deque>
  21
  22 #include <boost/range.hpp>
  23 #include <boost/type_traits/remove_reference.hpp>
  24
  25 #include <boost/variant/apply_visitor.hpp>
  26 #include <boost/variant/static_visitor.hpp>
  27 #include <boost/variant/variant_fwd.hpp>
  28
  29 #include <boost/geometry/core/closure.hpp>
  30 #include <boost/geometry/core/coordinate_type.hpp>
  31 #include <boost/geometry/core/cs.hpp>
  32 #include <boost/geometry/core/interior_rings.hpp>
  33 #include <boost/geometry/core/point_order.hpp>
  34 #include <boost/geometry/core/tags.hpp>
  35
  36 #include <boost/geometry/geometries/concepts/check.hpp>
  37
  38 #include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp>
  39 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
  40 #include <boost/geometry/algorithms/clear.hpp>
  41
  42 #include <boost/geometry/strategies/default_strategy.hpp>
  43
  44 #include <boost/geometry/util/condition.hpp>
  45
  46
  47 /*
  48 Remove spikes from a ring/polygon.
  49 Ring (having 8 vertices, including closing vertex)
  50 +------+
  51 |      |
  52 |      +--+
  53 |      |  ^this "spike" is removed, can be located outside/inside the ring
  54 +------+
  55 (the actualy determination if it is removed is done by a strategy)
  56
  57 */
  58
  59
  60 namespace boost { namespace geometry
  61 {
  62
  63
  64 #ifndef DOXYGEN_NO_DETAIL
  65 namespace detail { namespace remove_spikes
  66 {
  67
  68
  69 struct range_remove_spikes
  70 {
  71     template <typename Range, typename SideStrategy>
  72     static inline void apply(Range& range, SideStrategy const& strategy)
  73     {
  74         typedef typename point_type<Range>::type point_type;
  75
  76         std::size_t n = boost::size(range);
  77         std::size_t const min_num_points = core_detail::closure::minimum_ring_size
  78             <
  79                 geometry::closure<Range>::value
  80             >::value - 1; // subtract one: a polygon with only one spike should result into one point
  81         if (n < min_num_points)
  82         {
  83             return;
  84         }
  85
  86         std::deque<point_type> cleaned;
  87         for (typename boost::range_iterator<Range const>::type it = boost::begin(range);
  88             it != boost::end(range); ++it)
  89         {
  90             // Add point
  91             cleaned.push_back(*it);
  92
  93             while(cleaned.size() >= 3
  94                && detail::point_is_spike_or_equal(cleaned.back(),
  95                                                   *(cleaned.end() - 3),
  96                                                   *(cleaned.end() - 2),
  97                                                   strategy))
  98             {
  99                 // Remove pen-ultimate point causing the spike (or which was equal)
 100                 cleaned.erase(cleaned.end() - 2);
 101             }
 102         }
 103
 104         // For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent
 105         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
 106         {
 107             cleaned.pop_back();
 108         }
 109
 110         bool found = false;
 111         do
 112         {
 113             found = false;
 114             // Check for spike in first point
 115             int const penultimate = 2;
 116             while(cleaned.size() >= 3
 117                && detail::point_is_spike_or_equal(cleaned.front(),
 118                                                   *(cleaned.end() - penultimate),
 119                                                   cleaned.back(),
 120                                                   strategy))
 121             {
 122                 cleaned.pop_back();
 123                 found = true;
 124             }
 125             // Check for spike in second point
 126             while(cleaned.size() >= 3
 127                && detail::point_is_spike_or_equal(*(cleaned.begin() + 1),
 128                                                   cleaned.back(),
 129                                                   cleaned.front(),
 130                                                   strategy))
 131             {
 132                 cleaned.pop_front();
 133                 found = true;
 134             }
 135         }
 136         while (found);
 137
 138         if (cleaned.size() == 2)
 139         {
 140             // Ticket #9871: open polygon with only two points.
 141             // the second point forms, by definition, a spike
 142             cleaned.pop_back();
 143         }
 144
 145         // Close if necessary
 146         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
 147         {
 148             cleaned.push_back(cleaned.front());
 149         }
 150
 151         // Copy output
 152         geometry::clear(range);
 153         std::copy(cleaned.begin(), cleaned.end(), range::back_inserter(range));
 154     }
 155 };
 156
 157
 158 struct polygon_remove_spikes
 159 {
 160     template <typename Polygon, typename SideStrategy>
 161     static inline void apply(Polygon& polygon, SideStrategy const& strategy)
 162     {
 163         typedef range_remove_spikes per_range;
 164         per_range::apply(exterior_ring(polygon), strategy);
 165
 166         typename interior_return_type<Polygon>::type
 167             rings = interior_rings(polygon);
 168
 169         for (typename detail::interior_iterator<Polygon>::type
 170                 it = boost::begin(rings); it != boost::end(rings); ++it)
 171         {
 172             per_range::apply(*it, strategy);
 173         }
 174     }
 175 };
 176
 177
 178 template <typename SingleVersion>
 179 struct multi_remove_spikes
 180 {
 181     template <typename MultiGeometry, typename SideStrategy>
 182     static inline void apply(MultiGeometry& multi, SideStrategy const& strategy)
 183     {
 184         for (typename boost::range_iterator<MultiGeometry>::type
 185                 it = boost::begin(multi);
 186             it != boost::end(multi);
 187             ++it)
 188         {
 189             SingleVersion::apply(*it, strategy);
 190         }
 191     }
 192 };
 193
 194
 195 }} // namespace detail::remove_spikes
 196 #endif // DOXYGEN_NO_DETAIL
 197
 198
 199
 200 #ifndef DOXYGEN_NO_DISPATCH
 201 namespace dispatch
 202 {
 203
 204
 205 template
 206 <
 207     typename Geometry,
 208     typename Tag = typename tag<Geometry>::type
 209 >
 210 struct remove_spikes
 211 {
 212     template <typename SideStrategy>
 213     static inline void apply(Geometry&, SideStrategy const&)
 214     {}
 215 };
 216
 217
 218 template <typename Ring>
 219 struct remove_spikes<Ring, ring_tag>
 220     : detail::remove_spikes::range_remove_spikes
 221 {};
 222
 223
 224
 225 template <typename Polygon>
 226 struct remove_spikes<Polygon, polygon_tag>
 227     : detail::remove_spikes::polygon_remove_spikes
 228 {};
 229
 230
 231 template <typename MultiPolygon>
 232 struct remove_spikes<MultiPolygon, multi_polygon_tag>
 233     : detail::remove_spikes::multi_remove_spikes
 234         <
 235             detail::remove_spikes::polygon_remove_spikes
 236         >
 237 {};
 238
 239
 240 } // namespace dispatch
 241 #endif
 242
 243
 244 namespace resolve_variant {
 245
 246 template <typename Geometry>
 247 struct remove_spikes
 248 {
 249     template <typename Strategy>
 250     static void apply(Geometry& geometry, Strategy const& strategy)
 251     {
 252         concepts::check<Geometry>();
 253         dispatch::remove_spikes<Geometry>::apply(geometry, strategy);
 254     }
 255
 256     static void apply(Geometry& geometry, geometry::default_strategy const&)
 257     {
 258         typedef typename strategy::side::services::default_strategy
 259             <
 260                 typename cs_tag<Geometry>::type
 261             >::type side_strategy;
 262
 263         apply(geometry, side_strategy());
 264     }
 265 };
 266
 267 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 268 struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 269 {
 270     template <typename Strategy>
 271     struct visitor: boost::static_visitor<void>
 272     {
 273         Strategy const& m_strategy;
 274
 275         visitor(Strategy const& strategy) : m_strategy(strategy) {}
 276
 277         template <typename Geometry>
 278         void operator()(Geometry& geometry) const
 279         {
 280             remove_spikes<Geometry>::apply(geometry, m_strategy);
 281         }
 282     };
 283
 284     template <typename Strategy>
 285     static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry,
 286                              Strategy const& strategy)
 287     {
 288         boost::apply_visitor(visitor<Strategy>(strategy), geometry);
 289     }
 290 };
 291
 292 } // namespace resolve_variant
 293
 294
 295 /*!
 296     \ingroup remove_spikes
 297     \tparam Geometry geometry type
 298     \param geometry the geometry to make remove_spikes
 299 */
 300 template <typename Geometry>
 301 inline void remove_spikes(Geometry& geometry)
 302 {
 303     resolve_variant::remove_spikes<Geometry>::apply(geometry, geometry::default_strategy());
 304 }
 305
 306 /*!
 307     \ingroup remove_spikes
 308     \tparam Geometry geometry type
 309     \tparam Strategy side strategy type
 310     \param geometry the geometry to make remove_spikes
 311     \param strategy the side strategy used by the algorithm
 312 */
 313 template <typename Geometry, typename Strategy>
 314 inline void remove_spikes(Geometry& geometry, Strategy const& strategy)
 315 {
 316     resolve_variant::remove_spikes<Geometry>::apply(geometry, strategy);
 317 }
 318
 319
 320 }} // namespace boost::geometry
 321
 322
 323 #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP