1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2015-2016, 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 
8 // Distributed under the Boost Software License, Version 1.0.
9 // (See accompanying file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 
12 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP
13 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP
14 
15 #include <cstddef>
16 
17 #include <algorithm>
18 #include <vector>
19 
20 #include <boost/range.hpp>
21 
22 #include <boost/geometry/core/access.hpp>
23 #include <boost/geometry/core/assert.hpp>
24 #include <boost/geometry/core/coordinate_system.hpp>
25 #include <boost/geometry/core/coordinate_type.hpp>
26 
27 #include <boost/geometry/util/math.hpp>
28 #include <boost/geometry/util/range.hpp>
29 
30 #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
31 #include <boost/geometry/algorithms/detail/max_interval_gap.hpp>
32 #include <boost/geometry/algorithms/detail/expand/indexed.hpp>
33 
34 
35 namespace boost { namespace geometry
36 {
37 
38 #ifndef DOXYGEN_NO_DETAIL
39 namespace detail { namespace envelope
40 {
41 
42 
43 template <typename T>
44 class longitude_interval
45 {
46     typedef T const& reference_type;
47 
48 public:
49     typedef T value_type;
50     typedef T difference_type;
51 
longitude_interval(T const & left,T const & right)52     longitude_interval(T const& left, T const& right)
53     {
54         m_end[0] = left;
55         m_end[1] = right;
56     }
57 
58     template <std::size_t Index>
get() const59     reference_type get() const
60     {
61         return m_end[Index];
62     }
63 
length() const64     difference_type length() const
65     {
66         return get<1>() - get<0>();
67     }
68 
69 private:
70     T m_end[2];
71 };
72 
73 
74 template <typename Units>
75 struct envelope_range_of_longitudes
76 {
77     template <std::size_t Index>
78     struct longitude_less
79     {
80         template <typename Interval>
operator ()boost::geometry::detail::envelope::envelope_range_of_longitudes::longitude_less81         inline bool operator()(Interval const& i1, Interval const& i2) const
82         {
83             return math::smaller(i1.template get<Index>(),
84                                  i2.template get<Index>());
85         }
86     };
87 
88     template <typename RangeOfLongitudeIntervals, typename Longitude>
applyboost::geometry::detail::envelope::envelope_range_of_longitudes89     static inline void apply(RangeOfLongitudeIntervals const& range,
90                              Longitude& lon_min, Longitude& lon_max)
91     {
92         typedef typename math::detail::constants_on_spheroid
93             <
94                 Longitude, Units
95             > constants;
96 
97         Longitude const zero = 0;
98         Longitude const period = constants::period();
99 
100         lon_min = lon_max = zero;
101 
102         // the range of longitude intervals can be empty if all input boxes
103         // degenerate to the north or south pole (or combination of the two)
104         // in this case the initialization values for lon_min and
105         // lon_max are valid choices
106         if (! boost::empty(range))
107         {
108             lon_min = std::min_element(boost::begin(range),
109                                        boost::end(range),
110                                        longitude_less<0>())->template get<0>();
111             lon_max = std::max_element(boost::begin(range),
112                                        boost::end(range),
113                                        longitude_less<1>())->template get<1>();
114 
115             if (math::larger(lon_max - lon_min, constants::half_period()))
116             {
117                 Longitude max_gap_left, max_gap_right;
118                 Longitude max_gap = geometry::maximum_gap(range,
119                                                           max_gap_left,
120                                                           max_gap_right);
121 
122                 BOOST_GEOMETRY_ASSERT(! math::larger(lon_min, lon_max));
123                 BOOST_GEOMETRY_ASSERT
124                     (! math::larger(lon_max, constants::max_longitude()));
125                 BOOST_GEOMETRY_ASSERT
126                     (! math::smaller(lon_min, constants::min_longitude()));
127 
128                 BOOST_GEOMETRY_ASSERT
129                     (! math::larger(max_gap_left, max_gap_right));
130                 BOOST_GEOMETRY_ASSERT
131                     (! math::larger(max_gap_right, constants::max_longitude()));
132                 BOOST_GEOMETRY_ASSERT
133                     (! math::smaller(max_gap_left, constants::min_longitude()));
134 
135                 if (math::larger(max_gap, zero))
136                 {
137                     Longitude wrapped_gap = period + lon_min - lon_max;
138                     if (math::larger(max_gap, wrapped_gap))
139                     {
140                         lon_min = max_gap_right;
141                         lon_max = max_gap_left + period;
142                     }
143                 }
144             }
145         }
146     }
147 };
148 
149 
150 template <std::size_t Dimension, std::size_t DimensionCount>
151 struct envelope_range_of_boxes_by_expansion
152 {
153     template <typename RangeOfBoxes, typename Box, typename Strategy>
applyboost::geometry::detail::envelope::envelope_range_of_boxes_by_expansion154     static inline void apply(RangeOfBoxes const& range_of_boxes,
155                              Box& mbr,
156                              Strategy const& strategy)
157     {
158         typedef typename boost::range_value<RangeOfBoxes>::type box_type;
159 
160         typedef typename boost::range_iterator
161             <
162                 RangeOfBoxes const
163             >::type iterator_type;
164 
165         // first initialize MBR
166         detail::indexed_point_view<Box, min_corner> mbr_min(mbr);
167         detail::indexed_point_view<Box, max_corner> mbr_max(mbr);
168 
169         detail::indexed_point_view<box_type const, min_corner>
170             first_box_min(range::front(range_of_boxes));
171 
172         detail::indexed_point_view<box_type const, max_corner>
173             first_box_max(range::front(range_of_boxes));
174 
175         detail::conversion::point_to_point
176             <
177                 detail::indexed_point_view<box_type const, min_corner>,
178                 detail::indexed_point_view<Box, min_corner>,
179                 Dimension,
180                 DimensionCount
181             >::apply(first_box_min, mbr_min);
182 
183         detail::conversion::point_to_point
184             <
185                 detail::indexed_point_view<box_type const, max_corner>,
186                 detail::indexed_point_view<Box, max_corner>,
187                 Dimension,
188                 DimensionCount
189             >::apply(first_box_max, mbr_max);
190 
191         // now expand using the remaining boxes
192         iterator_type it = boost::begin(range_of_boxes);
193         for (++it; it != boost::end(range_of_boxes); ++it)
194         {
195             detail::expand::indexed_loop
196                 <
197                     strategy::compare::default_strategy,
198                     strategy::compare::default_strategy,
199                     min_corner,
200                     Dimension,
201                     DimensionCount
202                 >::apply(mbr, *it, strategy);
203 
204             detail::expand::indexed_loop
205                 <
206                     strategy::compare::default_strategy,
207                     strategy::compare::default_strategy,
208                     max_corner,
209                     Dimension,
210                     DimensionCount
211                 >::apply(mbr, *it, strategy);
212         }
213     }
214 
215 };
216 
217 
218 struct envelope_range_of_boxes
219 {
220     template <std::size_t Index>
221     struct latitude_less
222     {
223         template <typename Box>
operator ()boost::geometry::detail::envelope::envelope_range_of_boxes::latitude_less224         inline bool operator()(Box const& box1, Box const& box2) const
225         {
226             return math::smaller(geometry::get<Index, 1>(box1),
227                                  geometry::get<Index, 1>(box2));
228         }
229     };
230 
231     template <typename RangeOfBoxes, typename Box, typename Strategy>
applyboost::geometry::detail::envelope::envelope_range_of_boxes232     static inline void apply(RangeOfBoxes const& range_of_boxes,
233                              Box& mbr,
234                              Strategy const& strategy)
235     {
236         // boxes in the range are assumed to be normalized already
237 
238         typedef typename boost::range_value<RangeOfBoxes>::type box_type;
239         typedef typename coordinate_type<box_type>::type coordinate_type;
240         typedef typename coordinate_system<box_type>::type::units units_type;
241         typedef typename boost::range_iterator
242             <
243                 RangeOfBoxes const
244             >::type iterator_type;
245 
246         typedef math::detail::constants_on_spheroid
247             <
248                 coordinate_type, units_type
249             > constants;
250 
251         typedef longitude_interval<coordinate_type> interval_type;
252         typedef std::vector<interval_type> interval_range_type;
253 
254         BOOST_GEOMETRY_ASSERT(! boost::empty(range_of_boxes));
255 
256         iterator_type it_min = std::min_element(boost::begin(range_of_boxes),
257                                                 boost::end(range_of_boxes),
258                                                 latitude_less<min_corner>());
259         iterator_type it_max = std::max_element(boost::begin(range_of_boxes),
260                                                 boost::end(range_of_boxes),
261                                                 latitude_less<max_corner>());
262 
263         coordinate_type const min_longitude = constants::min_longitude();
264         coordinate_type const max_longitude = constants::max_longitude();
265         coordinate_type const period = constants::period();
266 
267         interval_range_type intervals;
268         for (iterator_type it = boost::begin(range_of_boxes);
269              it != boost::end(range_of_boxes);
270              ++it)
271         {
272             coordinate_type lat_min = geometry::get<min_corner, 1>(*it);
273             coordinate_type lat_max = geometry::get<max_corner, 1>(*it);
274             if (math::equals(lat_min, constants::max_latitude())
275                 || math::equals(lat_max, constants::min_latitude()))
276             {
277                 // if the box degenerates to the south or north pole
278                 // just ignore it
279                 continue;
280             }
281 
282             coordinate_type lon_left = geometry::get<min_corner, 0>(*it);
283             coordinate_type lon_right = geometry::get<max_corner, 0>(*it);
284 
285             if (math::larger(lon_right, max_longitude))
286             {
287                 intervals.push_back(interval_type(lon_left, max_longitude));
288                 intervals.push_back
289                     (interval_type(min_longitude, lon_right - period));
290             }
291             else
292             {
293                 intervals.push_back(interval_type(lon_left, lon_right));
294             }
295         }
296 
297         coordinate_type lon_min = 0;
298         coordinate_type lon_max = 0;
299         envelope_range_of_longitudes
300             <
301                 units_type
302             >::apply(intervals, lon_min, lon_max);
303 
304         // do not convert units; conversion will be performed at a
305         // higher level
306 
307         // assign now the min/max longitude/latitude values
308         detail::indexed_point_view<Box, min_corner> mbr_min(mbr);
309         detail::indexed_point_view<Box, max_corner> mbr_max(mbr);
310 
311         geometry::set<0>(mbr_min, lon_min);
312         geometry::set<1>(mbr_min, geometry::get<min_corner, 1>(*it_min));
313         geometry::set<0>(mbr_max, lon_max);
314         geometry::set<1>(mbr_max, geometry::get<max_corner, 1>(*it_max));
315 
316         // what remains to be done is to compute the envelope range
317         // for the remaining dimensions (if any)
318         envelope_range_of_boxes_by_expansion
319             <
320                 2, dimension<Box>::value
321             >::apply(range_of_boxes, mbr, strategy);
322     }
323 };
324 
325 
326 }} // namespace detail::envelope
327 #endif // DOXYGEN_NO_DETAIL
328 
329 }} // namespace boost::geometry
330 
331 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_ENVELOPE_RANGE_OF_BOXES_HPP
332