boost/geometry/strategies/cartesian/disjoint_segment_box.hpp

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