ceph/src/boost/boost/geometry/algorithms/detail/disjoint/segment_box.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
   6 // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland.
   7
   8 // This file was modified by Oracle on 2013-2017.
   9 // Modifications copyright (c) 2013-2017, 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 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  14
  15 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  16 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  17
  18 // Use, modification and distribution is subject to the Boost Software License,
  19 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  20 // http://www.boost.org/LICENSE_1_0.txt)
  21
  22 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP
  23 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP
  24
  25 #include <cstddef>
  26
  27 #include <boost/geometry/core/tags.hpp>
  28 #include <boost/geometry/core/radian_access.hpp>
  29
  30 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
  31 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
  32 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  33 #include <boost/geometry/algorithms/detail/envelope/segment.hpp>
  34 #include <boost/geometry/algorithms/detail/normalize.hpp>
  35 #include <boost/geometry/algorithms/dispatch/disjoint.hpp>
  36
  37 #include <boost/geometry/formulas/vertex_longitude.hpp>
  38
  39 #include <boost/geometry/geometries/box.hpp>
  40
  41 namespace boost { namespace geometry
  42 {
  43
  44
  45 #ifndef DOXYGEN_NO_DETAIL
  46 namespace detail { namespace disjoint
  47 {
  48
  49 template <typename CS_Tag>
  50 struct disjoint_segment_box_sphere_or_spheroid
  51 {
  52 private:
  53
  54     template <typename CT>
  55     static inline void swap(CT& lon1,
  56                             CT& lat1,
  57                             CT& lon2,
  58                             CT& lat2)
  59     {
  60         std::swap(lon1, lon2);
  61         std::swap(lat1, lat2);
  62     }
  63
  64
  65 public:
  66
  67     template <typename Segment, typename Box, typename Strategy>
  68     static inline bool apply(Segment const& segment,
  69                              Box const& box,
  70                              Strategy const& azimuth_strategy)
  71     {
  72         assert_dimension_equal<Segment, Box>();
  73
  74         typedef typename point_type<Segment>::type segment_point_type;
  75         typedef typename cs_tag<Segment>::type segment_cs_type;
  76
  77         segment_point_type p0, p1;
  78         geometry::detail::assign_point_from_index<0>(segment, p0);
  79         geometry::detail::assign_point_from_index<1>(segment, p1);
  80
  81         // Simplest cases first
  82
  83         // Case 1: if box contains one of segment's endpoints then they are not disjoint
  84         if (! disjoint_point_box(p0, box) || ! disjoint_point_box(p1, box))
  85         {
  86             return false;
  87         }
  88
  89         // Case 2: disjoint if bounding boxes are disjoint
  90
  91         typedef typename coordinate_type<segment_point_type>::type CT;
  92
  93         segment_point_type p0_normalized =
  94                 geometry::detail::return_normalized<segment_point_type>(p0);
  95         segment_point_type p1_normalized =
  96                 geometry::detail::return_normalized<segment_point_type>(p1);
  97
  98         CT lon1 = geometry::get_as_radian<0>(p0_normalized);
  99         CT lat1 = geometry::get_as_radian<1>(p0_normalized);
 100         CT lon2 = geometry::get_as_radian<0>(p1_normalized);
 101         CT lat2 = geometry::get_as_radian<1>(p1_normalized);
 102
 103         if (lon1 > lon2)
 104         {
 105             swap(lon1, lat1, lon2, lat2);
 106         }
 107
 108         //Compute alp1 outside envelope and pass it to envelope_segment_impl
 109         //in order for it to be used later in the algorithm
 110         CT alp1;
 111
 112         azimuth_strategy.apply(lon1, lat1, lon2, lat2, alp1);
 113
 114         geometry::model::box<segment_point_type> box_seg;
 115
 116         geometry::detail::envelope::envelope_segment_impl<segment_cs_type>
 117                 ::template apply<geometry::radian>(lon1, lat1,
 118                                                    lon2, lat2,
 119                                                    box_seg,
 120                                                    azimuth_strategy,
 121                                                    alp1);
 122         if (disjoint_box_box(box, box_seg))
 123         {
 124             return true;
 125         }
 126
 127         // Case 3: test intersection by comparing angles
 128
 129         CT a_b0, a_b1, a_b2, a_b3;
 130
 131         CT b_lon_min = geometry::get_as_radian<geometry::min_corner, 0>(box);
 132         CT b_lat_min = geometry::get_as_radian<geometry::min_corner, 1>(box);
 133         CT b_lon_max = geometry::get_as_radian<geometry::max_corner, 0>(box);
 134         CT b_lat_max = geometry::get_as_radian<geometry::max_corner, 1>(box);
 135
 136         azimuth_strategy.apply(lon1, lat1, b_lon_min, b_lat_min, a_b0);
 137         azimuth_strategy.apply(lon1, lat1, b_lon_max, b_lat_min, a_b1);
 138         azimuth_strategy.apply(lon1, lat1, b_lon_min, b_lat_max, a_b2);
 139         azimuth_strategy.apply(lon1, lat1, b_lon_max, b_lat_max, a_b3);
 140
 141         bool b0 = alp1 > a_b0;
 142         bool b1 = alp1 > a_b1;
 143         bool b2 = alp1 > a_b2;
 144         bool b3 = alp1 > a_b3;
 145
 146         // if not all box points on the same side of the segment then
 147         // there is an intersection
 148         if (!(b0 && b1 && b2 && b3) && (b0 || b1 || b2 || b3))
 149         {
 150             return false;
 151         }
 152
 153         // Case 4: The only intersection case not covered above is when all four
 154         // points of the box are above (below) the segment in northern (southern)
 155         // hemisphere. Then we have to compute the vertex of the segment
 156
 157         CT vertex_lat;
 158         CT lat_sum = lat1 + lat2;
 159
 160         if ((b0 && b1 && b2 && b3 && lat_sum > CT(0))
 161                 || (!(b0 && b1 && b2 && b3) && lat_sum < CT(0)))
 162         {
 163             CT b_lat_below; //latitude of box closest to equator
 164
 165             if (lat_sum > CT(0))
 166             {
 167                 vertex_lat = geometry::get_as_radian<geometry::max_corner, 1>(box_seg);
 168                 b_lat_below = b_lat_min;
 169             } else {
 170                 vertex_lat = geometry::get_as_radian<geometry::min_corner, 1>(box_seg);
 171                 b_lat_below = b_lat_max;
 172             }
 173
 174             //optimization TODO: computing the spherical longitude should suffice for
 175             // the majority of cases
 176             CT vertex_lon = geometry::formula::vertex_longitude<CT, CS_Tag>
 177                                     ::apply(lon1, lat1,
 178                                             lon2, lat2,
 179                                             vertex_lat,
 180                                             alp1,
 181                                             azimuth_strategy);
 182
 183             // Check if the vertex point is within the band defined by the
 184             // minimum and maximum longitude of the box; if yes, then return
 185             // false if the point is above the min latitude of the box; return
 186             // true in all other cases
 187             if (vertex_lon >= b_lon_min && vertex_lon <= b_lon_max
 188                     && std::abs(vertex_lat) > std::abs(b_lat_below))
 189             {
 190                 return false;
 191             }
 192         }
 193
 194         return true;
 195     }
 196 };
 197
 198 struct disjoint_segment_box
 199 {
 200     template <typename Segment, typename Box, typename Strategy>
 201     static inline bool apply(Segment const& segment,
 202                              Box const& box,
 203                              Strategy const& strategy)
 204     {
 205         return strategy.apply(segment, box);
 206     }
 207 };
 208
 209 }} // namespace detail::disjoint
 210 #endif // DOXYGEN_NO_DETAIL
 211
 212
 213 #ifndef DOXYGEN_NO_DISPATCH
 214 namespace dispatch
 215 {
 216
 217
 218 template <typename Segment, typename Box, std::size_t DimensionCount>
 219 struct disjoint<Segment, Box, DimensionCount, segment_tag, box_tag, false>
 220         : detail::disjoint::disjoint_segment_box
 221 {};
 222
 223
 224 } // namespace dispatch
 225 #endif // DOXYGEN_NO_DISPATCH
 226
 227
 228 }} // namespace boost::geometry
 229
 230
 231 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP