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