detail/envelope/range_of_boxes.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2015-2020, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0006 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0007 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0008
0009 // Distributed under the Boost Software License, Version 1.0.
0010 // (See accompanying file LICENSE_1_0.txt or copy at
0011 // http://www.boost.org/LICENSE_1_0.txt)
0012
0013 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP
0014 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP
0015
0016 #include <algorithm>
0017 #include <cstddef>
0018 #include <type_traits>
0019 #include <vector>
0020
0021 #include <boost/range/begin.hpp>
0022 #include <boost/range/empty.hpp>
0023 #include <boost/range/end.hpp>
0024 #include <boost/range/value_type.hpp>
0025
0026 #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
0027 #include <boost/geometry/algorithms/detail/max_interval_gap.hpp>
0028 #include <boost/geometry/algorithms/detail/expand/indexed.hpp>
0029
0030 #include <boost/geometry/core/access.hpp>
0031 #include <boost/geometry/core/assert.hpp>
0032 #include <boost/geometry/core/coordinate_system.hpp>
0033 #include <boost/geometry/core/coordinate_type.hpp>
0034
0035 #include <boost/geometry/util/math.hpp>
0036 #include <boost/geometry/util/normalize_spheroidal_coordinates.hpp>
0037 #include <boost/geometry/util/range.hpp>
0038
0039 #include <boost/geometry/views/detail/indexed_point_view.hpp>
0040
0041
0042 namespace boost { namespace geometry
0043 {
0044
0045 #ifndef DOXYGEN_NO_DETAIL
0046 namespace detail { namespace envelope
0047 {
0048
0049
0050 template <typename T>
0051 class longitude_interval
0052 {
0053     typedef T const& reference_type;
0054
0055 public:
0056     typedef T value_type;
0057     typedef T difference_type;
0058
0059     longitude_interval(T const& left, T const& right)
0060     {
0061         m_end[0] = left;
0062         m_end[1] = right;
0063     }
0064
0065     template <std::size_t Index>
0066     reference_type get() const
0067     {
0068         return m_end[Index];
0069     }
0070
0071     difference_type length() const
0072     {
0073         return get<1>() - get<0>();
0074     }
0075
0076 private:
0077     T m_end[2];
0078 };
0079
0080
0081 template <typename Units>
0082 struct envelope_range_of_longitudes
0083 {
0084     template <std::size_t Index>
0085     struct longitude_less
0086     {
0087         template <typename Interval>
0088         inline bool operator()(Interval const& i1, Interval const& i2) const
0089         {
0090             return math::smaller(i1.template get<Index>(),
0091                                  i2.template get<Index>());
0092         }
0093     };
0094
0095     template <typename RangeOfLongitudeIntervals, typename Longitude>
0096     static inline void apply(RangeOfLongitudeIntervals const& range,
0097                              Longitude& lon_min, Longitude& lon_max)
0098     {
0099         typedef typename math::detail::constants_on_spheroid
0100             <
0101                 Longitude, Units
0102             > constants;
0103
0104         Longitude const zero = 0;
0105         Longitude const period = constants::period();
0106
0107         lon_min = lon_max = zero;
0108
0109         // the range of longitude intervals can be empty if all input boxes
0110         // degenerate to the north or south pole (or combination of the two)
0111         // in this case the initialization values for lon_min and
0112         // lon_max are valid choices
0113         if (! boost::empty(range))
0114         {
0115             lon_min = std::min_element(boost::begin(range),
0116                                        boost::end(range),
0117                                        longitude_less<0>())->template get<0>();
0118             lon_max = std::max_element(boost::begin(range),
0119                                        boost::end(range),
0120                                        longitude_less<1>())->template get<1>();
0121
0122             if (math::larger(lon_max - lon_min, constants::half_period()))
0123             {
0124                 Longitude max_gap_left, max_gap_right;
0125                 Longitude max_gap = geometry::maximum_gap(range,
0126                                                           max_gap_left,
0127                                                           max_gap_right);
0128
0129                 BOOST_GEOMETRY_ASSERT(! math::larger(lon_min, lon_max));
0130                 BOOST_GEOMETRY_ASSERT
0131                     (! math::larger(lon_max, constants::max_longitude()));
0132                 BOOST_GEOMETRY_ASSERT
0133                     (! math::smaller(lon_min, constants::min_longitude()));
0134
0135                 BOOST_GEOMETRY_ASSERT
0136                     (! math::larger(max_gap_left, max_gap_right));
0137                 BOOST_GEOMETRY_ASSERT
0138                     (! math::larger(max_gap_right, constants::max_longitude()));
0139                 BOOST_GEOMETRY_ASSERT
0140                     (! math::smaller(max_gap_left, constants::min_longitude()));
0141
0142                 if (math::larger(max_gap, zero))
0143                 {
0144                     Longitude wrapped_gap = period + lon_min - lon_max;
0145                     if (math::larger(max_gap, wrapped_gap))
0146                     {
0147                         lon_min = max_gap_right;
0148                         lon_max = max_gap_left + period;
0149                     }
0150                 }
0151             }
0152         }
0153     }
0154 };
0155
0156
0157 template <std::size_t Dimension, std::size_t DimensionCount>
0158 struct envelope_range_of_boxes_by_expansion
0159 {
0160     template <typename RangeOfBoxes, typename Box>
0161     static inline void apply(RangeOfBoxes const& range_of_boxes, Box& mbr)
0162     {
0163         typedef typename boost::range_value<RangeOfBoxes>::type box_type;
0164
0165         // first initialize MBR
0166         detail::indexed_point_view<Box, min_corner> mbr_min(mbr);
0167         detail::indexed_point_view<Box, max_corner> mbr_max(mbr);
0168
0169         detail::indexed_point_view<box_type const, min_corner>
0170             first_box_min(range::front(range_of_boxes));
0171
0172         detail::indexed_point_view<box_type const, max_corner>
0173             first_box_max(range::front(range_of_boxes));
0174
0175         detail::conversion::point_to_point
0176             <
0177                 detail::indexed_point_view<box_type const, min_corner>,
0178                 detail::indexed_point_view<Box, min_corner>,
0179                 Dimension,
0180                 DimensionCount
0181             >::apply(first_box_min, mbr_min);
0182
0183         detail::conversion::point_to_point
0184             <
0185                 detail::indexed_point_view<box_type const, max_corner>,
0186                 detail::indexed_point_view<Box, max_corner>,
0187                 Dimension,
0188                 DimensionCount
0189             >::apply(first_box_max, mbr_max);
0190
0191         // now expand using the remaining boxes
0192         auto it = boost::begin(range_of_boxes);
0193         for (++it; it != boost::end(range_of_boxes); ++it)
0194         {
0195             detail::expand::indexed_loop
0196                 <
0197                     min_corner,
0198                     Dimension,
0199                     DimensionCount
0200                 >::apply(mbr, *it);
0201
0202             detail::expand::indexed_loop
0203                 <
0204                     max_corner,
0205                     Dimension,
0206                     DimensionCount
0207                 >::apply(mbr, *it);
0208         }
0209     }
0210
0211 };
0212
0213
0214 struct envelope_range_of_boxes
0215 {
0216     template <std::size_t Index>
0217     struct latitude_less
0218     {
0219         template <typename Box>
0220         inline bool operator()(Box const& box1, Box const& box2) const
0221         {
0222             return math::smaller(geometry::get<Index, 1>(box1),
0223                                  geometry::get<Index, 1>(box2));
0224         }
0225     };
0226
0227     template <typename RangeOfBoxes, typename Box>
0228     static inline void apply(RangeOfBoxes const& range_of_boxes, Box& mbr)
0229     {
0230         // boxes in the range are assumed to be normalized already
0231
0232         typedef typename boost::range_value<RangeOfBoxes>::type box_type;
0233         typedef typename coordinate_type<box_type>::type coordinate_type;
0234         typedef typename detail::cs_angular_units<box_type>::type units_type;
0235
0236         static const bool is_equatorial = ! std::is_same
0237                                             <
0238                                                 typename cs_tag<box_type>::type,
0239                                                 spherical_polar_tag
0240                                             >::value;
0241
0242         typedef math::detail::constants_on_spheroid
0243             <
0244                 coordinate_type, units_type, is_equatorial
0245             > constants;
0246
0247         typedef longitude_interval<coordinate_type> interval_type;
0248         typedef std::vector<interval_type> interval_range_type;
0249
0250         BOOST_GEOMETRY_ASSERT(! boost::empty(range_of_boxes));
0251
0252         auto const it_min = std::min_element(boost::begin(range_of_boxes),
0253                                              boost::end(range_of_boxes),
0254                                              latitude_less<min_corner>());
0255         auto const it_max = std::max_element(boost::begin(range_of_boxes),
0256                                              boost::end(range_of_boxes),
0257                                              latitude_less<max_corner>());
0258
0259         coordinate_type const min_longitude = constants::min_longitude();
0260         coordinate_type const max_longitude = constants::max_longitude();
0261         coordinate_type const period = constants::period();
0262
0263         interval_range_type intervals;
0264         for (auto it = boost::begin(range_of_boxes);
0265              it != boost::end(range_of_boxes);
0266              ++it)
0267         {
0268             auto const& box = *it;
0269             if (is_inverse_spheroidal_coordinates(box))
0270             {
0271                 continue;
0272             }
0273
0274             coordinate_type lat_min = geometry::get<min_corner, 1>(box);
0275             coordinate_type lat_max = geometry::get<max_corner, 1>(box);
0276             if (math::equals(lat_min, constants::max_latitude())
0277                 || math::equals(lat_max, constants::min_latitude()))
0278             {
0279                 // if the box degenerates to the south or north pole
0280                 // just ignore it
0281                 continue;
0282             }
0283
0284             coordinate_type lon_left = geometry::get<min_corner, 0>(box);
0285             coordinate_type lon_right = geometry::get<max_corner, 0>(box);
0286
0287             if (math::larger(lon_right, max_longitude))
0288             {
0289                 intervals.push_back(interval_type(lon_left, max_longitude));
0290                 intervals.push_back
0291                     (interval_type(min_longitude, lon_right - period));
0292             }
0293             else
0294             {
0295                 intervals.push_back(interval_type(lon_left, lon_right));
0296             }
0297         }
0298
0299         coordinate_type lon_min = 0;
0300         coordinate_type lon_max = 0;
0301         envelope_range_of_longitudes
0302             <
0303                 units_type
0304             >::apply(intervals, lon_min, lon_max);
0305
0306         // do not convert units; conversion will be performed at a
0307         // higher level
0308
0309         // assign now the min/max longitude/latitude values
0310         detail::indexed_point_view<Box, min_corner> mbr_min(mbr);
0311         detail::indexed_point_view<Box, max_corner> mbr_max(mbr);
0312
0313         geometry::set<0>(mbr_min, lon_min);
0314         geometry::set<1>(mbr_min, geometry::get<min_corner, 1>(*it_min));
0315         geometry::set<0>(mbr_max, lon_max);
0316         geometry::set<1>(mbr_max, geometry::get<max_corner, 1>(*it_max));
0317
0318         // what remains to be done is to compute the envelope range
0319         // for the remaining dimensions (if any)
0320         envelope_range_of_boxes_by_expansion
0321             <
0322                 2, dimension<Box>::value
0323             >::apply(range_of_boxes, mbr);
0324     }
0325 };
0326
0327
0328 }} // namespace detail::envelope
0329 #endif // DOXYGEN_NO_DETAIL
0330
0331 }} // namespace boost::geometry
0332
0333 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP