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