1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
5 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
6 // Copyright (c) 2014-2015 Samuel Debionne, Grenoble, France.
7 
8 // This file was modified by Oracle on 2015, 2016.
9 // Modifications copyright (c) 2015-2016, Oracle and/or its affiliates.
10 
11 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
13 
14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
16 
17 // Distributed under the Boost Software License, Version 1.0.
18 // (See accompanying file LICENSE_1_0.txt or copy at
19 // http://www.boost.org/LICENSE_1_0.txt)
20 
21 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXPAND_POINT_HPP
22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXPAND_POINT_HPP
23 
24 #include <cstddef>
25 #include <algorithm>
26 
27 #include <boost/mpl/assert.hpp>
28 #include <boost/type_traits/is_same.hpp>
29 
30 #include <boost/geometry/core/access.hpp>
31 #include <boost/geometry/core/coordinate_dimension.hpp>
32 #include <boost/geometry/core/coordinate_system.hpp>
33 #include <boost/geometry/core/coordinate_type.hpp>
34 #include <boost/geometry/core/tags.hpp>
35 
36 #include <boost/geometry/util/math.hpp>
37 #include <boost/geometry/util/select_coordinate_type.hpp>
38 
39 #include <boost/geometry/strategies/compare.hpp>
40 #include <boost/geometry/policies/compare.hpp>
41 
42 #include <boost/geometry/algorithms/detail/normalize.hpp>
43 #include <boost/geometry/algorithms/detail/envelope/transform_units.hpp>
44 
45 #include <boost/geometry/algorithms/dispatch/expand.hpp>
46 
47 
48 namespace boost { namespace geometry
49 {
50 
51 #ifndef DOXYGEN_NO_DETAIL
52 namespace detail { namespace expand
53 {
54 
55 
56 template
57 <
58     typename StrategyLess, typename StrategyGreater,
59     std::size_t Dimension, std::size_t DimensionCount
60 >
61 struct point_loop
62 {
63     template <typename Box, typename Point, typename Strategy>
applyboost::geometry::detail::expand::point_loop64     static inline void apply(Box& box, Point const& source, Strategy const& strategy)
65     {
66         typedef typename strategy::compare::detail::select_strategy
67             <
68                 StrategyLess, 1, Point, Dimension
69             >::type less_type;
70 
71         typedef typename strategy::compare::detail::select_strategy
72             <
73                 StrategyGreater, -1, Point, Dimension
74             >::type greater_type;
75 
76         typedef typename select_coordinate_type
77             <
78                 Point, Box
79             >::type coordinate_type;
80 
81         less_type less;
82         greater_type greater;
83 
84         coordinate_type const coord = get<Dimension>(source);
85 
86         if (less(coord, get<min_corner, Dimension>(box)))
87         {
88             set<min_corner, Dimension>(box, coord);
89         }
90 
91         if (greater(coord, get<max_corner, Dimension>(box)))
92         {
93             set<max_corner, Dimension>(box, coord);
94         }
95 
96         point_loop
97             <
98                 StrategyLess, StrategyGreater, Dimension + 1, DimensionCount
99             >::apply(box, source, strategy);
100     }
101 };
102 
103 
104 template
105 <
106     typename StrategyLess,
107     typename StrategyGreater,
108     std::size_t DimensionCount
109 >
110 struct point_loop
111     <
112         StrategyLess, StrategyGreater, DimensionCount, DimensionCount
113     >
114 {
115     template <typename Box, typename Point, typename Strategy>
applyboost::geometry::detail::expand::point_loop116     static inline void apply(Box&, Point const&, Strategy const&) {}
117 };
118 
119 
120 // implementation for the spherical equatorial and geographic coordinate systems
121 template
122 <
123     typename StrategyLess,
124     typename StrategyGreater,
125     std::size_t DimensionCount
126 >
127 struct point_loop_on_spheroid
128 {
129     template <typename Box, typename Point, typename Strategy>
applyboost::geometry::detail::expand::point_loop_on_spheroid130     static inline void apply(Box& box,
131                              Point const& point,
132                              Strategy const& strategy)
133     {
134         typedef typename point_type<Box>::type box_point_type;
135         typedef typename coordinate_type<Box>::type box_coordinate_type;
136 
137         typedef math::detail::constants_on_spheroid
138             <
139                 box_coordinate_type,
140                 typename coordinate_system<Box>::type::units
141             > constants;
142 
143         // normalize input point and input box
144         Point p_normalized = detail::return_normalized<Point>(point);
145         detail::normalize(box, box);
146 
147         // transform input point to be of the same type as the box point
148         box_point_type box_point;
149         detail::envelope::transform_units(p_normalized, box_point);
150 
151         box_coordinate_type p_lon = geometry::get<0>(box_point);
152         box_coordinate_type p_lat = geometry::get<1>(box_point);
153 
154         typename coordinate_type<Box>::type
155             b_lon_min = geometry::get<min_corner, 0>(box),
156             b_lat_min = geometry::get<min_corner, 1>(box),
157             b_lon_max = geometry::get<max_corner, 0>(box),
158             b_lat_max = geometry::get<max_corner, 1>(box);
159 
160         if (math::equals(math::abs(p_lat), constants::max_latitude()))
161         {
162             // the point of expansion is the either the north or the
163             // south pole; the only important coordinate here is the
164             // pole's latitude, as the longitude can be anything;
165             // we, thus, take into account the point's latitude only and return
166             geometry::set<min_corner, 1>(box, (std::min)(p_lat, b_lat_min));
167             geometry::set<max_corner, 1>(box, (std::max)(p_lat, b_lat_max));
168             return;
169         }
170 
171         if (math::equals(b_lat_min, b_lat_max)
172             && math::equals(math::abs(b_lat_min), constants::max_latitude()))
173         {
174             // the box degenerates to either the north or the south pole;
175             // the only important coordinate here is the pole's latitude,
176             // as the longitude can be anything;
177             // we thus take into account the box's latitude only and return
178             geometry::set<min_corner, 0>(box, p_lon);
179             geometry::set<min_corner, 1>(box, (std::min)(p_lat, b_lat_min));
180             geometry::set<max_corner, 0>(box, p_lon);
181             geometry::set<max_corner, 1>(box, (std::max)(p_lat, b_lat_max));
182             return;
183         }
184 
185         // update latitudes
186         b_lat_min = (std::min)(b_lat_min, p_lat);
187         b_lat_max = (std::max)(b_lat_max, p_lat);
188 
189         // update longitudes
190         if (math::smaller(p_lon, b_lon_min))
191         {
192             box_coordinate_type p_lon_shifted = p_lon + constants::period();
193 
194             if (math::larger(p_lon_shifted, b_lon_max))
195             {
196                 // here we could check using: ! math::larger(.., ..)
197                 if (math::smaller(b_lon_min - p_lon, p_lon_shifted - b_lon_max))
198                 {
199                     b_lon_min = p_lon;
200                 }
201                 else
202                 {
203                     b_lon_max = p_lon_shifted;
204                 }
205             }
206         }
207         else if (math::larger(p_lon, b_lon_max))
208         {
209             // in this case, and since p_lon is normalized in the range
210             // (-180, 180], we must have that b_lon_max <= 180
211             if (b_lon_min < 0
212                 && math::larger(p_lon - b_lon_max,
213                                 constants::period() - p_lon + b_lon_min))
214             {
215                 b_lon_min = p_lon;
216                 b_lon_max += constants::period();
217             }
218             else
219             {
220                 b_lon_max = p_lon;
221             }
222         }
223 
224         geometry::set<min_corner, 0>(box, b_lon_min);
225         geometry::set<min_corner, 1>(box, b_lat_min);
226         geometry::set<max_corner, 0>(box, b_lon_max);
227         geometry::set<max_corner, 1>(box, b_lat_max);
228 
229         point_loop
230             <
231                 StrategyLess, StrategyGreater, 2, DimensionCount
232             >::apply(box, point, strategy);
233     }
234 };
235 
236 
237 }} // namespace detail::expand
238 #endif // DOXYGEN_NO_DETAIL
239 
240 #ifndef DOXYGEN_NO_DISPATCH
241 namespace dispatch
242 {
243 
244 
245 // Box + point -> new box containing also point
246 template
247 <
248     typename BoxOut, typename Point,
249     typename StrategyLess, typename StrategyGreater,
250     typename CSTagOut, typename CSTag
251 >
252 struct expand
253     <
254         BoxOut, Point,
255         StrategyLess, StrategyGreater,
256         box_tag, point_tag,
257         CSTagOut, CSTag
258     > : detail::expand::point_loop
259         <
260             StrategyLess, StrategyGreater, 0, dimension<Point>::value
261         >
262 {
263     BOOST_MPL_ASSERT_MSG((boost::is_same<CSTagOut, CSTag>::value),
264                          COORDINATE_SYSTEMS_MUST_BE_THE_SAME,
265                          (types<CSTagOut, CSTag>()));
266 };
267 
268 template
269 <
270     typename BoxOut, typename Point,
271     typename StrategyLess, typename StrategyGreater
272 >
273 struct expand
274     <
275         BoxOut, Point,
276         StrategyLess, StrategyGreater,
277         box_tag, point_tag,
278         spherical_equatorial_tag, spherical_equatorial_tag
279     > : detail::expand::point_loop_on_spheroid
280         <
281             StrategyLess, StrategyGreater, dimension<Point>::value
282         >
283 {};
284 
285 template
286 <
287     typename BoxOut, typename Point,
288     typename StrategyLess, typename StrategyGreater
289 >
290 struct expand
291     <
292         BoxOut, Point,
293         StrategyLess, StrategyGreater,
294         box_tag, point_tag,
295         geographic_tag, geographic_tag
296     > : detail::expand::point_loop_on_spheroid
297         <
298             StrategyLess, StrategyGreater, dimension<Point>::value
299         >
300 {};
301 
302 
303 } // namespace dispatch
304 #endif // DOXYGEN_NO_DISPATCH
305 
306 }} // namespace boost::geometry
307 
308 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EXPAND_POINT_HPP
309