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

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