boost/geometry/algorithms/detail/expand/point.hpp

   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>
  64     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>
 116     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>
 130     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