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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2015-2017, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
   6 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   8
   9 // Distributed under the Boost Software License, Version 1.0.
  10 // (See accompanying file LICENSE_1_0.txt or copy at
  11 // http://www.boost.org/LICENSE_1_0.txt)
  12
  13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP
  14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP
  15
  16 #include <cstddef>
  17
  18 #include <algorithm>
  19 #include <vector>
  20
  21 #include <boost/range.hpp>
  22
  23 #include <boost/geometry/core/access.hpp>
  24 #include <boost/geometry/core/assert.hpp>
  25 #include <boost/geometry/core/coordinate_system.hpp>
  26 #include <boost/geometry/core/coordinate_type.hpp>
  27
  28 #include <boost/geometry/util/math.hpp>
  29 #include <boost/geometry/util/range.hpp>
  30
  31 #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
  32 #include <boost/geometry/algorithms/detail/max_interval_gap.hpp>
  33 #include <boost/geometry/algorithms/detail/expand/indexed.hpp>
  34
  35
  36 namespace boost { namespace geometry
  37 {
  38
  39 #ifndef DOXYGEN_NO_DETAIL
  40 namespace detail { namespace envelope
  41 {
  42
  43
  44 template <typename T>
  45 class longitude_interval
  46 {
  47     typedef T const& reference_type;
  48
  49 public:
  50     typedef T value_type;
  51     typedef T difference_type;
  52
  53     longitude_interval(T const& left, T const& right)
  54     {
  55         m_end[0] = left;
  56         m_end[1] = right;
  57     }
  58
  59     template <std::size_t Index>
  60     reference_type get() const
  61     {
  62         return m_end[Index];
  63     }
  64
  65     difference_type length() const
  66     {
  67         return get<1>() - get<0>();
  68     }
  69
  70 private:
  71     T m_end[2];
  72 };
  73
  74
  75 template <typename Units>
  76 struct envelope_range_of_longitudes
  77 {
  78     template <std::size_t Index>
  79     struct longitude_less
  80     {
  81         template <typename Interval>
  82         inline bool operator()(Interval const& i1, Interval const& i2) const
  83         {
  84             return math::smaller(i1.template get<Index>(),
  85                                  i2.template get<Index>());
  86         }
  87     };
  88
  89     template <typename RangeOfLongitudeIntervals, typename Longitude>
  90     static inline void apply(RangeOfLongitudeIntervals const& range,
  91                              Longitude& lon_min, Longitude& lon_max)
  92     {
  93         typedef typename math::detail::constants_on_spheroid
  94             <
  95                 Longitude, Units
  96             > constants;
  97
  98         Longitude const zero = 0;
  99         Longitude const period = constants::period();
 100
 101         lon_min = lon_max = zero;
 102
 103         // the range of longitude intervals can be empty if all input boxes
 104         // degenerate to the north or south pole (or combination of the two)
 105         // in this case the initialization values for lon_min and
 106         // lon_max are valid choices
 107         if (! boost::empty(range))
 108         {
 109             lon_min = std::min_element(boost::begin(range),
 110                                        boost::end(range),
 111                                        longitude_less<0>())->template get<0>();
 112             lon_max = std::max_element(boost::begin(range),
 113                                        boost::end(range),
 114                                        longitude_less<1>())->template get<1>();
 115
 116             if (math::larger(lon_max - lon_min, constants::half_period()))
 117             {
 118                 Longitude max_gap_left, max_gap_right;
 119                 Longitude max_gap = geometry::maximum_gap(range,
 120                                                           max_gap_left,
 121                                                           max_gap_right);
 122
 123                 BOOST_GEOMETRY_ASSERT(! math::larger(lon_min, lon_max));
 124                 BOOST_GEOMETRY_ASSERT
 125                     (! math::larger(lon_max, constants::max_longitude()));
 126                 BOOST_GEOMETRY_ASSERT
 127                     (! math::smaller(lon_min, constants::min_longitude()));
 128
 129                 BOOST_GEOMETRY_ASSERT
 130                     (! math::larger(max_gap_left, max_gap_right));
 131                 BOOST_GEOMETRY_ASSERT
 132                     (! math::larger(max_gap_right, constants::max_longitude()));
 133                 BOOST_GEOMETRY_ASSERT
 134                     (! math::smaller(max_gap_left, constants::min_longitude()));
 135
 136                 if (math::larger(max_gap, zero))
 137                 {
 138                     Longitude wrapped_gap = period + lon_min - lon_max;
 139                     if (math::larger(max_gap, wrapped_gap))
 140                     {
 141                         lon_min = max_gap_right;
 142                         lon_max = max_gap_left + period;
 143                     }
 144                 }
 145             }
 146         }
 147     }
 148 };
 149
 150
 151 template <std::size_t Dimension, std::size_t DimensionCount>
 152 struct envelope_range_of_boxes_by_expansion
 153 {
 154     template <typename RangeOfBoxes, typename Box, typename Strategy>
 155     static inline void apply(RangeOfBoxes const& range_of_boxes,
 156                              Box& mbr,
 157                              Strategy const& strategy)
 158     {
 159         typedef typename boost::range_value<RangeOfBoxes>::type box_type;
 160
 161         typedef typename boost::range_iterator
 162             <
 163                 RangeOfBoxes const
 164             >::type iterator_type;
 165
 166         // first initialize MBR
 167         detail::indexed_point_view<Box, min_corner> mbr_min(mbr);
 168         detail::indexed_point_view<Box, max_corner> mbr_max(mbr);
 169
 170         detail::indexed_point_view<box_type const, min_corner>
 171             first_box_min(range::front(range_of_boxes));
 172
 173         detail::indexed_point_view<box_type const, max_corner>
 174             first_box_max(range::front(range_of_boxes));
 175
 176         detail::conversion::point_to_point
 177             <
 178                 detail::indexed_point_view<box_type const, min_corner>,
 179                 detail::indexed_point_view<Box, min_corner>,
 180                 Dimension,
 181                 DimensionCount
 182             >::apply(first_box_min, mbr_min);
 183
 184         detail::conversion::point_to_point
 185             <
 186                 detail::indexed_point_view<box_type const, max_corner>,
 187                 detail::indexed_point_view<Box, max_corner>,
 188                 Dimension,
 189                 DimensionCount
 190             >::apply(first_box_max, mbr_max);
 191
 192         // now expand using the remaining boxes
 193         iterator_type it = boost::begin(range_of_boxes);
 194         for (++it; it != boost::end(range_of_boxes); ++it)
 195         {
 196             detail::expand::indexed_loop
 197                 <
 198                     min_corner,
 199                     Dimension,
 200                     DimensionCount
 201                 >::apply(mbr, *it, strategy);
 202
 203             detail::expand::indexed_loop
 204                 <
 205                     max_corner,
 206                     Dimension,
 207                     DimensionCount
 208                 >::apply(mbr, *it, strategy);
 209         }
 210     }
 211
 212 };
 213
 214
 215 struct envelope_range_of_boxes
 216 {
 217     template <std::size_t Index>
 218     struct latitude_less
 219     {
 220         template <typename Box>
 221         inline bool operator()(Box const& box1, Box const& box2) const
 222         {
 223             return math::smaller(geometry::get<Index, 1>(box1),
 224                                  geometry::get<Index, 1>(box2));
 225         }
 226     };
 227
 228     template <typename RangeOfBoxes, typename Box, typename Strategy>
 229     static inline void apply(RangeOfBoxes const& range_of_boxes,
 230                              Box& mbr,
 231                              Strategy const& strategy)
 232     {
 233         // boxes in the range are assumed to be normalized already
 234
 235         typedef typename boost::range_value<RangeOfBoxes>::type box_type;
 236         typedef typename coordinate_type<box_type>::type coordinate_type;
 237         typedef typename coordinate_system<box_type>::type::units units_type;
 238         typedef typename boost::range_iterator
 239             <
 240                 RangeOfBoxes const
 241             >::type iterator_type;
 242
 243         static const bool is_equatorial = ! boost::is_same
 244                                             <
 245                                                 typename cs_tag<box_type>::type,
 246                                                 spherical_polar_tag
 247                                             >::value;
 248
 249         typedef math::detail::constants_on_spheroid
 250             <
 251                 coordinate_type, units_type, is_equatorial
 252             > constants;
 253
 254         typedef longitude_interval<coordinate_type> interval_type;
 255         typedef std::vector<interval_type> interval_range_type;
 256
 257         BOOST_GEOMETRY_ASSERT(! boost::empty(range_of_boxes));
 258
 259         iterator_type it_min = std::min_element(boost::begin(range_of_boxes),
 260                                                 boost::end(range_of_boxes),
 261                                                 latitude_less<min_corner>());
 262         iterator_type it_max = std::max_element(boost::begin(range_of_boxes),
 263                                                 boost::end(range_of_boxes),
 264                                                 latitude_less<max_corner>());
 265
 266         coordinate_type const min_longitude = constants::min_longitude();
 267         coordinate_type const max_longitude = constants::max_longitude();
 268         coordinate_type const period = constants::period();
 269
 270         interval_range_type intervals;
 271         for (iterator_type it = boost::begin(range_of_boxes);
 272              it != boost::end(range_of_boxes);
 273              ++it)
 274         {
 275             coordinate_type lat_min = geometry::get<min_corner, 1>(*it);
 276             coordinate_type lat_max = geometry::get<max_corner, 1>(*it);
 277             if (math::equals(lat_min, constants::max_latitude())
 278                 || math::equals(lat_max, constants::min_latitude()))
 279             {
 280                 // if the box degenerates to the south or north pole
 281                 // just ignore it
 282                 continue;
 283             }
 284
 285             coordinate_type lon_left = geometry::get<min_corner, 0>(*it);
 286             coordinate_type lon_right = geometry::get<max_corner, 0>(*it);
 287
 288             if (math::larger(lon_right, max_longitude))
 289             {
 290                 intervals.push_back(interval_type(lon_left, max_longitude));
 291                 intervals.push_back
 292                     (interval_type(min_longitude, lon_right - period));
 293             }
 294             else
 295             {
 296                 intervals.push_back(interval_type(lon_left, lon_right));
 297             }
 298         }
 299
 300         coordinate_type lon_min = 0;
 301         coordinate_type lon_max = 0;
 302         envelope_range_of_longitudes
 303             <
 304                 units_type
 305             >::apply(intervals, lon_min, lon_max);
 306
 307         // do not convert units; conversion will be performed at a
 308         // higher level
 309
 310         // assign now the min/max longitude/latitude values
 311         detail::indexed_point_view<Box, min_corner> mbr_min(mbr);
 312         detail::indexed_point_view<Box, max_corner> mbr_max(mbr);
 313
 314         geometry::set<0>(mbr_min, lon_min);
 315         geometry::set<1>(mbr_min, geometry::get<min_corner, 1>(*it_min));
 316         geometry::set<0>(mbr_max, lon_max);
 317         geometry::set<1>(mbr_max, geometry::get<max_corner, 1>(*it_max));
 318
 319         // what remains to be done is to compute the envelope range
 320         // for the remaining dimensions (if any)
 321         envelope_range_of_boxes_by_expansion
 322             <
 323                 2, dimension<Box>::value
 324             >::apply(range_of_boxes, mbr, strategy);
 325     }
 326 };
 327
 328
 329 }} // namespace detail::envelope
 330 #endif // DOXYGEN_NO_DETAIL
 331
 332 }} // namespace boost::geometry
 333
 334 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP