]>
Commit | Line | Data |
---|---|---|
11fdf7f2 TL |
1 | // Boost.Geometry |
2 | ||
3 | // Copyright (c) 2017-2018, Oracle and/or its affiliates. | |
4 | ||
5 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
6 | ||
7 | // Licensed under the Boost Software License version 1.0. | |
8 | // http://www.boost.org/users/license.html | |
9 | ||
10 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DENSIFY_HPP | |
11 | #define BOOST_GEOMETRY_ALGORITHMS_DENSIFY_HPP | |
12 | ||
13 | ||
14 | #include <boost/geometry/algorithms/clear.hpp> | |
15 | #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp> | |
16 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
17 | #include <boost/geometry/core/closure.hpp> | |
92f5a8d4 | 18 | #include <boost/geometry/core/cs.hpp> |
11fdf7f2 TL |
19 | #include <boost/geometry/core/exception.hpp> |
20 | #include <boost/geometry/core/point_type.hpp> | |
21 | #include <boost/geometry/core/tag.hpp> | |
22 | #include <boost/geometry/core/tags.hpp> | |
23 | #include <boost/geometry/strategies/default_strategy.hpp> | |
24 | #include <boost/geometry/strategies/densify.hpp> | |
25 | #include <boost/geometry/util/condition.hpp> | |
26 | #include <boost/geometry/util/range.hpp> | |
27 | ||
28 | #include <boost/range/size.hpp> | |
29 | #include <boost/range/value_type.hpp> | |
30 | ||
31 | #include <boost/throw_exception.hpp> | |
32 | ||
33 | ||
34 | namespace boost { namespace geometry | |
35 | { | |
36 | ||
37 | ||
38 | #ifndef DOXYGEN_NO_DETAIL | |
39 | namespace detail { namespace densify | |
40 | { | |
41 | ||
42 | template <typename Range> | |
43 | struct push_back_policy | |
44 | { | |
45 | typedef typename boost::range_value<Range>::type point_type; | |
46 | ||
47 | inline explicit push_back_policy(Range & rng) | |
48 | : m_rng(rng) | |
49 | {} | |
50 | ||
51 | inline void apply(point_type const& p) | |
52 | { | |
53 | range::push_back(m_rng, p); | |
54 | } | |
55 | ||
56 | private: | |
57 | Range & m_rng; | |
58 | }; | |
59 | ||
60 | template <typename Range, typename Point> | |
61 | inline void convert_and_push_back(Range & range, Point const& p) | |
62 | { | |
63 | typename boost::range_value<Range>::type p2; | |
64 | geometry::detail::conversion::convert_point_to_point(p, p2); | |
65 | range::push_back(range, p2); | |
66 | } | |
67 | ||
68 | template <bool AppendLastPoint = true> | |
69 | struct densify_range | |
70 | { | |
71 | template <typename FwdRng, typename MutRng, typename T, typename Strategy> | |
72 | static inline void apply(FwdRng const& rng, MutRng & rng_out, | |
73 | T const& len, Strategy const& strategy) | |
74 | { | |
75 | typedef typename boost::range_iterator<FwdRng const>::type iterator_t; | |
76 | typedef typename boost::range_value<FwdRng>::type point_t; | |
77 | ||
78 | iterator_t it = boost::begin(rng); | |
79 | iterator_t end = boost::end(rng); | |
80 | ||
81 | if (it == end) // empty(rng) | |
82 | { | |
83 | return; | |
84 | } | |
85 | ||
86 | push_back_policy<MutRng> policy(rng_out); | |
87 | ||
88 | iterator_t prev = it; | |
89 | for ( ++it ; it != end ; prev = it++) | |
90 | { | |
91 | point_t const& p0 = *prev; | |
92 | point_t const& p1 = *it; | |
93 | ||
94 | convert_and_push_back(rng_out, p0); | |
95 | ||
96 | strategy.apply(p0, p1, policy, len); | |
97 | } | |
98 | ||
99 | if (BOOST_GEOMETRY_CONDITION(AppendLastPoint)) | |
100 | { | |
101 | convert_and_push_back(rng_out, *prev); // back(rng) | |
102 | } | |
103 | } | |
104 | }; | |
105 | ||
106 | template <bool IsClosed1, bool IsClosed2> // false, X | |
107 | struct densify_ring | |
108 | { | |
109 | template <typename Geometry, typename GeometryOut, typename T, typename Strategy> | |
110 | static inline void apply(Geometry const& ring, GeometryOut & ring_out, | |
111 | T const& len, Strategy const& strategy) | |
112 | { | |
113 | geometry::detail::densify::densify_range<true> | |
114 | ::apply(ring, ring_out, len, strategy); | |
115 | ||
116 | if (boost::size(ring) <= 1) | |
117 | return; | |
118 | ||
119 | typedef typename point_type<Geometry>::type point_t; | |
120 | point_t const& p0 = range::back(ring); | |
121 | point_t const& p1 = range::front(ring); | |
122 | ||
123 | push_back_policy<GeometryOut> policy(ring_out); | |
124 | ||
125 | strategy.apply(p0, p1, policy, len); | |
126 | ||
127 | if (BOOST_GEOMETRY_CONDITION(IsClosed2)) | |
128 | { | |
129 | convert_and_push_back(ring_out, p1); | |
130 | } | |
131 | } | |
132 | }; | |
133 | ||
134 | template <> | |
135 | struct densify_ring<true, true> | |
136 | : densify_range<true> | |
137 | {}; | |
138 | ||
139 | template <> | |
140 | struct densify_ring<true, false> | |
141 | : densify_range<false> | |
142 | {}; | |
143 | ||
144 | ||
145 | }} // namespace detail::densify | |
146 | #endif // DOXYGEN_NO_DETAIL | |
147 | ||
148 | ||
149 | #ifndef DOXYGEN_NO_DISPATCH | |
150 | namespace dispatch | |
151 | { | |
152 | ||
153 | ||
154 | template | |
155 | < | |
156 | typename Geometry, | |
157 | typename GeometryOut, | |
158 | typename Tag1 = typename tag<Geometry>::type, | |
159 | typename Tag2 = typename tag<GeometryOut>::type | |
160 | > | |
161 | struct densify | |
162 | : not_implemented<Tag1, Tag2> | |
163 | {}; | |
164 | ||
165 | template <typename Geometry, typename GeometryOut> | |
166 | struct densify<Geometry, GeometryOut, linestring_tag, linestring_tag> | |
167 | : geometry::detail::densify::densify_range<> | |
168 | {}; | |
169 | ||
170 | template <typename Geometry, typename GeometryOut> | |
171 | struct densify<Geometry, GeometryOut, multi_linestring_tag, multi_linestring_tag> | |
172 | { | |
173 | template <typename T, typename Strategy> | |
174 | static void apply(Geometry const& mls, GeometryOut & mls_out, | |
175 | T const& len, Strategy const& strategy) | |
176 | { | |
177 | std::size_t count = boost::size(mls); | |
178 | range::resize(mls_out, count); | |
179 | ||
180 | for (std::size_t i = 0 ; i < count ; ++i) | |
181 | { | |
182 | geometry::detail::densify::densify_range<> | |
183 | ::apply(range::at(mls, i), range::at(mls_out, i), | |
184 | len, strategy); | |
185 | } | |
186 | } | |
187 | }; | |
188 | ||
189 | template <typename Geometry, typename GeometryOut> | |
190 | struct densify<Geometry, GeometryOut, ring_tag, ring_tag> | |
191 | : geometry::detail::densify::densify_ring | |
192 | < | |
193 | geometry::closure<Geometry>::value != geometry::open, | |
194 | geometry::closure<GeometryOut>::value != geometry::open | |
195 | > | |
196 | {}; | |
197 | ||
198 | template <typename Geometry, typename GeometryOut> | |
199 | struct densify<Geometry, GeometryOut, polygon_tag, polygon_tag> | |
200 | { | |
201 | template <typename T, typename Strategy> | |
202 | static void apply(Geometry const& poly, GeometryOut & poly_out, | |
203 | T const& len, Strategy const& strategy) | |
204 | { | |
205 | apply_ring(exterior_ring(poly), exterior_ring(poly_out), | |
206 | len, strategy); | |
207 | ||
208 | std::size_t count = boost::size(interior_rings(poly)); | |
209 | range::resize(interior_rings(poly_out), count); | |
210 | ||
211 | for (std::size_t i = 0 ; i < count ; ++i) | |
212 | { | |
213 | apply_ring(range::at(interior_rings(poly), i), | |
214 | range::at(interior_rings(poly_out), i), | |
215 | len, strategy); | |
216 | } | |
217 | } | |
218 | ||
219 | template <typename Ring, typename RingOut, typename T, typename Strategy> | |
220 | static void apply_ring(Ring const& ring, RingOut & ring_out, | |
221 | T const& len, Strategy const& strategy) | |
222 | { | |
223 | densify<Ring, RingOut, ring_tag, ring_tag> | |
224 | ::apply(ring, ring_out, len, strategy); | |
225 | } | |
226 | }; | |
227 | ||
228 | template <typename Geometry, typename GeometryOut> | |
229 | struct densify<Geometry, GeometryOut, multi_polygon_tag, multi_polygon_tag> | |
230 | { | |
231 | template <typename T, typename Strategy> | |
232 | static void apply(Geometry const& mpoly, GeometryOut & mpoly_out, | |
233 | T const& len, Strategy const& strategy) | |
234 | { | |
235 | std::size_t count = boost::size(mpoly); | |
236 | range::resize(mpoly_out, count); | |
237 | ||
238 | for (std::size_t i = 0 ; i < count ; ++i) | |
239 | { | |
240 | apply_poly(range::at(mpoly, i), | |
241 | range::at(mpoly_out, i), | |
242 | len, strategy); | |
243 | } | |
244 | } | |
245 | ||
246 | template <typename Poly, typename PolyOut, typename T, typename Strategy> | |
247 | static void apply_poly(Poly const& poly, PolyOut & poly_out, | |
248 | T const& len, Strategy const& strategy) | |
249 | { | |
250 | densify<Poly, PolyOut, polygon_tag, polygon_tag>:: | |
251 | apply(poly, poly_out, len, strategy); | |
252 | } | |
253 | }; | |
254 | ||
255 | ||
256 | } // namespace dispatch | |
257 | #endif // DOXYGEN_NO_DISPATCH | |
258 | ||
259 | ||
260 | namespace resolve_strategy | |
261 | { | |
262 | ||
263 | struct densify | |
264 | { | |
265 | template <typename Geometry, typename Distance, typename Strategy> | |
266 | static inline void apply(Geometry const& geometry, | |
267 | Geometry& out, | |
268 | Distance const& max_distance, | |
269 | Strategy const& strategy) | |
270 | { | |
271 | dispatch::densify<Geometry, Geometry> | |
272 | ::apply(geometry, out, max_distance, strategy); | |
273 | } | |
274 | ||
275 | template <typename Geometry, typename Distance> | |
276 | static inline void apply(Geometry const& geometry, | |
277 | Geometry& out, | |
278 | Distance const& max_distance, | |
279 | default_strategy) | |
280 | { | |
281 | typedef typename strategy::densify::services::default_strategy | |
282 | < | |
283 | typename cs_tag<Geometry>::type | |
284 | >::type strategy_type; | |
285 | ||
286 | /*BOOST_CONCEPT_ASSERT( | |
287 | (concepts::DensifyStrategy<strategy_type>) | |
288 | );*/ | |
289 | ||
290 | apply(geometry, out, max_distance, strategy_type()); | |
291 | } | |
292 | }; | |
293 | ||
294 | } // namespace resolve_strategy | |
295 | ||
296 | ||
297 | namespace resolve_variant { | |
298 | ||
299 | template <typename Geometry> | |
300 | struct densify | |
301 | { | |
302 | template <typename Distance, typename Strategy> | |
303 | static inline void apply(Geometry const& geometry, | |
304 | Geometry& out, | |
305 | Distance const& max_distance, | |
306 | Strategy const& strategy) | |
307 | { | |
308 | resolve_strategy::densify::apply(geometry, out, max_distance, strategy); | |
309 | } | |
310 | }; | |
311 | ||
312 | template <BOOST_VARIANT_ENUM_PARAMS(typename T)> | |
313 | struct densify<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> > | |
314 | { | |
315 | template <typename Distance, typename Strategy> | |
316 | struct visitor: boost::static_visitor<void> | |
317 | { | |
318 | Distance const& m_max_distance; | |
319 | Strategy const& m_strategy; | |
320 | ||
321 | visitor(Distance const& max_distance, Strategy const& strategy) | |
322 | : m_max_distance(max_distance) | |
323 | , m_strategy(strategy) | |
324 | {} | |
325 | ||
326 | template <typename Geometry> | |
327 | void operator()(Geometry const& geometry, Geometry& out) const | |
328 | { | |
329 | densify<Geometry>::apply(geometry, out, m_max_distance, m_strategy); | |
330 | } | |
331 | }; | |
332 | ||
333 | template <typename Distance, typename Strategy> | |
334 | static inline void | |
335 | apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry, | |
336 | boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& out, | |
337 | Distance const& max_distance, | |
338 | Strategy const& strategy) | |
339 | { | |
340 | boost::apply_visitor( | |
341 | visitor<Distance, Strategy>(max_distance, strategy), | |
342 | geometry, | |
343 | out | |
344 | ); | |
345 | } | |
346 | }; | |
347 | ||
348 | } // namespace resolve_variant | |
349 | ||
350 | ||
351 | /*! | |
352 | \brief Densify a geometry using a specified strategy | |
353 | \ingroup densify | |
354 | \tparam Geometry \tparam_geometry | |
355 | \tparam Distance A numerical distance measure | |
356 | \tparam Strategy A type fulfilling a DensifyStrategy concept | |
357 | \param geometry Input geometry, to be densified | |
358 | \param out Output geometry, densified version of the input geometry | |
359 | \param max_distance Distance threshold (in units depending on strategy) | |
360 | \param strategy Densify strategy to be used for densification | |
361 | ||
362 | \qbk{distinguish,with strategy} | |
363 | \qbk{[include reference/algorithms/densify.qbk]} | |
364 | ||
365 | \qbk{ | |
366 | [heading Available Strategies] | |
367 | \* [link geometry.reference.strategies.strategy_densify_cartesian Cartesian] | |
368 | \* [link geometry.reference.strategies.strategy_densify_spherical Spherical] | |
369 | \* [link geometry.reference.strategies.strategy_densify_geographic Geographic] | |
370 | ||
371 | [heading Example] | |
372 | [densify_strategy] | |
373 | [densify_strategy_output] | |
92f5a8d4 TL |
374 | |
375 | [heading See also] | |
376 | \* [link geometry.reference.algorithms.line_interpolate line_interpolate] | |
11fdf7f2 TL |
377 | } |
378 | */ | |
379 | template <typename Geometry, typename Distance, typename Strategy> | |
380 | inline void densify(Geometry const& geometry, | |
381 | Geometry& out, | |
382 | Distance const& max_distance, | |
383 | Strategy const& strategy) | |
384 | { | |
385 | concepts::check<Geometry>(); | |
386 | ||
387 | if (max_distance <= Distance(0)) | |
388 | { | |
389 | BOOST_THROW_EXCEPTION(geometry::invalid_input_exception()); | |
390 | } | |
391 | ||
392 | geometry::clear(out); | |
393 | ||
394 | resolve_variant::densify | |
395 | < | |
396 | Geometry | |
397 | >::apply(geometry, out, max_distance, strategy); | |
398 | } | |
399 | ||
400 | ||
401 | /*! | |
402 | \brief Densify a geometry | |
403 | \ingroup densify | |
404 | \tparam Geometry \tparam_geometry | |
405 | \tparam Distance A numerical distance measure | |
406 | \param geometry Input geometry, to be densified | |
407 | \param out Output geometry, densified version of the input geometry | |
408 | \param max_distance Distance threshold (in units depending on coordinate system) | |
409 | ||
410 | \qbk{[include reference/algorithms/densify.qbk]} | |
411 | ||
412 | \qbk{ | |
413 | [heading Example] | |
414 | [densify] | |
415 | [densify_output] | |
92f5a8d4 TL |
416 | |
417 | [heading See also] | |
418 | \* [link geometry.reference.algorithms.line_interpolate line_interpolate] | |
11fdf7f2 TL |
419 | } |
420 | */ | |
421 | template <typename Geometry, typename Distance> | |
422 | inline void densify(Geometry const& geometry, | |
423 | Geometry& out, | |
424 | Distance const& max_distance) | |
425 | { | |
426 | densify(geometry, out, max_distance, default_strategy()); | |
427 | } | |
428 | ||
429 | ||
430 | }} // namespace boost::geometry | |
431 | ||
432 | #endif // BOOST_GEOMETRY_ALGORITHMS_DENSIFY_HPP |