1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2018-2021 Oracle and/or its affiliates.
4 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
5 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
7 // Use, modification and distribution is subject to the Boost Software License,
8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP
15 #include <type_traits>
17 #include <boost/range/begin.hpp>
18 #include <boost/range/end.hpp>
19 #include <boost/range/iterator.hpp>
20 #include <boost/range/value_type.hpp>
21 #include <boost/variant/static_visitor.hpp>
22 #include <boost/variant/variant_fwd.hpp>
24 #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
25 #include <boost/geometry/algorithms/detail/dummy_geometries.hpp>
27 #include <boost/geometry/core/cs.hpp>
28 #include <boost/geometry/core/closure.hpp>
29 #include <boost/geometry/core/static_assert.hpp>
30 #include <boost/geometry/core/tags.hpp>
32 #include <boost/geometry/geometries/concepts/check.hpp>
34 #include <boost/geometry/strategies/default_strategy.hpp>
35 #include <boost/geometry/strategies/detail.hpp>
36 #include <boost/geometry/strategies/line_interpolate/cartesian.hpp>
37 #include <boost/geometry/strategies/line_interpolate/geographic.hpp>
38 #include <boost/geometry/strategies/line_interpolate/spherical.hpp>
40 namespace boost { namespace geometry
44 #ifndef DOXYGEN_NO_DETAIL
45 namespace detail { namespace line_interpolate
48 struct convert_and_push_back
50 template <typename Range, typename Point>
51 static inline void apply(Point const& p, Range& range)
53 typename boost::range_value<Range>::type p2;
54 geometry::detail::conversion::convert_point_to_point(p, p2);
55 range::push_back(range, p2);
59 struct convert_and_assign
61 template <typename Point1, typename Point2>
62 static inline void apply(Point1 const& p1, Point2& p2)
64 geometry::detail::conversion::convert_point_to_point(p1, p2);
71 \brief Internal, calculates interpolation point of a linestring using iterator pairs and
74 template <typename Policy>
75 struct interpolate_range
84 static inline void apply(Range const& range,
85 Distance const& max_distance,
86 PointLike & pointlike,
87 Strategies const& strategies)
89 typedef typename boost::range_iterator<Range const>::type iterator_t;
90 typedef typename boost::range_value<Range const>::type point_t;
92 iterator_t it = boost::begin(range);
93 iterator_t end = boost::end(range);
95 if (it == end) // empty(range)
97 BOOST_THROW_EXCEPTION(empty_input_exception());
100 if (max_distance <= 0) //non positive distance
102 Policy::apply(*it, pointlike);
106 auto const pp_strategy = strategies.distance(dummy_point(), dummy_point());
107 auto const strategy = strategies.line_interpolate(range);
109 typedef decltype(pp_strategy.apply(
110 std::declval<point_t>(), std::declval<point_t>())) distance_type;
112 iterator_t prev = it++;
113 distance_type repeated_distance = max_distance;
114 distance_type prev_distance = 0;
115 distance_type current_distance = 0;
116 point_t start_p = *prev;
118 for ( ; it != end ; ++it)
120 distance_type dist = pp_strategy.apply(*prev, *it);
121 current_distance = prev_distance + dist;
123 while (current_distance >= repeated_distance)
126 distance_type diff_distance = current_distance - prev_distance;
127 BOOST_ASSERT(diff_distance != distance_type(0));
128 strategy.apply(start_p, *it,
129 (repeated_distance - prev_distance)/diff_distance,
132 Policy::apply(p, pointlike);
133 if (std::is_same<PointLike, point_t>::value)
138 prev_distance = repeated_distance;
139 repeated_distance += max_distance;
141 prev_distance = current_distance;
146 // case when max_distance is larger than linestring's length
147 // return the last point in range (range is not empty)
148 if (repeated_distance == max_distance)
150 Policy::apply(*(end-1), pointlike);
155 template <typename Policy>
156 struct interpolate_segment
158 template <typename Segment, typename Distance, typename Pointlike, typename Strategy>
159 static inline void apply(Segment const& segment,
160 Distance const& max_distance,
162 Strategy const& strategy)
164 interpolate_range<Policy>().apply(segment_view<Segment>(segment),
165 max_distance, point, strategy);
169 }} // namespace detail::line_interpolate
170 #endif // DOXYGEN_NO_DETAIL
173 #ifndef DOXYGEN_NO_DISPATCH
182 typename Tag1 = typename tag<Geometry>::type,
183 typename Tag2 = typename tag<Pointlike>::type
185 struct line_interpolate
187 BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
188 "Not implemented for this Geometry type.",
189 Geometry, Pointlike);
193 template <typename Geometry, typename Pointlike>
194 struct line_interpolate<Geometry, Pointlike, linestring_tag, point_tag>
195 : detail::line_interpolate::interpolate_range
197 detail::line_interpolate::convert_and_assign
201 template <typename Geometry, typename Pointlike>
202 struct line_interpolate<Geometry, Pointlike, linestring_tag, multi_point_tag>
203 : detail::line_interpolate::interpolate_range
205 detail::line_interpolate::convert_and_push_back
209 template <typename Geometry, typename Pointlike>
210 struct line_interpolate<Geometry, Pointlike, segment_tag, point_tag>
211 : detail::line_interpolate::interpolate_segment
213 detail::line_interpolate::convert_and_assign
217 template <typename Geometry, typename Pointlike>
218 struct line_interpolate<Geometry, Pointlike, segment_tag, multi_point_tag>
219 : detail::line_interpolate::interpolate_segment
221 detail::line_interpolate::convert_and_push_back
225 } // namespace dispatch
226 #endif // DOXYGEN_NO_DISPATCH
229 namespace resolve_strategy {
234 bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
236 struct line_interpolate
238 template <typename Geometry, typename Distance, typename Pointlike>
239 static inline void apply(Geometry const& geometry,
240 Distance const& max_distance,
241 Pointlike & pointlike,
242 Strategies const& strategies)
244 dispatch::line_interpolate
247 >::apply(geometry, max_distance, pointlike, strategies);
251 template <typename Strategy>
252 struct line_interpolate<Strategy, false>
254 template <typename Geometry, typename Distance, typename Pointlike>
255 static inline void apply(Geometry const& geometry,
256 Distance const& max_distance,
257 Pointlike & pointlike,
258 Strategy const& strategy)
260 using strategies::line_interpolate::services::strategy_converter;
262 dispatch::line_interpolate
265 >::apply(geometry, max_distance, pointlike,
266 strategy_converter<Strategy>::get(strategy));
271 struct line_interpolate<default_strategy, false>
273 template <typename Geometry, typename Distance, typename Pointlike>
274 static inline void apply(Geometry const& geometry,
275 Distance const& max_distance,
276 Pointlike & pointlike,
279 typedef typename strategies::line_interpolate::services::default_strategy
282 >::type strategy_type;
284 dispatch::line_interpolate
287 >::apply(geometry, max_distance, pointlike, strategy_type());
291 } // namespace resolve_strategy
294 namespace resolve_variant {
296 template <typename Geometry>
297 struct line_interpolate
299 template <typename Distance, typename Pointlike, typename Strategy>
300 static inline void apply(Geometry const& geometry,
301 Distance const& max_distance,
302 Pointlike & pointlike,
303 Strategy const& strategy)
305 return resolve_strategy::line_interpolate
308 >::apply(geometry, max_distance, pointlike, strategy);
312 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
313 struct line_interpolate<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
315 template <typename Pointlike, typename Strategy>
316 struct visitor: boost::static_visitor<void>
318 Pointlike const& m_pointlike;
319 Strategy const& m_strategy;
321 visitor(Pointlike const& pointlike, Strategy const& strategy)
322 : m_pointlike(pointlike)
323 , m_strategy(strategy)
326 template <typename Geometry, typename Distance>
327 void operator()(Geometry const& geometry, Distance const& max_distance) const
329 line_interpolate<Geometry>::apply(geometry, max_distance,
330 m_pointlike, m_strategy);
334 template <typename Distance, typename Pointlike, typename Strategy>
336 apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
337 Distance const& max_distance,
338 Pointlike & pointlike,
339 Strategy const& strategy)
341 boost::apply_visitor(
342 visitor<Pointlike, Strategy>(pointlike, strategy),
349 } // namespace resolve_variant
352 \brief Returns one or more points interpolated along a LineString \brief_strategy
353 \ingroup line_interpolate
354 \tparam Geometry Any type fulfilling a LineString concept
355 \tparam Distance A numerical distance measure
356 \tparam Pointlike Any type fulfilling Point or Multipoint concept
357 \tparam Strategy A type fulfilling a LineInterpolatePointStrategy concept
358 \param geometry Input geometry
359 \param max_distance Distance threshold (in units depending on coordinate system)
360 representing the spacing between the points
361 \param pointlike Output: either a Point (exactly one point will be constructed) or
362 a MultiPoint (depending on the max_distance one or more points will be constructed)
363 \param strategy line_interpolate strategy to be used for interpolation of
366 \qbk{[include reference/algorithms/line_interpolate.qbk]}
368 \qbk{distinguish,with strategy}
371 [heading Available Strategies]
372 \* [link geometry.reference.strategies.strategy_line_interpolate_cartesian Cartesian]
373 \* [link geometry.reference.strategies.strategy_line_interpolate_spherical Spherical]
374 \* [link geometry.reference.strategies.strategy_line_interpolate_geographic Geographic]
377 [line_interpolate_strategy]
378 [line_interpolate_strategy_output]
381 \* [link geometry.reference.algorithms.densify densify]
391 inline void line_interpolate(Geometry const& geometry,
392 Distance const& max_distance,
393 Pointlike & pointlike,
394 Strategy const& strategy)
396 concepts::check<Geometry const>();
398 // detail::throw_on_empty_input(geometry);
400 return resolve_variant::line_interpolate<Geometry>
401 ::apply(geometry, max_distance, pointlike, strategy);
406 \brief Returns one or more points interpolated along a LineString.
407 \ingroup line_interpolate
408 \tparam Geometry Any type fulfilling a LineString concept
409 \tparam Distance A numerical distance measure
410 \tparam Pointlike Any type fulfilling Point or Multipoint concept
411 \param geometry Input geometry
412 \param max_distance Distance threshold (in units depending on coordinate system)
413 representing the spacing between the points
414 \param pointlike Output: either a Point (exactly one point will be constructed) or
415 a MultiPoint (depending on the max_distance one or more points will be constructed)
417 \qbk{[include reference/algorithms/line_interpolate.qbk]
421 [line_interpolate_output]
424 \* [link geometry.reference.algorithms.densify densify]
427 template<typename Geometry, typename Distance, typename Pointlike>
428 inline void line_interpolate(Geometry const& geometry,
429 Distance const& max_distance,
430 Pointlike & pointlike)
432 concepts::check<Geometry const>();
434 // detail::throw_on_empty_input(geometry);
436 return resolve_variant::line_interpolate<Geometry>
437 ::apply(geometry, max_distance, pointlike, default_strategy());
440 }} // namespace boost::geometry
442 #endif // BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP