ceph/src/boost/libs/geometry/include/boost/geometry/index/detail/algorithms/segment_intersection.hpp

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