1 // Boost.Geometry 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-2019. 9 // Modifications copyright (c) 2013-2019, Oracle and/or its affiliates. 10 11 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle 12 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 13 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 14 15 // Use, modification and distribution is subject to the Boost Software License, 16 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 17 // http://www.boost.org/LICENSE_1_0.txt) 18 19 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP 20 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP 21 22 23 #include <cstddef> 24 #include <utility> 25 26 #include <boost/numeric/conversion/cast.hpp> 27 28 #include <boost/geometry/util/math.hpp> 29 #include <boost/geometry/util/calculation_type.hpp> 30 31 #include <boost/geometry/core/access.hpp> 32 #include <boost/geometry/core/tags.hpp> 33 #include <boost/geometry/core/coordinate_dimension.hpp> 34 #include <boost/geometry/core/point_type.hpp> 35 36 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> 37 38 #include <boost/geometry/strategies/cartesian/point_in_box.hpp> 39 #include <boost/geometry/strategies/disjoint.hpp> 40 41 42 namespace boost { namespace geometry { namespace strategy { namespace disjoint 43 { 44 45 namespace detail 46 { 47 48 template <std::size_t I> 49 struct compute_tmin_tmax_per_dim 50 { 51 template <typename SegmentPoint, typename Box, typename RelativeDistance> applyboost::geometry::strategy::disjoint::detail::compute_tmin_tmax_per_dim52 static inline void apply(SegmentPoint const& p0, 53 SegmentPoint const& p1, 54 Box const& box, 55 RelativeDistance& ti_min, 56 RelativeDistance& ti_max, 57 RelativeDistance& diff) 58 { 59 typedef typename coordinate_type<Box>::type box_coordinate_type; 60 typedef typename coordinate_type 61 < 62 SegmentPoint 63 >::type point_coordinate_type; 64 65 RelativeDistance c_p0 = boost::numeric_cast 66 < 67 point_coordinate_type 68 >( geometry::get<I>(p0) ); 69 70 RelativeDistance c_p1 = boost::numeric_cast 71 < 72 point_coordinate_type 73 >( geometry::get<I>(p1) ); 74 75 RelativeDistance c_b_min = boost::numeric_cast 76 < 77 box_coordinate_type 78 >( geometry::get<geometry::min_corner, I>(box) ); 79 80 RelativeDistance c_b_max = boost::numeric_cast 81 < 82 box_coordinate_type 83 >( geometry::get<geometry::max_corner, I>(box) ); 84 85 if ( geometry::get<I>(p1) >= geometry::get<I>(p0) ) 86 { 87 diff = c_p1 - c_p0; 88 ti_min = c_b_min - c_p0; 89 ti_max = c_b_max - c_p0; 90 } 91 else 92 { 93 diff = c_p0 - c_p1; 94 ti_min = c_p0 - c_b_max; 95 ti_max = c_p0 - c_b_min; 96 } 97 } 98 }; 99 100 101 template 102 < 103 typename RelativeDistance, 104 typename SegmentPoint, 105 typename Box, 106 std::size_t I, 107 std::size_t Dimension 108 > 109 struct disjoint_segment_box_impl 110 { 111 template <typename RelativeDistancePair> applyboost::geometry::strategy::disjoint::detail::disjoint_segment_box_impl112 static inline bool apply(SegmentPoint const& p0, 113 SegmentPoint const& p1, 114 Box const& box, 115 RelativeDistancePair& t_min, 116 RelativeDistancePair& t_max) 117 { 118 RelativeDistance ti_min, ti_max, diff; 119 120 compute_tmin_tmax_per_dim<I>::apply(p0, p1, box, ti_min, ti_max, diff); 121 122 if ( geometry::math::equals(diff, 0) ) 123 { 124 if ( (geometry::math::equals(t_min.second, 0) 125 && t_min.first > ti_max) 126 || 127 (geometry::math::equals(t_max.second, 0) 128 && t_max.first < ti_min) 129 || 130 (math::sign(ti_min) * math::sign(ti_max) > 0) ) 131 { 132 return true; 133 } 134 } 135 136 RelativeDistance t_min_x_diff = t_min.first * diff; 137 RelativeDistance t_max_x_diff = t_max.first * diff; 138 139 if ( t_min_x_diff > ti_max * t_min.second 140 || t_max_x_diff < ti_min * t_max.second ) 141 { 142 return true; 143 } 144 145 if ( ti_min * t_min.second > t_min_x_diff ) 146 { 147 t_min.first = ti_min; 148 t_min.second = diff; 149 } 150 if ( ti_max * t_max.second < t_max_x_diff ) 151 { 152 t_max.first = ti_max; 153 t_max.second = diff; 154 } 155 156 if ( t_min.first > t_min.second || t_max.first < 0 ) 157 { 158 return true; 159 } 160 161 return disjoint_segment_box_impl 162 < 163 RelativeDistance, 164 SegmentPoint, 165 Box, 166 I + 1, 167 Dimension 168 >::apply(p0, p1, box, t_min, t_max); 169 } 170 }; 171 172 173 template 174 < 175 typename RelativeDistance, 176 typename SegmentPoint, 177 typename Box, 178 std::size_t Dimension 179 > 180 struct disjoint_segment_box_impl 181 < 182 RelativeDistance, SegmentPoint, Box, 0, Dimension 183 > 184 { applyboost::geometry::strategy::disjoint::detail::disjoint_segment_box_impl185 static inline bool apply(SegmentPoint const& p0, 186 SegmentPoint const& p1, 187 Box const& box) 188 { 189 std::pair<RelativeDistance, RelativeDistance> t_min, t_max; 190 RelativeDistance diff; 191 192 compute_tmin_tmax_per_dim<0>::apply(p0, p1, box, 193 t_min.first, t_max.first, diff); 194 195 if ( geometry::math::equals(diff, 0) ) 196 { 197 if ( geometry::math::equals(t_min.first, 0) ) { t_min.first = -1; } 198 if ( geometry::math::equals(t_max.first, 0) ) { t_max.first = 1; } 199 200 if (math::sign(t_min.first) * math::sign(t_max.first) > 0) 201 { 202 return true; 203 } 204 } 205 206 if ( t_min.first > diff || t_max.first < 0 ) 207 { 208 return true; 209 } 210 211 t_min.second = t_max.second = diff; 212 213 return disjoint_segment_box_impl 214 < 215 RelativeDistance, SegmentPoint, Box, 1, Dimension 216 >::apply(p0, p1, box, t_min, t_max); 217 } 218 }; 219 220 221 template 222 < 223 typename RelativeDistance, 224 typename SegmentPoint, 225 typename Box, 226 std::size_t Dimension 227 > 228 struct disjoint_segment_box_impl 229 < 230 RelativeDistance, SegmentPoint, Box, Dimension, Dimension 231 > 232 { 233 template <typename RelativeDistancePair> applyboost::geometry::strategy::disjoint::detail::disjoint_segment_box_impl234 static inline bool apply(SegmentPoint const&, SegmentPoint const&, 235 Box const&, 236 RelativeDistancePair&, RelativeDistancePair&) 237 { 238 return false; 239 } 240 }; 241 242 } // namespace detail 243 244 // NOTE: This may be temporary place for this or corresponding strategy 245 // It seems to be more appropriate to implement the opposite of it 246 // e.g. intersection::segment_box because in disjoint() algorithm 247 // other strategies that are used are intersection and covered_by strategies. 248 struct segment_box 249 { 250 typedef covered_by::cartesian_point_box disjoint_point_box_strategy_type; 251 get_disjoint_point_box_strategyboost::geometry::strategy::disjoint::segment_box252 static inline disjoint_point_box_strategy_type get_disjoint_point_box_strategy() 253 { 254 return disjoint_point_box_strategy_type(); 255 } 256 257 template <typename Segment, typename Box> applyboost::geometry::strategy::disjoint::segment_box258 static inline bool apply(Segment const& segment, Box const& box) 259 { 260 assert_dimension_equal<Segment, Box>(); 261 262 typedef typename util::calculation_type::geometric::binary 263 < 264 Segment, Box, void 265 >::type relative_distance_type; 266 267 typedef typename point_type<Segment>::type segment_point_type; 268 segment_point_type p0, p1; 269 geometry::detail::assign_point_from_index<0>(segment, p0); 270 geometry::detail::assign_point_from_index<1>(segment, p1); 271 272 return detail::disjoint_segment_box_impl 273 < 274 relative_distance_type, segment_point_type, Box, 275 0, dimension<Box>::value 276 >::apply(p0, p1, box); 277 } 278 }; 279 280 281 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS 282 283 284 namespace services 285 { 286 287 template <typename Linear, typename Box, typename LinearTag> 288 struct default_strategy<Linear, Box, LinearTag, box_tag, 1, 2, cartesian_tag, cartesian_tag> 289 { 290 typedef disjoint::segment_box type; 291 }; 292 293 template <typename Box, typename Linear, typename LinearTag> 294 struct default_strategy<Box, Linear, box_tag, LinearTag, 2, 1, cartesian_tag, cartesian_tag> 295 { 296 typedef disjoint::segment_box type; 297 }; 298 299 300 } // namespace services 301 302 303 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS 304 305 306 }}}} // namespace boost::geometry::strategy::disjoint 307 308 309 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP 310