geometry/algorithms/line_interpolate.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2018-2023 Oracle and/or its affiliates.
0004 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0005 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0006
0007 // Use, modification and distribution is subject to the Boost Software License,
0008 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010
0011 #ifndef BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP
0012 #define BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP
0013
0014 #include <type_traits>
0015
0016 #include <boost/range/begin.hpp>
0017 #include <boost/range/end.hpp>
0018 #include <boost/range/value_type.hpp>
0019 #include <boost/variant/apply_visitor.hpp>
0020 #include <boost/variant/static_visitor.hpp>
0021 #include <boost/variant/variant_fwd.hpp>
0022
0023 #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
0024 #include <boost/geometry/algorithms/detail/dummy_geometries.hpp>
0025
0026 #include <boost/geometry/core/exception.hpp>
0027 #include <boost/geometry/core/static_assert.hpp>
0028 #include <boost/geometry/core/tags.hpp>
0029
0030 #include <boost/geometry/geometries/concepts/check.hpp>
0031
0032 #include <boost/geometry/strategies/default_strategy.hpp>
0033 #include <boost/geometry/strategies/detail.hpp>
0034 #include <boost/geometry/strategies/line_interpolate/cartesian.hpp>
0035 #include <boost/geometry/strategies/line_interpolate/geographic.hpp>
0036 #include <boost/geometry/strategies/line_interpolate/spherical.hpp>
0037
0038 #include <boost/geometry/util/condition.hpp>
0039 #include <boost/geometry/util/range.hpp>
0040 #include <boost/geometry/util/type_traits.hpp>
0041
0042 #include <boost/geometry/views/segment_view.hpp>
0043
0044 namespace boost { namespace geometry
0045 {
0046
0047
0048 #ifndef DOXYGEN_NO_DETAIL
0049 namespace detail { namespace line_interpolate
0050 {
0051
0052 struct convert_and_push_back
0053 {
0054     template <typename Range, typename Point>
0055     static inline void apply(Point const& p, Range& range)
0056     {
0057         typename boost::range_value<Range>::type p2;
0058         geometry::detail::conversion::convert_point_to_point(p, p2);
0059         range::push_back(range, p2);
0060     }
0061 };
0062
0063 struct convert_and_assign
0064 {
0065     template <typename Point1, typename Point2>
0066     static inline void apply(Point1 const& p1, Point2& p2)
0067     {
0068         geometry::detail::conversion::convert_point_to_point(p1, p2);
0069     }
0070
0071 };
0072
0073
0074 /*!
0075 \brief Internal, calculates interpolation point of a linestring using iterator pairs and
0076     specified strategy
0077 */
0078 template <typename Policy>
0079 struct interpolate_range
0080 {
0081     template
0082     <
0083         typename Range,
0084         typename Distance,
0085         typename PointLike,
0086         typename Strategies
0087     >
0088     static inline void apply(Range const& range,
0089                              Distance const& max_distance,
0090                              PointLike & pointlike,
0091                              Strategies const& strategies)
0092     {
0093         typedef typename boost::range_value<Range const>::type point_t;
0094
0095         auto it = boost::begin(range);
0096         auto const end = boost::end(range);
0097
0098         if (it == end) // empty(range)
0099         {
0100             BOOST_THROW_EXCEPTION(empty_input_exception());
0101             return;
0102         }
0103         if (max_distance <= 0) //non positive distance
0104         {
0105             Policy::apply(*it, pointlike);
0106             return;
0107         }
0108
0109         auto const pp_strategy = strategies.distance(dummy_point(), dummy_point());
0110         auto const strategy = strategies.line_interpolate(range);
0111
0112         typedef decltype(pp_strategy.apply(
0113                     std::declval<point_t>(), std::declval<point_t>())) distance_type;
0114
0115         auto prev = it++;
0116         distance_type repeated_distance = max_distance;
0117         distance_type prev_distance = 0;
0118         distance_type current_distance = 0;
0119         point_t start_p = *prev;
0120
0121         for ( ; it != end ; ++it)
0122         {
0123             distance_type dist = pp_strategy.apply(*prev, *it);
0124             current_distance = prev_distance + dist;
0125
0126             while (current_distance >= repeated_distance)
0127             {
0128                 point_t p;
0129                 distance_type diff_distance = current_distance - prev_distance;
0130                 BOOST_ASSERT(diff_distance != distance_type(0));
0131                 strategy.apply(start_p, *it,
0132                                (repeated_distance - prev_distance)/diff_distance,
0133                                p,
0134                                diff_distance);
0135                 Policy::apply(p, pointlike);
0136                 if ( BOOST_GEOMETRY_CONDITION(util::is_point<PointLike>::value) )
0137                 {
0138                     return;
0139                 }
0140                 start_p = p;
0141                 prev_distance = repeated_distance;
0142                 repeated_distance += max_distance;
0143             }
0144             prev_distance = current_distance;
0145             prev = it;
0146             start_p = *prev;
0147         }
0148
0149         // case when max_distance is larger than linestring's length
0150         // return the last point in range (range is not empty)
0151         if (repeated_distance == max_distance)
0152         {
0153             Policy::apply(*(end-1), pointlike);
0154         }
0155     }
0156 };
0157
0158 template <typename Policy>
0159 struct interpolate_segment
0160 {
0161     template <typename Segment, typename Distance, typename Pointlike, typename Strategy>
0162     static inline void apply(Segment const& segment,
0163                              Distance const& max_distance,
0164                              Pointlike & point,
0165                              Strategy const& strategy)
0166     {
0167         interpolate_range<Policy>().apply(segment_view<Segment>(segment),
0168                                           max_distance, point, strategy);
0169     }
0170 };
0171
0172 }} // namespace detail::line_interpolate
0173 #endif // DOXYGEN_NO_DETAIL
0174
0175
0176 #ifndef DOXYGEN_NO_DISPATCH
0177 namespace dispatch
0178 {
0179
0180
0181 template
0182 <
0183     typename Geometry,
0184     typename Pointlike,
0185     typename Tag1 = typename tag<Geometry>::type,
0186     typename Tag2 = typename tag<Pointlike>::type
0187 >
0188 struct line_interpolate
0189 {
0190     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0191         "Not implemented for this Geometry type.",
0192         Geometry, Pointlike);
0193 };
0194
0195
0196 template <typename Geometry, typename Pointlike>
0197 struct line_interpolate<Geometry, Pointlike, linestring_tag, point_tag>
0198     : detail::line_interpolate::interpolate_range
0199         <
0200             detail::line_interpolate::convert_and_assign
0201         >
0202 {};
0203
0204 template <typename Geometry, typename Pointlike>
0205 struct line_interpolate<Geometry, Pointlike, linestring_tag, multi_point_tag>
0206     : detail::line_interpolate::interpolate_range
0207         <
0208             detail::line_interpolate::convert_and_push_back
0209         >
0210 {};
0211
0212 template <typename Geometry, typename Pointlike>
0213 struct line_interpolate<Geometry, Pointlike, segment_tag, point_tag>
0214     : detail::line_interpolate::interpolate_segment
0215         <
0216             detail::line_interpolate::convert_and_assign
0217         >
0218 {};
0219
0220 template <typename Geometry, typename Pointlike>
0221 struct line_interpolate<Geometry, Pointlike, segment_tag, multi_point_tag>
0222     : detail::line_interpolate::interpolate_segment
0223         <
0224             detail::line_interpolate::convert_and_push_back
0225         >
0226 {};
0227
0228 } // namespace dispatch
0229 #endif // DOXYGEN_NO_DISPATCH
0230
0231
0232 namespace resolve_strategy {
0233
0234 template
0235 <
0236     typename Strategies,
0237     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
0238 >
0239 struct line_interpolate
0240 {
0241     template <typename Geometry, typename Distance, typename Pointlike>
0242     static inline void apply(Geometry const& geometry,
0243                              Distance const& max_distance,
0244                              Pointlike & pointlike,
0245                              Strategies const& strategies)
0246     {
0247         dispatch::line_interpolate
0248             <
0249                 Geometry, Pointlike
0250             >::apply(geometry, max_distance, pointlike, strategies);
0251     }
0252 };
0253
0254 template <typename Strategy>
0255 struct line_interpolate<Strategy, false>
0256 {
0257     template <typename Geometry, typename Distance, typename Pointlike>
0258     static inline void apply(Geometry const& geometry,
0259                              Distance const& max_distance,
0260                              Pointlike & pointlike,
0261                              Strategy const& strategy)
0262     {
0263         using strategies::line_interpolate::services::strategy_converter;
0264
0265         dispatch::line_interpolate
0266             <
0267                 Geometry, Pointlike
0268             >::apply(geometry, max_distance, pointlike,
0269                      strategy_converter<Strategy>::get(strategy));
0270     }
0271 };
0272
0273 template <>
0274 struct line_interpolate<default_strategy, false>
0275 {
0276     template <typename Geometry, typename Distance, typename Pointlike>
0277     static inline void apply(Geometry const& geometry,
0278                              Distance const& max_distance,
0279                              Pointlike & pointlike,
0280                              default_strategy)
0281     {
0282         typedef typename strategies::line_interpolate::services::default_strategy
0283             <
0284                 Geometry
0285             >::type strategy_type;
0286
0287         dispatch::line_interpolate
0288             <
0289                 Geometry, Pointlike
0290             >::apply(geometry, max_distance, pointlike, strategy_type());
0291     }
0292 };
0293
0294 } // namespace resolve_strategy
0295
0296
0297 namespace resolve_variant {
0298
0299 template <typename Geometry>
0300 struct line_interpolate
0301 {
0302     template <typename Distance, typename Pointlike, typename Strategy>
0303     static inline void apply(Geometry const& geometry,
0304                              Distance const& max_distance,
0305                              Pointlike & pointlike,
0306                              Strategy const& strategy)
0307     {
0308         return resolve_strategy::line_interpolate
0309                 <
0310                     Strategy
0311                 >::apply(geometry, max_distance, pointlike, strategy);
0312     }
0313 };
0314
0315 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
0316 struct line_interpolate<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
0317 {
0318     template <typename Pointlike, typename Strategy>
0319     struct visitor: boost::static_visitor<void>
0320     {
0321         Pointlike const& m_pointlike;
0322         Strategy const& m_strategy;
0323
0324         visitor(Pointlike const& pointlike, Strategy const& strategy)
0325             : m_pointlike(pointlike)
0326             , m_strategy(strategy)
0327         {}
0328
0329         template <typename Geometry, typename Distance>
0330         void operator()(Geometry const& geometry, Distance const& max_distance) const
0331         {
0332             line_interpolate<Geometry>::apply(geometry, max_distance,
0333                                               m_pointlike, m_strategy);
0334         }
0335     };
0336
0337     template <typename Distance, typename Pointlike, typename Strategy>
0338     static inline void
0339     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
0340           Distance const& max_distance,
0341           Pointlike & pointlike,
0342           Strategy const& strategy)
0343     {
0344         boost::apply_visitor(
0345             visitor<Pointlike, Strategy>(pointlike, strategy),
0346             geometry,
0347             max_distance
0348         );
0349     }
0350 };
0351
0352 } // namespace resolve_variant
0353
0354 /*!
0355 \brief     Returns one or more points interpolated along a LineString \brief_strategy
0356 \ingroup line_interpolate
0357 \tparam Geometry Any type fulfilling a LineString concept
0358 \tparam Distance A numerical distance measure
0359 \tparam Pointlike Any type fulfilling Point or Multipoint concept
0360 \tparam Strategy A type fulfilling a LineInterpolatePointStrategy concept
0361 \param geometry Input geometry
0362 \param max_distance Distance threshold (in units depending on coordinate system)
0363 representing the spacing between the points
0364 \param pointlike Output: either a Point (exactly one point will be constructed) or
0365 a MultiPoint (depending on the max_distance one or more points will be constructed)
0366 \param strategy line_interpolate strategy to be used for interpolation of
0367 points
0368
0369 \qbk{[include reference/algorithms/line_interpolate.qbk]}
0370
0371 \qbk{distinguish,with strategy}
0372
0373 \qbk{
0374 [heading Available Strategies]
0375 \* [link geometry.reference.strategies.strategy_line_interpolate_cartesian Cartesian]
0376 \* [link geometry.reference.strategies.strategy_line_interpolate_spherical Spherical]
0377 \* [link geometry.reference.strategies.strategy_line_interpolate_geographic Geographic]
0378
0379 [heading Example]
0380 [line_interpolate_strategy]
0381 [line_interpolate_strategy_output]
0382
0383 [heading See also]
0384 \* [link geometry.reference.algorithms.densify densify]
0385 }
0386  */
0387 template
0388 <
0389     typename Geometry,
0390     typename Distance,
0391     typename Pointlike,
0392     typename Strategy
0393 >
0394 inline void line_interpolate(Geometry const& geometry,
0395                              Distance const& max_distance,
0396                              Pointlike & pointlike,
0397                              Strategy const& strategy)
0398 {
0399     concepts::check<Geometry const>();
0400
0401     // detail::throw_on_empty_input(geometry);
0402
0403     return resolve_variant::line_interpolate<Geometry>
0404                           ::apply(geometry, max_distance, pointlike, strategy);
0405 }
0406
0407
0408 /*!
0409 \brief     Returns one or more points interpolated along a LineString.
0410 \ingroup line_interpolate
0411 \tparam Geometry Any type fulfilling a LineString concept
0412 \tparam Distance A numerical distance measure
0413 \tparam Pointlike Any type fulfilling Point or Multipoint concept
0414 \param geometry Input geometry
0415 \param max_distance Distance threshold (in units depending on coordinate system)
0416 representing the spacing between the points
0417 \param pointlike Output: either a Point (exactly one point will be constructed) or
0418 a MultiPoint (depending on the max_distance one or more points will be constructed)
0419
0420 \qbk{[include reference/algorithms/line_interpolate.qbk]
0421
0422 [heading Example]
0423 [line_interpolate]
0424 [line_interpolate_output]
0425
0426 [heading See also]
0427 \* [link geometry.reference.algorithms.densify densify]
0428 }
0429  */
0430 template<typename Geometry, typename Distance, typename Pointlike>
0431 inline void line_interpolate(Geometry const& geometry,
0432                              Distance const& max_distance,
0433                              Pointlike & pointlike)
0434 {
0435     concepts::check<Geometry const>();
0436
0437     // detail::throw_on_empty_input(geometry);
0438
0439     return resolve_variant::line_interpolate<Geometry>
0440                           ::apply(geometry, max_distance, pointlike, default_strategy());
0441 }
0442
0443 }} // namespace boost::geometry
0444
0445 #endif // BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP