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 // This file was modified by Oracle on 2017.
9 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
17 #ifndef BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
18 #define BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
22 #include <boost/range.hpp>
23 #include <boost/type_traits/remove_reference.hpp>
25 #include <boost/variant/apply_visitor.hpp>
26 #include <boost/variant/static_visitor.hpp>
27 #include <boost/variant/variant_fwd.hpp>
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>
36 #include <boost/geometry/geometries/concepts/check.hpp>
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>
42 #include <boost/geometry/strategies/default_strategy.hpp>
44 #include <boost/geometry/util/condition.hpp>
45 #include <boost/geometry/util/range.hpp>
49 Remove spikes from a ring/polygon.
50 Ring (having 8 vertices, including closing vertex)
54 | | ^this "spike" is removed, can be located outside/inside the ring
56 (the actualy determination if it is removed is done by a strategy)
61 namespace boost { namespace geometry
65 #ifndef DOXYGEN_NO_DETAIL
66 namespace detail { namespace remove_spikes
70 struct range_remove_spikes
72 template <typename Range, typename SideStrategy>
73 static inline void apply(Range& range, SideStrategy const& strategy)
75 typedef typename point_type<Range>::type point_type;
77 std::size_t n = boost::size(range);
78 std::size_t const min_num_points = core_detail::closure::minimum_ring_size
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)
87 std::vector<point_type> cleaned;
90 for (typename boost::range_iterator<Range const>::type it = boost::begin(range);
91 it != boost::end(range); ++it)
94 cleaned.push_back(*it);
96 while(cleaned.size() >= 3
97 && detail::is_spike_or_equal(range::at(cleaned, cleaned.size() - 3),
98 range::at(cleaned, cleaned.size() - 2),
102 // Remove pen-ultimate point causing the spike (or which was equal)
103 cleaned.erase(cleaned.end() - 2);
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();
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) )
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
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
148 if (cleaned_count == 2)
150 // Ticket #9871: open polygon with only two points.
151 // the second point forms, by definition, a spike
156 // Close if necessary
157 if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
159 BOOST_GEOMETRY_ASSERT(cleaned_e != cleaned.end());
160 *cleaned_e = *cleaned_b;
166 geometry::clear(range);
167 std::copy(cleaned_b, cleaned_e, range::back_inserter(range));
172 struct polygon_remove_spikes
174 template <typename Polygon, typename SideStrategy>
175 static inline void apply(Polygon& polygon, SideStrategy const& strategy)
177 typedef range_remove_spikes per_range;
178 per_range::apply(exterior_ring(polygon), strategy);
180 typename interior_return_type<Polygon>::type
181 rings = interior_rings(polygon);
183 for (typename detail::interior_iterator<Polygon>::type
184 it = boost::begin(rings); it != boost::end(rings); ++it)
186 per_range::apply(*it, strategy);
192 template <typename SingleVersion>
193 struct multi_remove_spikes
195 template <typename MultiGeometry, typename SideStrategy>
196 static inline void apply(MultiGeometry& multi, SideStrategy const& strategy)
198 for (typename boost::range_iterator<MultiGeometry>::type
199 it = boost::begin(multi);
200 it != boost::end(multi);
203 SingleVersion::apply(*it, strategy);
209 }} // namespace detail::remove_spikes
210 #endif // DOXYGEN_NO_DETAIL
214 #ifndef DOXYGEN_NO_DISPATCH
222 typename Tag = typename tag<Geometry>::type
226 template <typename SideStrategy>
227 static inline void apply(Geometry&, SideStrategy const&)
232 template <typename Ring>
233 struct remove_spikes<Ring, ring_tag>
234 : detail::remove_spikes::range_remove_spikes
239 template <typename Polygon>
240 struct remove_spikes<Polygon, polygon_tag>
241 : detail::remove_spikes::polygon_remove_spikes
245 template <typename MultiPolygon>
246 struct remove_spikes<MultiPolygon, multi_polygon_tag>
247 : detail::remove_spikes::multi_remove_spikes
249 detail::remove_spikes::polygon_remove_spikes
254 } // namespace dispatch
258 namespace resolve_variant {
260 template <typename Geometry>
263 template <typename Strategy>
264 static void apply(Geometry& geometry, Strategy const& strategy)
266 concepts::check<Geometry>();
267 dispatch::remove_spikes<Geometry>::apply(geometry, strategy);
270 static void apply(Geometry& geometry, geometry::default_strategy const&)
272 typedef typename strategy::side::services::default_strategy
274 typename cs_tag<Geometry>::type
275 >::type side_strategy;
277 apply(geometry, side_strategy());
281 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
282 struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
284 template <typename Strategy>
285 struct visitor: boost::static_visitor<void>
287 Strategy const& m_strategy;
289 visitor(Strategy const& strategy) : m_strategy(strategy) {}
291 template <typename Geometry>
292 void operator()(Geometry& geometry) const
294 remove_spikes<Geometry>::apply(geometry, m_strategy);
298 template <typename Strategy>
299 static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry,
300 Strategy const& strategy)
302 boost::apply_visitor(visitor<Strategy>(strategy), geometry);
306 } // namespace resolve_variant
310 \ingroup remove_spikes
311 \tparam Geometry geometry type
312 \param geometry the geometry to make remove_spikes
314 template <typename Geometry>
315 inline void remove_spikes(Geometry& geometry)
317 resolve_variant::remove_spikes<Geometry>::apply(geometry, geometry::default_strategy());
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
327 template <typename Geometry, typename Strategy>
328 inline void remove_spikes(Geometry& geometry, Strategy const& strategy)
330 resolve_variant::remove_spikes<Geometry>::apply(geometry, strategy);
334 }} // namespace boost::geometry
337 #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP