1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
8 // This file was modified by Oracle on 2013-2014.
9 // Modifications copyright (c) 2013-2014, Oracle and/or its affiliates.
11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
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)
21 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP
22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP
27 #include <boost/numeric/conversion/cast.hpp>
29 #include <boost/geometry/util/math.hpp>
30 #include <boost/geometry/util/calculation_type.hpp>
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>
37 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
39 #include <boost/geometry/algorithms/dispatch/disjoint.hpp>
42 namespace boost { namespace geometry
46 #ifndef DOXYGEN_NO_DETAIL
47 namespace detail { namespace disjoint
51 template <std::size_t I>
52 struct compute_tmin_tmax_per_dim
54 template <typename SegmentPoint, typename Box, typename RelativeDistance>
55 static inline void apply(SegmentPoint const& p0,
56 SegmentPoint const& p1,
58 RelativeDistance& ti_min,
59 RelativeDistance& ti_max,
60 RelativeDistance& diff)
62 typedef typename coordinate_type<Box>::type box_coordinate_type;
63 typedef typename coordinate_type
66 >::type point_coordinate_type;
68 RelativeDistance c_p0 = boost::numeric_cast
71 >( geometry::get<I>(p0) );
73 RelativeDistance c_p1 = boost::numeric_cast
76 >( geometry::get<I>(p1) );
78 RelativeDistance c_b_min = boost::numeric_cast
81 >( geometry::get<geometry::min_corner, I>(box) );
83 RelativeDistance c_b_max = boost::numeric_cast
86 >( geometry::get<geometry::max_corner, I>(box) );
88 if ( geometry::get<I>(p1) >= geometry::get<I>(p0) )
91 ti_min = c_b_min - c_p0;
92 ti_max = c_b_max - c_p0;
97 ti_min = c_p0 - c_b_max;
98 ti_max = c_p0 - c_b_min;
106 typename RelativeDistance,
107 typename SegmentPoint,
110 std::size_t Dimension
112 struct disjoint_segment_box_impl
114 template <typename RelativeDistancePair>
115 static inline bool apply(SegmentPoint const& p0,
116 SegmentPoint const& p1,
118 RelativeDistancePair& t_min,
119 RelativeDistancePair& t_max)
121 RelativeDistance ti_min, ti_max, diff;
123 compute_tmin_tmax_per_dim<I>::apply(p0, p1, box, ti_min, ti_max, diff);
125 if ( geometry::math::equals(diff, 0) )
127 if ( (geometry::math::equals(t_min.second, 0)
128 && t_min.first > ti_max)
130 (geometry::math::equals(t_max.second, 0)
131 && t_max.first < ti_min)
133 (math::sign(ti_min) * math::sign(ti_max) > 0) )
139 RelativeDistance t_min_x_diff = t_min.first * diff;
140 RelativeDistance t_max_x_diff = t_max.first * diff;
142 if ( t_min_x_diff > ti_max * t_min.second
143 || t_max_x_diff < ti_min * t_max.second )
148 if ( ti_min * t_min.second > t_min_x_diff )
150 t_min.first = ti_min;
153 if ( ti_max * t_max.second < t_max_x_diff )
155 t_max.first = ti_max;
159 if ( t_min.first > t_min.second || t_max.first < 0 )
164 return disjoint_segment_box_impl
171 >::apply(p0, p1, box, t_min, t_max);
178 typename RelativeDistance,
179 typename SegmentPoint,
181 std::size_t Dimension
183 struct disjoint_segment_box_impl
185 RelativeDistance, SegmentPoint, Box, 0, Dimension
188 static inline bool apply(SegmentPoint const& p0,
189 SegmentPoint const& p1,
192 std::pair<RelativeDistance, RelativeDistance> t_min, t_max;
193 RelativeDistance diff;
195 compute_tmin_tmax_per_dim<0>::apply(p0, p1, box,
196 t_min.first, t_max.first, diff);
198 if ( geometry::math::equals(diff, 0) )
200 if ( geometry::math::equals(t_min.first, 0) ) { t_min.first = -1; }
201 if ( geometry::math::equals(t_max.first, 0) ) { t_max.first = 1; }
203 if (math::sign(t_min.first) * math::sign(t_max.first) > 0)
209 if ( t_min.first > diff || t_max.first < 0 )
214 t_min.second = t_max.second = diff;
216 return disjoint_segment_box_impl
218 RelativeDistance, SegmentPoint, Box, 1, Dimension
219 >::apply(p0, p1, box, t_min, t_max);
226 typename RelativeDistance,
227 typename SegmentPoint,
229 std::size_t Dimension
231 struct disjoint_segment_box_impl
233 RelativeDistance, SegmentPoint, Box, Dimension, Dimension
236 template <typename RelativeDistancePair>
237 static inline bool apply(SegmentPoint const&, SegmentPoint const&,
239 RelativeDistancePair&, RelativeDistancePair&)
246 //=========================================================================
249 template <typename Segment, typename Box>
250 struct disjoint_segment_box
252 static inline bool apply(Segment const& segment, Box const& box)
254 assert_dimension_equal<Segment, Box>();
256 typedef typename util::calculation_type::geometric::binary
259 >::type relative_distance_type;
261 typedef typename point_type<Segment>::type segment_point_type;
262 segment_point_type p0, p1;
263 geometry::detail::assign_point_from_index<0>(segment, p0);
264 geometry::detail::assign_point_from_index<1>(segment, p1);
266 return disjoint_segment_box_impl
268 relative_distance_type, segment_point_type, Box,
269 0, dimension<Box>::value
270 >::apply(p0, p1, box);
275 }} // namespace detail::disjoint
276 #endif // DOXYGEN_NO_DETAIL
280 #ifndef DOXYGEN_NO_DISPATCH
285 template <typename Segment, typename Box, std::size_t DimensionCount>
286 struct disjoint<Segment, Box, DimensionCount, segment_tag, box_tag, false>
287 : detail::disjoint::disjoint_segment_box<Segment, Box>
291 } // namespace dispatch
292 #endif // DOXYGEN_NO_DISPATCH
295 }} // namespace boost::geometry
298 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP