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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2018, 2019 Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
   6 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   7
   8 // Use, modification and distribution is subject to the Boost Software License,
   9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  10 // http://www.boost.org/LICENSE_1_0.txt)
  11
  12 #ifndef BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP
  13 #define BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP
  14
  15 #include <iterator>
  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
  22 #include <boost/geometry/core/cs.hpp>
  23 #include <boost/geometry/core/closure.hpp>
  24 #include <boost/geometry/core/tags.hpp>
  25
  26 #include <boost/geometry/geometries/concepts/check.hpp>
  27
  28 #include <boost/geometry/algorithms/assign.hpp>
  29 #include <boost/geometry/algorithms/length.hpp>
  30 #include <boost/geometry/strategies/default_strategy.hpp>
  31 #include <boost/geometry/strategies/line_interpolate.hpp>
  32
  33 namespace boost { namespace geometry
  34 {
  35
  36
  37 #ifndef DOXYGEN_NO_DETAIL
  38 namespace detail { namespace line_interpolate
  39 {
  40
  41 struct convert_and_push_back
  42 {
  43     template <typename Range, typename Point>
  44     inline void apply(Point const& p, Range& range)
  45     {
  46         typename boost::range_value<Range>::type p2;
  47         geometry::detail::conversion::convert_point_to_point(p, p2);
  48         range::push_back(range, p2);
  49     }
  50 };
  51
  52 struct convert_and_assign
  53 {
  54     template <typename Point1, typename Point2>
  55     inline void apply(Point1 const& p1, Point2& p2)
  56     {
  57         geometry::detail::conversion::convert_point_to_point(p1, p2);
  58     }
  59
  60 };
  61
  62
  63 /*!
  64 \brief Internal, calculates interpolation point of a linestring using iterator pairs and
  65     specified strategy
  66 */
  67 template <typename Policy>
  68 struct interpolate_range
  69 {
  70     template
  71     <
  72         typename Range,
  73         typename Distance,
  74         typename PointLike,
  75         typename Strategy
  76     >
  77     static inline void apply(Range const& range,
  78                              Distance const& max_distance,
  79                              PointLike & pointlike,
  80                              Strategy const& strategy)
  81     {
  82         Policy policy;
  83
  84         typedef typename boost::range_iterator<Range const>::type iterator_t;
  85         typedef typename boost::range_value<Range const>::type point_t;
  86
  87         iterator_t it = boost::begin(range);
  88         iterator_t end = boost::end(range);
  89
  90         if (it == end) // empty(range)
  91         {
  92             BOOST_THROW_EXCEPTION(empty_input_exception());
  93             return;
  94         }
  95         if (max_distance <= 0) //non positive distance
  96         {
  97             policy.apply(*it, pointlike);
  98             return;
  99         }
 100
 101         iterator_t prev = it++;
 102         Distance repeated_distance = max_distance;
 103         Distance prev_distance = 0;
 104         Distance current_distance = 0;
 105         point_t start_p = *prev;
 106
 107         for ( ; it != end ; ++it)
 108         {
 109             Distance dist = strategy.get_distance_pp_strategy().apply(*prev, *it);
 110             current_distance = prev_distance + dist;
 111
 112             while (current_distance >= repeated_distance)
 113             {
 114                 point_t p;
 115                 Distance diff_distance = current_distance - prev_distance;
 116                 BOOST_ASSERT(diff_distance != Distance(0));
 117                 strategy.apply(start_p, *it,
 118                                (repeated_distance - prev_distance)/diff_distance,
 119                                p,
 120                                diff_distance);
 121                 policy.apply(p, pointlike);
 122                 if (boost::is_same<PointLike, point_t>::value)
 123                 {
 124                     return;
 125                 }
 126                 start_p = p;
 127                 prev_distance = repeated_distance;
 128                 repeated_distance += max_distance;
 129             }
 130             prev_distance = current_distance;
 131             prev = it;
 132             start_p = *prev;
 133         }
 134
 135         // case when max_distance is larger than linestring's length
 136         // return the last point in range (range is not empty)
 137         if (repeated_distance == max_distance)
 138         {
 139             policy.apply(*(end-1), pointlike);
 140         }
 141     }
 142 };
 143
 144 template <typename Policy>
 145 struct interpolate_segment
 146 {
 147     template <typename Segment, typename Distance, typename Pointlike, typename Strategy>
 148     static inline void apply(Segment const& segment,
 149                              Distance const& max_distance,
 150                              Pointlike & point,
 151                              Strategy const& strategy)
 152     {
 153         interpolate_range<Policy>().apply(segment_view<Segment>(segment),
 154                                           max_distance, point, strategy);
 155     }
 156 };
 157
 158 }} // namespace detail::line_interpolate
 159 #endif // DOXYGEN_NO_DETAIL
 160
 161
 162 #ifndef DOXYGEN_NO_DISPATCH
 163 namespace dispatch
 164 {
 165
 166
 167 template
 168 <
 169     typename Geometry,
 170     typename Pointlike,
 171     typename Tag1 = typename tag<Geometry>::type,
 172     typename Tag2 = typename tag<Pointlike>::type
 173 >
 174 struct line_interpolate
 175 {
 176     BOOST_MPL_ASSERT_MSG
 177         (
 178             false, NOT_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE
 179             , (types<Geometry>)
 180         );
 181 };
 182
 183
 184 template <typename Geometry, typename Pointlike>
 185 struct line_interpolate<Geometry, Pointlike, linestring_tag, point_tag>
 186     : detail::line_interpolate::interpolate_range
 187         <
 188             detail::line_interpolate::convert_and_assign
 189         >
 190 {};
 191
 192 template <typename Geometry, typename Pointlike>
 193 struct line_interpolate<Geometry, Pointlike, linestring_tag, multi_point_tag>
 194     : detail::line_interpolate::interpolate_range
 195         <
 196             detail::line_interpolate::convert_and_push_back
 197         >
 198 {};
 199
 200 template <typename Geometry, typename Pointlike>
 201 struct line_interpolate<Geometry, Pointlike, segment_tag, point_tag>
 202     : detail::line_interpolate::interpolate_segment
 203         <
 204             detail::line_interpolate::convert_and_assign
 205         >
 206 {};
 207
 208 template <typename Geometry, typename Pointlike>
 209 struct line_interpolate<Geometry, Pointlike, segment_tag, multi_point_tag>
 210     : detail::line_interpolate::interpolate_segment
 211         <
 212             detail::line_interpolate::convert_and_push_back
 213         >
 214 {};
 215
 216 } // namespace dispatch
 217 #endif // DOXYGEN_NO_DISPATCH
 218
 219
 220 namespace resolve_strategy {
 221
 222 struct line_interpolate
 223 {
 224     template
 225     <
 226         typename Geometry,
 227         typename Distance,
 228         typename Pointlike,
 229         typename Strategy
 230     >
 231     static inline void apply(Geometry const& geometry,
 232                              Distance const& max_distance,
 233                              Pointlike & pointlike,
 234                              Strategy const& strategy)
 235     {
 236         dispatch::line_interpolate<Geometry, Pointlike>::apply(geometry,
 237                                                                max_distance,
 238                                                                pointlike,
 239                                                                strategy);
 240     }
 241
 242     template <typename Geometry, typename Distance, typename Pointlike>
 243     static inline void apply(Geometry const& geometry,
 244                              Distance const& max_distance,
 245                              Pointlike & pointlike,
 246                              default_strategy)
 247     {
 248         typedef typename strategy::line_interpolate::services::default_strategy
 249             <
 250                 typename cs_tag<Geometry>::type
 251             >::type strategy_type;
 252
 253         dispatch::line_interpolate<Geometry, Pointlike>::apply(geometry,
 254                                                                max_distance,
 255                                                                pointlike,
 256                                                                strategy_type());
 257     }
 258 };
 259
 260 } // namespace resolve_strategy
 261
 262
 263 namespace resolve_variant {
 264
 265 template <typename Geometry>
 266 struct line_interpolate
 267 {
 268     template <typename Distance, typename Pointlike, typename Strategy>
 269     static inline void apply(Geometry const& geometry,
 270                              Distance const& max_distance,
 271                              Pointlike & pointlike,
 272                              Strategy const& strategy)
 273     {
 274         return resolve_strategy::line_interpolate::apply(geometry,
 275                                                          max_distance,
 276                                                          pointlike,
 277                                                          strategy);
 278     }
 279 };
 280
 281 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
 282 struct line_interpolate<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
 283 {
 284     template <typename Pointlike, typename Strategy>
 285     struct visitor: boost::static_visitor<void>
 286     {
 287         Pointlike const& m_pointlike;
 288         Strategy const& m_strategy;
 289
 290         visitor(Pointlike const& pointlike, Strategy const& strategy)
 291             : m_pointlike(pointlike)
 292             , m_strategy(strategy)
 293         {}
 294
 295         template <typename Geometry, typename Distance>
 296         void operator()(Geometry const& geometry, Distance const& max_distance) const
 297         {
 298             line_interpolate<Geometry>::apply(geometry, max_distance,
 299                                               m_pointlike, m_strategy);
 300         }
 301     };
 302
 303     template <typename Distance, typename Pointlike, typename Strategy>
 304     static inline void
 305     apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> const& geometry,
 306           double const& max_distance,
 307           Pointlike & pointlike,
 308           Strategy const& strategy)
 309     {
 310         boost::apply_visitor(
 311             visitor<Pointlike, Strategy>(pointlike, strategy),
 312             geometry,
 313             max_distance
 314         );
 315     }
 316 };
 317
 318 } // namespace resolve_variant
 319
 320 /*!
 321 \brief  Returns one or more points interpolated along a LineString \brief_strategy
 322 \ingroup line_interpolate
 323 \tparam Geometry Any type fulfilling a LineString concept
 324 \tparam Distance A numerical distance measure
 325 \tparam Pointlike Any type fulfilling Point or Multipoint concept
 326 \tparam Strategy A type fulfilling a LineInterpolatePointStrategy concept
 327 \param geometry Input geometry
 328 \param max_distance Distance threshold (in units depending on coordinate system)
 329 representing the spacing between the points
 330 \param pointlike Output: either a Point (exactly one point will be constructed) or
 331 a MultiPoint (depending on the max_distance one or more points will be constructed)
 332 \param strategy line_interpolate strategy to be used for interpolation of
 333 points
 334
 335 \qbk{[include reference/algorithms/line_interpolate.qbk]}
 336
 337 \qbk{distinguish,with strategy}
 338
 339 \qbk{
 340 [heading Available Strategies]
 341 \* [link geometry.reference.strategies.strategy_line_interpolate_cartesian Cartesian]
 342 \* [link geometry.reference.strategies.strategy_line_interpolate_spherical Spherical]
 343 \* [link geometry.reference.strategies.strategy_line_interpolate_geographic Geographic]
 344
 345 [heading Example]
 346 [line_interpolate_strategy]
 347 [line_interpolate_strategy_output]
 348
 349 [heading See also]
 350 \* [link geometry.reference.algorithms.densify densify]
 351 }
 352  */
 353 template
 354 <
 355     typename Geometry,
 356     typename Distance,
 357     typename Pointlike,
 358     typename Strategy
 359 >
 360 inline void line_interpolate(Geometry const& geometry,
 361                              Distance const& max_distance,
 362                              Pointlike & pointlike,
 363                              Strategy const& strategy)
 364 {
 365     concepts::check<Geometry const>();
 366
 367     // detail::throw_on_empty_input(geometry);
 368
 369     return resolve_variant::line_interpolate<Geometry>
 370                           ::apply(geometry, max_distance, pointlike, strategy);
 371 }
 372
 373
 374 /*!
 375 \brief  Returns one or more points interpolated along a LineString.
 376 \ingroup line_interpolate
 377 \tparam Geometry Any type fulfilling a LineString concept
 378 \tparam Distance A numerical distance measure
 379 \tparam Pointlike Any type fulfilling Point or Multipoint concept
 380 \param geometry Input geometry
 381 \param max_distance Distance threshold (in units depending on coordinate system)
 382 representing the spacing between the points
 383 \param pointlike Output: either a Point (exactly one point will be constructed) or
 384 a MultiPoint (depending on the max_distance one or more points will be constructed)
 385
 386 \qbk{[include reference/algorithms/line_interpolate.qbk]
 387
 388 [heading Example]
 389 [line_interpolate]
 390 [line_interpolate_output]
 391
 392 [heading See also]
 393 \* [link geometry.reference.algorithms.densify densify]
 394 }
 395  */
 396 template<typename Geometry, typename Distance, typename Pointlike>
 397 inline void line_interpolate(Geometry const& geometry,
 398                              Distance const& max_distance,
 399                              Pointlike & pointlike)
 400 {
 401     concepts::check<Geometry const>();
 402
 403     // detail::throw_on_empty_input(geometry);
 404
 405     return resolve_variant::line_interpolate<Geometry>
 406                           ::apply(geometry, max_distance, pointlike, default_strategy());
 407 }
 408
 409 }} // namespace boost::geometry
 410
 411 #endif // BOOST_GEOMETRY_ALGORITHMS_LINE_INTERPOLATE_HPP