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>
18 #include <boost/geometry/core/cs.hpp>
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
push_back_policyboost::geometry::detail::densify::push_back_policy47 inline explicit push_back_policy(Range & rng)
48 : m_rng(rng)
49 {}
50
applyboost::geometry::detail::densify::push_back_policy51 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>
convert_and_push_back(Range & range,Point const & p)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>
applyboost::geometry::detail::densify::densify_range72 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>
applyboost::geometry::detail::densify::densify_ring110 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>
applyboost::geometry::dispatch::densify174 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>
applyboost::geometry::dispatch::densify202 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>
apply_ringboost::geometry::dispatch::densify220 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>
applyboost::geometry::dispatch::densify232 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>
apply_polyboost::geometry::dispatch::densify247 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>
applyboost::geometry::resolve_strategy::densify266 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>
applyboost::geometry::resolve_strategy::densify276 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>
applyboost::geometry::resolve_variant::densify303 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
visitorboost::geometry::resolve_variant::densify::visitor321 visitor(Distance const& max_distance, Strategy const& strategy)
322 : m_max_distance(max_distance)
323 , m_strategy(strategy)
324 {}
325
326 template <typename Geometry>
operator ()boost::geometry::resolve_variant::densify::visitor327 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
applyboost::geometry::resolve_variant::densify335 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]
374
375 [heading See also]
376 \* [link geometry.reference.algorithms.line_interpolate line_interpolate]
377 }
378 */
379 template <typename Geometry, typename Distance, typename Strategy>
densify(Geometry const & geometry,Geometry & out,Distance const & max_distance,Strategy const & 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]
416
417 [heading See also]
418 \* [link geometry.reference.algorithms.line_interpolate line_interpolate]
419 }
420 */
421 template <typename Geometry, typename Distance>
densify(Geometry const & geometry,Geometry & out,Distance const & max_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
433