]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
20effc67 TL |
8 | // This file was modified by Oracle on 2017-2020. |
9 | // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates. | |
b32b8144 FG |
10 | |
11 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
12 | ||
7c673cae FG |
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 | ||
20effc67 TL |
22 | #include <boost/range/begin.hpp> |
23 | #include <boost/range/end.hpp> | |
24 | #include <boost/range/size.hpp> | |
7c673cae FG |
25 | |
26 | #include <boost/variant/apply_visitor.hpp> | |
27 | #include <boost/variant/static_visitor.hpp> | |
28 | #include <boost/variant/variant_fwd.hpp> | |
29 | ||
30 | #include <boost/geometry/core/closure.hpp> | |
31 | #include <boost/geometry/core/coordinate_type.hpp> | |
32 | #include <boost/geometry/core/cs.hpp> | |
33 | #include <boost/geometry/core/interior_rings.hpp> | |
34 | #include <boost/geometry/core/point_order.hpp> | |
35 | #include <boost/geometry/core/tags.hpp> | |
36 | ||
37 | #include <boost/geometry/geometries/concepts/check.hpp> | |
38 | ||
39 | #include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp> | |
40 | #include <boost/geometry/algorithms/detail/interior_iterator.hpp> | |
41 | #include <boost/geometry/algorithms/clear.hpp> | |
42 | ||
b32b8144 FG |
43 | #include <boost/geometry/strategies/default_strategy.hpp> |
44 | ||
7c673cae | 45 | #include <boost/geometry/util/condition.hpp> |
92f5a8d4 | 46 | #include <boost/geometry/util/range.hpp> |
7c673cae FG |
47 | |
48 | ||
49 | /* | |
50 | Remove spikes from a ring/polygon. | |
51 | Ring (having 8 vertices, including closing vertex) | |
52 | +------+ | |
53 | | | | |
54 | | +--+ | |
55 | | | ^this "spike" is removed, can be located outside/inside the ring | |
56 | +------+ | |
57 | (the actualy determination if it is removed is done by a strategy) | |
58 | ||
59 | */ | |
60 | ||
61 | ||
62 | namespace boost { namespace geometry | |
63 | { | |
64 | ||
65 | ||
66 | #ifndef DOXYGEN_NO_DETAIL | |
67 | namespace detail { namespace remove_spikes | |
68 | { | |
69 | ||
70 | ||
7c673cae FG |
71 | struct range_remove_spikes |
72 | { | |
b32b8144 FG |
73 | template <typename Range, typename SideStrategy> |
74 | static inline void apply(Range& range, SideStrategy const& strategy) | |
7c673cae | 75 | { |
b32b8144 FG |
76 | typedef typename point_type<Range>::type point_type; |
77 | ||
7c673cae FG |
78 | std::size_t n = boost::size(range); |
79 | std::size_t const min_num_points = core_detail::closure::minimum_ring_size | |
80 | < | |
81 | geometry::closure<Range>::value | |
82 | >::value - 1; // subtract one: a polygon with only one spike should result into one point | |
83 | if (n < min_num_points) | |
84 | { | |
85 | return; | |
86 | } | |
87 | ||
92f5a8d4 TL |
88 | std::vector<point_type> cleaned; |
89 | cleaned.reserve(n); | |
90 | ||
7c673cae FG |
91 | for (typename boost::range_iterator<Range const>::type it = boost::begin(range); |
92 | it != boost::end(range); ++it) | |
93 | { | |
94 | // Add point | |
95 | cleaned.push_back(*it); | |
96 | ||
97 | while(cleaned.size() >= 3 | |
92f5a8d4 TL |
98 | && detail::is_spike_or_equal(range::at(cleaned, cleaned.size() - 3), |
99 | range::at(cleaned, cleaned.size() - 2), | |
100 | range::back(cleaned), | |
101 | strategy)) | |
7c673cae FG |
102 | { |
103 | // Remove pen-ultimate point causing the spike (or which was equal) | |
104 | cleaned.erase(cleaned.end() - 2); | |
105 | } | |
106 | } | |
107 | ||
92f5a8d4 TL |
108 | typedef typename std::vector<point_type>::iterator cleaned_iterator; |
109 | cleaned_iterator cleaned_b = cleaned.begin(); | |
110 | cleaned_iterator cleaned_e = cleaned.end(); | |
111 | std::size_t cleaned_count = cleaned.size(); | |
112 | ||
7c673cae FG |
113 | // For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent |
114 | if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) ) | |
115 | { | |
92f5a8d4 TL |
116 | --cleaned_e; |
117 | --cleaned_count; | |
7c673cae FG |
118 | } |
119 | ||
120 | bool found = false; | |
121 | do | |
122 | { | |
123 | found = false; | |
124 | // Check for spike in first point | |
92f5a8d4 TL |
125 | while(cleaned_count >= 3 |
126 | && detail::is_spike_or_equal(*(cleaned_e - 2), // prev | |
127 | *(cleaned_e - 1), // back | |
128 | *(cleaned_b), // front | |
129 | strategy)) | |
7c673cae | 130 | { |
92f5a8d4 TL |
131 | --cleaned_e; |
132 | --cleaned_count; | |
7c673cae FG |
133 | found = true; |
134 | } | |
135 | // Check for spike in second point | |
92f5a8d4 TL |
136 | while(cleaned_count >= 3 |
137 | && detail::is_spike_or_equal(*(cleaned_e - 1), // back | |
138 | *(cleaned_b), // front | |
139 | *(cleaned_b + 1), // next | |
140 | strategy)) | |
7c673cae | 141 | { |
92f5a8d4 TL |
142 | ++cleaned_b; |
143 | --cleaned_count; | |
7c673cae FG |
144 | found = true; |
145 | } | |
146 | } | |
147 | while (found); | |
148 | ||
92f5a8d4 | 149 | if (cleaned_count == 2) |
7c673cae FG |
150 | { |
151 | // Ticket #9871: open polygon with only two points. | |
152 | // the second point forms, by definition, a spike | |
92f5a8d4 TL |
153 | --cleaned_e; |
154 | //--cleaned_count; | |
7c673cae FG |
155 | } |
156 | ||
157 | // Close if necessary | |
158 | if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) ) | |
159 | { | |
92f5a8d4 TL |
160 | BOOST_GEOMETRY_ASSERT(cleaned_e != cleaned.end()); |
161 | *cleaned_e = *cleaned_b; | |
162 | ++cleaned_e; | |
163 | //++cleaned_count; | |
7c673cae FG |
164 | } |
165 | ||
166 | // Copy output | |
167 | geometry::clear(range); | |
92f5a8d4 | 168 | std::copy(cleaned_b, cleaned_e, range::back_inserter(range)); |
7c673cae FG |
169 | } |
170 | }; | |
171 | ||
172 | ||
7c673cae FG |
173 | struct polygon_remove_spikes |
174 | { | |
b32b8144 FG |
175 | template <typename Polygon, typename SideStrategy> |
176 | static inline void apply(Polygon& polygon, SideStrategy const& strategy) | |
7c673cae | 177 | { |
b32b8144 FG |
178 | typedef range_remove_spikes per_range; |
179 | per_range::apply(exterior_ring(polygon), strategy); | |
7c673cae FG |
180 | |
181 | typename interior_return_type<Polygon>::type | |
182 | rings = interior_rings(polygon); | |
183 | ||
184 | for (typename detail::interior_iterator<Polygon>::type | |
185 | it = boost::begin(rings); it != boost::end(rings); ++it) | |
186 | { | |
b32b8144 | 187 | per_range::apply(*it, strategy); |
7c673cae FG |
188 | } |
189 | } | |
190 | }; | |
191 | ||
192 | ||
b32b8144 | 193 | template <typename SingleVersion> |
7c673cae FG |
194 | struct multi_remove_spikes |
195 | { | |
b32b8144 FG |
196 | template <typename MultiGeometry, typename SideStrategy> |
197 | static inline void apply(MultiGeometry& multi, SideStrategy const& strategy) | |
7c673cae FG |
198 | { |
199 | for (typename boost::range_iterator<MultiGeometry>::type | |
200 | it = boost::begin(multi); | |
201 | it != boost::end(multi); | |
202 | ++it) | |
203 | { | |
b32b8144 | 204 | SingleVersion::apply(*it, strategy); |
7c673cae FG |
205 | } |
206 | } | |
207 | }; | |
208 | ||
209 | ||
210 | }} // namespace detail::remove_spikes | |
211 | #endif // DOXYGEN_NO_DETAIL | |
212 | ||
213 | ||
214 | ||
215 | #ifndef DOXYGEN_NO_DISPATCH | |
216 | namespace dispatch | |
217 | { | |
218 | ||
219 | ||
220 | template | |
221 | < | |
222 | typename Geometry, | |
223 | typename Tag = typename tag<Geometry>::type | |
224 | > | |
225 | struct remove_spikes | |
226 | { | |
b32b8144 FG |
227 | template <typename SideStrategy> |
228 | static inline void apply(Geometry&, SideStrategy const&) | |
7c673cae FG |
229 | {} |
230 | }; | |
231 | ||
232 | ||
233 | template <typename Ring> | |
234 | struct remove_spikes<Ring, ring_tag> | |
b32b8144 | 235 | : detail::remove_spikes::range_remove_spikes |
7c673cae FG |
236 | {}; |
237 | ||
238 | ||
239 | ||
240 | template <typename Polygon> | |
241 | struct remove_spikes<Polygon, polygon_tag> | |
b32b8144 | 242 | : detail::remove_spikes::polygon_remove_spikes |
7c673cae FG |
243 | {}; |
244 | ||
245 | ||
246 | template <typename MultiPolygon> | |
247 | struct remove_spikes<MultiPolygon, multi_polygon_tag> | |
248 | : detail::remove_spikes::multi_remove_spikes | |
249 | < | |
7c673cae | 250 | detail::remove_spikes::polygon_remove_spikes |
7c673cae FG |
251 | > |
252 | {}; | |
253 | ||
254 | ||
255 | } // namespace dispatch | |
256 | #endif | |
257 | ||
258 | ||
259 | namespace resolve_variant { | |
260 | ||
261 | template <typename Geometry> | |
262 | struct remove_spikes | |
263 | { | |
b32b8144 FG |
264 | template <typename Strategy> |
265 | static void apply(Geometry& geometry, Strategy const& strategy) | |
7c673cae FG |
266 | { |
267 | concepts::check<Geometry>(); | |
b32b8144 FG |
268 | dispatch::remove_spikes<Geometry>::apply(geometry, strategy); |
269 | } | |
270 | ||
271 | static void apply(Geometry& geometry, geometry::default_strategy const&) | |
272 | { | |
273 | typedef typename strategy::side::services::default_strategy | |
274 | < | |
275 | typename cs_tag<Geometry>::type | |
276 | >::type side_strategy; | |
277 | ||
278 | apply(geometry, side_strategy()); | |
7c673cae FG |
279 | } |
280 | }; | |
281 | ||
282 | template <BOOST_VARIANT_ENUM_PARAMS(typename T)> | |
283 | struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > | |
284 | { | |
b32b8144 | 285 | template <typename Strategy> |
7c673cae FG |
286 | struct visitor: boost::static_visitor<void> |
287 | { | |
b32b8144 FG |
288 | Strategy const& m_strategy; |
289 | ||
290 | visitor(Strategy const& strategy) : m_strategy(strategy) {} | |
291 | ||
7c673cae FG |
292 | template <typename Geometry> |
293 | void operator()(Geometry& geometry) const | |
294 | { | |
b32b8144 | 295 | remove_spikes<Geometry>::apply(geometry, m_strategy); |
7c673cae FG |
296 | } |
297 | }; | |
298 | ||
b32b8144 FG |
299 | template <typename Strategy> |
300 | static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry, | |
301 | Strategy const& strategy) | |
7c673cae | 302 | { |
b32b8144 | 303 | boost::apply_visitor(visitor<Strategy>(strategy), geometry); |
7c673cae FG |
304 | } |
305 | }; | |
306 | ||
307 | } // namespace resolve_variant | |
308 | ||
309 | ||
310 | /*! | |
311 | \ingroup remove_spikes | |
312 | \tparam Geometry geometry type | |
313 | \param geometry the geometry to make remove_spikes | |
314 | */ | |
315 | template <typename Geometry> | |
316 | inline void remove_spikes(Geometry& geometry) | |
317 | { | |
b32b8144 FG |
318 | resolve_variant::remove_spikes<Geometry>::apply(geometry, geometry::default_strategy()); |
319 | } | |
320 | ||
321 | /*! | |
322 | \ingroup remove_spikes | |
323 | \tparam Geometry geometry type | |
324 | \tparam Strategy side strategy type | |
325 | \param geometry the geometry to make remove_spikes | |
326 | \param strategy the side strategy used by the algorithm | |
327 | */ | |
328 | template <typename Geometry, typename Strategy> | |
329 | inline void remove_spikes(Geometry& geometry, Strategy const& strategy) | |
330 | { | |
331 | resolve_variant::remove_spikes<Geometry>::apply(geometry, strategy); | |
7c673cae FG |
332 | } |
333 | ||
334 | ||
335 | }} // namespace boost::geometry | |
336 | ||
337 | ||
338 | #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP |