ceph/src/boost/boost/geometry/algorithms/line_interpolate.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   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
   6
   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)
  10
  11 #ifndef BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP
  12 #define BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP
  13
  14 #include <iterator>
  15 #include <type_traits>
  16
  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>
  23
  24 #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
  25 #include <boost/geometry/algorithms/detail/dummy_geometries.hpp>
  26
  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>
  31
  32 #include <boost/geometry/geometries/concepts/check.hpp>
  33
  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>
  39
  40 namespace boost { namespace geometry
  41 {
  42
  43
  44 #ifndef DOXYGEN_NO_DETAIL
  45 namespace detail { namespace line_interpolate
  46 {
  47
  48 struct convert_and_push_back
  49 {
  50     template <typename Range, typename Point>
  51     static inline void apply(Point const& p, Range& range)
  52     {
  53         typename boost::range_value<Range>::type p2;
  54         geometry::detail::conversion::convert_point_to_point(p, p2);
  55         range::push_back(range, p2);
  56     }
  57 };
  58
  59 struct convert_and_assign
  60 {
  61     template <typename Point1, typename Point2>
  62     static inline void apply(Point1 const& p1, Point2& p2)
  63     {
  64         geometry::detail::conversion::convert_point_to_point(p1, p2);
  65     }
  66
  67 };
  68
  69
  70 /*!
  71 \brief Internal, calculates interpolation point of a linestring using iterator pairs and
  72     specified strategy
  73 */
  74 template <typename Policy>
  75 struct interpolate_range
  76 {
  77     template
  78     <
  79         typename Range,
  80         typename Distance,
  81         typename PointLike,
  82         typename Strategies
  83     >
  84     static inline void apply(Range const& range,
  85                              Distance const& max_distance,
  86                              PointLike & pointlike,
  87                              Strategies const& strategies)
  88     {
  89         typedef typename boost::range_iterator<Range const>::type iterator_t;
  90         typedef typename boost::range_value<Range const>::type point_t;
  91
  92         iterator_t it = boost::begin(range);
  93         iterator_t end = boost::end(range);
  94
  95         if (it == end) // empty(range)
  96         {
  97             BOOST_THROW_EXCEPTION(empty_input_exception());
  98             return;
  99         }
 100         if (max_distance <= 0) //non positive distance
 101         {
 102             Policy::apply(*it, pointlike);
 103             return;
 104         }
 105
 106         auto const pp_strategy = strategies.distance(dummy_point(), dummy_point());
 107         auto const strategy = strategies.line_interpolate(range);
 108
 109         typedef decltype(pp_strategy.apply(
 110                     std::declval<point_t>(), std::declval<point_t>())) distance_type;
 111
 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;
 117
 118         for ( ; it != end ; ++it)
 119         {
 120             distance_type dist = pp_strategy.apply(*prev, *it);
 121             current_distance = prev_distance + dist;
 122
 123             while (current_distance >= repeated_distance)
 124             {
 125                 point_t p;
 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,
 130                                p,
 131                                diff_distance);
 132                 Policy::apply(p, pointlike);
 133                 if (std::is_same<PointLike, point_t>::value)
 134                 {
 135                     return;
 136                 }
 137                 start_p = p;
 138                 prev_distance = repeated_distance;
 139                 repeated_distance += max_distance;
 140             }
 141             prev_distance = current_distance;
 142             prev = it;
 143             start_p = *prev;
 144         }
 145
 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)
 149         {
 150             Policy::apply(*(end-1), pointlike);
 151         }
 152     }
 153 };
 154
 155 template <typename Policy>
 156 struct interpolate_segment
 157 {
 158     template <typename Segment, typename Distance, typename Pointlike, typename Strategy>
 159     static inline void apply(Segment const& segment,
 160                              Distance const& max_distance,
 161                              Pointlike & point,
 162                              Strategy const& strategy)
 163     {
 164         interpolate_range<Policy>().apply(segment_view<Segment>(segment),
 165                                           max_distance, point, strategy);
 166     }
 167 };
 168
 169 }} // namespace detail::line_interpolate
 170 #endif // DOXYGEN_NO_DETAIL
 171
 172
 173 #ifndef DOXYGEN_NO_DISPATCH
 174 namespace dispatch
 175 {
 176
 177
 178 template
 179 <
 180     typename Geometry,
 181     typename Pointlike,
 182     typename Tag1 = typename tag<Geometry>::type,
 183     typename Tag2 = typename tag<Pointlike>::type
 184 >
 185 struct line_interpolate
 186 {
 187     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
 188         "Not implemented for this Geometry type.",
 189         Geometry, Pointlike);
 190 };
 191
 192
 193 template <typename Geometry, typename Pointlike>
 194 struct line_interpolate<Geometry, Pointlike, linestring_tag, point_tag>
 195     : detail::line_interpolate::interpolate_range
 196         <
 197             detail::line_interpolate::convert_and_assign
 198         >
 199 {};
 200
 201 template <typename Geometry, typename Pointlike>
 202 struct line_interpolate<Geometry, Pointlike, linestring_tag, multi_point_tag>
 203     : detail::line_interpolate::interpolate_range
 204         <
 205             detail::line_interpolate::convert_and_push_back
 206         >
 207 {};
 208
 209 template <typename Geometry, typename Pointlike>
 210 struct line_interpolate<Geometry, Pointlike, segment_tag, point_tag>
 211     : detail::line_interpolate::interpolate_segment
 212         <
 213             detail::line_interpolate::convert_and_assign
 214         >
 215 {};
 216
 217 template <typename Geometry, typename Pointlike>
 218 struct line_interpolate<Geometry, Pointlike, segment_tag, multi_point_tag>
 219     : detail::line_interpolate::interpolate_segment
 220         <
 221             detail::line_interpolate::convert_and_push_back
 222         >
 223 {};
 224
 225 } // namespace dispatch
 226 #endif // DOXYGEN_NO_DISPATCH
 227
 228
 229 namespace resolve_strategy {
 230
 231 template
 232 <
 233     typename Strategies,
 234     bool IsUmbrella = strategies::detail::is_umbrella_strategy<Strategies>::value
 235 >
 236 struct line_interpolate
 237 {
 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)
 243     {
 244         dispatch::line_interpolate
 245             <
 246                 Geometry, Pointlike
 247             >::apply(geometry, max_distance, pointlike, strategies);
 248     }
 249 };
 250
 251 template <typename Strategy>
 252 struct line_interpolate<Strategy, false>
 253 {
 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)
 259     {
 260         using strategies::line_interpolate::services::strategy_converter;
 261
 262         dispatch::line_interpolate
 263             <
 264                 Geometry, Pointlike
 265             >::apply(geometry, max_distance, pointlike,
 266                      strategy_converter<Strategy>::get(strategy));
 267     }
 268 };
 269
 270 template <>
 271 struct line_interpolate<default_strategy, false>
 272 {
 273     template <typename Geometry, typename Distance, typename Pointlike>
 274     static inline void apply(Geometry const& geometry,
 275                              Distance const& max_distance,
 276                              Pointlike & pointlike,
 277                              default_strategy)
 278     {
 279         typedef typename strategies::line_interpolate::services::default_strategy
 280             <
 281                 Geometry
 282             >::type strategy_type;
 283
 284         dispatch::line_interpolate
 285             <
 286                 Geometry, Pointlike
 287             >::apply(geometry, max_distance, pointlike, strategy_type());
 288     }
 289 };
 290
 291 } // namespace resolve_strategy
 292
 293
 294 namespace resolve_variant {
 295
 296 template <typename Geometry>
 297 struct line_interpolate
 298 {
 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)
 304     {
 305         return resolve_strategy::line_interpolate
 306                 <
 307                     Strategy
 308                 >::apply(geometry, max_distance, pointlike, strategy);
 309     }
 310 };
 311
 312 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 313 struct line_interpolate<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 314 {
 315     template <typename Pointlike, typename Strategy>
 316     struct visitor: boost::static_visitor<void>
 317     {
 318         Pointlike const& m_pointlike;
 319         Strategy const& m_strategy;
 320
 321         visitor(Pointlike const& pointlike, Strategy const& strategy)
 322             : m_pointlike(pointlike)
 323             , m_strategy(strategy)
 324         {}
 325
 326         template <typename Geometry, typename Distance>
 327         void operator()(Geometry const& geometry, Distance const& max_distance) const
 328         {
 329             line_interpolate<Geometry>::apply(geometry, max_distance,
 330                                               m_pointlike, m_strategy);
 331         }
 332     };
 333
 334     template <typename Distance, typename Pointlike, typename Strategy>
 335     static inline void
 336     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
 337           Distance const& max_distance,
 338           Pointlike & pointlike,
 339           Strategy const& strategy)
 340     {
 341         boost::apply_visitor(
 342             visitor<Pointlike, Strategy>(pointlike, strategy),
 343             geometry,
 344             max_distance
 345         );
 346     }
 347 };
 348
 349 } // namespace resolve_variant
 350
 351 /*!
 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
 364 points
 365
 366 \qbk{[include reference/algorithms/line_interpolate.qbk]}
 367
 368 \qbk{distinguish,with strategy}
 369
 370 \qbk{
 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]
 375
 376 [heading Example]
 377 [line_interpolate_strategy]
 378 [line_interpolate_strategy_output]
 379
 380 [heading See also]
 381 \* [link geometry.reference.algorithms.densify densify]
 382 }
 383  */
 384 template
 385 <
 386     typename Geometry,
 387     typename Distance,
 388     typename Pointlike,
 389     typename Strategy
 390 >
 391 inline void line_interpolate(Geometry const& geometry,
 392                              Distance const& max_distance,
 393                              Pointlike & pointlike,
 394                              Strategy const& strategy)
 395 {
 396     concepts::check<Geometry const>();
 397
 398     // detail::throw_on_empty_input(geometry);
 399
 400     return resolve_variant::line_interpolate<Geometry>
 401                           ::apply(geometry, max_distance, pointlike, strategy);
 402 }
 403
 404
 405 /*!
 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)
 416
 417 \qbk{[include reference/algorithms/line_interpolate.qbk]
 418
 419 [heading Example]
 420 [line_interpolate]
 421 [line_interpolate_output]
 422
 423 [heading See also]
 424 \* [link geometry.reference.algorithms.densify densify]
 425 }
 426  */
 427 template<typename Geometry, typename Distance, typename Pointlike>
 428 inline void line_interpolate(Geometry const& geometry,
 429                              Distance const& max_distance,
 430                              Pointlike & pointlike)
 431 {
 432     concepts::check<Geometry const>();
 433
 434     // detail::throw_on_empty_input(geometry);
 435
 436     return resolve_variant::line_interpolate<Geometry>
 437                           ::apply(geometry, max_distance, pointlike, default_strategy());
 438 }
 439
 440 }} // namespace boost::geometry
 441
 442 #endif // BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP