ceph/src/boost/boost/geometry/algorithms/detail/envelope/segment.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
   6
   7 // This file was modified by Oracle on 2015-2017.
   8 // Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
   9
  10 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
  11 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  12 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  13
  14 // Distributed under the Boost Software License, Version 1.0.
  15 // (See accompanying file LICENSE_1_0.txt or copy at
  16 // http://www.boost.org/LICENSE_1_0.txt)
  17
  18 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_SEGMENT_HPP
  19 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_SEGMENT_HPP
  20
  21 #include <cstddef>
  22 #include <utility>
  23
  24 #include <boost/numeric/conversion/cast.hpp>
  25
  26 #include <boost/geometry/core/assert.hpp>
  27 #include <boost/geometry/core/coordinate_system.hpp>
  28 #include <boost/geometry/core/coordinate_type.hpp>
  29 #include <boost/geometry/core/cs.hpp>
  30 #include <boost/geometry/core/srs.hpp>
  31 #include <boost/geometry/core/point_type.hpp>
  32 #include <boost/geometry/core/radian_access.hpp>
  33 #include <boost/geometry/core/tags.hpp>
  34
  35 #include <boost/geometry/util/math.hpp>
  36
  37 #include <boost/geometry/geometries/helper_geometry.hpp>
  38
  39 #include <boost/geometry/formulas/vertex_latitude.hpp>
  40
  41 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
  42
  43 #include <boost/geometry/algorithms/detail/envelope/point.hpp>
  44 #include <boost/geometry/algorithms/detail/envelope/transform_units.hpp>
  45
  46 #include <boost/geometry/algorithms/detail/expand/point.hpp>
  47
  48 #include <boost/geometry/algorithms/dispatch/envelope.hpp>
  49
  50 namespace boost { namespace geometry
  51 {
  52
  53 #ifndef DOXYGEN_NO_DETAIL
  54 namespace detail { namespace envelope
  55 {
  56
  57 template <typename CalculationType, typename CS_Tag>
  58 struct envelope_segment_call_vertex_latitude
  59 {
  60     template <typename T1, typename T2, typename Strategy>
  61     static inline CalculationType apply(T1 const& lat1,
  62                                         T2 const& alp1,
  63                                         Strategy const& )
  64     {
  65         return geometry::formula::vertex_latitude<CalculationType, CS_Tag>
  66             ::apply(lat1, alp1);
  67     }
  68 };
  69
  70 template <typename CalculationType>
  71 struct envelope_segment_call_vertex_latitude<CalculationType, geographic_tag>
  72 {
  73     template <typename T1, typename T2, typename Strategy>
  74     static inline CalculationType apply(T1 const& lat1,
  75                                         T2 const& alp1,
  76                                         Strategy const& strategy)
  77     {
  78         return geometry::formula::vertex_latitude<CalculationType, geographic_tag>
  79             ::apply(lat1, alp1, strategy.model());
  80     }
  81 };
  82
  83 template <typename Units, typename CS_Tag>
  84 struct envelope_segment_convert_polar
  85 {
  86     template <typename T>
  87     static inline void pre(T & , T & ) {}
  88
  89     template <typename T>
  90     static inline void post(T & , T & ) {}
  91 };
  92
  93 template <typename Units>
  94 struct envelope_segment_convert_polar<Units, spherical_polar_tag>
  95 {
  96     template <typename T>
  97     static inline void pre(T & lat1, T & lat2)
  98     {
  99         lat1 = math::latitude_convert_ep<Units>(lat1);
 100         lat2 = math::latitude_convert_ep<Units>(lat2);
 101     }
 102
 103     template <typename T>
 104     static inline void post(T & lat1, T & lat2)
 105     {
 106         lat1 = math::latitude_convert_ep<Units>(lat1);
 107         lat2 = math::latitude_convert_ep<Units>(lat2);
 108         std::swap(lat1, lat2);
 109     }
 110 };
 111
 112 template <typename CS_Tag>
 113 class envelope_segment_impl
 114 {
 115 private:
 116
 117     // degrees or radians
 118     template <typename CalculationType>
 119     static inline void swap(CalculationType& lon1,
 120                             CalculationType& lat1,
 121                             CalculationType& lon2,
 122                             CalculationType& lat2)
 123     {
 124         std::swap(lon1, lon2);
 125         std::swap(lat1, lat2);
 126     }
 127
 128     // radians
 129     template <typename CalculationType>
 130     static inline bool contains_pi_half(CalculationType const& a1,
 131                                         CalculationType const& a2)
 132     {
 133         // azimuths a1 and a2 are assumed to be in radians
 134         BOOST_GEOMETRY_ASSERT(! math::equals(a1, a2));
 135
 136         static CalculationType const pi_half = math::half_pi<CalculationType>();
 137
 138         return (a1 < a2)
 139                 ? (a1 < pi_half && pi_half < a2)
 140                 : (a1 > pi_half && pi_half > a2);
 141     }
 142
 143     // radians or degrees
 144     template <typename Units, typename CoordinateType>
 145     static inline bool crosses_antimeridian(CoordinateType const& lon1,
 146                                             CoordinateType const& lon2)
 147     {
 148         typedef math::detail::constants_on_spheroid
 149             <
 150                 CoordinateType, Units
 151             > constants;
 152
 153         return math::abs(lon1 - lon2) > constants::half_period(); // > pi
 154     }
 155
 156     // degrees or radians
 157     template <typename Units, typename CalculationType, typename Strategy>
 158     static inline void compute_box_corners(CalculationType& lon1,
 159                                            CalculationType& lat1,
 160                                            CalculationType& lon2,
 161                                            CalculationType& lat2,
 162                                            CalculationType a1,
 163                                            CalculationType a2,
 164                                            Strategy const& strategy)
 165     {
 166         // coordinates are assumed to be in radians
 167         BOOST_GEOMETRY_ASSERT(lon1 <= lon2);
 168
 169         CalculationType lat1_rad = math::as_radian<Units>(lat1);
 170         CalculationType lat2_rad = math::as_radian<Units>(lat2);
 171
 172         if (lat1 > lat2)
 173         {
 174             std::swap(lat1, lat2);
 175             std::swap(lat1_rad, lat2_rad);
 176             std::swap(a1, a2);
 177         }
 178
 179         if (math::equals(a1, a2))
 180         {
 181             // the segment must lie on the equator or is very short
 182             return;
 183         }
 184
 185         if (contains_pi_half(a1, a2))
 186         {
 187             CalculationType p_max = envelope_segment_call_vertex_latitude
 188                 <CalculationType, CS_Tag>::apply(lat1_rad, a1, strategy);
 189
 190             CalculationType const mid_lat = lat1 + lat2;
 191             if (mid_lat < 0)
 192             {
 193                 // update using min latitude
 194                 CalculationType const lat_min_rad = -p_max;
 195                 CalculationType const lat_min
 196                     = math::from_radian<Units>(lat_min_rad);
 197
 198                 if (lat1 > lat_min)
 199                 {
 200                     lat1 = lat_min;
 201                 }
 202             }
 203             else
 204             {
 205                 // update using max latitude
 206                 CalculationType const lat_max_rad = p_max;
 207                 CalculationType const lat_max
 208                     = math::from_radian<Units>(lat_max_rad);
 209
 210                 if (lat2 < lat_max)
 211                 {
 212                     lat2 = lat_max;
 213                 }
 214             }
 215         }
 216     }
 217
 218     template <typename Units, typename CalculationType>
 219     static inline void special_cases(CalculationType& lon1,
 220                                      CalculationType& lat1,
 221                                      CalculationType& lon2,
 222                                      CalculationType& lat2)
 223     {
 224         typedef math::detail::constants_on_spheroid
 225             <
 226                 CalculationType, Units
 227             > constants;
 228
 229         bool is_pole1 = math::equals(math::abs(lat1), constants::max_latitude());
 230         bool is_pole2 = math::equals(math::abs(lat2), constants::max_latitude());
 231
 232         if (is_pole1 && is_pole2)
 233         {
 234             // both points are poles; nothing more to do:
 235             // longitudes are already normalized to 0
 236             // but just in case
 237             lon1 = 0;
 238             lon2 = 0;
 239         }
 240         else if (is_pole1 && !is_pole2)
 241         {
 242             // first point is a pole, second point is not:
 243             // make the longitude of the first point the same as that
 244             // of the second point
 245             lon1 = lon2;
 246         }
 247         else if (!is_pole1 && is_pole2)
 248         {
 249             // second point is a pole, first point is not:
 250             // make the longitude of the second point the same as that
 251             // of the first point
 252             lon2 = lon1;
 253         }
 254
 255         if (lon1 == lon2)
 256         {
 257             // segment lies on a meridian
 258             if (lat1 > lat2)
 259             {
 260                 std::swap(lat1, lat2);
 261             }
 262             return;
 263         }
 264
 265         BOOST_GEOMETRY_ASSERT(!is_pole1 && !is_pole2);
 266
 267         if (lon1 > lon2)
 268         {
 269             swap(lon1, lat1, lon2, lat2);
 270         }
 271
 272         if (crosses_antimeridian<Units>(lon1, lon2))
 273         {
 274             lon1 += constants::period();
 275             swap(lon1, lat1, lon2, lat2);
 276         }
 277     }
 278
 279     template
 280     <
 281         typename Units,
 282         typename CalculationType,
 283         typename Box
 284     >
 285     static inline void create_box(CalculationType lon1,
 286                                   CalculationType lat1,
 287                                   CalculationType lon2,
 288                                   CalculationType lat2,
 289                                   Box& mbr)
 290     {
 291         typedef typename coordinate_type<Box>::type box_coordinate_type;
 292
 293         typedef typename helper_geometry
 294             <
 295                 Box, box_coordinate_type, Units
 296             >::type helper_box_type;
 297
 298         helper_box_type helper_mbr;
 299
 300         geometry::set
 301             <
 302                 min_corner, 0
 303             >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lon1));
 304
 305         geometry::set
 306             <
 307                 min_corner, 1
 308             >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lat1));
 309
 310         geometry::set
 311             <
 312                 max_corner, 0
 313             >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lon2));
 314
 315         geometry::set
 316             <
 317                 max_corner, 1
 318             >(helper_mbr, boost::numeric_cast<box_coordinate_type>(lat2));
 319
 320         transform_units(helper_mbr, mbr);
 321     }
 322
 323
 324     template <typename Units, typename CalculationType, typename Strategy>
 325     static inline void apply(CalculationType& lon1,
 326                              CalculationType& lat1,
 327                              CalculationType& lon2,
 328                              CalculationType& lat2,
 329                              Strategy const& strategy)
 330     {
 331         special_cases<Units>(lon1, lat1, lon2, lat2);
 332
 333         CalculationType lon1_rad = math::as_radian<Units>(lon1);
 334         CalculationType lat1_rad = math::as_radian<Units>(lat1);
 335         CalculationType lon2_rad = math::as_radian<Units>(lon2);
 336         CalculationType lat2_rad = math::as_radian<Units>(lat2);
 337         CalculationType alp1, alp2;
 338         strategy.apply(lon1_rad, lat1_rad, lon2_rad, lat2_rad, alp1, alp2);
 339
 340         compute_box_corners<Units>(lon1, lat1, lon2, lat2, alp1, alp2, strategy);
 341     }
 342
 343     template <typename Units, typename CalculationType, typename Strategy>
 344     static inline void apply(CalculationType& lon1,
 345                              CalculationType& lat1,
 346                              CalculationType& lon2,
 347                              CalculationType& lat2,
 348                              Strategy const& strategy,
 349                              CalculationType alp1)
 350     {
 351         special_cases<Units>(lon1, lat1, lon2, lat2);
 352
 353         CalculationType lon1_rad = math::as_radian<Units>(lon1);
 354         CalculationType lat1_rad = math::as_radian<Units>(lat1);
 355         CalculationType lon2_rad = math::as_radian<Units>(lon2);
 356         CalculationType lat2_rad = math::as_radian<Units>(lat2);
 357         CalculationType alp2;
 358         strategy.apply(lon2_rad, lat2_rad, lon1_rad, lat1_rad, alp2);
 359         alp2 += math::pi<CalculationType>();
 360
 361         compute_box_corners<Units>(lon1, lat1, lon2, lat2, alp1, alp2, strategy);
 362     }
 363
 364 public:
 365     template
 366     <
 367         typename Units,
 368         typename CalculationType,
 369         typename Box,
 370         typename Strategy
 371     >
 372     static inline void apply(CalculationType lon1,
 373                              CalculationType lat1,
 374                              CalculationType lon2,
 375                              CalculationType lat2,
 376                              Box& mbr,
 377                              Strategy const& strategy)
 378     {
 379         typedef envelope_segment_convert_polar<Units, typename cs_tag<Box>::type> convert_polar;
 380
 381         convert_polar::pre(lat1, lat2);
 382
 383         apply<Units>(lon1, lat1, lon2, lat2, strategy);
 384
 385         convert_polar::post(lat1, lat2);
 386
 387         create_box<Units>(lon1, lat1, lon2, lat2, mbr);
 388     }
 389
 390     template
 391     <
 392         typename Units,
 393         typename CalculationType,
 394         typename Box,
 395         typename Strategy
 396     >
 397     static inline void apply(CalculationType lon1,
 398                              CalculationType lat1,
 399                              CalculationType lon2,
 400                              CalculationType lat2,
 401                              Box& mbr,
 402                              Strategy const& strategy,
 403                              CalculationType alp1)
 404     {
 405         typedef envelope_segment_convert_polar<Units, typename cs_tag<Box>::type> convert_polar;
 406
 407         convert_polar::pre(lat1, lat2);
 408
 409         apply<Units>(lon1, lat1, lon2, lat2, strategy, alp1);
 410
 411         convert_polar::post(lat1, lat2);
 412
 413         create_box<Units>(lon1, lat1, lon2, lat2, mbr);
 414     }
 415 };
 416
 417 template <std::size_t Dimension, std::size_t DimensionCount>
 418 struct envelope_one_segment
 419 {
 420     template<typename Point, typename Box, typename Strategy>
 421     static inline void apply(Point const& p1,
 422                              Point const& p2,
 423                              Box& mbr,
 424                              Strategy const& strategy)
 425     {
 426         envelope_one_point<Dimension, DimensionCount>::apply(p1, mbr, strategy);
 427         detail::expand::point_loop
 428             <
 429                 Dimension,
 430                 DimensionCount
 431             >::apply(mbr, p2, strategy);
 432     }
 433 };
 434
 435
 436 template <std::size_t DimensionCount>
 437 struct envelope_segment
 438 {
 439     template <typename Point, typename Box, typename Strategy>
 440     static inline void apply(Point const& p1,
 441                              Point const& p2,
 442                              Box& mbr,
 443                              Strategy const& strategy)
 444     {
 445         // first compute the envelope range for the first two coordinates
 446         strategy.apply(p1, p2, mbr);
 447
 448         // now compute the envelope range for coordinates of
 449         // dimension 2 and higher
 450         envelope_one_segment<2, DimensionCount>::apply(p1, p2, mbr, strategy);
 451     }
 452
 453     template <typename Segment, typename Box, typename Strategy>
 454     static inline void apply(Segment const& segment, Box& mbr,
 455                              Strategy const& strategy)
 456     {
 457         typename point_type<Segment>::type p[2];
 458         detail::assign_point_from_index<0>(segment, p[0]);
 459         detail::assign_point_from_index<1>(segment, p[1]);
 460         apply(p[0], p[1], mbr, strategy);
 461     }
 462 };
 463
 464 }} // namespace detail::envelope
 465 #endif // DOXYGEN_NO_DETAIL
 466
 467
 468 #ifndef DOXYGEN_NO_DISPATCH
 469 namespace dispatch
 470 {
 471
 472
 473 template <typename Segment>
 474 struct envelope<Segment, segment_tag>
 475 {
 476     template <typename Box, typename Strategy>
 477     static inline void apply(Segment const& segment,
 478                              Box& mbr,
 479                              Strategy const& strategy)
 480     {
 481         typename point_type<Segment>::type p[2];
 482         detail::assign_point_from_index<0>(segment, p[0]);
 483         detail::assign_point_from_index<1>(segment, p[1]);
 484         detail::envelope::envelope_segment
 485             <
 486                dimension<Segment>::value
 487             >::apply(p[0], p[1], mbr, strategy);
 488     }
 489 };
 490
 491 } // namespace dispatch
 492 #endif // DOXYGEN_NO_DISPATCH
 493
 494 }} // namespace boost::geometry
 495
 496 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_SEGMENT_HPP