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