1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
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)
12 #ifndef BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
13 #define BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
17 #include <boost/range.hpp>
18 #include <boost/type_traits/remove_reference.hpp>
20 #include <boost/variant/apply_visitor.hpp>
21 #include <boost/variant/static_visitor.hpp>
22 #include <boost/variant/variant_fwd.hpp>
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>
31 #include <boost/geometry/geometries/concepts/check.hpp>
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>
37 #include <boost/geometry/util/condition.hpp>
41 Remove spikes from a ring/polygon.
42 Ring (having 8 vertices, including closing vertex)
46 | | ^this "spike" is removed, can be located outside/inside the ring
48 (the actualy determination if it is removed is done by a strategy)
53 namespace boost { namespace geometry
57 #ifndef DOXYGEN_NO_DETAIL
58 namespace detail { namespace remove_spikes
62 template <typename Range>
63 struct range_remove_spikes
65 typedef typename strategy::side::services::default_strategy
67 typename cs_tag<Range>::type
68 >::type side_strategy;
70 typedef typename coordinate_type<Range>::type coordinate_type;
71 typedef typename point_type<Range>::type point_type;
74 static inline void apply(Range& range)
76 std::size_t n = boost::size(range);
77 std::size_t const min_num_points = core_detail::closure::minimum_ring_size
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)
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)
91 cleaned.push_back(*it);
93 while(cleaned.size() >= 3
94 && detail::point_is_spike_or_equal(cleaned.back(), *(cleaned.end() - 3), *(cleaned.end() - 2)))
96 // Remove pen-ultimate point causing the spike (or which was equal)
97 cleaned.erase(cleaned.end() - 2);
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) )
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()))
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()))
127 if (cleaned.size() == 2)
129 // Ticket #9871: open polygon with only two points.
130 // the second point forms, by definition, a spike
134 // Close if necessary
135 if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
137 cleaned.push_back(cleaned.front());
141 geometry::clear(range);
142 std::copy(cleaned.begin(), cleaned.end(), range::back_inserter(range));
147 template <typename Polygon>
148 struct polygon_remove_spikes
150 static inline void apply(Polygon& polygon)
152 typedef typename geometry::ring_type<Polygon>::type ring_type;
154 typedef range_remove_spikes<ring_type> per_range;
155 per_range::apply(exterior_ring(polygon));
157 typename interior_return_type<Polygon>::type
158 rings = interior_rings(polygon);
160 for (typename detail::interior_iterator<Polygon>::type
161 it = boost::begin(rings); it != boost::end(rings); ++it)
163 per_range::apply(*it);
169 template <typename MultiGeometry, typename SingleVersion>
170 struct multi_remove_spikes
172 static inline void apply(MultiGeometry& multi)
174 for (typename boost::range_iterator<MultiGeometry>::type
175 it = boost::begin(multi);
176 it != boost::end(multi);
179 SingleVersion::apply(*it);
185 }} // namespace detail::remove_spikes
186 #endif // DOXYGEN_NO_DETAIL
190 #ifndef DOXYGEN_NO_DISPATCH
198 typename Tag = typename tag<Geometry>::type
202 static inline void apply(Geometry&)
207 template <typename Ring>
208 struct remove_spikes<Ring, ring_tag>
209 : detail::remove_spikes::range_remove_spikes<Ring>
214 template <typename Polygon>
215 struct remove_spikes<Polygon, polygon_tag>
216 : detail::remove_spikes::polygon_remove_spikes<Polygon>
220 template <typename MultiPolygon>
221 struct remove_spikes<MultiPolygon, multi_polygon_tag>
222 : detail::remove_spikes::multi_remove_spikes
225 detail::remove_spikes::polygon_remove_spikes
227 typename boost::range_value<MultiPolygon>::type
233 } // namespace dispatch
237 namespace resolve_variant {
239 template <typename Geometry>
242 static void apply(Geometry& geometry)
244 concepts::check<Geometry>();
245 dispatch::remove_spikes<Geometry>::apply(geometry);
249 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
250 struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
252 struct visitor: boost::static_visitor<void>
254 template <typename Geometry>
255 void operator()(Geometry& geometry) const
257 remove_spikes<Geometry>::apply(geometry);
261 static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry)
263 boost::apply_visitor(visitor(), geometry);
267 } // namespace resolve_variant
271 \ingroup remove_spikes
272 \tparam Geometry geometry type
273 \param geometry the geometry to make remove_spikes
275 template <typename Geometry>
276 inline void remove_spikes(Geometry& geometry)
278 resolve_variant::remove_spikes<Geometry>::apply(geometry);
282 }} // namespace boost::geometry
285 #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP