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) 2013-2015 Adam Wulkiewicz, Lodz, Poland. 7 8 // This file was modified by Oracle on 2015, 2016, 2017, 2019. 9 // Modifications copyright (c) 2016-2019, Oracle and/or its affiliates. 10 11 // Contributed and/or modified by Adam Wulkiewicz, 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 // Use, modification and distribution is subject to the Boost Software License, 17 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 18 // http://www.boost.org/LICENSE_1_0.txt) 19 20 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_BOX_IN_BOX_HPP 21 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_BOX_IN_BOX_HPP 22 23 24 #include <boost/geometry/core/access.hpp> 25 #include <boost/geometry/core/coordinate_dimension.hpp> 26 #include <boost/geometry/strategies/covered_by.hpp> 27 #include <boost/geometry/strategies/within.hpp> 28 #include <boost/geometry/util/normalize_spheroidal_coordinates.hpp> 29 30 31 namespace boost { namespace geometry { namespace strategy 32 { 33 34 35 namespace within 36 { 37 38 39 #ifndef DOXYGEN_NO_DETAIL 40 namespace detail 41 { 42 43 44 struct box_within_coord 45 { 46 template <typename BoxContainedValue, typename BoxContainingValue> applyboost::geometry::strategy::within::detail::box_within_coord47 static inline bool apply(BoxContainedValue const& bed_min, 48 BoxContainedValue const& bed_max, 49 BoxContainingValue const& bing_min, 50 BoxContainingValue const& bing_max) 51 { 52 return bing_min <= bed_min && bed_max <= bing_max // contained in containing 53 && bed_min < bed_max; // interiors overlap 54 } 55 }; 56 57 58 struct box_covered_by_coord 59 { 60 template <typename BoxContainedValue, typename BoxContainingValue> applyboost::geometry::strategy::within::detail::box_covered_by_coord61 static inline bool apply(BoxContainedValue const& bed_min, 62 BoxContainedValue const& bed_max, 63 BoxContainingValue const& bing_min, 64 BoxContainingValue const& bing_max) 65 { 66 return bed_min >= bing_min && bed_max <= bing_max; 67 } 68 }; 69 70 71 struct box_within_longitude_diff 72 { 73 template <typename CalcT> applyboost::geometry::strategy::within::detail::box_within_longitude_diff74 static inline bool apply(CalcT const& diff_ed) 75 { 76 return diff_ed > CalcT(0); 77 } 78 }; 79 80 struct box_covered_by_longitude_diff 81 { 82 template <typename CalcT> applyboost::geometry::strategy::within::detail::box_covered_by_longitude_diff83 static inline bool apply(CalcT const&) 84 { 85 return true; 86 } 87 }; 88 89 template <typename Geometry, 90 typename CoordCheck, 91 typename InteriorCheck> 92 struct box_longitude_range 93 { 94 template <typename BoxContainedValue, typename BoxContainingValue> applyboost::geometry::strategy::within::detail::box_longitude_range95 static inline bool apply(BoxContainedValue const& bed_min, 96 BoxContainedValue const& bed_max, 97 BoxContainingValue const& bing_min, 98 BoxContainingValue const& bing_max) 99 { 100 typedef typename select_most_precise 101 < 102 BoxContainedValue, 103 BoxContainingValue 104 >::type calc_t; 105 typedef typename geometry::detail::cs_angular_units<Geometry>::type units_t; 106 typedef math::detail::constants_on_spheroid<calc_t, units_t> constants; 107 108 if (CoordCheck::apply(bed_min, bed_max, bing_min, bing_max)) 109 { 110 return true; 111 } 112 113 // min <= max <=> diff >= 0 114 calc_t const diff_ed = bed_max - bed_min; 115 calc_t const diff_ing = bing_max - bing_min; 116 117 // if containing covers the whole globe it contains all 118 if (diff_ing >= constants::period()) 119 { 120 return true; 121 } 122 123 // if containing is smaller it cannot contain 124 // and check interior (within vs covered_by) 125 if (diff_ing < diff_ed || ! InteriorCheck::apply(diff_ed)) 126 { 127 return false; 128 } 129 130 // calculate positive longitude translation with bing_min as origin 131 calc_t const diff_min = math::longitude_distance_unsigned<units_t>(bing_min, bed_min); 132 133 // max of contained translated into the containing origin must be lesser than max of containing 134 return bing_min + diff_min + diff_ed <= bing_max 135 /*|| bing_max - diff_min - diff_ed >= bing_min*/; 136 } 137 }; 138 139 140 template 141 < 142 template <typename, std::size_t, typename> class SubStrategy, 143 typename CSTag, 144 std::size_t Dimension, 145 std::size_t DimensionCount 146 > 147 struct relate_box_box_loop 148 { 149 template <typename Box1, typename Box2> applyboost::geometry::strategy::within::detail::relate_box_box_loop150 static inline bool apply(Box1 const& b_contained, Box2 const& b_containing) 151 { 152 assert_dimension_equal<Box1, Box2>(); 153 154 if (! SubStrategy<Box1, Dimension, CSTag>::apply( 155 get<min_corner, Dimension>(b_contained), 156 get<max_corner, Dimension>(b_contained), 157 get<min_corner, Dimension>(b_containing), 158 get<max_corner, Dimension>(b_containing) 159 ) 160 ) 161 { 162 return false; 163 } 164 165 return within::detail::relate_box_box_loop 166 < 167 SubStrategy, CSTag, 168 Dimension + 1, DimensionCount 169 >::apply(b_contained, b_containing); 170 } 171 }; 172 173 template 174 < 175 template <typename, std::size_t, typename> class SubStrategy, 176 typename CSTag, 177 std::size_t DimensionCount 178 > 179 struct relate_box_box_loop<SubStrategy, CSTag, DimensionCount, DimensionCount> 180 { 181 template <typename Box1, typename Box2> applyboost::geometry::strategy::within::detail::relate_box_box_loop182 static inline bool apply(Box1 const& , Box2 const& ) 183 { 184 return true; 185 } 186 }; 187 188 189 } // namespace detail 190 #endif // DOXYGEN_NO_DETAIL 191 192 193 // for backward compatibility 194 template <typename Geometry, std::size_t Dimension, typename CSTag> 195 struct box_within_range 196 : within::detail::box_within_coord 197 {}; 198 199 200 template <typename Geometry, std::size_t Dimension, typename CSTag> 201 struct box_covered_by_range 202 : within::detail::box_covered_by_coord 203 {}; 204 205 206 // spherical_equatorial_tag, spherical_polar_tag and geographic_cat are casted to spherical_tag 207 template <typename Geometry> 208 struct box_within_range<Geometry, 0, spherical_tag> 209 : within::detail::box_longitude_range 210 < 211 Geometry, 212 within::detail::box_within_coord, 213 within::detail::box_within_longitude_diff 214 > 215 {}; 216 217 218 template <typename Geometry> 219 struct box_covered_by_range<Geometry, 0, spherical_tag> 220 : within::detail::box_longitude_range 221 < 222 Geometry, 223 within::detail::box_covered_by_coord, 224 within::detail::box_covered_by_longitude_diff 225 > 226 {}; 227 228 229 // for backward compatibility 230 template 231 < 232 typename B1, 233 typename B2, 234 template <typename, std::size_t, typename> class SubStrategy = box_within_range 235 > 236 struct box_in_box 237 { 238 template <typename Box1, typename Box2> applyboost::geometry::strategy::within::box_in_box239 static inline bool apply(Box1 const& box1, Box2 const& box2) 240 { 241 typedef typename tag_cast 242 < 243 typename geometry::cs_tag<Box1>::type, 244 spherical_tag 245 >::type cs_tag; 246 247 return within::detail::relate_box_box_loop 248 < 249 SubStrategy, cs_tag, 250 0, dimension<Box1>::type::value 251 >::apply(box1, box2); 252 } 253 }; 254 255 256 struct cartesian_box_box 257 { 258 template <typename Box1, typename Box2> applyboost::geometry::strategy::within::cartesian_box_box259 static inline bool apply(Box1 const& box1, Box2 const& box2) 260 { 261 return within::detail::relate_box_box_loop 262 < 263 box_within_range, 264 cartesian_tag, 265 0, dimension<Box1>::type::value 266 >::apply(box1, box2); 267 } 268 }; 269 270 struct spherical_box_box 271 { 272 template <typename Box1, typename Box2> applyboost::geometry::strategy::within::spherical_box_box273 static inline bool apply(Box1 const& box1, Box2 const& box2) 274 { 275 return within::detail::relate_box_box_loop 276 < 277 box_within_range, 278 spherical_tag, 279 0, dimension<Box1>::type::value 280 >::apply(box1, box2); 281 } 282 }; 283 284 285 } // namespace within 286 287 288 namespace covered_by 289 { 290 291 292 struct cartesian_box_box 293 { 294 template <typename Box1, typename Box2> applyboost::geometry::strategy::covered_by::cartesian_box_box295 static inline bool apply(Box1 const& box1, Box2 const& box2) 296 { 297 return within::detail::relate_box_box_loop 298 < 299 strategy::within::box_covered_by_range, 300 cartesian_tag, 301 0, dimension<Box1>::type::value 302 >::apply(box1, box2); 303 } 304 }; 305 306 struct spherical_box_box 307 { 308 template <typename Box1, typename Box2> applyboost::geometry::strategy::covered_by::spherical_box_box309 static inline bool apply(Box1 const& box1, Box2 const& box2) 310 { 311 return within::detail::relate_box_box_loop 312 < 313 strategy::within::box_covered_by_range, 314 spherical_tag, 315 0, dimension<Box1>::type::value 316 >::apply(box1, box2); 317 } 318 }; 319 320 321 } 322 323 324 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS 325 326 327 namespace within { namespace services 328 { 329 330 template <typename BoxContained, typename BoxContaining> 331 struct default_strategy 332 < 333 BoxContained, BoxContaining, 334 box_tag, box_tag, 335 areal_tag, areal_tag, 336 cartesian_tag, cartesian_tag 337 > 338 { 339 typedef cartesian_box_box type; 340 }; 341 342 // spherical_equatorial_tag, spherical_polar_tag and geographic_cat are casted to spherical_tag 343 template <typename BoxContained, typename BoxContaining> 344 struct default_strategy 345 < 346 BoxContained, BoxContaining, 347 box_tag, box_tag, 348 areal_tag, areal_tag, 349 spherical_tag, spherical_tag 350 > 351 { 352 typedef spherical_box_box type; 353 }; 354 355 356 }} // namespace within::services 357 358 namespace covered_by { namespace services 359 { 360 361 template <typename BoxContained, typename BoxContaining> 362 struct default_strategy 363 < 364 BoxContained, BoxContaining, 365 box_tag, box_tag, 366 areal_tag, areal_tag, 367 cartesian_tag, cartesian_tag 368 > 369 { 370 typedef cartesian_box_box type; 371 }; 372 373 // spherical_equatorial_tag, spherical_polar_tag and geographic_cat are casted to spherical_tag 374 template <typename BoxContained, typename BoxContaining> 375 struct default_strategy 376 < 377 BoxContained, BoxContaining, 378 box_tag, box_tag, 379 areal_tag, areal_tag, 380 spherical_tag, spherical_tag 381 > 382 { 383 typedef spherical_box_box type; 384 }; 385 386 387 }} // namespace covered_by::services 388 389 390 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS 391 392 393 }}} // namespace boost::geometry::strategy 394 395 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_BOX_IN_BOX_HPP 396