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