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