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 #include <boost/geometry/util/range.hpp>
  46
  47
  48 /*
  49 Remove spikes from a ring/polygon.
  50 Ring (having 8 vertices, including closing vertex)
  51 +------+
  52 |      |
  53 |      +--+
  54 |      |  ^this "spike" is removed, can be located outside/inside the ring
  55 +------+
  56 (the actualy determination if it is removed is done by a strategy)
  57
  58 */
  59
  60
  61 namespace boost { namespace geometry
  62 {
  63
  64
  65 #ifndef DOXYGEN_NO_DETAIL
  66 namespace detail { namespace remove_spikes
  67 {
  68
  69
  70 struct range_remove_spikes
  71 {
  72     template <typename Range, typename SideStrategy>
  73     static inline void apply(Range& range, SideStrategy const& strategy)
  74     {
  75         typedef typename point_type<Range>::type point_type;
  76
  77         std::size_t n = boost::size(range);
  78         std::size_t const min_num_points = core_detail::closure::minimum_ring_size
  79             <
  80                 geometry::closure<Range>::value
  81             >::value - 1; // subtract one: a polygon with only one spike should result into one point
  82         if (n < min_num_points)
  83         {
  84             return;
  85         }
  86
  87         std::vector<point_type> cleaned;
  88         cleaned.reserve(n);
  89
  90         for (typename boost::range_iterator<Range const>::type it = boost::begin(range);
  91             it != boost::end(range); ++it)
  92         {
  93             // Add point
  94             cleaned.push_back(*it);
  95
  96             while(cleaned.size() >= 3
  97                   && detail::is_spike_or_equal(range::at(cleaned, cleaned.size() - 3),
  98                                                range::at(cleaned, cleaned.size() - 2),
  99                                                range::back(cleaned),
 100                                                strategy))
 101             {
 102                 // Remove pen-ultimate point causing the spike (or which was equal)
 103                 cleaned.erase(cleaned.end() - 2);
 104             }
 105         }
 106
 107         typedef typename std::vector<point_type>::iterator cleaned_iterator;
 108         cleaned_iterator cleaned_b = cleaned.begin();
 109         cleaned_iterator cleaned_e = cleaned.end();
 110         std::size_t cleaned_count = cleaned.size();
 111
 112         // For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent
 113         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
 114         {
 115             --cleaned_e;
 116             --cleaned_count;
 117         }
 118
 119         bool found = false;
 120         do
 121         {
 122             found = false;
 123             // Check for spike in first point
 124             while(cleaned_count >= 3
 125                   && detail::is_spike_or_equal(*(cleaned_e - 2), // prev
 126                                                *(cleaned_e - 1), // back
 127                                                *(cleaned_b),     // front
 128                                                strategy))
 129             {
 130                 --cleaned_e;
 131                 --cleaned_count;
 132                 found = true;
 133             }
 134             // Check for spike in second point
 135             while(cleaned_count >= 3
 136                   && detail::is_spike_or_equal(*(cleaned_e - 1), // back
 137                                                *(cleaned_b),     // front
 138                                                *(cleaned_b + 1), // next
 139                                                strategy))
 140             {
 141                 ++cleaned_b;
 142                 --cleaned_count;
 143                 found = true;
 144             }
 145         }
 146         while (found);
 147
 148         if (cleaned_count == 2)
 149         {
 150             // Ticket #9871: open polygon with only two points.
 151             // the second point forms, by definition, a spike
 152             --cleaned_e;
 153             //--cleaned_count;
 154         }
 155
 156         // Close if necessary
 157         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
 158         {
 159             BOOST_GEOMETRY_ASSERT(cleaned_e != cleaned.end());
 160             *cleaned_e = *cleaned_b;
 161             ++cleaned_e;
 162             //++cleaned_count;
 163         }
 164
 165         // Copy output
 166         geometry::clear(range);
 167         std::copy(cleaned_b, cleaned_e, range::back_inserter(range));
 168     }
 169 };
 170
 171
 172 struct polygon_remove_spikes
 173 {
 174     template <typename Polygon, typename SideStrategy>
 175     static inline void apply(Polygon& polygon, SideStrategy const& strategy)
 176     {
 177         typedef range_remove_spikes per_range;
 178         per_range::apply(exterior_ring(polygon), strategy);
 179
 180         typename interior_return_type<Polygon>::type
 181             rings = interior_rings(polygon);
 182
 183         for (typename detail::interior_iterator<Polygon>::type
 184                 it = boost::begin(rings); it != boost::end(rings); ++it)
 185         {
 186             per_range::apply(*it, strategy);
 187         }
 188     }
 189 };
 190
 191
 192 template <typename SingleVersion>
 193 struct multi_remove_spikes
 194 {
 195     template <typename MultiGeometry, typename SideStrategy>
 196     static inline void apply(MultiGeometry& multi, SideStrategy const& strategy)
 197     {
 198         for (typename boost::range_iterator<MultiGeometry>::type
 199                 it = boost::begin(multi);
 200             it != boost::end(multi);
 201             ++it)
 202         {
 203             SingleVersion::apply(*it, strategy);
 204         }
 205     }
 206 };
 207
 208
 209 }} // namespace detail::remove_spikes
 210 #endif // DOXYGEN_NO_DETAIL
 211
 212
 213
 214 #ifndef DOXYGEN_NO_DISPATCH
 215 namespace dispatch
 216 {
 217
 218
 219 template
 220 <
 221     typename Geometry,
 222     typename Tag = typename tag<Geometry>::type
 223 >
 224 struct remove_spikes
 225 {
 226     template <typename SideStrategy>
 227     static inline void apply(Geometry&, SideStrategy const&)
 228     {}
 229 };
 230
 231
 232 template <typename Ring>
 233 struct remove_spikes<Ring, ring_tag>
 234     : detail::remove_spikes::range_remove_spikes
 235 {};
 236
 237
 238
 239 template <typename Polygon>
 240 struct remove_spikes<Polygon, polygon_tag>
 241     : detail::remove_spikes::polygon_remove_spikes
 242 {};
 243
 244
 245 template <typename MultiPolygon>
 246 struct remove_spikes<MultiPolygon, multi_polygon_tag>
 247     : detail::remove_spikes::multi_remove_spikes
 248         <
 249             detail::remove_spikes::polygon_remove_spikes
 250         >
 251 {};
 252
 253
 254 } // namespace dispatch
 255 #endif
 256
 257
 258 namespace resolve_variant {
 259
 260 template <typename Geometry>
 261 struct remove_spikes
 262 {
 263     template <typename Strategy>
 264     static void apply(Geometry& geometry, Strategy const& strategy)
 265     {
 266         concepts::check<Geometry>();
 267         dispatch::remove_spikes<Geometry>::apply(geometry, strategy);
 268     }
 269
 270     static void apply(Geometry& geometry, geometry::default_strategy const&)
 271     {
 272         typedef typename strategy::side::services::default_strategy
 273             <
 274                 typename cs_tag<Geometry>::type
 275             >::type side_strategy;
 276
 277         apply(geometry, side_strategy());
 278     }
 279 };
 280
 281 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 282 struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 283 {
 284     template <typename Strategy>
 285     struct visitor: boost::static_visitor<void>
 286     {
 287         Strategy const& m_strategy;
 288
 289         visitor(Strategy const& strategy) : m_strategy(strategy) {}
 290
 291         template <typename Geometry>
 292         void operator()(Geometry& geometry) const
 293         {
 294             remove_spikes<Geometry>::apply(geometry, m_strategy);
 295         }
 296     };
 297
 298     template <typename Strategy>
 299     static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry,
 300                              Strategy const& strategy)
 301     {
 302         boost::apply_visitor(visitor<Strategy>(strategy), geometry);
 303     }
 304 };
 305
 306 } // namespace resolve_variant
 307
 308
 309 /*!
 310     \ingroup remove_spikes
 311     \tparam Geometry geometry type
 312     \param geometry the geometry to make remove_spikes
 313 */
 314 template <typename Geometry>
 315 inline void remove_spikes(Geometry& geometry)
 316 {
 317     resolve_variant::remove_spikes<Geometry>::apply(geometry, geometry::default_strategy());
 318 }
 319
 320 /*!
 321     \ingroup remove_spikes
 322     \tparam Geometry geometry type
 323     \tparam Strategy side strategy type
 324     \param geometry the geometry to make remove_spikes
 325     \param strategy the side strategy used by the algorithm
 326 */
 327 template <typename Geometry, typename Strategy>
 328 inline void remove_spikes(Geometry& geometry, Strategy const& strategy)
 329 {
 330     resolve_variant::remove_spikes<Geometry>::apply(geometry, strategy);
 331 }
 332
 333
 334 }} // namespace boost::geometry
 335
 336
 337 #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP