]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
55 | 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> | |
115 | 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 | (math::sign(ti_min) * math::sign(ti_max) > 0) ) | |
134 | { | |
135 | return true; | |
136 | } | |
137 | } | |
138 | ||
139 | RelativeDistance t_min_x_diff = t_min.first * diff; | |
140 | RelativeDistance t_max_x_diff = t_max.first * diff; | |
141 | ||
142 | if ( t_min_x_diff > ti_max * t_min.second | |
143 | || t_max_x_diff < ti_min * t_max.second ) | |
144 | { | |
145 | return true; | |
146 | } | |
147 | ||
148 | if ( ti_min * t_min.second > t_min_x_diff ) | |
149 | { | |
150 | t_min.first = ti_min; | |
151 | t_min.second = diff; | |
152 | } | |
153 | if ( ti_max * t_max.second < t_max_x_diff ) | |
154 | { | |
155 | t_max.first = ti_max; | |
156 | t_max.second = diff; | |
157 | } | |
158 | ||
159 | if ( t_min.first > t_min.second || t_max.first < 0 ) | |
160 | { | |
161 | return true; | |
162 | } | |
163 | ||
164 | return disjoint_segment_box_impl | |
165 | < | |
166 | RelativeDistance, | |
167 | SegmentPoint, | |
168 | Box, | |
169 | I + 1, | |
170 | Dimension | |
171 | >::apply(p0, p1, box, t_min, t_max); | |
172 | } | |
173 | }; | |
174 | ||
175 | ||
176 | template | |
177 | < | |
178 | typename RelativeDistance, | |
179 | typename SegmentPoint, | |
180 | typename Box, | |
181 | std::size_t Dimension | |
182 | > | |
183 | struct disjoint_segment_box_impl | |
184 | < | |
185 | RelativeDistance, SegmentPoint, Box, 0, Dimension | |
186 | > | |
187 | { | |
188 | static inline bool apply(SegmentPoint const& p0, | |
189 | SegmentPoint const& p1, | |
190 | Box const& box) | |
191 | { | |
192 | std::pair<RelativeDistance, RelativeDistance> t_min, t_max; | |
193 | RelativeDistance diff; | |
194 | ||
195 | compute_tmin_tmax_per_dim<0>::apply(p0, p1, box, | |
196 | t_min.first, t_max.first, diff); | |
197 | ||
198 | if ( geometry::math::equals(diff, 0) ) | |
199 | { | |
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; } | |
202 | ||
203 | if (math::sign(t_min.first) * math::sign(t_max.first) > 0) | |
204 | { | |
205 | return true; | |
206 | } | |
207 | } | |
208 | ||
209 | if ( t_min.first > diff || t_max.first < 0 ) | |
210 | { | |
211 | return true; | |
212 | } | |
213 | ||
214 | t_min.second = t_max.second = diff; | |
215 | ||
216 | return disjoint_segment_box_impl | |
217 | < | |
218 | RelativeDistance, SegmentPoint, Box, 1, Dimension | |
219 | >::apply(p0, p1, box, t_min, t_max); | |
220 | } | |
221 | }; | |
222 | ||
223 | ||
224 | template | |
225 | < | |
226 | typename RelativeDistance, | |
227 | typename SegmentPoint, | |
228 | typename Box, | |
229 | std::size_t Dimension | |
230 | > | |
231 | struct disjoint_segment_box_impl | |
232 | < | |
233 | RelativeDistance, SegmentPoint, Box, Dimension, Dimension | |
234 | > | |
235 | { | |
236 | template <typename RelativeDistancePair> | |
237 | static inline bool apply(SegmentPoint const&, SegmentPoint const&, | |
238 | Box const&, | |
239 | RelativeDistancePair&, RelativeDistancePair&) | |
240 | { | |
241 | return false; | |
242 | } | |
243 | }; | |
244 | ||
245 | ||
246 | //========================================================================= | |
247 | ||
248 | ||
249 | template <typename Segment, typename Box> | |
250 | struct disjoint_segment_box | |
251 | { | |
252 | static inline bool apply(Segment const& segment, Box const& box) | |
253 | { | |
254 | assert_dimension_equal<Segment, Box>(); | |
255 | ||
256 | typedef typename util::calculation_type::geometric::binary | |
257 | < | |
258 | Segment, Box, void | |
259 | >::type relative_distance_type; | |
260 | ||
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); | |
265 | ||
266 | return disjoint_segment_box_impl | |
267 | < | |
268 | relative_distance_type, segment_point_type, Box, | |
269 | 0, dimension<Box>::value | |
270 | >::apply(p0, p1, box); | |
271 | } | |
272 | }; | |
273 | ||
274 | ||
275 | }} // namespace detail::disjoint | |
276 | #endif // DOXYGEN_NO_DETAIL | |
277 | ||
278 | ||
279 | ||
280 | #ifndef DOXYGEN_NO_DISPATCH | |
281 | namespace dispatch | |
282 | { | |
283 | ||
284 | ||
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> | |
288 | {}; | |
289 | ||
290 | ||
291 | } // namespace dispatch | |
292 | #endif // DOXYGEN_NO_DISPATCH | |
293 | ||
294 | ||
295 | }} // namespace boost::geometry | |
296 | ||
297 | ||
298 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP |