]>
Commit | Line | Data |
---|---|---|
b32b8144 | 1 | // Boost.Geometry |
7c673cae FG |
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 | ||
92f5a8d4 TL |
8 | // This file was modified by Oracle on 2013-2019. |
9 | // Modifications copyright (c) 2013-2019, Oracle and/or its affiliates. | |
7c673cae | 10 | |
b32b8144 | 11 | // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle |
7c673cae | 12 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle |
b32b8144 | 13 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
7c673cae FG |
14 | |
15 | // Use, modification and distribution is subject to the Boost Software License, | |
16 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
17 | // http://www.boost.org/LICENSE_1_0.txt) | |
18 | ||
b32b8144 FG |
19 | #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP |
20 | #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP | |
21 | ||
7c673cae FG |
22 | |
23 | #include <cstddef> | |
24 | #include <utility> | |
25 | ||
26 | #include <boost/numeric/conversion/cast.hpp> | |
27 | ||
28 | #include <boost/geometry/util/math.hpp> | |
29 | #include <boost/geometry/util/calculation_type.hpp> | |
30 | ||
31 | #include <boost/geometry/core/access.hpp> | |
32 | #include <boost/geometry/core/tags.hpp> | |
33 | #include <boost/geometry/core/coordinate_dimension.hpp> | |
34 | #include <boost/geometry/core/point_type.hpp> | |
35 | ||
36 | #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> | |
37 | ||
92f5a8d4 | 38 | #include <boost/geometry/strategies/cartesian/point_in_box.hpp> |
b32b8144 | 39 | #include <boost/geometry/strategies/disjoint.hpp> |
7c673cae FG |
40 | |
41 | ||
b32b8144 | 42 | namespace boost { namespace geometry { namespace strategy { namespace disjoint |
7c673cae FG |
43 | { |
44 | ||
b32b8144 | 45 | namespace detail |
7c673cae FG |
46 | { |
47 | ||
7c673cae FG |
48 | template <std::size_t I> |
49 | struct compute_tmin_tmax_per_dim | |
50 | { | |
51 | template <typename SegmentPoint, typename Box, typename RelativeDistance> | |
52 | static inline void apply(SegmentPoint const& p0, | |
53 | SegmentPoint const& p1, | |
54 | Box const& box, | |
55 | RelativeDistance& ti_min, | |
56 | RelativeDistance& ti_max, | |
57 | RelativeDistance& diff) | |
58 | { | |
59 | typedef typename coordinate_type<Box>::type box_coordinate_type; | |
60 | typedef typename coordinate_type | |
61 | < | |
62 | SegmentPoint | |
63 | >::type point_coordinate_type; | |
64 | ||
65 | RelativeDistance c_p0 = boost::numeric_cast | |
66 | < | |
67 | point_coordinate_type | |
68 | >( geometry::get<I>(p0) ); | |
69 | ||
70 | RelativeDistance c_p1 = boost::numeric_cast | |
71 | < | |
72 | point_coordinate_type | |
73 | >( geometry::get<I>(p1) ); | |
74 | ||
75 | RelativeDistance c_b_min = boost::numeric_cast | |
76 | < | |
77 | box_coordinate_type | |
78 | >( geometry::get<geometry::min_corner, I>(box) ); | |
79 | ||
80 | RelativeDistance c_b_max = boost::numeric_cast | |
81 | < | |
82 | box_coordinate_type | |
83 | >( geometry::get<geometry::max_corner, I>(box) ); | |
84 | ||
85 | if ( geometry::get<I>(p1) >= geometry::get<I>(p0) ) | |
86 | { | |
87 | diff = c_p1 - c_p0; | |
88 | ti_min = c_b_min - c_p0; | |
89 | ti_max = c_b_max - c_p0; | |
90 | } | |
91 | else | |
92 | { | |
93 | diff = c_p0 - c_p1; | |
94 | ti_min = c_p0 - c_b_max; | |
95 | ti_max = c_p0 - c_b_min; | |
96 | } | |
97 | } | |
98 | }; | |
99 | ||
100 | ||
101 | template | |
102 | < | |
103 | typename RelativeDistance, | |
104 | typename SegmentPoint, | |
105 | typename Box, | |
106 | std::size_t I, | |
107 | std::size_t Dimension | |
108 | > | |
109 | struct disjoint_segment_box_impl | |
110 | { | |
111 | template <typename RelativeDistancePair> | |
112 | static inline bool apply(SegmentPoint const& p0, | |
113 | SegmentPoint const& p1, | |
114 | Box const& box, | |
115 | RelativeDistancePair& t_min, | |
116 | RelativeDistancePair& t_max) | |
117 | { | |
118 | RelativeDistance ti_min, ti_max, diff; | |
119 | ||
120 | compute_tmin_tmax_per_dim<I>::apply(p0, p1, box, ti_min, ti_max, diff); | |
121 | ||
122 | if ( geometry::math::equals(diff, 0) ) | |
123 | { | |
124 | if ( (geometry::math::equals(t_min.second, 0) | |
125 | && t_min.first > ti_max) | |
126 | || | |
127 | (geometry::math::equals(t_max.second, 0) | |
128 | && t_max.first < ti_min) | |
129 | || | |
130 | (math::sign(ti_min) * math::sign(ti_max) > 0) ) | |
131 | { | |
132 | return true; | |
133 | } | |
134 | } | |
135 | ||
136 | RelativeDistance t_min_x_diff = t_min.first * diff; | |
137 | RelativeDistance t_max_x_diff = t_max.first * diff; | |
138 | ||
139 | if ( t_min_x_diff > ti_max * t_min.second | |
140 | || t_max_x_diff < ti_min * t_max.second ) | |
141 | { | |
142 | return true; | |
143 | } | |
144 | ||
145 | if ( ti_min * t_min.second > t_min_x_diff ) | |
146 | { | |
147 | t_min.first = ti_min; | |
148 | t_min.second = diff; | |
149 | } | |
150 | if ( ti_max * t_max.second < t_max_x_diff ) | |
151 | { | |
152 | t_max.first = ti_max; | |
153 | t_max.second = diff; | |
154 | } | |
155 | ||
156 | if ( t_min.first > t_min.second || t_max.first < 0 ) | |
157 | { | |
158 | return true; | |
159 | } | |
160 | ||
161 | return disjoint_segment_box_impl | |
162 | < | |
163 | RelativeDistance, | |
164 | SegmentPoint, | |
165 | Box, | |
166 | I + 1, | |
167 | Dimension | |
168 | >::apply(p0, p1, box, t_min, t_max); | |
169 | } | |
170 | }; | |
171 | ||
172 | ||
173 | template | |
174 | < | |
175 | typename RelativeDistance, | |
176 | typename SegmentPoint, | |
177 | typename Box, | |
178 | std::size_t Dimension | |
179 | > | |
180 | struct disjoint_segment_box_impl | |
181 | < | |
182 | RelativeDistance, SegmentPoint, Box, 0, Dimension | |
183 | > | |
184 | { | |
185 | static inline bool apply(SegmentPoint const& p0, | |
186 | SegmentPoint const& p1, | |
187 | Box const& box) | |
188 | { | |
189 | std::pair<RelativeDistance, RelativeDistance> t_min, t_max; | |
190 | RelativeDistance diff; | |
191 | ||
192 | compute_tmin_tmax_per_dim<0>::apply(p0, p1, box, | |
193 | t_min.first, t_max.first, diff); | |
194 | ||
195 | if ( geometry::math::equals(diff, 0) ) | |
196 | { | |
197 | if ( geometry::math::equals(t_min.first, 0) ) { t_min.first = -1; } | |
198 | if ( geometry::math::equals(t_max.first, 0) ) { t_max.first = 1; } | |
199 | ||
200 | if (math::sign(t_min.first) * math::sign(t_max.first) > 0) | |
201 | { | |
202 | return true; | |
203 | } | |
204 | } | |
205 | ||
206 | if ( t_min.first > diff || t_max.first < 0 ) | |
207 | { | |
208 | return true; | |
209 | } | |
210 | ||
211 | t_min.second = t_max.second = diff; | |
212 | ||
213 | return disjoint_segment_box_impl | |
214 | < | |
215 | RelativeDistance, SegmentPoint, Box, 1, Dimension | |
216 | >::apply(p0, p1, box, t_min, t_max); | |
217 | } | |
218 | }; | |
219 | ||
220 | ||
221 | template | |
222 | < | |
223 | typename RelativeDistance, | |
224 | typename SegmentPoint, | |
225 | typename Box, | |
226 | std::size_t Dimension | |
227 | > | |
228 | struct disjoint_segment_box_impl | |
229 | < | |
230 | RelativeDistance, SegmentPoint, Box, Dimension, Dimension | |
231 | > | |
232 | { | |
233 | template <typename RelativeDistancePair> | |
234 | static inline bool apply(SegmentPoint const&, SegmentPoint const&, | |
235 | Box const&, | |
236 | RelativeDistancePair&, RelativeDistancePair&) | |
237 | { | |
238 | return false; | |
239 | } | |
240 | }; | |
241 | ||
b32b8144 | 242 | } // namespace detail |
7c673cae | 243 | |
b32b8144 FG |
244 | // NOTE: This may be temporary place for this or corresponding strategy |
245 | // It seems to be more appropriate to implement the opposite of it | |
246 | // e.g. intersection::segment_box because in disjoint() algorithm | |
247 | // other strategies that are used are intersection and covered_by strategies. | |
248 | struct segment_box | |
249 | { | |
92f5a8d4 | 250 | typedef covered_by::cartesian_point_box disjoint_point_box_strategy_type; |
b32b8144 | 251 | |
92f5a8d4 | 252 | static inline disjoint_point_box_strategy_type get_disjoint_point_box_strategy() |
b32b8144 | 253 | { |
92f5a8d4 | 254 | return disjoint_point_box_strategy_type(); |
b32b8144 | 255 | } |
7c673cae | 256 | |
b32b8144 | 257 | template <typename Segment, typename Box> |
7c673cae FG |
258 | static inline bool apply(Segment const& segment, Box const& box) |
259 | { | |
260 | assert_dimension_equal<Segment, Box>(); | |
261 | ||
262 | typedef typename util::calculation_type::geometric::binary | |
263 | < | |
264 | Segment, Box, void | |
265 | >::type relative_distance_type; | |
266 | ||
267 | typedef typename point_type<Segment>::type segment_point_type; | |
268 | segment_point_type p0, p1; | |
269 | geometry::detail::assign_point_from_index<0>(segment, p0); | |
270 | geometry::detail::assign_point_from_index<1>(segment, p1); | |
271 | ||
b32b8144 | 272 | return detail::disjoint_segment_box_impl |
7c673cae FG |
273 | < |
274 | relative_distance_type, segment_point_type, Box, | |
275 | 0, dimension<Box>::value | |
276 | >::apply(p0, p1, box); | |
277 | } | |
278 | }; | |
279 | ||
280 | ||
b32b8144 FG |
281 | #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS |
282 | ||
7c673cae | 283 | |
b32b8144 FG |
284 | namespace services |
285 | { | |
7c673cae | 286 | |
b32b8144 FG |
287 | template <typename Linear, typename Box, typename LinearTag> |
288 | struct default_strategy<Linear, Box, LinearTag, box_tag, 1, 2, cartesian_tag, cartesian_tag> | |
289 | { | |
290 | typedef disjoint::segment_box type; | |
291 | }; | |
7c673cae | 292 | |
b32b8144 FG |
293 | template <typename Box, typename Linear, typename LinearTag> |
294 | struct default_strategy<Box, Linear, box_tag, LinearTag, 2, 1, cartesian_tag, cartesian_tag> | |
7c673cae | 295 | { |
b32b8144 FG |
296 | typedef disjoint::segment_box type; |
297 | }; | |
7c673cae FG |
298 | |
299 | ||
b32b8144 | 300 | } // namespace services |
7c673cae FG |
301 | |
302 | ||
b32b8144 | 303 | #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS |
7c673cae FG |
304 | |
305 | ||
b32b8144 | 306 | }}}} // namespace boost::geometry::strategy::disjoint |
7c673cae FG |
307 | |
308 | ||
b32b8144 | 309 | #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP |