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