Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
Chris@16: // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
Chris@16: 
Chris@101: // This file was modified by Oracle on 2014.
Chris@101: // Modifications copyright (c) 2014 Oracle and/or its affiliates.
Chris@101: 
Chris@16: // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
Chris@16: // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@101: // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
Chris@101: 
Chris@16: #ifndef BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP
Chris@16: 
Chris@16: 
Chris@16: #include <cstddef>
Chris@16: 
Chris@16: #include <boost/geometry/core/access.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/not_implemented.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/geometries/concepts/check.hpp>
Chris@16: 
Chris@101: #include <boost/geometry/algorithms/detail/relate/relate.hpp>
Chris@101: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail { namespace overlaps
Chris@16: {
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     std::size_t Dimension,
Chris@16:     std::size_t DimensionCount
Chris@16: >
Chris@16: struct box_box_loop
Chris@16: {
Chris@16:     template <typename Box1, typename Box2>
Chris@16:     static inline void apply(Box1 const& b1, Box2 const& b2,
Chris@16:             bool& overlaps, bool& one_in_two, bool& two_in_one)
Chris@16:     {
Chris@16:         assert_dimension_equal<Box1, Box2>();
Chris@16: 
Chris@16:         typedef typename coordinate_type<Box1>::type coordinate_type1;
Chris@16:         typedef typename coordinate_type<Box2>::type coordinate_type2;
Chris@16: 
Chris@16:         coordinate_type1 const& min1 = get<min_corner, Dimension>(b1);
Chris@16:         coordinate_type1 const& max1 = get<max_corner, Dimension>(b1);
Chris@16:         coordinate_type2 const& min2 = get<min_corner, Dimension>(b2);
Chris@16:         coordinate_type2 const& max2 = get<max_corner, Dimension>(b2);
Chris@16: 
Chris@16:         // We might use the (not yet accepted) Boost.Interval
Chris@16:         // submission in the future
Chris@16: 
Chris@16:         // If:
Chris@16:         // B1: |-------|
Chris@16:         // B2:           |------|
Chris@16:         // in any dimension -> no overlap
Chris@16:         if (max1 <= min2 || min1 >= max2)
Chris@16:         {
Chris@16:             overlaps = false;
Chris@16:             return;
Chris@16:         }
Chris@16: 
Chris@16:         // If:
Chris@16:         // B1: |--------------------|
Chris@16:         // B2:   |-------------|
Chris@16:         // in all dimensions -> within, then no overlap
Chris@16:         // B1: |--------------------|
Chris@16:         // B2: |-------------|
Chris@16:         // this is "within-touch" -> then no overlap. So use < and >
Chris@16:         if (min1 < min2 || max1 > max2)
Chris@16:         {
Chris@16:             one_in_two = false;
Chris@16:         }
Chris@16:         // Same other way round
Chris@16:         if (min2 < min1 || max2 > max1)
Chris@16:         {
Chris@16:             two_in_one = false;
Chris@16:         }
Chris@16: 
Chris@16:         box_box_loop
Chris@16:             <
Chris@16:                 Dimension + 1,
Chris@16:                 DimensionCount
Chris@16:             >::apply(b1, b2, overlaps, one_in_two, two_in_one);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     std::size_t DimensionCount
Chris@16: >
Chris@16: struct box_box_loop<DimensionCount, DimensionCount>
Chris@16: {
Chris@16:     template <typename Box1, typename Box2>
Chris@16:     static inline void apply(Box1 const& , Box2 const&, bool&, bool&, bool&)
Chris@16:     {
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: struct box_box
Chris@16: {
Chris@16:     template <typename Box1, typename Box2>
Chris@16:     static inline bool apply(Box1 const& b1, Box2 const& b2)
Chris@16:     {
Chris@16:         bool overlaps = true;
Chris@16:         bool within1 = true;
Chris@16:         bool within2 = true;
Chris@16:         box_box_loop
Chris@16:             <
Chris@16:                 0,
Chris@16:                 dimension<Box1>::type::value
Chris@16:             >::apply(b1, b2, overlaps, within1, within2);
Chris@16: 
Chris@16:         /*
Chris@16:         \see http://docs.codehaus.org/display/GEOTDOC/02+Geometry+Relationships#02GeometryRelationships-Overlaps
Chris@16:         where is stated that "inside" is not an "overlap",
Chris@16:         this is true and is implemented as such.
Chris@16:         */
Chris@16:         return overlaps && ! within1 && ! within2;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: }} // namespace detail::overlaps
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: //struct not_implemented_for_this_geometry_type : public boost::false_type {};
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DISPATCH
Chris@16: namespace dispatch
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Geometry1,
Chris@16:     typename Geometry2,
Chris@16:     typename Tag1 = typename tag<Geometry1>::type,
Chris@16:     typename Tag2 = typename tag<Geometry2>::type
Chris@16: >
Chris@101: struct overlaps
Chris@101:     : detail::relate::relate_base
Chris@101:         <
Chris@101:             detail::relate::static_mask_overlaps_type,
Chris@101:             Geometry1,
Chris@101:             Geometry2
Chris@101:         >
Chris@16: {};
Chris@16: 
Chris@16: 
Chris@16: template <typename Box1, typename Box2>
Chris@16: struct overlaps<Box1, Box2, box_tag, box_tag>
Chris@16:     : detail::overlaps::box_box
Chris@16: {};
Chris@16: 
Chris@16: } // namespace dispatch
Chris@16: #endif // DOXYGEN_NO_DISPATCH
Chris@16: 
Chris@16: 
Chris@16: /*!
Chris@16: \brief \brief_check2{overlap}
Chris@16: \ingroup overlaps
Chris@101: \tparam Geometry1 \tparam_geometry
Chris@101: \tparam Geometry2 \tparam_geometry
Chris@101: \param geometry1 \param_geometry
Chris@101: \param geometry2 \param_geometry
Chris@16: \return \return_check2{overlap}
Chris@16: 
Chris@16: \qbk{[include reference/algorithms/overlaps.qbk]}
Chris@16: */
Chris@16: template <typename Geometry1, typename Geometry2>
Chris@16: inline bool overlaps(Geometry1 const& geometry1, Geometry2 const& geometry2)
Chris@16: {
Chris@16:     concept::check<Geometry1 const>();
Chris@16:     concept::check<Geometry2 const>();
Chris@16: 
Chris@16:     return dispatch::overlaps
Chris@16:         <
Chris@16:             Geometry1,
Chris@16:             Geometry2
Chris@16:         >::apply(geometry1, geometry2);
Chris@16: }
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_OVERLAPS_HPP