]>
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 | ||
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) | |
11 | ||
12 | #ifndef BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP | |
13 | #define BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP | |
14 | ||
15 | #include <deque> | |
16 | ||
17 | #include <boost/range.hpp> | |
18 | #include <boost/type_traits/remove_reference.hpp> | |
19 | ||
20 | #include <boost/variant/apply_visitor.hpp> | |
21 | #include <boost/variant/static_visitor.hpp> | |
22 | #include <boost/variant/variant_fwd.hpp> | |
23 | ||
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> | |
30 | ||
31 | #include <boost/geometry/geometries/concepts/check.hpp> | |
32 | ||
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> | |
36 | ||
37 | #include <boost/geometry/util/condition.hpp> | |
38 | ||
39 | ||
40 | /* | |
41 | Remove spikes from a ring/polygon. | |
42 | Ring (having 8 vertices, including closing vertex) | |
43 | +------+ | |
44 | | | | |
45 | | +--+ | |
46 | | | ^this "spike" is removed, can be located outside/inside the ring | |
47 | +------+ | |
48 | (the actualy determination if it is removed is done by a strategy) | |
49 | ||
50 | */ | |
51 | ||
52 | ||
53 | namespace boost { namespace geometry | |
54 | { | |
55 | ||
56 | ||
57 | #ifndef DOXYGEN_NO_DETAIL | |
58 | namespace detail { namespace remove_spikes | |
59 | { | |
60 | ||
61 | ||
62 | template <typename Range> | |
63 | struct range_remove_spikes | |
64 | { | |
65 | typedef typename strategy::side::services::default_strategy | |
66 | < | |
67 | typename cs_tag<Range>::type | |
68 | >::type side_strategy; | |
69 | ||
70 | typedef typename coordinate_type<Range>::type coordinate_type; | |
71 | typedef typename point_type<Range>::type point_type; | |
72 | ||
73 | ||
74 | static inline void apply(Range& range) | |
75 | { | |
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 | |
94 | && detail::point_is_spike_or_equal(cleaned.back(), *(cleaned.end() - 3), *(cleaned.end() - 2))) | |
95 | { | |
96 | // Remove pen-ultimate point causing the spike (or which was equal) | |
97 | cleaned.erase(cleaned.end() - 2); | |
98 | } | |
99 | } | |
100 | ||
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) ) | |
103 | { | |
104 | cleaned.pop_back(); | |
105 | } | |
106 | ||
107 | bool found = false; | |
108 | do | |
109 | { | |
110 | found = false; | |
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())) | |
114 | { | |
115 | cleaned.pop_back(); | |
116 | found = true; | |
117 | } | |
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())) | |
120 | { | |
121 | cleaned.pop_front(); | |
122 | found = true; | |
123 | } | |
124 | } | |
125 | while (found); | |
126 | ||
127 | if (cleaned.size() == 2) | |
128 | { | |
129 | // Ticket #9871: open polygon with only two points. | |
130 | // the second point forms, by definition, a spike | |
131 | cleaned.pop_back(); | |
132 | } | |
133 | ||
134 | // Close if necessary | |
135 | if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) ) | |
136 | { | |
137 | cleaned.push_back(cleaned.front()); | |
138 | } | |
139 | ||
140 | // Copy output | |
141 | geometry::clear(range); | |
142 | std::copy(cleaned.begin(), cleaned.end(), range::back_inserter(range)); | |
143 | } | |
144 | }; | |
145 | ||
146 | ||
147 | template <typename Polygon> | |
148 | struct polygon_remove_spikes | |
149 | { | |
150 | static inline void apply(Polygon& polygon) | |
151 | { | |
152 | typedef typename geometry::ring_type<Polygon>::type ring_type; | |
153 | ||
154 | typedef range_remove_spikes<ring_type> per_range; | |
155 | per_range::apply(exterior_ring(polygon)); | |
156 | ||
157 | typename interior_return_type<Polygon>::type | |
158 | rings = interior_rings(polygon); | |
159 | ||
160 | for (typename detail::interior_iterator<Polygon>::type | |
161 | it = boost::begin(rings); it != boost::end(rings); ++it) | |
162 | { | |
163 | per_range::apply(*it); | |
164 | } | |
165 | } | |
166 | }; | |
167 | ||
168 | ||
169 | template <typename MultiGeometry, typename SingleVersion> | |
170 | struct multi_remove_spikes | |
171 | { | |
172 | static inline void apply(MultiGeometry& multi) | |
173 | { | |
174 | for (typename boost::range_iterator<MultiGeometry>::type | |
175 | it = boost::begin(multi); | |
176 | it != boost::end(multi); | |
177 | ++it) | |
178 | { | |
179 | SingleVersion::apply(*it); | |
180 | } | |
181 | } | |
182 | }; | |
183 | ||
184 | ||
185 | }} // namespace detail::remove_spikes | |
186 | #endif // DOXYGEN_NO_DETAIL | |
187 | ||
188 | ||
189 | ||
190 | #ifndef DOXYGEN_NO_DISPATCH | |
191 | namespace dispatch | |
192 | { | |
193 | ||
194 | ||
195 | template | |
196 | < | |
197 | typename Geometry, | |
198 | typename Tag = typename tag<Geometry>::type | |
199 | > | |
200 | struct remove_spikes | |
201 | { | |
202 | static inline void apply(Geometry&) | |
203 | {} | |
204 | }; | |
205 | ||
206 | ||
207 | template <typename Ring> | |
208 | struct remove_spikes<Ring, ring_tag> | |
209 | : detail::remove_spikes::range_remove_spikes<Ring> | |
210 | {}; | |
211 | ||
212 | ||
213 | ||
214 | template <typename Polygon> | |
215 | struct remove_spikes<Polygon, polygon_tag> | |
216 | : detail::remove_spikes::polygon_remove_spikes<Polygon> | |
217 | {}; | |
218 | ||
219 | ||
220 | template <typename MultiPolygon> | |
221 | struct remove_spikes<MultiPolygon, multi_polygon_tag> | |
222 | : detail::remove_spikes::multi_remove_spikes | |
223 | < | |
224 | MultiPolygon, | |
225 | detail::remove_spikes::polygon_remove_spikes | |
226 | < | |
227 | typename boost::range_value<MultiPolygon>::type | |
228 | > | |
229 | > | |
230 | {}; | |
231 | ||
232 | ||
233 | } // namespace dispatch | |
234 | #endif | |
235 | ||
236 | ||
237 | namespace resolve_variant { | |
238 | ||
239 | template <typename Geometry> | |
240 | struct remove_spikes | |
241 | { | |
242 | static void apply(Geometry& geometry) | |
243 | { | |
244 | concepts::check<Geometry>(); | |
245 | dispatch::remove_spikes<Geometry>::apply(geometry); | |
246 | } | |
247 | }; | |
248 | ||
249 | template <BOOST_VARIANT_ENUM_PARAMS(typename T)> | |
250 | struct remove_spikes<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > | |
251 | { | |
252 | struct visitor: boost::static_visitor<void> | |
253 | { | |
254 | template <typename Geometry> | |
255 | void operator()(Geometry& geometry) const | |
256 | { | |
257 | remove_spikes<Geometry>::apply(geometry); | |
258 | } | |
259 | }; | |
260 | ||
261 | static inline void apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry) | |
262 | { | |
263 | boost::apply_visitor(visitor(), geometry); | |
264 | } | |
265 | }; | |
266 | ||
267 | } // namespace resolve_variant | |
268 | ||
269 | ||
270 | /*! | |
271 | \ingroup remove_spikes | |
272 | \tparam Geometry geometry type | |
273 | \param geometry the geometry to make remove_spikes | |
274 | */ | |
275 | template <typename Geometry> | |
276 | inline void remove_spikes(Geometry& geometry) | |
277 | { | |
278 | resolve_variant::remove_spikes<Geometry>::apply(geometry); | |
279 | } | |
280 | ||
281 | ||
282 | }} // namespace boost::geometry | |
283 | ||
284 | ||
285 | #endif // BOOST_GEOMETRY_ALGORITHMS_REMOVE_SPIKES_HPP |