ceph/src/boost/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 // This file was modified by Oracle on 2020-2021.
   8 // Modifications copyright (c) 2020-2021, Oracle and/or its affiliates.
   9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  10 //
  11 // Use, modification and distribution is subject to the Boost Software License,
  12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  13 // http://www.boost.org/LICENSE_1_0.txt)
  14
  15 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_SEGMENT_INTERSECTION_HPP
  16 #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_SEGMENT_INTERSECTION_HPP
  17
  18 #include <limits>
  19 #include <type_traits>
  20
  21 #include <boost/geometry/core/access.hpp>
  22 #include <boost/geometry/core/coordinate_dimension.hpp>
  23 #include <boost/geometry/core/static_assert.hpp>
  24 #include <boost/geometry/core/tag.hpp>
  25 #include <boost/geometry/core/tags.hpp>
  26
  27 namespace boost { namespace geometry { namespace index { namespace detail {
  28
  29 //template <typename Indexable, typename Point>
  30 //struct default_relative_distance_type
  31 //{
  32 //    typedef typename select_most_precise<
  33 //        typename select_most_precise<
  34 //        typename coordinate_type<Indexable>::type,
  35 //        typename coordinate_type<Point>::type
  36 //        >::type,
  37 //        float // TODO - use bigger type, calculated from the size of coordinate types
  38 //    >::type type;
  39 //
  40 //
  41 //    BOOST_GEOMETRY_STATIC_ASSERT((!std::is_unsigned<type>::value),
  42 //        "Distance type can not be unsigned.", type);
  43 //};
  44
  45 namespace dispatch {
  46
  47 template <typename Box, typename Point, size_t I>
  48 struct box_segment_intersection_dim
  49 {
  50     BOOST_STATIC_ASSERT(0 <= dimension<Box>::value);
  51     BOOST_STATIC_ASSERT(0 <= dimension<Point>::value);
  52     BOOST_STATIC_ASSERT(I < size_t(dimension<Box>::value));
  53     BOOST_STATIC_ASSERT(I < size_t(dimension<Point>::value));
  54     BOOST_STATIC_ASSERT(dimension<Point>::value == dimension<Box>::value);
  55
  56     // WARNING! - RelativeDistance must be IEEE float for this to work
  57
  58     template <typename RelativeDistance>
  59     static inline bool apply(Box const& b, Point const& p0, Point const& p1,
  60                              RelativeDistance & t_near, RelativeDistance & t_far)
  61     {
  62         RelativeDistance ray_d = geometry::get<I>(p1) - geometry::get<I>(p0);
  63         RelativeDistance tn = ( geometry::get<min_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
  64         RelativeDistance tf = ( geometry::get<max_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
  65         if ( tf < tn )
  66             ::std::swap(tn, tf);
  67
  68         if ( t_near < tn )
  69             t_near = tn;
  70         if ( tf < t_far )
  71             t_far = tf;
  72
  73         return 0 <= t_far && t_near <= t_far;
  74     }
  75 };
  76
  77 template <typename Box, typename Point, size_t CurrentDimension>
  78 struct box_segment_intersection
  79 {
  80     BOOST_STATIC_ASSERT(0 < CurrentDimension);
  81
  82     typedef box_segment_intersection_dim<Box, Point, CurrentDimension - 1> for_dim;
  83
  84     template <typename RelativeDistance>
  85     static inline bool apply(Box const& b, Point const& p0, Point const& p1,
  86                              RelativeDistance & t_near, RelativeDistance & t_far)
  87     {
  88         return box_segment_intersection<Box, Point, CurrentDimension - 1>::apply(b, p0, p1, t_near, t_far)
  89             && for_dim::apply(b, p0, p1, t_near, t_far);
  90     }
  91 };
  92
  93 template <typename Box, typename Point>
  94 struct box_segment_intersection<Box, Point, 1>
  95 {
  96     typedef box_segment_intersection_dim<Box, Point, 0> for_dim;
  97
  98     template <typename RelativeDistance>
  99     static inline bool apply(Box const& b, Point const& p0, Point const& p1,
 100                              RelativeDistance & t_near, RelativeDistance & t_far)
 101     {
 102         return for_dim::apply(b, p0, p1, t_near, t_far);
 103     }
 104 };
 105
 106 template <typename Indexable, typename Point, typename Tag>
 107 struct segment_intersection
 108 {
 109     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
 110         "Not implemented for this Indexable type.",
 111         Indexable, Point, Tag);
 112 };
 113
 114 template <typename Indexable, typename Point>
 115 struct segment_intersection<Indexable, Point, point_tag>
 116 {
 117     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
 118         "Segment-Point intersection unavailable.",
 119         Indexable, Point);
 120 };
 121
 122 template <typename Indexable, typename Point>
 123 struct segment_intersection<Indexable, Point, box_tag>
 124 {
 125     typedef dispatch::box_segment_intersection<Indexable, Point, dimension<Indexable>::value> impl;
 126
 127     template <typename RelativeDistance>
 128     static inline bool apply(Indexable const& b, Point const& p0, Point const& p1, RelativeDistance & relative_distance)
 129     {
 130
 131 // TODO: this ASSERT CHECK is wrong for user-defined CoordinateTypes!
 132
 133         static const bool check = !std::is_integral<RelativeDistance>::value;
 134         BOOST_GEOMETRY_STATIC_ASSERT(check,
 135             "RelativeDistance must be a floating point type.",
 136             RelativeDistance);
 137
 138         RelativeDistance t_near = -(::std::numeric_limits<RelativeDistance>::max)();
 139         RelativeDistance t_far = (::std::numeric_limits<RelativeDistance>::max)();
 140
 141         return impl::apply(b, p0, p1, t_near, t_far) &&
 142                (t_near <= 1) &&
 143                ( relative_distance = 0 < t_near ? t_near : 0, true );
 144     }
 145 };
 146
 147 } // namespace dispatch
 148
 149 template <typename Indexable, typename Point, typename RelativeDistance> inline
 150 bool segment_intersection(Indexable const& b,
 151                           Point const& p0,
 152                           Point const& p1,
 153                           RelativeDistance & relative_distance)
 154 {
 155     // TODO check Indexable and Point concepts
 156
 157     return dispatch::segment_intersection<
 158             Indexable, Point,
 159             typename tag<Indexable>::type
 160         >::apply(b, p0, p1, relative_distance);
 161 }
 162
 163 }}}} // namespace boost::geometry::index::detail
 164
 165 #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_SEGMENT_INTERSECTION_HPP