1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. 4 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France. 5 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK. 6 // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland. 7 8 // This file was modified by Oracle on 2013-2014. 9 // Modifications copyright (c) 2013-2014, Oracle and/or its affiliates. 10 11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 13 14 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library 15 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. 16 17 // Use, modification and distribution is subject to the Boost Software License, 18 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 19 // http://www.boost.org/LICENSE_1_0.txt) 20 21 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP 22 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP 23 24 #include <cstddef> 25 #include <utility> 26 27 #include <boost/numeric/conversion/cast.hpp> 28 29 #include <boost/geometry/util/math.hpp> 30 #include <boost/geometry/util/calculation_type.hpp> 31 32 #include <boost/geometry/core/access.hpp> 33 #include <boost/geometry/core/tags.hpp> 34 #include <boost/geometry/core/coordinate_dimension.hpp> 35 #include <boost/geometry/core/point_type.hpp> 36 37 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> 38 39 #include <boost/geometry/algorithms/dispatch/disjoint.hpp> 40 41 42 namespace boost { namespace geometry 43 { 44 45 46 #ifndef DOXYGEN_NO_DETAIL 47 namespace detail { namespace disjoint 48 { 49 50 51 template <std::size_t I> 52 struct compute_tmin_tmax_per_dim 53 { 54 template <typename SegmentPoint, typename Box, typename RelativeDistance> applyboost::geometry::detail::disjoint::compute_tmin_tmax_per_dim55 static inline void apply(SegmentPoint const& p0, 56 SegmentPoint const& p1, 57 Box const& box, 58 RelativeDistance& ti_min, 59 RelativeDistance& ti_max, 60 RelativeDistance& diff) 61 { 62 typedef typename coordinate_type<Box>::type box_coordinate_type; 63 typedef typename coordinate_type 64 < 65 SegmentPoint 66 >::type point_coordinate_type; 67 68 RelativeDistance c_p0 = boost::numeric_cast 69 < 70 point_coordinate_type 71 >( geometry::get<I>(p0) ); 72 73 RelativeDistance c_p1 = boost::numeric_cast 74 < 75 point_coordinate_type 76 >( geometry::get<I>(p1) ); 77 78 RelativeDistance c_b_min = boost::numeric_cast 79 < 80 box_coordinate_type 81 >( geometry::get<geometry::min_corner, I>(box) ); 82 83 RelativeDistance c_b_max = boost::numeric_cast 84 < 85 box_coordinate_type 86 >( geometry::get<geometry::max_corner, I>(box) ); 87 88 if ( geometry::get<I>(p1) >= geometry::get<I>(p0) ) 89 { 90 diff = c_p1 - c_p0; 91 ti_min = c_b_min - c_p0; 92 ti_max = c_b_max - c_p0; 93 } 94 else 95 { 96 diff = c_p0 - c_p1; 97 ti_min = c_p0 - c_b_max; 98 ti_max = c_p0 - c_b_min; 99 } 100 } 101 }; 102 103 104 template 105 < 106 typename RelativeDistance, 107 typename SegmentPoint, 108 typename Box, 109 std::size_t I, 110 std::size_t Dimension 111 > 112 struct disjoint_segment_box_impl 113 { 114 template <typename RelativeDistancePair> applyboost::geometry::detail::disjoint::disjoint_segment_box_impl115 static inline bool apply(SegmentPoint const& p0, 116 SegmentPoint const& p1, 117 Box const& box, 118 RelativeDistancePair& t_min, 119 RelativeDistancePair& t_max) 120 { 121 RelativeDistance ti_min, ti_max, diff; 122 123 compute_tmin_tmax_per_dim<I>::apply(p0, p1, box, ti_min, ti_max, diff); 124 125 if ( geometry::math::equals(diff, 0) ) 126 { 127 if ( (geometry::math::equals(t_min.second, 0) 128 && t_min.first > ti_max) 129 || 130 (geometry::math::equals(t_max.second, 0) 131 && t_max.first < ti_min) ) 132 { 133 return true; 134 } 135 } 136 137 RelativeDistance t_min_x_diff = t_min.first * diff; 138 RelativeDistance t_max_x_diff = t_max.first * diff; 139 140 if ( t_min_x_diff > ti_max * t_min.second 141 || t_max_x_diff < ti_min * t_max.second ) 142 { 143 return true; 144 } 145 146 if ( ti_min * t_min.second > t_min_x_diff ) 147 { 148 t_min.first = ti_min; 149 t_min.second = diff; 150 } 151 if ( ti_max * t_max.second < t_max_x_diff ) 152 { 153 t_max.first = ti_max; 154 t_max.second = diff; 155 } 156 157 if ( t_min.first > t_min.second || t_max.first < 0 ) 158 { 159 return true; 160 } 161 162 return disjoint_segment_box_impl 163 < 164 RelativeDistance, 165 SegmentPoint, 166 Box, 167 I + 1, 168 Dimension 169 >::apply(p0, p1, box, t_min, t_max); 170 } 171 }; 172 173 174 template 175 < 176 typename RelativeDistance, 177 typename SegmentPoint, 178 typename Box, 179 std::size_t Dimension 180 > 181 struct disjoint_segment_box_impl 182 < 183 RelativeDistance, SegmentPoint, Box, 0, Dimension 184 > 185 { applyboost::geometry::detail::disjoint::disjoint_segment_box_impl186 static inline bool apply(SegmentPoint const& p0, 187 SegmentPoint const& p1, 188 Box const& box) 189 { 190 std::pair<RelativeDistance, RelativeDistance> t_min, t_max; 191 RelativeDistance diff; 192 193 compute_tmin_tmax_per_dim<0>::apply(p0, p1, box, 194 t_min.first, t_max.first, diff); 195 196 if ( geometry::math::equals(diff, 0) ) 197 { 198 if ( geometry::math::equals(t_min.first, 0) ) { t_min.first = -1; } 199 if ( geometry::math::equals(t_max.first, 0) ) { t_max.first = 1; } 200 } 201 202 if ( t_min.first > diff || t_max.first < 0 ) 203 { 204 return true; 205 } 206 207 t_min.second = t_max.second = diff; 208 209 return disjoint_segment_box_impl 210 < 211 RelativeDistance, SegmentPoint, Box, 1, Dimension 212 >::apply(p0, p1, box, t_min, t_max); 213 } 214 }; 215 216 217 template 218 < 219 typename RelativeDistance, 220 typename SegmentPoint, 221 typename Box, 222 std::size_t Dimension 223 > 224 struct disjoint_segment_box_impl 225 < 226 RelativeDistance, SegmentPoint, Box, Dimension, Dimension 227 > 228 { 229 template <typename RelativeDistancePair> applyboost::geometry::detail::disjoint::disjoint_segment_box_impl230 static inline bool apply(SegmentPoint const&, SegmentPoint const&, 231 Box const&, 232 RelativeDistancePair&, RelativeDistancePair&) 233 { 234 return false; 235 } 236 }; 237 238 239 //========================================================================= 240 241 242 template <typename Segment, typename Box> 243 struct disjoint_segment_box 244 { applyboost::geometry::detail::disjoint::disjoint_segment_box245 static inline bool apply(Segment const& segment, Box const& box) 246 { 247 assert_dimension_equal<Segment, Box>(); 248 249 typedef typename util::calculation_type::geometric::binary 250 < 251 Segment, Box, void 252 >::type relative_distance_type; 253 254 typedef typename point_type<Segment>::type segment_point_type; 255 segment_point_type p0, p1; 256 geometry::detail::assign_point_from_index<0>(segment, p0); 257 geometry::detail::assign_point_from_index<1>(segment, p1); 258 259 return disjoint_segment_box_impl 260 < 261 relative_distance_type, segment_point_type, Box, 262 0, dimension<Box>::value 263 >::apply(p0, p1, box); 264 } 265 }; 266 267 268 }} // namespace detail::disjoint 269 #endif // DOXYGEN_NO_DETAIL 270 271 272 273 #ifndef DOXYGEN_NO_DISPATCH 274 namespace dispatch 275 { 276 277 278 template <typename Segment, typename Box, std::size_t DimensionCount> 279 struct disjoint<Segment, Box, DimensionCount, segment_tag, box_tag, false> 280 : detail::disjoint::disjoint_segment_box<Segment, Box> 281 {}; 282 283 284 } // namespace dispatch 285 #endif // DOXYGEN_NO_DISPATCH 286 287 288 }} // namespace boost::geometry 289 290 291 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP 292