]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
46 | 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> | |
72 | 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> | |
86 | 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> | |
111 | 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 | |
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 |