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 7 // This file was modified by Oracle on 2014, 2015, 2017. 8 // Modifications copyright (c) 2014-2017 Oracle and/or its affiliates. 9 10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 11 12 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library 13 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. 14 15 // Use, modification and distribution is subject to the Boost Software License, 16 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17 // http://www.boost.org/LICENSE_1_0.txt) 18 19 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAPS_IMPLEMENTATION_HPP 20 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAPS_IMPLEMENTATION_HPP 21 22 23 #include <cstddef> 24 25 #include <boost/geometry/core/access.hpp> 26 27 #include <boost/geometry/algorithms/not_implemented.hpp> 28 29 #include <boost/geometry/geometries/concepts/check.hpp> 30 31 #include <boost/geometry/algorithms/relate.hpp> 32 #include <boost/geometry/algorithms/detail/overlaps/interface.hpp> 33 34 35 namespace boost { namespace geometry 36 { 37 38 #ifndef DOXYGEN_NO_DETAIL 39 namespace detail { namespace overlaps 40 { 41 42 template 43 < 44 std::size_t Dimension, 45 std::size_t DimensionCount 46 > 47 struct box_box_loop 48 { 49 template <typename Box1, typename Box2> applyboost::geometry::detail::overlaps::box_box_loop50 static inline void apply(Box1 const& b1, Box2 const& b2, 51 bool& overlaps, bool& one_in_two, bool& two_in_one) 52 { 53 assert_dimension_equal<Box1, Box2>(); 54 55 typedef typename coordinate_type<Box1>::type coordinate_type1; 56 typedef typename coordinate_type<Box2>::type coordinate_type2; 57 58 coordinate_type1 const& min1 = get<min_corner, Dimension>(b1); 59 coordinate_type1 const& max1 = get<max_corner, Dimension>(b1); 60 coordinate_type2 const& min2 = get<min_corner, Dimension>(b2); 61 coordinate_type2 const& max2 = get<max_corner, Dimension>(b2); 62 63 // We might use the (not yet accepted) Boost.Interval 64 // submission in the future 65 66 // If: 67 // B1: |-------| 68 // B2: |------| 69 // in any dimension -> no overlap 70 if (max1 <= min2 || min1 >= max2) 71 { 72 overlaps = false; 73 return; 74 } 75 76 // If: 77 // B1: |--------------------| 78 // B2: |-------------| 79 // in all dimensions -> within, then no overlap 80 // B1: |--------------------| 81 // B2: |-------------| 82 // this is "within-touch" -> then no overlap. So use < and > 83 if (min1 < min2 || max1 > max2) 84 { 85 one_in_two = false; 86 } 87 88 // Same other way round 89 if (min2 < min1 || max2 > max1) 90 { 91 two_in_one = false; 92 } 93 94 box_box_loop 95 < 96 Dimension + 1, 97 DimensionCount 98 >::apply(b1, b2, overlaps, one_in_two, two_in_one); 99 } 100 }; 101 102 template 103 < 104 std::size_t DimensionCount 105 > 106 struct box_box_loop<DimensionCount, DimensionCount> 107 { 108 template <typename Box1, typename Box2> applyboost::geometry::detail::overlaps::box_box_loop109 static inline void apply(Box1 const& , Box2 const&, bool&, bool&, bool&) 110 { 111 } 112 }; 113 114 struct box_box 115 { 116 template <typename Box1, typename Box2, typename Strategy> applyboost::geometry::detail::overlaps::box_box117 static inline bool apply(Box1 const& b1, Box2 const& b2, Strategy const& /*strategy*/) 118 { 119 bool overlaps = true; 120 bool within1 = true; 121 bool within2 = true; 122 box_box_loop 123 < 124 0, 125 dimension<Box1>::type::value 126 >::apply(b1, b2, overlaps, within1, within2); 127 128 /* 129 \see http://docs.codehaus.org/display/GEOTDOC/02+Geometry+Relationships#02GeometryRelationships-Overlaps 130 where is stated that "inside" is not an "overlap", 131 this is true and is implemented as such. 132 */ 133 return overlaps && ! within1 && ! within2; 134 } 135 }; 136 137 }} // namespace detail::overlaps 138 #endif // DOXYGEN_NO_DETAIL 139 140 141 #ifndef DOXYGEN_NO_DISPATCH 142 namespace dispatch 143 { 144 145 template <typename Box1, typename Box2> 146 struct overlaps<Box1, Box2, box_tag, box_tag> 147 : detail::overlaps::box_box 148 {}; 149 150 } // namespace dispatch 151 #endif // DOXYGEN_NO_DISPATCH 152 153 154 }} // namespace boost::geometry 155 156 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAPS_IMPLEMENTATION_HPP 157