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