ceph/src/boost/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-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>
  52     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>
 112     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 {
 185     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>
 234     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
 252     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>
 258     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