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 longitude_interval(T const & left,T const & right)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> get() const58 reference_type get() const 59 { 60 return m_end[Index]; 61 } 62 length() const63 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> operator ()boost::geometry::detail::envelope::envelope_range_of_longitudes::longitude_less80 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> applyboost::geometry::detail::envelope::envelope_range_of_longitudes88 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> applyboost::geometry::detail::envelope::envelope_range_of_boxes_by_expansion153 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> operator ()boost::geometry::detail::envelope::envelope_range_of_boxes::latitude_less221 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> applyboost::geometry::detail::envelope::envelope_range_of_boxes229 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 327