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 // This file was modified by Oracle on 2014.
   8 // Modifications copyright (c) 2014 Oracle and/or its affiliates.
   9
  10 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
  11 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
  12
  13 // Use, modification and distribution is subject to the Boost Software License,
  14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  15 // http://www.boost.org/LICENSE_1_0.txt)
  16
  17 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  18
  19 #ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP
  20 #define BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_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/detail/relate/relate.hpp>
  32
  33 namespace boost { namespace geometry
  34 {
  35
  36 #ifndef DOXYGEN_NO_DETAIL
  37 namespace detail { namespace overlaps
  38 {
  39
  40 template
  41 <
  42     std::size_t Dimension,
  43     std::size_t DimensionCount
  44 >
  45 struct box_box_loop
  46 {
  47     template <typename Box1, typename Box2>
  48     static inline void apply(Box1 const& b1, Box2 const& b2,
  49             bool& overlaps, bool& one_in_two, bool& two_in_one)
  50     {
  51         assert_dimension_equal<Box1, Box2>();
  52
  53         typedef typename coordinate_type<Box1>::type coordinate_type1;
  54         typedef typename coordinate_type<Box2>::type coordinate_type2;
  55
  56         coordinate_type1 const& min1 = get<min_corner, Dimension>(b1);
  57         coordinate_type1 const& max1 = get<max_corner, Dimension>(b1);
  58         coordinate_type2 const& min2 = get<min_corner, Dimension>(b2);
  59         coordinate_type2 const& max2 = get<max_corner, Dimension>(b2);
  60
  61         // We might use the (not yet accepted) Boost.Interval
  62         // submission in the future
  63
  64         // If:
  65         // B1: |-------|
  66         // B2:           |------|
  67         // in any dimension -> no overlap
  68         if (max1 <= min2 || min1 >= max2)
  69         {
  70             overlaps = false;
  71             return;
  72         }
  73
  74         // If:
  75         // B1: |--------------------|
  76         // B2:   |-------------|
  77         // in all dimensions -> within, then no overlap
  78         // B1: |--------------------|
  79         // B2: |-------------|
  80         // this is "within-touch" -> then no overlap. So use < and >
  81         if (min1 < min2 || max1 > max2)
  82         {
  83             one_in_two = false;
  84         }
  85         // Same other way round
  86         if (min2 < min1 || max2 > max1)
  87         {
  88             two_in_one = false;
  89         }
  90
  91         box_box_loop
  92             <
  93                 Dimension + 1,
  94                 DimensionCount
  95             >::apply(b1, b2, overlaps, one_in_two, two_in_one);
  96     }
  97 };
  98
  99 template
 100 <
 101     std::size_t DimensionCount
 102 >
 103 struct box_box_loop<DimensionCount, DimensionCount>
 104 {
 105     template <typename Box1, typename Box2>
 106     static inline void apply(Box1 const& , Box2 const&, bool&, bool&, bool&)
 107     {
 108     }
 109 };
 110
 111 struct box_box
 112 {
 113     template <typename Box1, typename Box2>
 114     static inline bool apply(Box1 const& b1, Box2 const& b2)
 115     {
 116         bool overlaps = true;
 117         bool within1 = true;
 118         bool within2 = true;
 119         box_box_loop
 120             <
 121                 0,
 122                 dimension<Box1>::type::value
 123             >::apply(b1, b2, overlaps, within1, within2);
 124
 125         /*
 126         \see http://docs.codehaus.org/display/GEOTDOC/02+Geometry+Relationships#02GeometryRelationships-Overlaps
 127         where is stated that "inside" is not an "overlap",
 128         this is true and is implemented as such.
 129         */
 130         return overlaps && ! within1 && ! within2;
 131     }
 132 };
 133
 134 }} // namespace detail::overlaps
 135 #endif // DOXYGEN_NO_DETAIL
 136
 137 //struct not_implemented_for_this_geometry_type : public boost::false_type {};
 138
 139 #ifndef DOXYGEN_NO_DISPATCH
 140 namespace dispatch
 141 {
 142
 143
 144 template
 145 <
 146     typename Geometry1,
 147     typename Geometry2,
 148     typename Tag1 = typename tag<Geometry1>::type,
 149     typename Tag2 = typename tag<Geometry2>::type
 150 >
 151 struct overlaps
 152     : detail::relate::relate_base
 153         <
 154             detail::relate::static_mask_overlaps_type,
 155             Geometry1,
 156             Geometry2
 157         >
 158 {};
 159
 160
 161 template <typename Box1, typename Box2>
 162 struct overlaps<Box1, Box2, box_tag, box_tag>
 163     : detail::overlaps::box_box
 164 {};
 165
 166 } // namespace dispatch
 167 #endif // DOXYGEN_NO_DISPATCH
 168
 169
 170 /*!
 171 \brief \brief_check2{overlap}
 172 \ingroup overlaps
 173 \tparam Geometry1 \tparam_geometry
 174 \tparam Geometry2 \tparam_geometry
 175 \param geometry1 \param_geometry
 176 \param geometry2 \param_geometry
 177 \return \return_check2{overlap}
 178
 179 \qbk{[include reference/algorithms/overlaps.qbk]}
 180 */
 181 template <typename Geometry1, typename Geometry2>
 182 inline bool overlaps(Geometry1 const& geometry1, Geometry2 const& geometry2)
 183 {
 184     concept::check<Geometry1 const>();
 185     concept::check<Geometry2 const>();
 186
 187     return dispatch::overlaps
 188         <
 189             Geometry1,
 190             Geometry2
 191         >::apply(geometry1, geometry2);
 192 }
 193
 194 }} // namespace boost::geometry
 195
 196 #endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP