detail/overlaps/implementation.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
0006
0007 // This file was modified by Oracle on 2014-2022.
0008 // Modifications copyright (c) 2014-2022 Oracle and/or its affiliates.
0009
0010 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0011
0012 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
0013 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
0014
0015 // Use, modification and distribution is subject to the Boost Software License,
0016 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0017 // http://www.boost.org/LICENSE_1_0.txt)
0018
0019 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAPS_IMPLEMENTATION_HPP
0020 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAPS_IMPLEMENTATION_HPP
0021
0022
0023 #include <cstddef>
0024
0025 #include <boost/geometry/core/access.hpp>
0026
0027 #include <boost/geometry/algorithms/detail/gc_topological_dimension.hpp>
0028 #include <boost/geometry/algorithms/detail/overlaps/interface.hpp>
0029 #include <boost/geometry/algorithms/detail/relate/implementation.hpp>
0030 #include <boost/geometry/algorithms/detail/relate/implementation_gc.hpp>
0031 #include <boost/geometry/algorithms/not_implemented.hpp>
0032
0033 #include <boost/geometry/geometries/concepts/check.hpp>
0034
0035 #include <boost/geometry/strategies/relate/cartesian.hpp>
0036 #include <boost/geometry/strategies/relate/geographic.hpp>
0037 #include <boost/geometry/strategies/relate/spherical.hpp>
0038
0039 #include <boost/geometry/views/detail/geometry_collection_view.hpp>
0040
0041
0042 namespace boost { namespace geometry
0043 {
0044
0045 #ifndef DOXYGEN_NO_DETAIL
0046 namespace detail { namespace overlaps
0047 {
0048
0049 template
0050 <
0051     std::size_t Dimension,
0052     std::size_t DimensionCount
0053 >
0054 struct box_box_loop
0055 {
0056     template <typename Box1, typename Box2>
0057     static inline void apply(Box1 const& b1, Box2 const& b2,
0058             bool& overlaps, bool& one_in_two, bool& two_in_one)
0059     {
0060         assert_dimension_equal<Box1, Box2>();
0061
0062         typedef typename coordinate_type<Box1>::type coordinate_type1;
0063         typedef typename coordinate_type<Box2>::type coordinate_type2;
0064
0065         coordinate_type1 const& min1 = get<min_corner, Dimension>(b1);
0066         coordinate_type1 const& max1 = get<max_corner, Dimension>(b1);
0067         coordinate_type2 const& min2 = get<min_corner, Dimension>(b2);
0068         coordinate_type2 const& max2 = get<max_corner, Dimension>(b2);
0069
0070         // We might use the (not yet accepted) Boost.Interval
0071         // submission in the future
0072
0073         // If:
0074         // B1: |-------|
0075         // B2:           |------|
0076         // in any dimension -> no overlap
0077         if (max1 <= min2 || min1 >= max2)
0078         {
0079             overlaps = false;
0080             return;
0081         }
0082
0083         // If:
0084         // B1: |--------------------|
0085         // B2:   |-------------|
0086         // in all dimensions -> within, then no overlap
0087         // B1: |--------------------|
0088         // B2: |-------------|
0089         // this is "within-touch" -> then no overlap. So use < and >
0090         if (min1 < min2 || max1 > max2)
0091         {
0092             one_in_two = false;
0093         }
0094
0095         // Same other way round
0096         if (min2 < min1 || max2 > max1)
0097         {
0098             two_in_one = false;
0099         }
0100
0101         box_box_loop
0102             <
0103                 Dimension + 1,
0104                 DimensionCount
0105             >::apply(b1, b2, overlaps, one_in_two, two_in_one);
0106     }
0107 };
0108
0109 template
0110 <
0111     std::size_t DimensionCount
0112 >
0113 struct box_box_loop<DimensionCount, DimensionCount>
0114 {
0115     template <typename Box1, typename Box2>
0116     static inline void apply(Box1 const& , Box2 const&, bool&, bool&, bool&)
0117     {
0118     }
0119 };
0120
0121 struct box_box
0122 {
0123     template <typename Box1, typename Box2, typename Strategy>
0124     static inline bool apply(Box1 const& b1, Box2 const& b2, Strategy const& /*strategy*/)
0125     {
0126         bool overlaps = true;
0127         bool within1 = true;
0128         bool within2 = true;
0129         box_box_loop
0130             <
0131                 0,
0132                 dimension<Box1>::type::value
0133             >::apply(b1, b2, overlaps, within1, within2);
0134
0135         /*
0136         \see http://docs.codehaus.org/display/GEOTDOC/02+Geometry+Relationships#02GeometryRelationships-Overlaps
0137         where is stated that "inside" is not an "overlap",
0138         this is true and is implemented as such.
0139         */
0140         return overlaps && ! within1 && ! within2;
0141     }
0142 };
0143
0144 }} // namespace detail::overlaps
0145 #endif // DOXYGEN_NO_DETAIL
0146
0147
0148 #ifndef DOXYGEN_NO_DISPATCH
0149 namespace dispatch
0150 {
0151
0152 template <typename Box1, typename Box2>
0153 struct overlaps<Box1, Box2, box_tag, box_tag>
0154     : detail::overlaps::box_box
0155 {};
0156
0157
0158 template <typename Geometry1, typename Geometry2>
0159 struct overlaps<Geometry1, Geometry2, geometry_collection_tag, geometry_collection_tag>
0160 {
0161     template <typename Strategy>
0162     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0163                              Strategy const& strategy)
0164     {
0165         int dimension1 = detail::gc_topological_dimension(geometry1);
0166         int dimension2 = detail::gc_topological_dimension(geometry2);
0167
0168         if (dimension1 >= 0 && dimension2 >= 0)
0169         {
0170             if (dimension1 == 1 && dimension2 == 1)
0171             {
0172                 return detail::relate::relate_impl
0173                     <
0174                         detail::de9im::static_mask_overlaps_d1_1_d2_1_type,
0175                         Geometry1,
0176                         Geometry2
0177                     >::apply(geometry1, geometry2, strategy);
0178             }
0179             else if (dimension1 == dimension2)
0180             {
0181                 return detail::relate::relate_impl
0182                     <
0183                         detail::de9im::static_mask_overlaps_d1_eq_d2_type,
0184                         Geometry1,
0185                         Geometry2
0186                     >::apply(geometry1, geometry2, strategy);
0187             }
0188         }
0189
0190         return false;
0191     }
0192 };
0193
0194 template <typename Geometry1, typename Geometry2, typename Tag1>
0195 struct overlaps<Geometry1, Geometry2, Tag1, geometry_collection_tag>
0196 {
0197     template <typename Strategy>
0198     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0199                              Strategy const& strategy)
0200     {
0201         using gc1_view_t = detail::geometry_collection_view<Geometry1>;
0202         return overlaps
0203             <
0204                 gc1_view_t, Geometry2
0205             >::apply(gc1_view_t(geometry1), geometry2, strategy);
0206     }
0207 };
0208
0209 template <typename Geometry1, typename Geometry2, typename Tag2>
0210 struct overlaps<Geometry1, Geometry2, geometry_collection_tag, Tag2>
0211 {
0212     template <typename Strategy>
0213     static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
0214                              Strategy const& strategy)
0215     {
0216         using gc2_view_t = detail::geometry_collection_view<Geometry2>;
0217         return overlaps
0218             <
0219                 Geometry1, gc2_view_t
0220             >::apply(geometry1, gc2_view_t(geometry2), strategy);
0221     }
0222 };
0223
0224
0225 } // namespace dispatch
0226 #endif // DOXYGEN_NO_DISPATCH
0227
0228
0229 }} // namespace boost::geometry
0230
0231 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAPS_IMPLEMENTATION_HPP