boost/geometry/algorithms/overlaps.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
   5 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
   6
   7 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
   8 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP
  16
  17
  18 #include <cstddef>
  19
  20 #include <boost/mpl/assert.hpp>
  21
  22 #include <boost/geometry/core/access.hpp>
  23
  24 #include <boost/geometry/geometries/concepts/check.hpp>
  25
  26 namespace boost { namespace geometry
  27 {
  28
  29 #ifndef DOXYGEN_NO_DETAIL
  30 namespace detail { namespace overlaps
  31 {
  32
  33 template
  34 <
  35     typename Box1,
  36     typename Box2,
  37     std::size_t Dimension,
  38     std::size_t DimensionCount
  39 >
  40 struct box_box_loop
  41 {
  42     static inline void apply(Box1 const& b1, Box2 const& b2,
  43             bool& overlaps, bool& one_in_two, bool& two_in_one)
  44     {
  45         assert_dimension_equal<Box1, Box2>();
  46
  47         typedef typename coordinate_type<Box1>::type coordinate_type1;
  48         typedef typename coordinate_type<Box2>::type coordinate_type2;
  49
  50         coordinate_type1 const& min1 = get<min_corner, Dimension>(b1);
  51         coordinate_type1 const& max1 = get<max_corner, Dimension>(b1);
  52         coordinate_type2 const& min2 = get<min_corner, Dimension>(b2);
  53         coordinate_type2 const& max2 = get<max_corner, Dimension>(b2);
  54
  55         // We might use the (not yet accepted) Boost.Interval
  56         // submission in the future
  57
  58         // If:
  59         // B1: |-------|
  60         // B2:           |------|
  61         // in any dimension -> no overlap
  62         if (max1 <= min2 || min1 >= max2)
  63         {
  64             overlaps = false;
  65             return;
  66         }
  67
  68         // If:
  69         // B1: |--------------------|
  70         // B2:   |-------------|
  71         // in all dimensions -> within, then no overlap
  72         // B1: |--------------------|
  73         // B2: |-------------|
  74         // this is "within-touch" -> then no overlap. So use < and >
  75         if (min1 < min2 || max1 > max2)
  76         {
  77             one_in_two = false;
  78         }
  79         // Same other way round
  80         if (min2 < min1 || max2 > max1)
  81         {
  82             two_in_one = false;
  83         }
  84
  85         box_box_loop
  86             <
  87                 Box1,
  88                 Box2,
  89                 Dimension + 1,
  90                 DimensionCount
  91             >::apply(b1, b2, overlaps, one_in_two, two_in_one);
  92     }
  93 };
  94
  95 template
  96 <
  97     typename Box1,
  98     typename Box2,
  99     std::size_t DimensionCount
 100 >
 101 struct box_box_loop<Box1, Box2, DimensionCount, DimensionCount>
 102 {
 103     static inline void apply(Box1 const& , Box2 const&, bool&, bool&, bool&)
 104     {
 105     }
 106 };
 107
 108 template
 109 <
 110     typename Box1,
 111     typename Box2
 112 >
 113 struct box_box
 114 {
 115     static inline bool apply(Box1 const& b1, Box2 const& b2)
 116     {
 117         bool overlaps = true;
 118         bool within1 = true;
 119         bool within2 = true;
 120         box_box_loop
 121             <
 122                 Box1,
 123                 Box2,
 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
 138
 139 }} // namespace detail::overlaps
 140 #endif // DOXYGEN_NO_DETAIL
 141
 142 //struct not_implemented_for_this_geometry_type : public boost::false_type {};
 143
 144 #ifndef DOXYGEN_NO_DISPATCH
 145 namespace dispatch
 146 {
 147
 148
 149 template
 150 <
 151     typename Tag1,
 152     typename Tag2,
 153     typename Geometry1,
 154     typename Geometry2
 155 >
 156 struct overlaps
 157 {
 158     BOOST_MPL_ASSERT_MSG
 159         (
 160             false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPE
 161             , (types<Geometry1, Geometry2>)
 162         );
 163 };
 164
 165
 166 template <typename Box1, typename Box2>
 167 struct overlaps<box_tag, box_tag, Box1, Box2>
 168     : detail::overlaps::box_box<Box1, Box2>
 169 {};
 170
 171
 172
 173
 174 } // namespace dispatch
 175 #endif // DOXYGEN_NO_DISPATCH
 176
 177
 178 /*!
 179 \brief \brief_check2{overlap}
 180 \ingroup overlaps
 181 \return \return_check2{overlap}
 182
 183 \qbk{[include reference/algorithms/overlaps.qbk]}
 184 */
 185 template <typename Geometry1, typename Geometry2>
 186 inline bool overlaps(Geometry1 const& geometry1, Geometry2 const& geometry2)
 187 {
 188     concept::check<Geometry1 const>();
 189     concept::check<Geometry2 const>();
 190
 191     return dispatch::overlaps
 192         <
 193             typename tag<Geometry1>::type,
 194             typename tag<Geometry2>::type,
 195             Geometry1,
 196             Geometry2
 197         >::apply(geometry1, geometry2);
 198 }
 199
 200 }} // namespace boost::geometry
 201
 202 #endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP