detail/algorithms/segment_intersection.hpp

0001 // Boost.Geometry Index
0002 //
0003 // n-dimensional box-segment intersection
0004 //
0005 // Copyright (c) 2011-2014 Adam Wulkiewicz, Lodz, Poland.
0006 //
0007 // This file was modified by Oracle on 2020-2021.
0008 // Modifications copyright (c) 2020-2021, Oracle and/or its affiliates.
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010 //
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_SEGMENT_INTERSECTION_HPP
0016 #define BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_SEGMENT_INTERSECTION_HPP
0017
0018 #include <limits>
0019 #include <type_traits>
0020
0021 #include <boost/geometry/core/access.hpp>
0022 #include <boost/geometry/core/coordinate_dimension.hpp>
0023 #include <boost/geometry/core/static_assert.hpp>
0024 #include <boost/geometry/core/tag.hpp>
0025 #include <boost/geometry/core/tags.hpp>
0026
0027 namespace boost { namespace geometry { namespace index { namespace detail {
0028
0029 //template <typename Indexable, typename Point>
0030 //struct default_relative_distance_type
0031 //{
0032 //    typedef typename select_most_precise<
0033 //        typename select_most_precise<
0034 //        typename coordinate_type<Indexable>::type,
0035 //        typename coordinate_type<Point>::type
0036 //        >::type,
0037 //        float // TODO - use bigger type, calculated from the size of coordinate types
0038 //    >::type type;
0039 //
0040 //
0041 //    BOOST_GEOMETRY_STATIC_ASSERT((!std::is_unsigned<type>::value),
0042 //        "Distance type can not be unsigned.", type);
0043 //};
0044
0045 namespace dispatch {
0046
0047 template <typename Box, typename Point, size_t I>
0048 struct box_segment_intersection_dim
0049 {
0050     BOOST_STATIC_ASSERT(0 <= dimension<Box>::value);
0051     BOOST_STATIC_ASSERT(0 <= dimension<Point>::value);
0052     BOOST_STATIC_ASSERT(I < size_t(dimension<Box>::value));
0053     BOOST_STATIC_ASSERT(I < size_t(dimension<Point>::value));
0054     BOOST_STATIC_ASSERT(dimension<Point>::value == dimension<Box>::value);
0055
0056     // WARNING! - RelativeDistance must be IEEE float for this to work
0057
0058     template <typename RelativeDistance>
0059     static inline bool apply(Box const& b, Point const& p0, Point const& p1,
0060                              RelativeDistance & t_near, RelativeDistance & t_far)
0061     {
0062         RelativeDistance ray_d = geometry::get<I>(p1) - geometry::get<I>(p0);
0063         RelativeDistance tn = ( geometry::get<min_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
0064         RelativeDistance tf = ( geometry::get<max_corner, I>(b) - geometry::get<I>(p0) ) / ray_d;
0065         if ( tf < tn )
0066             ::std::swap(tn, tf);
0067
0068         if ( t_near < tn )
0069             t_near = tn;
0070         if ( tf < t_far )
0071             t_far = tf;
0072
0073         return 0 <= t_far && t_near <= t_far;
0074     }
0075 };
0076
0077 template <typename Box, typename Point, size_t CurrentDimension>
0078 struct box_segment_intersection
0079 {
0080     BOOST_STATIC_ASSERT(0 < CurrentDimension);
0081
0082     typedef box_segment_intersection_dim<Box, Point, CurrentDimension - 1> for_dim;
0083
0084     template <typename RelativeDistance>
0085     static inline bool apply(Box const& b, Point const& p0, Point const& p1,
0086                              RelativeDistance & t_near, RelativeDistance & t_far)
0087     {
0088         return box_segment_intersection<Box, Point, CurrentDimension - 1>::apply(b, p0, p1, t_near, t_far)
0089             && for_dim::apply(b, p0, p1, t_near, t_far);
0090     }
0091 };
0092
0093 template <typename Box, typename Point>
0094 struct box_segment_intersection<Box, Point, 1>
0095 {
0096     typedef box_segment_intersection_dim<Box, Point, 0> for_dim;
0097
0098     template <typename RelativeDistance>
0099     static inline bool apply(Box const& b, Point const& p0, Point const& p1,
0100                              RelativeDistance & t_near, RelativeDistance & t_far)
0101     {
0102         return for_dim::apply(b, p0, p1, t_near, t_far);
0103     }
0104 };
0105
0106 template <typename Indexable, typename Point, typename Tag>
0107 struct segment_intersection
0108 {
0109     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0110         "Not implemented for this Indexable type.",
0111         Indexable, Point, Tag);
0112 };
0113
0114 template <typename Indexable, typename Point>
0115 struct segment_intersection<Indexable, Point, point_tag>
0116 {
0117     BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
0118         "Segment-Point intersection unavailable.",
0119         Indexable, Point);
0120 };
0121
0122 template <typename Indexable, typename Point>
0123 struct segment_intersection<Indexable, Point, box_tag>
0124 {
0125     typedef dispatch::box_segment_intersection<Indexable, Point, dimension<Indexable>::value> impl;
0126
0127     template <typename RelativeDistance>
0128     static inline bool apply(Indexable const& b, Point const& p0, Point const& p1, RelativeDistance & relative_distance)
0129     {
0130
0131 // TODO: this ASSERT CHECK is wrong for user-defined CoordinateTypes!
0132
0133         static const bool check = !std::is_integral<RelativeDistance>::value;
0134         BOOST_GEOMETRY_STATIC_ASSERT(check,
0135             "RelativeDistance must be a floating point type.",
0136             RelativeDistance);
0137
0138         RelativeDistance t_near = -(::std::numeric_limits<RelativeDistance>::max)();
0139         RelativeDistance t_far = (::std::numeric_limits<RelativeDistance>::max)();
0140
0141         return impl::apply(b, p0, p1, t_near, t_far) &&
0142                (t_near <= 1) &&
0143                ( relative_distance = 0 < t_near ? t_near : 0, true );
0144     }
0145 };
0146
0147 } // namespace dispatch
0148
0149 template <typename Indexable, typename Point, typename RelativeDistance> inline
0150 bool segment_intersection(Indexable const& b,
0151                           Point const& p0,
0152                           Point const& p1,
0153                           RelativeDistance & relative_distance)
0154 {
0155     // TODO check Indexable and Point concepts
0156
0157     return dispatch::segment_intersection<
0158             Indexable, Point,
0159             typename tag<Indexable>::type
0160         >::apply(b, p0, p1, relative_distance);
0161 }
0162
0163 }}}} // namespace boost::geometry::index::detail
0164
0165 #endif // BOOST_GEOMETRY_INDEX_DETAIL_ALGORITHMS_SEGMENT_INTERSECTION_HPP