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