]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2014, Oracle and/or its affiliates. | |
4 | ||
5 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle | |
6 | ||
7 | // Licensed under the Boost Software License version 1.0. | |
8 | // http://www.boost.org/users/license.html | |
9 | ||
10 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP | |
11 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP | |
12 | ||
13 | #include <cstddef> | |
14 | ||
15 | #include <functional> | |
16 | #include <vector> | |
17 | ||
18 | #include <boost/core/ignore_unused.hpp> | |
19 | #include <boost/mpl/if.hpp> | |
20 | #include <boost/numeric/conversion/cast.hpp> | |
21 | #include <boost/type_traits/is_same.hpp> | |
22 | ||
23 | #include <boost/geometry/core/access.hpp> | |
24 | #include <boost/geometry/core/assert.hpp> | |
25 | #include <boost/geometry/core/closure.hpp> | |
26 | #include <boost/geometry/core/coordinate_dimension.hpp> | |
27 | #include <boost/geometry/core/point_type.hpp> | |
28 | #include <boost/geometry/core/tags.hpp> | |
29 | ||
30 | #include <boost/geometry/util/calculation_type.hpp> | |
31 | #include <boost/geometry/util/condition.hpp> | |
32 | #include <boost/geometry/util/math.hpp> | |
33 | ||
34 | #include <boost/geometry/strategies/distance.hpp> | |
35 | #include <boost/geometry/strategies/tags.hpp> | |
36 | ||
37 | #include <boost/geometry/policies/compare.hpp> | |
38 | ||
39 | #include <boost/geometry/algorithms/equals.hpp> | |
40 | #include <boost/geometry/algorithms/intersects.hpp> | |
41 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
42 | ||
43 | #include <boost/geometry/algorithms/detail/assign_box_corners.hpp> | |
44 | #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> | |
45 | #include <boost/geometry/algorithms/detail/distance/default_strategies.hpp> | |
46 | #include <boost/geometry/algorithms/detail/distance/is_comparable.hpp> | |
47 | ||
48 | #include <boost/geometry/algorithms/dispatch/distance.hpp> | |
49 | ||
50 | ||
51 | ||
52 | namespace boost { namespace geometry | |
53 | { | |
54 | ||
55 | ||
56 | #ifndef DOXYGEN_NO_DETAIL | |
57 | namespace detail { namespace distance | |
58 | { | |
59 | ||
60 | ||
61 | template | |
62 | < | |
63 | typename Segment, | |
64 | typename Box, | |
65 | typename Strategy, | |
66 | bool UsePointBoxStrategy = false | |
67 | > | |
68 | class segment_to_box_2D_generic | |
69 | { | |
70 | private: | |
71 | typedef typename point_type<Segment>::type segment_point; | |
72 | typedef typename point_type<Box>::type box_point; | |
73 | ||
74 | typedef typename strategy::distance::services::comparable_type | |
75 | < | |
76 | Strategy | |
77 | >::type comparable_strategy; | |
78 | ||
79 | typedef detail::closest_feature::point_to_point_range | |
80 | < | |
81 | segment_point, | |
82 | std::vector<box_point>, | |
83 | open, | |
84 | comparable_strategy | |
85 | > point_to_point_range; | |
86 | ||
87 | typedef typename strategy::distance::services::return_type | |
88 | < | |
89 | comparable_strategy, segment_point, box_point | |
90 | >::type comparable_return_type; | |
91 | ||
92 | public: | |
93 | typedef typename strategy::distance::services::return_type | |
94 | < | |
95 | Strategy, segment_point, box_point | |
96 | >::type return_type; | |
97 | ||
98 | static inline return_type apply(Segment const& segment, | |
99 | Box const& box, | |
100 | Strategy const& strategy, | |
101 | bool check_intersection = true) | |
102 | { | |
103 | if (check_intersection && geometry::intersects(segment, box)) | |
104 | { | |
105 | return 0; | |
106 | } | |
107 | ||
108 | comparable_strategy cstrategy = | |
109 | strategy::distance::services::get_comparable | |
110 | < | |
111 | Strategy | |
112 | >::apply(strategy); | |
113 | ||
114 | // get segment points | |
115 | segment_point p[2]; | |
116 | detail::assign_point_from_index<0>(segment, p[0]); | |
117 | detail::assign_point_from_index<1>(segment, p[1]); | |
118 | ||
119 | // get box points | |
120 | std::vector<box_point> box_points(4); | |
121 | detail::assign_box_corners_oriented<true>(box, box_points); | |
122 | ||
123 | comparable_return_type cd[6]; | |
124 | for (unsigned int i = 0; i < 4; ++i) | |
125 | { | |
126 | cd[i] = cstrategy.apply(box_points[i], p[0], p[1]); | |
127 | } | |
128 | ||
129 | std::pair | |
130 | < | |
131 | typename std::vector<box_point>::const_iterator, | |
132 | typename std::vector<box_point>::const_iterator | |
133 | > bit_min[2]; | |
134 | ||
135 | bit_min[0] = point_to_point_range::apply(p[0], | |
136 | box_points.begin(), | |
137 | box_points.end(), | |
138 | cstrategy, | |
139 | cd[4]); | |
140 | bit_min[1] = point_to_point_range::apply(p[1], | |
141 | box_points.begin(), | |
142 | box_points.end(), | |
143 | cstrategy, | |
144 | cd[5]); | |
145 | ||
146 | unsigned int imin = 0; | |
147 | for (unsigned int i = 1; i < 6; ++i) | |
148 | { | |
149 | if (cd[i] < cd[imin]) | |
150 | { | |
151 | imin = i; | |
152 | } | |
153 | } | |
154 | ||
155 | if (BOOST_GEOMETRY_CONDITION(is_comparable<Strategy>::value)) | |
156 | { | |
157 | return cd[imin]; | |
158 | } | |
159 | ||
160 | if (imin < 4) | |
161 | { | |
162 | return strategy.apply(box_points[imin], p[0], p[1]); | |
163 | } | |
164 | else | |
165 | { | |
166 | unsigned int bimin = imin - 4; | |
167 | return strategy.apply(p[bimin], | |
168 | *bit_min[bimin].first, | |
169 | *bit_min[bimin].second); | |
170 | } | |
171 | } | |
172 | }; | |
173 | ||
174 | ||
175 | template | |
176 | < | |
177 | typename Segment, | |
178 | typename Box, | |
179 | typename Strategy | |
180 | > | |
181 | class segment_to_box_2D_generic<Segment, Box, Strategy, true> | |
182 | { | |
183 | private: | |
184 | typedef typename point_type<Segment>::type segment_point; | |
185 | typedef typename point_type<Box>::type box_point; | |
186 | ||
187 | typedef typename strategy::distance::services::comparable_type | |
188 | < | |
189 | Strategy | |
190 | >::type comparable_strategy; | |
191 | ||
192 | typedef typename strategy::distance::services::return_type | |
193 | < | |
194 | comparable_strategy, segment_point, box_point | |
195 | >::type comparable_return_type; | |
196 | ||
197 | typedef typename detail::distance::default_strategy | |
198 | < | |
199 | segment_point, Box | |
200 | >::type point_box_strategy; | |
201 | ||
202 | typedef typename strategy::distance::services::comparable_type | |
203 | < | |
204 | point_box_strategy | |
205 | >::type point_box_comparable_strategy; | |
206 | ||
207 | public: | |
208 | typedef typename strategy::distance::services::return_type | |
209 | < | |
210 | Strategy, segment_point, box_point | |
211 | >::type return_type; | |
212 | ||
213 | static inline return_type apply(Segment const& segment, | |
214 | Box const& box, | |
215 | Strategy const& strategy, | |
216 | bool check_intersection = true) | |
217 | { | |
218 | if (check_intersection && geometry::intersects(segment, box)) | |
219 | { | |
220 | return 0; | |
221 | } | |
222 | ||
223 | comparable_strategy cstrategy = | |
224 | strategy::distance::services::get_comparable | |
225 | < | |
226 | Strategy | |
227 | >::apply(strategy); | |
228 | boost::ignore_unused(cstrategy); | |
229 | ||
230 | // get segment points | |
231 | segment_point p[2]; | |
232 | detail::assign_point_from_index<0>(segment, p[0]); | |
233 | detail::assign_point_from_index<1>(segment, p[1]); | |
234 | ||
235 | // get box points | |
236 | std::vector<box_point> box_points(4); | |
237 | detail::assign_box_corners_oriented<true>(box, box_points); | |
238 | ||
239 | comparable_return_type cd[6]; | |
240 | for (unsigned int i = 0; i < 4; ++i) | |
241 | { | |
242 | cd[i] = cstrategy.apply(box_points[i], p[0], p[1]); | |
243 | } | |
244 | ||
245 | point_box_comparable_strategy pb_cstrategy; | |
246 | boost::ignore_unused(pb_cstrategy); | |
247 | cd[4] = pb_cstrategy.apply(p[0], box); | |
248 | cd[5] = pb_cstrategy.apply(p[1], box); | |
249 | ||
250 | unsigned int imin = 0; | |
251 | for (unsigned int i = 1; i < 6; ++i) | |
252 | { | |
253 | if (cd[i] < cd[imin]) | |
254 | { | |
255 | imin = i; | |
256 | } | |
257 | } | |
258 | ||
259 | if (is_comparable<Strategy>::value) | |
260 | { | |
261 | return cd[imin]; | |
262 | } | |
263 | ||
264 | if (imin < 4) | |
265 | { | |
266 | strategy.apply(box_points[imin], p[0], p[1]); | |
267 | } | |
268 | else | |
269 | { | |
270 | return point_box_strategy().apply(p[imin - 4], box); | |
271 | } | |
272 | } | |
273 | }; | |
274 | ||
275 | ||
276 | ||
277 | ||
278 | template | |
279 | < | |
280 | typename ReturnType, | |
281 | typename SegmentPoint, | |
282 | typename BoxPoint, | |
283 | typename PPStrategy, | |
284 | typename PSStrategy | |
285 | > | |
286 | class segment_to_box_2D | |
287 | { | |
288 | private: | |
289 | template <typename Result> | |
290 | struct cast_to_result | |
291 | { | |
292 | template <typename T> | |
293 | static inline Result apply(T const& t) | |
294 | { | |
295 | return boost::numeric_cast<Result>(t); | |
296 | } | |
297 | }; | |
298 | ||
299 | ||
300 | template <typename T, bool IsLess /* true */> | |
301 | struct compare_less_equal | |
302 | { | |
303 | typedef compare_less_equal<T, !IsLess> other; | |
304 | ||
305 | template <typename T1, typename T2> | |
306 | inline bool operator()(T1 const& t1, T2 const& t2) const | |
307 | { | |
308 | return std::less_equal<T>()(cast_to_result<T>::apply(t1), | |
309 | cast_to_result<T>::apply(t2)); | |
310 | } | |
311 | }; | |
312 | ||
313 | template <typename T> | |
314 | struct compare_less_equal<T, false> | |
315 | { | |
316 | typedef compare_less_equal<T, true> other; | |
317 | ||
318 | template <typename T1, typename T2> | |
319 | inline bool operator()(T1 const& t1, T2 const& t2) const | |
320 | { | |
321 | return std::greater_equal<T>()(cast_to_result<T>::apply(t1), | |
322 | cast_to_result<T>::apply(t2)); | |
323 | } | |
324 | }; | |
325 | ||
326 | ||
327 | template <typename LessEqual> | |
328 | struct other_compare | |
329 | { | |
330 | typedef typename LessEqual::other type; | |
331 | }; | |
332 | ||
333 | ||
334 | // it is assumed here that p0 lies to the right of the box (so the | |
335 | // entire segment lies to the right of the box) | |
336 | template <typename LessEqual> | |
337 | struct right_of_box | |
338 | { | |
339 | static inline ReturnType apply(SegmentPoint const& p0, | |
340 | SegmentPoint const& p1, | |
341 | BoxPoint const& bottom_right, | |
342 | BoxPoint const& top_right, | |
343 | PPStrategy const& pp_strategy, | |
344 | PSStrategy const& ps_strategy) | |
345 | { | |
346 | boost::ignore_unused(pp_strategy, ps_strategy); | |
347 | ||
348 | // the implementation below is written for non-negative slope | |
349 | // segments | |
350 | // | |
351 | // for negative slope segments swap the roles of bottom_right | |
352 | // and top_right and use greater_equal instead of less_equal. | |
353 | ||
354 | typedef cast_to_result<ReturnType> cast; | |
355 | ||
356 | LessEqual less_equal; | |
357 | ||
358 | if (less_equal(geometry::get<1>(top_right), geometry::get<1>(p0))) | |
359 | { | |
360 | // closest box point is the top-right corner | |
361 | return cast::apply(pp_strategy.apply(p0, top_right)); | |
362 | } | |
363 | else if (less_equal(geometry::get<1>(bottom_right), | |
364 | geometry::get<1>(p0))) | |
365 | { | |
366 | // distance is realized between p0 and right-most | |
367 | // segment of box | |
368 | ReturnType diff = cast::apply(geometry::get<0>(p0)) | |
369 | - cast::apply(geometry::get<0>(bottom_right)); | |
370 | return strategy::distance::services::result_from_distance | |
371 | < | |
372 | PSStrategy, BoxPoint, SegmentPoint | |
373 | >::apply(ps_strategy, math::abs(diff)); | |
374 | } | |
375 | else | |
376 | { | |
377 | // distance is realized between the bottom-right | |
378 | // corner of the box and the segment | |
379 | return cast::apply(ps_strategy.apply(bottom_right, p0, p1)); | |
380 | } | |
381 | } | |
382 | }; | |
383 | ||
384 | ||
385 | // it is assumed here that p0 lies above the box (so the | |
386 | // entire segment lies above the box) | |
387 | template <typename LessEqual> | |
388 | struct above_of_box | |
389 | { | |
390 | static inline ReturnType apply(SegmentPoint const& p0, | |
391 | SegmentPoint const& p1, | |
392 | BoxPoint const& top_left, | |
393 | PSStrategy const& ps_strategy) | |
394 | { | |
395 | boost::ignore_unused(ps_strategy); | |
396 | ||
397 | // the segment lies above the box | |
398 | ||
399 | typedef cast_to_result<ReturnType> cast; | |
400 | ||
401 | LessEqual less_equal; | |
402 | ||
403 | // p0 is above the upper segment of the box | |
404 | // (and inside its band) | |
405 | if (less_equal(geometry::get<0>(top_left), geometry::get<0>(p0))) | |
406 | { | |
407 | ReturnType diff = cast::apply(geometry::get<1>(p0)) | |
408 | - cast::apply(geometry::get<1>(top_left)); | |
409 | return strategy::distance::services::result_from_distance | |
410 | < | |
411 | PSStrategy, SegmentPoint, BoxPoint | |
412 | >::apply(ps_strategy, math::abs(diff)); | |
413 | } | |
414 | ||
415 | // p0 is to the left of the box, but p1 is above the box | |
416 | // in this case the distance is realized between the | |
417 | // top-left corner of the box and the segment | |
418 | return cast::apply(ps_strategy.apply(top_left, p0, p1)); | |
419 | } | |
420 | }; | |
421 | ||
422 | ||
423 | template <typename LessEqual> | |
424 | struct check_right_left_of_box | |
425 | { | |
426 | static inline bool apply(SegmentPoint const& p0, | |
427 | SegmentPoint const& p1, | |
428 | BoxPoint const& top_left, | |
429 | BoxPoint const& top_right, | |
430 | BoxPoint const& bottom_left, | |
431 | BoxPoint const& bottom_right, | |
432 | PPStrategy const& pp_strategy, | |
433 | PSStrategy const& ps_strategy, | |
434 | ReturnType& result) | |
435 | { | |
436 | // p0 lies to the right of the box | |
437 | if (geometry::get<0>(p0) >= geometry::get<0>(top_right)) | |
438 | { | |
439 | result = right_of_box | |
440 | < | |
441 | LessEqual | |
442 | >::apply(p0, p1, bottom_right, top_right, | |
443 | pp_strategy, ps_strategy); | |
444 | return true; | |
445 | } | |
446 | ||
447 | // p1 lies to the left of the box | |
448 | if (geometry::get<0>(p1) <= geometry::get<0>(bottom_left)) | |
449 | { | |
450 | result = right_of_box | |
451 | < | |
452 | typename other_compare<LessEqual>::type | |
453 | >::apply(p1, p0, top_left, bottom_left, | |
454 | pp_strategy, ps_strategy); | |
455 | return true; | |
456 | } | |
457 | ||
458 | return false; | |
459 | } | |
460 | }; | |
461 | ||
462 | ||
463 | template <typename LessEqual> | |
464 | struct check_above_below_of_box | |
465 | { | |
466 | static inline bool apply(SegmentPoint const& p0, | |
467 | SegmentPoint const& p1, | |
468 | BoxPoint const& top_left, | |
469 | BoxPoint const& top_right, | |
470 | BoxPoint const& bottom_left, | |
471 | BoxPoint const& bottom_right, | |
472 | PSStrategy const& ps_strategy, | |
473 | ReturnType& result) | |
474 | { | |
475 | // the segment lies below the box | |
476 | if (geometry::get<1>(p1) < geometry::get<1>(bottom_left)) | |
477 | { | |
478 | result = above_of_box | |
479 | < | |
480 | typename other_compare<LessEqual>::type | |
481 | >::apply(p1, p0, bottom_right, ps_strategy); | |
482 | return true; | |
483 | } | |
484 | ||
485 | // the segment lies above the box | |
486 | if (geometry::get<1>(p0) > geometry::get<1>(top_right)) | |
487 | { | |
488 | result = above_of_box | |
489 | < | |
490 | LessEqual | |
491 | >::apply(p0, p1, top_left, ps_strategy); | |
492 | return true; | |
493 | } | |
494 | return false; | |
495 | } | |
496 | }; | |
497 | ||
498 | struct check_generic_position | |
499 | { | |
500 | static inline bool apply(SegmentPoint const& p0, | |
501 | SegmentPoint const& p1, | |
502 | BoxPoint const& bottom_left0, | |
503 | BoxPoint const& top_right0, | |
504 | BoxPoint const& bottom_left1, | |
505 | BoxPoint const& top_right1, | |
506 | BoxPoint const& corner1, | |
507 | BoxPoint const& corner2, | |
508 | PSStrategy const& ps_strategy, | |
509 | ReturnType& result) | |
510 | { | |
511 | typedef cast_to_result<ReturnType> cast; | |
512 | ||
513 | ReturnType diff0 = cast::apply(geometry::get<0>(p1)) | |
514 | - cast::apply(geometry::get<0>(p0)); | |
515 | ReturnType t_min0 = cast::apply(geometry::get<0>(bottom_left0)) | |
516 | - cast::apply(geometry::get<0>(p0)); | |
517 | ReturnType t_max0 = cast::apply(geometry::get<0>(top_right0)) | |
518 | - cast::apply(geometry::get<0>(p0)); | |
519 | ||
520 | ReturnType diff1 = cast::apply(geometry::get<1>(p1)) | |
521 | - cast::apply(geometry::get<1>(p0)); | |
522 | ReturnType t_min1 = cast::apply(geometry::get<1>(bottom_left1)) | |
523 | - cast::apply(geometry::get<1>(p0)); | |
524 | ReturnType t_max1 = cast::apply(geometry::get<1>(top_right1)) | |
525 | - cast::apply(geometry::get<1>(p0)); | |
526 | ||
527 | if (diff1 < 0) | |
528 | { | |
529 | diff1 = -diff1; | |
530 | t_min1 = -t_min1; | |
531 | t_max1 = -t_max1; | |
532 | } | |
533 | ||
534 | // t_min0 > t_max1 | |
535 | if (t_min0 * diff1 > t_max1 * diff0) | |
536 | { | |
537 | result = cast::apply(ps_strategy.apply(corner1, p0, p1)); | |
538 | return true; | |
539 | } | |
540 | ||
541 | // t_max0 < t_min1 | |
542 | if (t_max0 * diff1 < t_min1 * diff0) | |
543 | { | |
544 | result = cast::apply(ps_strategy.apply(corner2, p0, p1)); | |
545 | return true; | |
546 | } | |
547 | return false; | |
548 | } | |
549 | }; | |
550 | ||
551 | static inline ReturnType | |
552 | non_negative_slope_segment(SegmentPoint const& p0, | |
553 | SegmentPoint const& p1, | |
554 | BoxPoint const& top_left, | |
555 | BoxPoint const& top_right, | |
556 | BoxPoint const& bottom_left, | |
557 | BoxPoint const& bottom_right, | |
558 | PPStrategy const& pp_strategy, | |
559 | PSStrategy const& ps_strategy) | |
560 | { | |
561 | typedef compare_less_equal<ReturnType, true> less_equal; | |
562 | ||
563 | // assert that the segment has non-negative slope | |
564 | BOOST_GEOMETRY_ASSERT( ( math::equals(geometry::get<0>(p0), geometry::get<0>(p1)) | |
565 | && geometry::get<1>(p0) < geometry::get<1>(p1)) | |
566 | || | |
567 | ( geometry::get<0>(p0) < geometry::get<0>(p1) | |
568 | && geometry::get<1>(p0) <= geometry::get<1>(p1) ) | |
569 | || geometry::has_nan_coordinate(p0) | |
570 | || geometry::has_nan_coordinate(p1)); | |
571 | ||
572 | ReturnType result(0); | |
573 | ||
574 | if (check_right_left_of_box | |
575 | < | |
576 | less_equal | |
577 | >::apply(p0, p1, | |
578 | top_left, top_right, bottom_left, bottom_right, | |
579 | pp_strategy, ps_strategy, result)) | |
580 | { | |
581 | return result; | |
582 | } | |
583 | ||
584 | if (check_above_below_of_box | |
585 | < | |
586 | less_equal | |
587 | >::apply(p0, p1, | |
588 | top_left, top_right, bottom_left, bottom_right, | |
589 | ps_strategy, result)) | |
590 | { | |
591 | return result; | |
592 | } | |
593 | ||
594 | if (check_generic_position::apply(p0, p1, | |
595 | bottom_left, top_right, | |
596 | bottom_left, top_right, | |
597 | top_left, bottom_right, | |
598 | ps_strategy, result)) | |
599 | { | |
600 | return result; | |
601 | } | |
602 | ||
603 | // in all other cases the box and segment intersect, so return 0 | |
604 | return result; | |
605 | } | |
606 | ||
607 | ||
608 | static inline ReturnType | |
609 | negative_slope_segment(SegmentPoint const& p0, | |
610 | SegmentPoint const& p1, | |
611 | BoxPoint const& top_left, | |
612 | BoxPoint const& top_right, | |
613 | BoxPoint const& bottom_left, | |
614 | BoxPoint const& bottom_right, | |
615 | PPStrategy const& pp_strategy, | |
616 | PSStrategy const& ps_strategy) | |
617 | { | |
618 | typedef compare_less_equal<ReturnType, false> greater_equal; | |
619 | ||
620 | // assert that the segment has negative slope | |
621 | BOOST_GEOMETRY_ASSERT( ( geometry::get<0>(p0) < geometry::get<0>(p1) | |
622 | && geometry::get<1>(p0) > geometry::get<1>(p1) ) | |
623 | || geometry::has_nan_coordinate(p0) | |
624 | || geometry::has_nan_coordinate(p1) ); | |
625 | ||
626 | ReturnType result(0); | |
627 | ||
628 | if (check_right_left_of_box | |
629 | < | |
630 | greater_equal | |
631 | >::apply(p0, p1, | |
632 | bottom_left, bottom_right, top_left, top_right, | |
633 | pp_strategy, ps_strategy, result)) | |
634 | { | |
635 | return result; | |
636 | } | |
637 | ||
638 | if (check_above_below_of_box | |
639 | < | |
640 | greater_equal | |
641 | >::apply(p1, p0, | |
642 | top_right, top_left, bottom_right, bottom_left, | |
643 | ps_strategy, result)) | |
644 | { | |
645 | return result; | |
646 | } | |
647 | ||
648 | if (check_generic_position::apply(p0, p1, | |
649 | bottom_left, top_right, | |
650 | top_right, bottom_left, | |
651 | bottom_left, top_right, | |
652 | ps_strategy, result)) | |
653 | { | |
654 | return result; | |
655 | } | |
656 | ||
657 | // in all other cases the box and segment intersect, so return 0 | |
658 | return result; | |
659 | } | |
660 | ||
661 | public: | |
662 | static inline ReturnType apply(SegmentPoint const& p0, | |
663 | SegmentPoint const& p1, | |
664 | BoxPoint const& top_left, | |
665 | BoxPoint const& top_right, | |
666 | BoxPoint const& bottom_left, | |
667 | BoxPoint const& bottom_right, | |
668 | PPStrategy const& pp_strategy, | |
669 | PSStrategy const& ps_strategy) | |
670 | { | |
671 | BOOST_GEOMETRY_ASSERT( geometry::less<SegmentPoint>()(p0, p1) | |
672 | || geometry::has_nan_coordinate(p0) | |
673 | || geometry::has_nan_coordinate(p1) ); | |
674 | ||
675 | if (geometry::get<0>(p0) < geometry::get<0>(p1) | |
676 | && geometry::get<1>(p0) > geometry::get<1>(p1)) | |
677 | { | |
678 | return negative_slope_segment(p0, p1, | |
679 | top_left, top_right, | |
680 | bottom_left, bottom_right, | |
681 | pp_strategy, ps_strategy); | |
682 | } | |
683 | ||
684 | return non_negative_slope_segment(p0, p1, | |
685 | top_left, top_right, | |
686 | bottom_left, bottom_right, | |
687 | pp_strategy, ps_strategy); | |
688 | } | |
689 | }; | |
690 | ||
691 | ||
692 | //========================================================================= | |
693 | ||
694 | ||
695 | template | |
696 | < | |
697 | typename Segment, | |
698 | typename Box, | |
699 | typename std::size_t Dimension, | |
700 | typename PPStrategy, | |
701 | typename PSStrategy | |
702 | > | |
703 | class segment_to_box | |
704 | : not_implemented<Segment, Box> | |
705 | {}; | |
706 | ||
707 | ||
708 | template | |
709 | < | |
710 | typename Segment, | |
711 | typename Box, | |
712 | typename PPStrategy, | |
713 | typename PSStrategy | |
714 | > | |
715 | class segment_to_box<Segment, Box, 2, PPStrategy, PSStrategy> | |
716 | { | |
717 | private: | |
718 | typedef typename point_type<Segment>::type segment_point; | |
719 | typedef typename point_type<Box>::type box_point; | |
720 | ||
721 | typedef typename strategy::distance::services::comparable_type | |
722 | < | |
723 | PPStrategy | |
724 | >::type pp_comparable_strategy; | |
725 | ||
726 | typedef typename strategy::distance::services::comparable_type | |
727 | < | |
728 | PSStrategy | |
729 | >::type ps_comparable_strategy; | |
730 | ||
731 | typedef typename strategy::distance::services::return_type | |
732 | < | |
733 | ps_comparable_strategy, segment_point, box_point | |
734 | >::type comparable_return_type; | |
735 | public: | |
736 | typedef typename strategy::distance::services::return_type | |
737 | < | |
738 | PSStrategy, segment_point, box_point | |
739 | >::type return_type; | |
740 | ||
741 | static inline return_type apply(Segment const& segment, | |
742 | Box const& box, | |
743 | PPStrategy const& pp_strategy, | |
744 | PSStrategy const& ps_strategy) | |
745 | { | |
746 | segment_point p[2]; | |
747 | detail::assign_point_from_index<0>(segment, p[0]); | |
748 | detail::assign_point_from_index<1>(segment, p[1]); | |
749 | ||
750 | if (geometry::equals(p[0], p[1])) | |
751 | { | |
752 | typedef typename boost::mpl::if_ | |
753 | < | |
754 | boost::is_same | |
755 | < | |
756 | ps_comparable_strategy, | |
757 | PSStrategy | |
758 | >, | |
759 | typename strategy::distance::services::comparable_type | |
760 | < | |
761 | typename detail::distance::default_strategy | |
762 | < | |
763 | segment_point, Box | |
764 | >::type | |
765 | >::type, | |
766 | typename detail::distance::default_strategy | |
767 | < | |
768 | segment_point, Box | |
769 | >::type | |
770 | >::type point_box_strategy_type; | |
771 | ||
772 | return dispatch::distance | |
773 | < | |
774 | segment_point, | |
775 | Box, | |
776 | point_box_strategy_type | |
777 | >::apply(p[0], box, point_box_strategy_type()); | |
778 | } | |
779 | ||
780 | box_point top_left, top_right, bottom_left, bottom_right; | |
781 | detail::assign_box_corners(box, bottom_left, bottom_right, | |
782 | top_left, top_right); | |
783 | ||
784 | if (geometry::less<segment_point>()(p[0], p[1])) | |
785 | { | |
786 | return segment_to_box_2D | |
787 | < | |
788 | return_type, | |
789 | segment_point, | |
790 | box_point, | |
791 | PPStrategy, | |
792 | PSStrategy | |
793 | >::apply(p[0], p[1], | |
794 | top_left, top_right, bottom_left, bottom_right, | |
795 | pp_strategy, | |
796 | ps_strategy); | |
797 | } | |
798 | else | |
799 | { | |
800 | return segment_to_box_2D | |
801 | < | |
802 | return_type, | |
803 | segment_point, | |
804 | box_point, | |
805 | PPStrategy, | |
806 | PSStrategy | |
807 | >::apply(p[1], p[0], | |
808 | top_left, top_right, bottom_left, bottom_right, | |
809 | pp_strategy, | |
810 | ps_strategy); | |
811 | } | |
812 | } | |
813 | }; | |
814 | ||
815 | ||
816 | }} // namespace detail::distance | |
817 | #endif // DOXYGEN_NO_DETAIL | |
818 | ||
819 | ||
820 | #ifndef DOXYGEN_NO_DISPATCH | |
821 | namespace dispatch | |
822 | { | |
823 | ||
824 | ||
825 | template <typename Segment, typename Box, typename Strategy> | |
826 | struct distance | |
827 | < | |
828 | Segment, Box, Strategy, segment_tag, box_tag, | |
829 | strategy_tag_distance_point_segment, false | |
830 | > | |
831 | { | |
832 | typedef typename strategy::distance::services::return_type | |
833 | < | |
834 | Strategy, | |
835 | typename point_type<Segment>::type, | |
836 | typename point_type<Box>::type | |
837 | >::type return_type; | |
838 | ||
839 | ||
840 | static inline return_type apply(Segment const& segment, | |
841 | Box const& box, | |
842 | Strategy const& strategy) | |
843 | { | |
844 | assert_dimension_equal<Segment, Box>(); | |
845 | ||
846 | typedef typename boost::mpl::if_ | |
847 | < | |
848 | boost::is_same | |
849 | < | |
850 | typename strategy::distance::services::comparable_type | |
851 | < | |
852 | Strategy | |
853 | >::type, | |
854 | Strategy | |
855 | >, | |
856 | typename strategy::distance::services::comparable_type | |
857 | < | |
858 | typename detail::distance::default_strategy | |
859 | < | |
860 | typename point_type<Segment>::type, | |
861 | typename point_type<Box>::type | |
862 | >::type | |
863 | >::type, | |
864 | typename detail::distance::default_strategy | |
865 | < | |
866 | typename point_type<Segment>::type, | |
867 | typename point_type<Box>::type | |
868 | >::type | |
869 | >::type pp_strategy_type; | |
870 | ||
871 | ||
872 | return detail::distance::segment_to_box | |
873 | < | |
874 | Segment, | |
875 | Box, | |
876 | dimension<Segment>::value, | |
877 | pp_strategy_type, | |
878 | Strategy | |
879 | >::apply(segment, box, pp_strategy_type(), strategy); | |
880 | } | |
881 | }; | |
882 | ||
883 | ||
884 | ||
885 | } // namespace dispatch | |
886 | #endif // DOXYGEN_NO_DISPATCH | |
887 | ||
888 | ||
889 | }} // namespace boost::geometry | |
890 | ||
891 | ||
892 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP |