1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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-2014.
9 // Modifications copyright (c) 2013-2014, Oracle and/or its affiliates.
10 
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
13 
14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
16 
17 // Use, modification and distribution is subject to the Boost Software License,
18 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
19 // http://www.boost.org/LICENSE_1_0.txt)
20 
21 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP
22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP
23 
24 #include <cstddef>
25 #include <utility>
26 
27 #include <boost/numeric/conversion/cast.hpp>
28 
29 #include <boost/geometry/util/math.hpp>
30 #include <boost/geometry/util/calculation_type.hpp>
31 
32 #include <boost/geometry/core/access.hpp>
33 #include <boost/geometry/core/tags.hpp>
34 #include <boost/geometry/core/coordinate_dimension.hpp>
35 #include <boost/geometry/core/point_type.hpp>
36 
37 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
38 
39 #include <boost/geometry/algorithms/dispatch/disjoint.hpp>
40 
41 
42 namespace boost { namespace geometry
43 {
44 
45 
46 #ifndef DOXYGEN_NO_DETAIL
47 namespace detail { namespace disjoint
48 {
49 
50 
51 template <std::size_t I>
52 struct compute_tmin_tmax_per_dim
53 {
54     template <typename SegmentPoint, typename Box, typename RelativeDistance>
applyboost::geometry::detail::disjoint::compute_tmin_tmax_per_dim55     static inline void apply(SegmentPoint const& p0,
56                              SegmentPoint const& p1,
57                              Box const& box,
58                              RelativeDistance& ti_min,
59                              RelativeDistance& ti_max,
60                              RelativeDistance& diff)
61     {
62         typedef typename coordinate_type<Box>::type box_coordinate_type;
63         typedef typename coordinate_type
64             <
65                 SegmentPoint
66             >::type point_coordinate_type;
67 
68         RelativeDistance c_p0 = boost::numeric_cast
69             <
70                 point_coordinate_type
71             >( geometry::get<I>(p0) );
72 
73         RelativeDistance c_p1 = boost::numeric_cast
74             <
75                 point_coordinate_type
76             >( geometry::get<I>(p1) );
77 
78         RelativeDistance c_b_min = boost::numeric_cast
79             <
80                 box_coordinate_type
81             >( geometry::get<geometry::min_corner, I>(box) );
82 
83         RelativeDistance c_b_max = boost::numeric_cast
84             <
85                 box_coordinate_type
86             >( geometry::get<geometry::max_corner, I>(box) );
87 
88         if ( geometry::get<I>(p1) >= geometry::get<I>(p0) )
89         {
90             diff = c_p1 - c_p0;
91             ti_min = c_b_min - c_p0;
92             ti_max = c_b_max - c_p0;
93         }
94         else
95         {
96             diff = c_p0 - c_p1;
97             ti_min = c_p0 - c_b_max;
98             ti_max = c_p0 - c_b_min;
99         }
100     }
101 };
102 
103 
104 template
105 <
106     typename RelativeDistance,
107     typename SegmentPoint,
108     typename Box,
109     std::size_t I,
110     std::size_t Dimension
111 >
112 struct disjoint_segment_box_impl
113 {
114     template <typename RelativeDistancePair>
applyboost::geometry::detail::disjoint::disjoint_segment_box_impl115     static inline bool apply(SegmentPoint const& p0,
116                              SegmentPoint const& p1,
117                              Box const& box,
118                              RelativeDistancePair& t_min,
119                              RelativeDistancePair& t_max)
120     {
121         RelativeDistance ti_min, ti_max, diff;
122 
123         compute_tmin_tmax_per_dim<I>::apply(p0, p1, box, ti_min, ti_max, diff);
124 
125         if ( geometry::math::equals(diff, 0) )
126         {
127             if ( (geometry::math::equals(t_min.second, 0)
128                   && t_min.first > ti_max)
129                  ||
130                  (geometry::math::equals(t_max.second, 0)
131                   && t_max.first < ti_min) )
132             {
133                 return true;
134             }
135         }
136 
137         RelativeDistance t_min_x_diff = t_min.first * diff;
138         RelativeDistance t_max_x_diff = t_max.first * diff;
139 
140         if ( t_min_x_diff > ti_max * t_min.second
141              || t_max_x_diff < ti_min * t_max.second )
142         {
143             return true;
144         }
145 
146         if ( ti_min * t_min.second > t_min_x_diff )
147         {
148             t_min.first = ti_min;
149             t_min.second = diff;
150         }
151         if ( ti_max * t_max.second < t_max_x_diff )
152         {
153             t_max.first = ti_max;
154             t_max.second = diff;
155         }
156 
157         if ( t_min.first > t_min.second || t_max.first < 0 )
158         {
159             return true;
160         }
161 
162         return disjoint_segment_box_impl
163             <
164                 RelativeDistance,
165                 SegmentPoint,
166                 Box,
167                 I + 1,
168                 Dimension
169             >::apply(p0, p1, box, t_min, t_max);
170     }
171 };
172 
173 
174 template
175 <
176     typename RelativeDistance,
177     typename SegmentPoint,
178     typename Box,
179     std::size_t Dimension
180 >
181 struct disjoint_segment_box_impl
182     <
183         RelativeDistance, SegmentPoint, Box, 0, Dimension
184     >
185 {
applyboost::geometry::detail::disjoint::disjoint_segment_box_impl186     static inline bool apply(SegmentPoint const& p0,
187                              SegmentPoint const& p1,
188                              Box const& box)
189     {
190         std::pair<RelativeDistance, RelativeDistance> t_min, t_max;
191         RelativeDistance diff;
192 
193         compute_tmin_tmax_per_dim<0>::apply(p0, p1, box,
194                                             t_min.first, t_max.first, diff);
195 
196         if ( geometry::math::equals(diff, 0) )
197         {
198             if ( geometry::math::equals(t_min.first, 0) ) { t_min.first = -1; }
199             if ( geometry::math::equals(t_max.first, 0) ) { t_max.first = 1; }
200         }
201 
202         if ( t_min.first > diff || t_max.first < 0 )
203         {
204             return true;
205         }
206 
207         t_min.second = t_max.second = diff;
208 
209         return disjoint_segment_box_impl
210             <
211                 RelativeDistance, SegmentPoint, Box, 1, Dimension
212             >::apply(p0, p1, box, t_min, t_max);
213     }
214 };
215 
216 
217 template
218 <
219     typename RelativeDistance,
220     typename SegmentPoint,
221     typename Box,
222     std::size_t Dimension
223 >
224 struct disjoint_segment_box_impl
225     <
226         RelativeDistance, SegmentPoint, Box, Dimension, Dimension
227     >
228 {
229     template <typename RelativeDistancePair>
applyboost::geometry::detail::disjoint::disjoint_segment_box_impl230     static inline bool apply(SegmentPoint const&, SegmentPoint const&,
231                              Box const&,
232                              RelativeDistancePair&, RelativeDistancePair&)
233     {
234         return false;
235     }
236 };
237 
238 
239 //=========================================================================
240 
241 
242 template <typename Segment, typename Box>
243 struct disjoint_segment_box
244 {
applyboost::geometry::detail::disjoint::disjoint_segment_box245     static inline bool apply(Segment const& segment, Box const& box)
246     {
247         assert_dimension_equal<Segment, Box>();
248 
249         typedef typename util::calculation_type::geometric::binary
250             <
251                 Segment, Box, void
252             >::type relative_distance_type;
253 
254         typedef typename point_type<Segment>::type segment_point_type;
255         segment_point_type p0, p1;
256         geometry::detail::assign_point_from_index<0>(segment, p0);
257         geometry::detail::assign_point_from_index<1>(segment, p1);
258 
259         return disjoint_segment_box_impl
260             <
261                 relative_distance_type, segment_point_type, Box,
262                 0, dimension<Box>::value
263             >::apply(p0, p1, box);
264     }
265 };
266 
267 
268 }} // namespace detail::disjoint
269 #endif // DOXYGEN_NO_DETAIL
270 
271 
272 
273 #ifndef DOXYGEN_NO_DISPATCH
274 namespace dispatch
275 {
276 
277 
278 template <typename Segment, typename Box, std::size_t DimensionCount>
279 struct disjoint<Segment, Box, DimensionCount, segment_tag, box_tag, false>
280     : detail::disjoint::disjoint_segment_box<Segment, Box>
281 {};
282 
283 
284 } // namespace dispatch
285 #endif // DOXYGEN_NO_DISPATCH
286 
287 
288 }} // namespace boost::geometry
289 
290 
291 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP
292