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