1 // Boost.Geometry
2 
3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
6 // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland.
7 
8 // This file was modified by Oracle on 2013-2017.
9 // Modifications copyright (c) 2013-2017, Oracle and/or its affiliates.
10 
11 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
13 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP
20 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP
21 
22 
23 #include <cstddef>
24 #include <utility>
25 
26 #include <boost/numeric/conversion/cast.hpp>
27 
28 #include <boost/geometry/util/math.hpp>
29 #include <boost/geometry/util/calculation_type.hpp>
30 
31 #include <boost/geometry/core/access.hpp>
32 #include <boost/geometry/core/tags.hpp>
33 #include <boost/geometry/core/coordinate_dimension.hpp>
34 #include <boost/geometry/core/point_type.hpp>
35 
36 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
37 
38 #include <boost/geometry/strategies/disjoint.hpp>
39 
40 
41 namespace boost { namespace geometry { namespace strategy { namespace disjoint
42 {
43 
44 namespace detail
45 {
46 
47 template <std::size_t I>
48 struct compute_tmin_tmax_per_dim
49 {
50     template <typename SegmentPoint, typename Box, typename RelativeDistance>
applyboost::geometry::strategy::disjoint::detail::compute_tmin_tmax_per_dim51     static inline void apply(SegmentPoint const& p0,
52                              SegmentPoint const& p1,
53                              Box const& box,
54                              RelativeDistance& ti_min,
55                              RelativeDistance& ti_max,
56                              RelativeDistance& diff)
57     {
58         typedef typename coordinate_type<Box>::type box_coordinate_type;
59         typedef typename coordinate_type
60             <
61                 SegmentPoint
62             >::type point_coordinate_type;
63 
64         RelativeDistance c_p0 = boost::numeric_cast
65             <
66                 point_coordinate_type
67             >( geometry::get<I>(p0) );
68 
69         RelativeDistance c_p1 = boost::numeric_cast
70             <
71                 point_coordinate_type
72             >( geometry::get<I>(p1) );
73 
74         RelativeDistance c_b_min = boost::numeric_cast
75             <
76                 box_coordinate_type
77             >( geometry::get<geometry::min_corner, I>(box) );
78 
79         RelativeDistance c_b_max = boost::numeric_cast
80             <
81                 box_coordinate_type
82             >( geometry::get<geometry::max_corner, I>(box) );
83 
84         if ( geometry::get<I>(p1) >= geometry::get<I>(p0) )
85         {
86             diff = c_p1 - c_p0;
87             ti_min = c_b_min - c_p0;
88             ti_max = c_b_max - c_p0;
89         }
90         else
91         {
92             diff = c_p0 - c_p1;
93             ti_min = c_p0 - c_b_max;
94             ti_max = c_p0 - c_b_min;
95         }
96     }
97 };
98 
99 
100 template
101 <
102     typename RelativeDistance,
103     typename SegmentPoint,
104     typename Box,
105     std::size_t I,
106     std::size_t Dimension
107 >
108 struct disjoint_segment_box_impl
109 {
110     template <typename RelativeDistancePair>
applyboost::geometry::strategy::disjoint::detail::disjoint_segment_box_impl111     static inline bool apply(SegmentPoint const& p0,
112                              SegmentPoint const& p1,
113                              Box const& box,
114                              RelativeDistancePair& t_min,
115                              RelativeDistancePair& t_max)
116     {
117         RelativeDistance ti_min, ti_max, diff;
118 
119         compute_tmin_tmax_per_dim<I>::apply(p0, p1, box, ti_min, ti_max, diff);
120 
121         if ( geometry::math::equals(diff, 0) )
122         {
123             if ( (geometry::math::equals(t_min.second, 0)
124                   && t_min.first > ti_max)
125                  ||
126                  (geometry::math::equals(t_max.second, 0)
127                   && t_max.first < ti_min)
128                  ||
129                  (math::sign(ti_min) * math::sign(ti_max) > 0) )
130             {
131                 return true;
132             }
133         }
134 
135         RelativeDistance t_min_x_diff = t_min.first * diff;
136         RelativeDistance t_max_x_diff = t_max.first * diff;
137 
138         if ( t_min_x_diff > ti_max * t_min.second
139              || t_max_x_diff < ti_min * t_max.second )
140         {
141             return true;
142         }
143 
144         if ( ti_min * t_min.second > t_min_x_diff )
145         {
146             t_min.first = ti_min;
147             t_min.second = diff;
148         }
149         if ( ti_max * t_max.second < t_max_x_diff )
150         {
151             t_max.first = ti_max;
152             t_max.second = diff;
153         }
154 
155         if ( t_min.first > t_min.second || t_max.first < 0 )
156         {
157             return true;
158         }
159 
160         return disjoint_segment_box_impl
161             <
162                 RelativeDistance,
163                 SegmentPoint,
164                 Box,
165                 I + 1,
166                 Dimension
167             >::apply(p0, p1, box, t_min, t_max);
168     }
169 };
170 
171 
172 template
173 <
174     typename RelativeDistance,
175     typename SegmentPoint,
176     typename Box,
177     std::size_t Dimension
178 >
179 struct disjoint_segment_box_impl
180     <
181         RelativeDistance, SegmentPoint, Box, 0, Dimension
182     >
183 {
applyboost::geometry::strategy::disjoint::detail::disjoint_segment_box_impl184     static inline bool apply(SegmentPoint const& p0,
185                              SegmentPoint const& p1,
186                              Box const& box)
187     {
188         std::pair<RelativeDistance, RelativeDistance> t_min, t_max;
189         RelativeDistance diff;
190 
191         compute_tmin_tmax_per_dim<0>::apply(p0, p1, box,
192                                             t_min.first, t_max.first, diff);
193 
194         if ( geometry::math::equals(diff, 0) )
195         {
196             if ( geometry::math::equals(t_min.first, 0) ) { t_min.first = -1; }
197             if ( geometry::math::equals(t_max.first, 0) ) { t_max.first = 1; }
198 
199             if (math::sign(t_min.first) * math::sign(t_max.first) > 0)
200             {
201                 return true;
202             }
203         }
204 
205         if ( t_min.first > diff || t_max.first < 0 )
206         {
207             return true;
208         }
209 
210         t_min.second = t_max.second = diff;
211 
212         return disjoint_segment_box_impl
213             <
214                 RelativeDistance, SegmentPoint, Box, 1, Dimension
215             >::apply(p0, p1, box, t_min, t_max);
216     }
217 };
218 
219 
220 template
221 <
222     typename RelativeDistance,
223     typename SegmentPoint,
224     typename Box,
225     std::size_t Dimension
226 >
227 struct disjoint_segment_box_impl
228     <
229         RelativeDistance, SegmentPoint, Box, Dimension, Dimension
230     >
231 {
232     template <typename RelativeDistancePair>
applyboost::geometry::strategy::disjoint::detail::disjoint_segment_box_impl233     static inline bool apply(SegmentPoint const&, SegmentPoint const&,
234                              Box const&,
235                              RelativeDistancePair&, RelativeDistancePair&)
236     {
237         return false;
238     }
239 };
240 
241 } // namespace detail
242 
243 // NOTE: This may be temporary place for this or corresponding strategy
244 // It seems to be more appropriate to implement the opposite of it
245 // e.g. intersection::segment_box because in disjoint() algorithm
246 // other strategies that are used are intersection and covered_by strategies.
247 struct segment_box
248 {
249     template <typename Segment, typename Box>
250     struct point_in_geometry_strategy
251         : services::default_strategy
252             <
253                 typename point_type<Segment>::type,
254                 Box
255             >
256     {};
257 
258     template <typename Segment, typename Box>
259     static inline typename point_in_geometry_strategy<Segment, Box>::type
get_point_in_geometry_strategyboost::geometry::strategy::disjoint::segment_box260         get_point_in_geometry_strategy()
261     {
262         typedef typename point_in_geometry_strategy<Segment, Box>::type strategy_type;
263 
264         return strategy_type();
265     }
266 
267     template <typename Segment, typename Box>
applyboost::geometry::strategy::disjoint::segment_box268     static inline bool apply(Segment const& segment, Box const& box)
269     {
270         assert_dimension_equal<Segment, Box>();
271 
272         typedef typename util::calculation_type::geometric::binary
273             <
274                 Segment, Box, void
275             >::type relative_distance_type;
276 
277         typedef typename point_type<Segment>::type segment_point_type;
278         segment_point_type p0, p1;
279         geometry::detail::assign_point_from_index<0>(segment, p0);
280         geometry::detail::assign_point_from_index<1>(segment, p1);
281 
282         return detail::disjoint_segment_box_impl
283             <
284                 relative_distance_type, segment_point_type, Box,
285                 0, dimension<Box>::value
286             >::apply(p0, p1, box);
287     }
288 };
289 
290 
291 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
292 
293 
294 namespace services
295 {
296 
297 template <typename Linear, typename Box, typename LinearTag>
298 struct default_strategy<Linear, Box, LinearTag, box_tag, 1, 2, cartesian_tag, cartesian_tag>
299 {
300     typedef disjoint::segment_box type;
301 };
302 
303 template <typename Box, typename Linear, typename LinearTag>
304 struct default_strategy<Box, Linear, box_tag, LinearTag, 2, 1, cartesian_tag, cartesian_tag>
305 {
306     typedef disjoint::segment_box type;
307 };
308 
309 
310 } // namespace services
311 
312 
313 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
314 
315 
316 }}}} // namespace boost::geometry::strategy::disjoint
317 
318 
319 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP
320