ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/overlaps.hpp

   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.
   8 // Modifications copyright (c) 2014-2015 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_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/relate.hpp>
  32 #include <boost/geometry/algorithms/detail/relate/relate_impl.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>
  50     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>
 109     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>
 117     static inline bool apply(Box1 const& b1, Box2 const& b2)
 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 //struct not_implemented_for_this_geometry_type : public boost::false_type {};
 141
 142 #ifndef DOXYGEN_NO_DISPATCH
 143 namespace dispatch
 144 {
 145
 146
 147 template
 148 <
 149     typename Geometry1,
 150     typename Geometry2,
 151     typename Tag1 = typename tag<Geometry1>::type,
 152     typename Tag2 = typename tag<Geometry2>::type
 153 >
 154 struct overlaps
 155     : detail::relate::relate_impl
 156         <
 157             detail::de9im::static_mask_overlaps_type,
 158             Geometry1,
 159             Geometry2
 160         >
 161 {};
 162
 163
 164 template <typename Box1, typename Box2>
 165 struct overlaps<Box1, Box2, box_tag, box_tag>
 166     : detail::overlaps::box_box
 167 {};
 168
 169 } // namespace dispatch
 170 #endif // DOXYGEN_NO_DISPATCH
 171
 172
 173 /*!
 174 \brief \brief_check2{overlap}
 175 \ingroup overlaps
 176 \tparam Geometry1 \tparam_geometry
 177 \tparam Geometry2 \tparam_geometry
 178 \param geometry1 \param_geometry
 179 \param geometry2 \param_geometry
 180 \return \return_check2{overlap}
 181
 182 \qbk{[include reference/algorithms/overlaps.qbk]}
 183 */
 184 template <typename Geometry1, typename Geometry2>
 185 inline bool overlaps(Geometry1 const& geometry1, Geometry2 const& geometry2)
 186 {
 187     concepts::check<Geometry1 const>();
 188     concepts::check<Geometry2 const>();
 189
 190     return dispatch::overlaps
 191         <
 192             Geometry1,
 193             Geometry2
 194         >::apply(geometry1, geometry2);
 195 }
 196
 197 }} // namespace boost::geometry
 198
 199 #endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP