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> swapboost::geometry::detail::disjoint::disjoint_segment_box_sphere_or_spheroid55 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> applyboost::geometry::detail::disjoint::disjoint_segment_box_sphere_or_spheroid68 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> applyboost::geometry::detail::disjoint::disjoint_segment_box201 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 232