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 // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland.
7 
8 // This file was modified by Oracle on 2015, 2016, 2017.
9 // Modifications copyright (c) 2016-2017, Oracle and/or its affiliates.
10 
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
12 
13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
15 
16 // Use, modification and distribution is subject to the Boost Software License,
17 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
18 // http://www.boost.org/LICENSE_1_0.txt)
19 
20 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_BOX_IN_BOX_HPP
21 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_BOX_IN_BOX_HPP
22 
23 
24 #include <boost/geometry/core/access.hpp>
25 #include <boost/geometry/core/coordinate_dimension.hpp>
26 #include <boost/geometry/strategies/covered_by.hpp>
27 #include <boost/geometry/strategies/within.hpp>
28 #include <boost/geometry/util/normalize_spheroidal_coordinates.hpp>
29 
30 
31 namespace boost { namespace geometry { namespace strategy
32 {
33 
34 
35 namespace within
36 {
37 
38 
39 struct box_within_coord
40 {
41     template <typename BoxContainedValue, typename BoxContainingValue>
applyboost::geometry::strategy::within::box_within_coord42     static inline bool apply(BoxContainedValue const& bed_min,
43                              BoxContainedValue const& bed_max,
44                              BoxContainingValue const& bing_min,
45                              BoxContainingValue const& bing_max)
46     {
47         return bing_min <= bed_min && bed_max <= bing_max // contained in containing
48             && bed_min < bed_max;                         // interiors overlap
49     }
50 };
51 
52 
53 struct box_covered_by_coord
54 {
55     template <typename BoxContainedValue, typename BoxContainingValue>
applyboost::geometry::strategy::within::box_covered_by_coord56     static inline bool apply(BoxContainedValue const& bed_min,
57                              BoxContainedValue const& bed_max,
58                              BoxContainingValue const& bing_min,
59                              BoxContainingValue const& bing_max)
60     {
61         return bed_min >= bing_min && bed_max <= bing_max;
62     }
63 };
64 
65 
66 template <typename Geometry, std::size_t Dimension, typename CSTag>
67 struct box_within_range
68     : box_within_coord
69 {};
70 
71 
72 template <typename Geometry, std::size_t Dimension, typename CSTag>
73 struct box_covered_by_range
74     : box_covered_by_coord
75 {};
76 
77 
78 struct box_within_longitude_diff
79 {
80     template <typename CalcT>
applyboost::geometry::strategy::within::box_within_longitude_diff81     static inline bool apply(CalcT const& diff_ed)
82     {
83         return diff_ed > CalcT(0);
84     }
85 };
86 
87 struct box_covered_by_longitude_diff
88 {
89     template <typename CalcT>
applyboost::geometry::strategy::within::box_covered_by_longitude_diff90     static inline bool apply(CalcT const&)
91     {
92         return true;
93     }
94 };
95 
96 template <typename Geometry,
97           typename CoordCheck,
98           typename InteriorCheck>
99 struct box_longitude_range
100 {
101     template <typename BoxContainedValue, typename BoxContainingValue>
applyboost::geometry::strategy::within::box_longitude_range102     static inline bool apply(BoxContainedValue const& bed_min,
103                              BoxContainedValue const& bed_max,
104                              BoxContainingValue const& bing_min,
105                              BoxContainingValue const& bing_max)
106     {
107         typedef typename select_most_precise
108             <
109                 BoxContainedValue,
110                 BoxContainingValue
111             >::type calc_t;
112         typedef typename coordinate_system<Geometry>::type::units units_t;
113         typedef math::detail::constants_on_spheroid<calc_t, units_t> constants;
114 
115         if (CoordCheck::apply(bed_min, bed_max, bing_min, bing_max))
116         {
117             return true;
118         }
119 
120         // min <= max <=> diff >= 0
121         calc_t const diff_ed = bed_max - bed_min;
122         calc_t const diff_ing = bing_max - bing_min;
123 
124         // if containing covers the whole globe it contains all
125         if (diff_ing >= constants::period())
126         {
127             return true;
128         }
129 
130         // if containing is smaller it cannot contain
131         // and check interior (within vs covered_by)
132         if (diff_ing < diff_ed || ! InteriorCheck::apply(diff_ed))
133         {
134             return false;
135         }
136 
137         // calculate positive longitude translation with bing_min as origin
138         calc_t const diff_min = math::longitude_distance_unsigned<units_t>(bing_min, bed_min);
139 
140         // max of contained translated into the containing origin must be lesser than max of containing
141         return bing_min + diff_min + diff_ed <= bing_max
142             /*|| bing_max - diff_min - diff_ed >= bing_min*/;
143     }
144 };
145 
146 
147 // spherical_equatorial_tag, spherical_polar_tag and geographic_cat are casted to spherical_tag
148 template <typename Geometry>
149 struct box_within_range<Geometry, 0, spherical_tag>
150     : box_longitude_range<Geometry, box_within_coord, box_within_longitude_diff>
151 {};
152 
153 
154 template <typename Geometry>
155 struct box_covered_by_range<Geometry, 0, spherical_tag>
156     : box_longitude_range<Geometry, box_covered_by_coord, box_covered_by_longitude_diff>
157 {};
158 
159 
160 template
161 <
162     template <typename, std::size_t, typename> class SubStrategy,
163     typename Box1,
164     typename Box2,
165     std::size_t Dimension,
166     std::size_t DimensionCount
167 >
168 struct relate_box_box_loop
169 {
applyboost::geometry::strategy::within::relate_box_box_loop170     static inline bool apply(Box1 const& b_contained, Box2 const& b_containing)
171     {
172         assert_dimension_equal<Box1, Box2>();
173         typedef typename tag_cast<typename cs_tag<Box1>::type, spherical_tag>::type cs_tag_t;
174 
175         if (! SubStrategy<Box1, Dimension, cs_tag_t>::apply(
176                     get<min_corner, Dimension>(b_contained),
177                     get<max_corner, Dimension>(b_contained),
178                     get<min_corner, Dimension>(b_containing),
179                     get<max_corner, Dimension>(b_containing)
180                 )
181             )
182         {
183             return false;
184         }
185 
186         return relate_box_box_loop
187             <
188                 SubStrategy,
189                 Box1, Box2,
190                 Dimension + 1, DimensionCount
191             >::apply(b_contained, b_containing);
192     }
193 };
194 
195 template
196 <
197     template <typename, std::size_t, typename> class SubStrategy,
198     typename Box1,
199     typename Box2,
200     std::size_t DimensionCount
201 >
202 struct relate_box_box_loop<SubStrategy, Box1, Box2, DimensionCount, DimensionCount>
203 {
applyboost::geometry::strategy::within::relate_box_box_loop204     static inline bool apply(Box1 const& , Box2 const& )
205     {
206         return true;
207     }
208 };
209 
210 template
211 <
212     typename Box1,
213     typename Box2,
214     template <typename, std::size_t, typename> class SubStrategy = box_within_range
215 >
216 struct box_in_box
217 {
applyboost::geometry::strategy::within::box_in_box218     static inline bool apply(Box1 const& box1, Box2 const& box2)
219     {
220         return relate_box_box_loop
221             <
222                 SubStrategy,
223                 Box1, Box2, 0, dimension<Box1>::type::value
224             >::apply(box1, box2);
225     }
226 };
227 
228 
229 } // namespace within
230 
231 
232 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
233 
234 
235 namespace within { namespace services
236 {
237 
238 template <typename BoxContained, typename BoxContaining>
239 struct default_strategy
240     <
241         BoxContained, BoxContaining,
242         box_tag, box_tag,
243         areal_tag, areal_tag,
244         cartesian_tag, cartesian_tag
245     >
246 {
247     typedef within::box_in_box<BoxContained, BoxContaining> type;
248 };
249 
250 // spherical_equatorial_tag, spherical_polar_tag and geographic_cat are casted to spherical_tag
251 template <typename BoxContained, typename BoxContaining>
252 struct default_strategy
253     <
254         BoxContained, BoxContaining,
255         box_tag, box_tag,
256         areal_tag, areal_tag,
257         spherical_tag, spherical_tag
258     >
259 {
260     typedef within::box_in_box<BoxContained, BoxContaining> type;
261 };
262 
263 
264 }} // namespace within::services
265 
266 namespace covered_by { namespace services
267 {
268 
269 template <typename BoxContained, typename BoxContaining>
270 struct default_strategy
271     <
272         BoxContained, BoxContaining,
273         box_tag, box_tag,
274         areal_tag, areal_tag,
275         cartesian_tag, cartesian_tag
276     >
277 {
278     typedef within::box_in_box
279                 <
280                     BoxContained, BoxContaining,
281                     within::box_covered_by_range
282                 > type;
283 };
284 
285 // spherical_equatorial_tag, spherical_polar_tag and geographic_cat are casted to spherical_tag
286 template <typename BoxContained, typename BoxContaining>
287 struct default_strategy
288     <
289         BoxContained, BoxContaining,
290         box_tag, box_tag,
291         areal_tag, areal_tag,
292         spherical_tag, spherical_tag
293     >
294 {
295     typedef within::box_in_box
296                 <
297                     BoxContained, BoxContaining,
298                     within::box_covered_by_range
299                 > type;
300 };
301 
302 
303 }} // namespace covered_by::services
304 
305 
306 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
307 
308 
309 }}} // namespace boost::geometry::strategy
310 
311 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_BOX_IN_BOX_HPP
312