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 longitude_interval(T const & left,T const & right)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> get() const63 reference_type get() const 64 { 65 return m_end[Index]; 66 } 67 length() const68 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> operator ()boost::geometry::detail::envelope::envelope_range_of_longitudes::longitude_less85 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> applyboost::geometry::detail::envelope::envelope_range_of_longitudes93 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> applyboost::geometry::detail::envelope::envelope_range_of_boxes_by_expansion158 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> operator ()boost::geometry::detail::envelope::envelope_range_of_boxes::latitude_less222 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> applyboost::geometry::detail::envelope::envelope_range_of_boxes230 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 339