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>
applyboost::geometry::detail::remove_spikes::range_remove_spikes73 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::deque<point_type> cleaned;
88 for (typename boost::range_iterator<Range const>::type it = boost::begin(range);
89 it != boost::end(range); ++it)
90 {
91 // Add point
92 cleaned.push_back(*it);
93
94 while(cleaned.size() >= 3
95 && detail::is_spike_or_equal(range::at(cleaned, cleaned.size() - 3),
96 range::at(cleaned, cleaned.size() - 2),
97 range::back(cleaned),
98 strategy))
99 {
100 // Remove pen-ultimate point causing the spike (or which was equal)
101 cleaned.erase(cleaned.end() - 2);
102 }
103 }
104
105 // For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent
106 if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
107 {
108 cleaned.pop_back();
109 }
110
111 bool found = false;
112 do
113 {
114 found = false;
115 // Check for spike in first point
116 int const penultimate = 2;
117 while(cleaned.size() >= 3
118 && detail::is_spike_or_equal(range::at(cleaned, cleaned.size() - penultimate),
119 range::back(cleaned),
120 range::front(cleaned),
121 strategy))
122 {
123 cleaned.pop_back();
124 found = true;
125 }
126 // Check for spike in second point
127 while(cleaned.size() >= 3
128 && detail::is_spike_or_equal(range::back(cleaned),
129 range::front(cleaned),
130 range::at(cleaned, 1),
131 strategy))
132 {
133 cleaned.pop_front();
134 found = true;
135 }
136 }
137 while (found);
138
139 if (cleaned.size() == 2)
140 {
141 // Ticket #9871: open polygon with only two points.
142 // the second point forms, by definition, a spike
143 cleaned.pop_back();
144 }
145
146 // Close if necessary
147 if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
148 {
149 cleaned.push_back(cleaned.front());
150 }
151
152 // Copy output
153 geometry::clear(range);
154 std::copy(cleaned.begin(), cleaned.end(), range::back_inserter(range));
155 }
156 };
157
158
159 struct polygon_remove_spikes
160 {
161 template <typename Polygon, typename SideStrategy>
applyboost::geometry::detail::remove_spikes::polygon_remove_spikes162 static inline void apply(Polygon& polygon, SideStrategy const& strategy)
163 {
164 typedef range_remove_spikes per_range;
165 per_range::apply(exterior_ring(polygon), strategy);
166
167 typename interior_return_type<Polygon>::type
168 rings = interior_rings(polygon);
169
170 for (typename detail::interior_iterator<Polygon>::type
171 it = boost::begin(rings); it != boost::end(rings); ++it)
172 {
173 per_range::apply(*it, strategy);
174 }
175 }
176 };
177
178
179 template <typename SingleVersion>
180 struct multi_remove_spikes
181 {
182 template <typename MultiGeometry, typename SideStrategy>
applyboost::geometry::detail::remove_spikes::multi_remove_spikes183 static inline void apply(MultiGeometry& multi, SideStrategy const& strategy)
184 {
185 for (typename boost::range_iterator<MultiGeometry>::type
186 it = boost::begin(multi);
187 it != boost::end(multi);
188 ++it)
189 {
190 SingleVersion::apply(*it, strategy);
191 }
192 }
193 };
194
195
196 }} // namespace detail::remove_spikes
197 #endif // DOXYGEN_NO_DETAIL
198
199
200
201 #ifndef DOXYGEN_NO_DISPATCH
202 namespace dispatch
203 {
204
205
206 template
207 <
208 typename Geometry,
209 typename Tag = typename tag<Geometry>::type
210 >
211 struct remove_spikes
212 {
213 template <typename SideStrategy>
applyboost::geometry::dispatch::remove_spikes214 static inline void apply(Geometry&, SideStrategy const&)
215 {}
216 };
217
218
219 template <typename Ring>
220 struct remove_spikes<Ring, ring_tag>
221 : detail::remove_spikes::range_remove_spikes
222 {};
223
224
225
226 template <typename Polygon>
227 struct remove_spikes<Polygon, polygon_tag>
228 : detail::remove_spikes::polygon_remove_spikes
229 {};
230
231
232 template <typename MultiPolygon>
233 struct remove_spikes<MultiPolygon, multi_polygon_tag>
234 : detail::remove_spikes::multi_remove_spikes
235 <
236 detail::remove_spikes::polygon_remove_spikes
237 >
238 {};
239
240
241 } // namespace dispatch
242 #endif
243
244
245 namespace resolve_variant {
246
247 template <typename Geometry>
248 struct remove_spikes
249 {
250 template <typename Strategy>
applyboost::geometry::resolve_variant::remove_spikes251 static void apply(Geometry& geometry, Strategy const& strategy)
252 {
253 concepts::check<Geometry>();
254 dispatch::remove_spikes<Geometry>::apply(geometry, strategy);
255 }
256
applyboost::geometry::resolve_variant::remove_spikes257 static void apply(Geometry& geometry, geometry::default_strategy const&)
258 {
259 typedef typename strategy::side::services::default_strategy
260 <
261 typename cs_tag<Geometry>::type
262 >::type side_strategy;
263
264 apply(geometry, side_strategy());
265 }
266 };
267
268 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
269 struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
270 {
271 template <typename Strategy>
272 struct visitor: boost::static_visitor<void>
273 {
274 Strategy const& m_strategy;
275
visitorboost::geometry::resolve_variant::remove_spikes::visitor276 visitor(Strategy const& strategy) : m_strategy(strategy) {}
277
278 template <typename Geometry>
operator ()boost::geometry::resolve_variant::remove_spikes::visitor279 void operator()(Geometry& geometry) const
280 {
281 remove_spikes<Geometry>::apply(geometry, m_strategy);
282 }
283 };
284
285 template <typename Strategy>
applyboost::geometry::resolve_variant::remove_spikes286 static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry,
287 Strategy const& strategy)
288 {
289 boost::apply_visitor(visitor<Strategy>(strategy), geometry);
290 }
291 };
292
293 } // namespace resolve_variant
294
295
296 /*!
297 \ingroup remove_spikes
298 \tparam Geometry geometry type
299 \param geometry the geometry to make remove_spikes
300 */
301 template <typename Geometry>
remove_spikes(Geometry & geometry)302 inline void remove_spikes(Geometry& geometry)
303 {
304 resolve_variant::remove_spikes<Geometry>::apply(geometry, geometry::default_strategy());
305 }
306
307 /*!
308 \ingroup remove_spikes
309 \tparam Geometry geometry type
310 \tparam Strategy side strategy type
311 \param geometry the geometry to make remove_spikes
312 \param strategy the side strategy used by the algorithm
313 */
314 template <typename Geometry, typename Strategy>
remove_spikes(Geometry & geometry,Strategy const & strategy)315 inline void remove_spikes(Geometry& geometry, Strategy const& strategy)
316 {
317 resolve_variant::remove_spikes<Geometry>::apply(geometry, strategy);
318 }
319
320
321 }} // namespace boost::geometry
322
323
324 #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP
325