1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014, Oracle and/or its affiliates.
5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
7 // Licensed under the Boost Software License version 1.0.
8 // http://www.boost.org/users/license.html
10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP
11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP
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>
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>
30 #include <boost/geometry/util/calculation_type.hpp>
31 #include <boost/geometry/util/condition.hpp>
32 #include <boost/geometry/util/math.hpp>
34 #include <boost/geometry/strategies/distance.hpp>
35 #include <boost/geometry/strategies/tags.hpp>
37 #include <boost/geometry/policies/compare.hpp>
39 #include <boost/geometry/algorithms/equals.hpp>
40 #include <boost/geometry/algorithms/intersects.hpp>
41 #include <boost/geometry/algorithms/not_implemented.hpp>
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>
48 #include <boost/geometry/algorithms/dispatch/distance.hpp>
52 namespace boost { namespace geometry
56 #ifndef DOXYGEN_NO_DETAIL
57 namespace detail { namespace distance
66 bool UsePointBoxStrategy = false
68 class segment_to_box_2D_generic
71 typedef typename point_type<Segment>::type segment_point;
72 typedef typename point_type<Box>::type box_point;
74 typedef typename strategy::distance::services::comparable_type
77 >::type comparable_strategy;
79 typedef detail::closest_feature::point_to_point_range
82 std::vector<box_point>,
85 > point_to_point_range;
87 typedef typename strategy::distance::services::return_type
89 comparable_strategy, segment_point, box_point
90 >::type comparable_return_type;
93 typedef typename strategy::distance::services::return_type
95 Strategy, segment_point, box_point
98 static inline return_type apply(Segment const& segment,
100 Strategy const& strategy,
101 bool check_intersection = true)
103 if (check_intersection && geometry::intersects(segment, box))
108 comparable_strategy cstrategy =
109 strategy::distance::services::get_comparable
114 // get segment points
116 detail::assign_point_from_index<0>(segment, p[0]);
117 detail::assign_point_from_index<1>(segment, p[1]);
120 std::vector<box_point> box_points(4);
121 detail::assign_box_corners_oriented<true>(box, box_points);
123 comparable_return_type cd[6];
124 for (unsigned int i = 0; i < 4; ++i)
126 cd[i] = cstrategy.apply(box_points[i], p[0], p[1]);
131 typename std::vector<box_point>::const_iterator,
132 typename std::vector<box_point>::const_iterator
135 bit_min[0] = point_to_point_range::apply(p[0],
140 bit_min[1] = point_to_point_range::apply(p[1],
146 unsigned int imin = 0;
147 for (unsigned int i = 1; i < 6; ++i)
149 if (cd[i] < cd[imin])
155 if (BOOST_GEOMETRY_CONDITION(is_comparable<Strategy>::value))
162 return strategy.apply(box_points[imin], p[0], p[1]);
166 unsigned int bimin = imin - 4;
167 return strategy.apply(p[bimin],
168 *bit_min[bimin].first,
169 *bit_min[bimin].second);
181 class segment_to_box_2D_generic<Segment, Box, Strategy, true>
184 typedef typename point_type<Segment>::type segment_point;
185 typedef typename point_type<Box>::type box_point;
187 typedef typename strategy::distance::services::comparable_type
190 >::type comparable_strategy;
192 typedef typename strategy::distance::services::return_type
194 comparable_strategy, segment_point, box_point
195 >::type comparable_return_type;
197 typedef typename detail::distance::default_strategy
200 >::type point_box_strategy;
202 typedef typename strategy::distance::services::comparable_type
205 >::type point_box_comparable_strategy;
208 typedef typename strategy::distance::services::return_type
210 Strategy, segment_point, box_point
213 static inline return_type apply(Segment const& segment,
215 Strategy const& strategy,
216 bool check_intersection = true)
218 if (check_intersection && geometry::intersects(segment, box))
223 comparable_strategy cstrategy =
224 strategy::distance::services::get_comparable
228 boost::ignore_unused(cstrategy);
230 // get segment points
232 detail::assign_point_from_index<0>(segment, p[0]);
233 detail::assign_point_from_index<1>(segment, p[1]);
236 std::vector<box_point> box_points(4);
237 detail::assign_box_corners_oriented<true>(box, box_points);
239 comparable_return_type cd[6];
240 for (unsigned int i = 0; i < 4; ++i)
242 cd[i] = cstrategy.apply(box_points[i], p[0], p[1]);
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);
250 unsigned int imin = 0;
251 for (unsigned int i = 1; i < 6; ++i)
253 if (cd[i] < cd[imin])
259 if (is_comparable<Strategy>::value)
266 strategy.apply(box_points[imin], p[0], p[1]);
270 return point_box_strategy().apply(p[imin - 4], box);
281 typename SegmentPoint,
286 class segment_to_box_2D
289 template <typename Result>
290 struct cast_to_result
292 template <typename T>
293 static inline Result apply(T const& t)
295 return boost::numeric_cast<Result>(t);
300 template <typename T, bool IsLess /* true */>
301 struct compare_less_equal
303 typedef compare_less_equal<T, !IsLess> other;
305 template <typename T1, typename T2>
306 inline bool operator()(T1 const& t1, T2 const& t2) const
308 return std::less_equal<T>()(cast_to_result<T>::apply(t1),
309 cast_to_result<T>::apply(t2));
313 template <typename T>
314 struct compare_less_equal<T, false>
316 typedef compare_less_equal<T, true> other;
318 template <typename T1, typename T2>
319 inline bool operator()(T1 const& t1, T2 const& t2) const
321 return std::greater_equal<T>()(cast_to_result<T>::apply(t1),
322 cast_to_result<T>::apply(t2));
327 template <typename LessEqual>
330 typedef typename LessEqual::other type;
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>
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)
346 boost::ignore_unused(pp_strategy, ps_strategy);
348 // the implementation below is written for non-negative slope
351 // for negative slope segments swap the roles of bottom_right
352 // and top_right and use greater_equal instead of less_equal.
354 typedef cast_to_result<ReturnType> cast;
356 LessEqual less_equal;
358 if (less_equal(geometry::get<1>(top_right), geometry::get<1>(p0)))
360 // closest box point is the top-right corner
361 return cast::apply(pp_strategy.apply(p0, top_right));
363 else if (less_equal(geometry::get<1>(bottom_right),
364 geometry::get<1>(p0)))
366 // distance is realized between p0 and right-most
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
372 PSStrategy, BoxPoint, SegmentPoint
373 >::apply(ps_strategy, math::abs(diff));
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));
385 // it is assumed here that p0 lies above the box (so the
386 // entire segment lies above the box)
387 template <typename LessEqual>
390 static inline ReturnType apply(SegmentPoint const& p0,
391 SegmentPoint const& p1,
392 BoxPoint const& top_left,
393 PSStrategy const& ps_strategy)
395 boost::ignore_unused(ps_strategy);
397 // the segment lies above the box
399 typedef cast_to_result<ReturnType> cast;
401 LessEqual less_equal;
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)))
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
411 PSStrategy, SegmentPoint, BoxPoint
412 >::apply(ps_strategy, math::abs(diff));
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));
423 template <typename LessEqual>
424 struct check_right_left_of_box
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,
436 // p0 lies to the right of the box
437 if (geometry::get<0>(p0) >= geometry::get<0>(top_right))
439 result = right_of_box
442 >::apply(p0, p1, bottom_right, top_right,
443 pp_strategy, ps_strategy);
447 // p1 lies to the left of the box
448 if (geometry::get<0>(p1) <= geometry::get<0>(bottom_left))
450 result = right_of_box
452 typename other_compare<LessEqual>::type
453 >::apply(p1, p0, top_left, bottom_left,
454 pp_strategy, ps_strategy);
463 template <typename LessEqual>
464 struct check_above_below_of_box
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,
475 // the segment lies below the box
476 if (geometry::get<1>(p1) < geometry::get<1>(bottom_left))
478 result = above_of_box
480 typename other_compare<LessEqual>::type
481 >::apply(p1, p0, bottom_right, ps_strategy);
485 // the segment lies above the box
486 if (geometry::get<1>(p0) > geometry::get<1>(top_right))
488 result = above_of_box
491 >::apply(p0, p1, top_left, ps_strategy);
498 struct check_generic_position
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,
511 typedef cast_to_result<ReturnType> cast;
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));
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));
535 if (t_min0 * diff1 > t_max1 * diff0)
537 result = cast::apply(ps_strategy.apply(corner1, p0, p1));
542 if (t_max0 * diff1 < t_min1 * diff0)
544 result = cast::apply(ps_strategy.apply(corner2, p0, p1));
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)
561 typedef compare_less_equal<ReturnType, true> less_equal;
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))
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));
572 ReturnType result(0);
574 if (check_right_left_of_box
578 top_left, top_right, bottom_left, bottom_right,
579 pp_strategy, ps_strategy, result))
584 if (check_above_below_of_box
588 top_left, top_right, bottom_left, bottom_right,
589 ps_strategy, result))
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))
603 // in all other cases the box and segment intersect, so return 0
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)
618 typedef compare_less_equal<ReturnType, false> greater_equal;
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) );
626 ReturnType result(0);
628 if (check_right_left_of_box
632 bottom_left, bottom_right, top_left, top_right,
633 pp_strategy, ps_strategy, result))
638 if (check_above_below_of_box
642 top_right, top_left, bottom_right, bottom_left,
643 ps_strategy, result))
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))
657 // in all other cases the box and segment intersect, so return 0
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)
671 BOOST_GEOMETRY_ASSERT( geometry::less<SegmentPoint>()(p0, p1)
672 || geometry::has_nan_coordinate(p0)
673 || geometry::has_nan_coordinate(p1) );
675 if (geometry::get<0>(p0) < geometry::get<0>(p1)
676 && geometry::get<1>(p0) > geometry::get<1>(p1))
678 return negative_slope_segment(p0, p1,
680 bottom_left, bottom_right,
681 pp_strategy, ps_strategy);
684 return non_negative_slope_segment(p0, p1,
686 bottom_left, bottom_right,
687 pp_strategy, ps_strategy);
692 //=========================================================================
699 typename std::size_t Dimension,
704 : not_implemented<Segment, Box>
715 class segment_to_box<Segment, Box, 2, PPStrategy, PSStrategy>
718 typedef typename point_type<Segment>::type segment_point;
719 typedef typename point_type<Box>::type box_point;
721 typedef typename strategy::distance::services::comparable_type
724 >::type pp_comparable_strategy;
726 typedef typename strategy::distance::services::comparable_type
729 >::type ps_comparable_strategy;
731 typedef typename strategy::distance::services::return_type
733 ps_comparable_strategy, segment_point, box_point
734 >::type comparable_return_type;
736 typedef typename strategy::distance::services::return_type
738 PSStrategy, segment_point, box_point
741 static inline return_type apply(Segment const& segment,
743 PPStrategy const& pp_strategy,
744 PSStrategy const& ps_strategy)
747 detail::assign_point_from_index<0>(segment, p[0]);
748 detail::assign_point_from_index<1>(segment, p[1]);
750 if (geometry::equals(p[0], p[1]))
752 typedef typename boost::mpl::if_
756 ps_comparable_strategy,
759 typename strategy::distance::services::comparable_type
761 typename detail::distance::default_strategy
766 typename detail::distance::default_strategy
770 >::type point_box_strategy_type;
772 return dispatch::distance
776 point_box_strategy_type
777 >::apply(p[0], box, point_box_strategy_type());
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);
784 if (geometry::less<segment_point>()(p[0], p[1]))
786 return segment_to_box_2D
794 top_left, top_right, bottom_left, bottom_right,
800 return segment_to_box_2D
808 top_left, top_right, bottom_left, bottom_right,
816 }} // namespace detail::distance
817 #endif // DOXYGEN_NO_DETAIL
820 #ifndef DOXYGEN_NO_DISPATCH
825 template <typename Segment, typename Box, typename Strategy>
828 Segment, Box, Strategy, segment_tag, box_tag,
829 strategy_tag_distance_point_segment, false
832 typedef typename strategy::distance::services::return_type
835 typename point_type<Segment>::type,
836 typename point_type<Box>::type
840 static inline return_type apply(Segment const& segment,
842 Strategy const& strategy)
844 assert_dimension_equal<Segment, Box>();
846 typedef typename boost::mpl::if_
850 typename strategy::distance::services::comparable_type
856 typename strategy::distance::services::comparable_type
858 typename detail::distance::default_strategy
860 typename point_type<Segment>::type,
861 typename point_type<Box>::type
864 typename detail::distance::default_strategy
866 typename point_type<Segment>::type,
867 typename point_type<Box>::type
869 >::type pp_strategy_type;
872 return detail::distance::segment_to_box
876 dimension<Segment>::value,
879 >::apply(segment, box, pp_strategy_type(), strategy);
885 } // namespace dispatch
886 #endif // DOXYGEN_NO_DISPATCH
889 }} // namespace boost::geometry
892 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISTANCE_SEGMENT_TO_BOX_HPP