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