1 // Boost.Geometry Index
2 //
3 // n-dimensional box-segment intersection
4 //
5 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
6 //
7 // Use, modification and distribution is subject to the Boost Software License,
8 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
9 // http://www.boost.org/LICENSE_1_0.txt)
10
11 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_SEGMENT_INTERSECTION_HPP
12 #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_SEGMENT_INTERSECTION_HPP
13
14 namespace boost { namespace geometry { namespace index { namespace detail {
15
16 //template <typename Indexable, typename Point>
17 //struct default_relative_distance_type
18 //{
19 // typedef typename select_most_precise<
20 // typename select_most_precise<
21 // typename coordinate_type<Indexable>::type,
22 // typename coordinate_type<Point>::type
23 // >::type,
24 // float // TODO - use bigger type, calculated from the size of coordinate types
25 // >::type type;
26 //
27 //
28 // BOOST_MPL_ASSERT_MSG((!::boost::is_unsigned<type>::value),
29 // THIS_TYPE_SHOULDNT_BE_UNSIGNED, (type));
30 //};
31
32 namespace dispatch {
33
34 template <typename Box, typename Point, size_t I>
35 struct box_segment_intersection_dim
36 {
37 BOOST_STATIC_ASSERT(0 <= dimension<Box>::value);
38 BOOST_STATIC_ASSERT(0 <= dimension<Point>::value);
39 BOOST_STATIC_ASSERT(I < size_t(dimension<Box>::value));
40 BOOST_STATIC_ASSERT(I < size_t(dimension<Point>::value));
41 BOOST_STATIC_ASSERT(dimension<Point>::value == dimension<Box>::value);
42
43 // WARNING! - RelativeDistance must be IEEE float for this to work
44
45 template <typename RelativeDistance>
applyboost::geometry::index::detail::dispatch::box_segment_intersection_dim46 static inline bool apply(Box const& b, Point const& p0, Point const& p1,
47 RelativeDistance & t_near, RelativeDistance & t_far)
48 {
49 RelativeDistance ray_d = geometry::get<I>(p1) - geometry::get<I>(p0);
50 RelativeDistance tn = ( geometry::get<min_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
51 RelativeDistance tf = ( geometry::get<max_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
52 if ( tf < tn )
53 ::std::swap(tn, tf);
54
55 if ( t_near < tn )
56 t_near = tn;
57 if ( tf < t_far )
58 t_far = tf;
59
60 return 0 <= t_far && t_near <= t_far;
61 }
62 };
63
64 template <typename Box, typename Point, size_t CurrentDimension>
65 struct box_segment_intersection
66 {
67 BOOST_STATIC_ASSERT(0 < CurrentDimension);
68
69 typedef box_segment_intersection_dim<Box, Point, CurrentDimension - 1> for_dim;
70
71 template <typename RelativeDistance>
applyboost::geometry::index::detail::dispatch::box_segment_intersection72 static inline bool apply(Box const& b, Point const& p0, Point const& p1,
73 RelativeDistance & t_near, RelativeDistance & t_far)
74 {
75 return box_segment_intersection<Box, Point, CurrentDimension - 1>::apply(b, p0, p1, t_near, t_far)
76 && for_dim::apply(b, p0, p1, t_near, t_far);
77 }
78 };
79
80 template <typename Box, typename Point>
81 struct box_segment_intersection<Box, Point, 1>
82 {
83 typedef box_segment_intersection_dim<Box, Point, 0> for_dim;
84
85 template <typename RelativeDistance>
applyboost::geometry::index::detail::dispatch::box_segment_intersection86 static inline bool apply(Box const& b, Point const& p0, Point const& p1,
87 RelativeDistance & t_near, RelativeDistance & t_far)
88 {
89 return for_dim::apply(b, p0, p1, t_near, t_far);
90 }
91 };
92
93 template <typename Indexable, typename Point, typename Tag>
94 struct segment_intersection
95 {
96 BOOST_MPL_ASSERT_MSG((false), NOT_IMPLEMENTED_FOR_THIS_GEOMETRY, (segment_intersection));
97 };
98
99 template <typename Indexable, typename Point>
100 struct segment_intersection<Indexable, Point, point_tag>
101 {
102 BOOST_MPL_ASSERT_MSG((false), SEGMENT_POINT_INTERSECTION_UNAVAILABLE, (segment_intersection));
103 };
104
105 template <typename Indexable, typename Point>
106 struct segment_intersection<Indexable, Point, box_tag>
107 {
108 typedef dispatch::box_segment_intersection<Indexable, Point, dimension<Indexable>::value> impl;
109
110 template <typename RelativeDistance>
applyboost::geometry::index::detail::dispatch::segment_intersection111 static inline bool apply(Indexable const& b, Point const& p0, Point const& p1, RelativeDistance & relative_distance)
112 {
113
114 // TODO: this ASSERT CHECK is wrong for user-defined CoordinateTypes!
115
116 static const bool check = !::boost::is_integral<RelativeDistance>::value;
117 BOOST_MPL_ASSERT_MSG(check, RELATIVE_DISTANCE_MUST_BE_FLOATING_POINT_TYPE, (RelativeDistance));
118
119 RelativeDistance t_near = -(::std::numeric_limits<RelativeDistance>::max)();
120 RelativeDistance t_far = (::std::numeric_limits<RelativeDistance>::max)();
121
122 return impl::apply(b, p0, p1, t_near, t_far) &&
123 (t_near <= 1) &&
124 ( relative_distance = 0 < t_near ? t_near : 0, true );
125 }
126 };
127
128 } // namespace dispatch
129
130 template <typename Indexable, typename Point, typename RelativeDistance> inline
segment_intersection(Indexable const & b,Point const & p0,Point const & p1,RelativeDistance & relative_distance)131 bool segment_intersection(Indexable const& b,
132 Point const& p0,
133 Point const& p1,
134 RelativeDistance & relative_distance)
135 {
136 // TODO check Indexable and Point concepts
137
138 return dispatch::segment_intersection<
139 Indexable, Point,
140 typename tag<Indexable>::type
141 >::apply(b, p0, p1, relative_distance);
142 }
143
144 }}}} // namespace boost::geometry::index::detail
145
146 #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_SEGMENT_INTERSECTION_HPP
147