geometry/algorithms/line_interpolate.hpp

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