ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/disjoint/segment_box.hpp

   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>
  55     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>
 115     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                  (math::sign(ti_min) * math::sign(ti_max) > 0) )
 134             {
 135                 return true;
 136             }
 137         }
 138
 139         RelativeDistance t_min_x_diff = t_min.first * diff;
 140         RelativeDistance t_max_x_diff = t_max.first * diff;
 141
 142         if ( t_min_x_diff > ti_max * t_min.second
 143              || t_max_x_diff < ti_min * t_max.second )
 144         {
 145             return true;
 146         }
 147
 148         if ( ti_min * t_min.second > t_min_x_diff )
 149         {
 150             t_min.first = ti_min;
 151             t_min.second = diff;
 152         }
 153         if ( ti_max * t_max.second < t_max_x_diff )
 154         {
 155             t_max.first = ti_max;
 156             t_max.second = diff;
 157         }
 158
 159         if ( t_min.first > t_min.second || t_max.first < 0 )
 160         {
 161             return true;
 162         }
 163
 164         return disjoint_segment_box_impl
 165             <
 166                 RelativeDistance,
 167                 SegmentPoint,
 168                 Box,
 169                 I + 1,
 170                 Dimension
 171             >::apply(p0, p1, box, t_min, t_max);
 172     }
 173 };
 174
 175
 176 template
 177 <
 178     typename RelativeDistance,
 179     typename SegmentPoint,
 180     typename Box,
 181     std::size_t Dimension
 182 >
 183 struct disjoint_segment_box_impl
 184     <
 185         RelativeDistance, SegmentPoint, Box, 0, Dimension
 186     >
 187 {
 188     static inline bool apply(SegmentPoint const& p0,
 189                              SegmentPoint const& p1,
 190                              Box const& box)
 191     {
 192         std::pair<RelativeDistance, RelativeDistance> t_min, t_max;
 193         RelativeDistance diff;
 194
 195         compute_tmin_tmax_per_dim<0>::apply(p0, p1, box,
 196                                             t_min.first, t_max.first, diff);
 197
 198         if ( geometry::math::equals(diff, 0) )
 199         {
 200             if ( geometry::math::equals(t_min.first, 0) ) { t_min.first = -1; }
 201             if ( geometry::math::equals(t_max.first, 0) ) { t_max.first = 1; }
 202
 203             if (math::sign(t_min.first) * math::sign(t_max.first) > 0)
 204             {
 205                 return true;
 206             }
 207         }
 208
 209         if ( t_min.first > diff || t_max.first < 0 )
 210         {
 211             return true;
 212         }
 213
 214         t_min.second = t_max.second = diff;
 215
 216         return disjoint_segment_box_impl
 217             <
 218                 RelativeDistance, SegmentPoint, Box, 1, Dimension
 219             >::apply(p0, p1, box, t_min, t_max);
 220     }
 221 };
 222
 223
 224 template
 225 <
 226     typename RelativeDistance,
 227     typename SegmentPoint,
 228     typename Box,
 229     std::size_t Dimension
 230 >
 231 struct disjoint_segment_box_impl
 232     <
 233         RelativeDistance, SegmentPoint, Box, Dimension, Dimension
 234     >
 235 {
 236     template <typename RelativeDistancePair>
 237     static inline bool apply(SegmentPoint const&, SegmentPoint const&,
 238                              Box const&,
 239                              RelativeDistancePair&, RelativeDistancePair&)
 240     {
 241         return false;
 242     }
 243 };
 244
 245
 246 //=========================================================================
 247
 248
 249 template <typename Segment, typename Box>
 250 struct disjoint_segment_box
 251 {
 252     static inline bool apply(Segment const& segment, Box const& box)
 253     {
 254         assert_dimension_equal<Segment, Box>();
 255
 256         typedef typename util::calculation_type::geometric::binary
 257             <
 258                 Segment, Box, void
 259             >::type relative_distance_type;
 260
 261         typedef typename point_type<Segment>::type segment_point_type;
 262         segment_point_type p0, p1;
 263         geometry::detail::assign_point_from_index<0>(segment, p0);
 264         geometry::detail::assign_point_from_index<1>(segment, p1);
 265
 266         return disjoint_segment_box_impl
 267             <
 268                 relative_distance_type, segment_point_type, Box,
 269                 0, dimension<Box>::value
 270             >::apply(p0, p1, box);
 271     }
 272 };
 273
 274
 275 }} // namespace detail::disjoint
 276 #endif // DOXYGEN_NO_DETAIL
 277
 278
 279
 280 #ifndef DOXYGEN_NO_DISPATCH
 281 namespace dispatch
 282 {
 283
 284
 285 template <typename Segment, typename Box, std::size_t DimensionCount>
 286 struct disjoint<Segment, Box, DimensionCount, segment_tag, box_tag, false>
 287     : detail::disjoint::disjoint_segment_box<Segment, Box>
 288 {};
 289
 290
 291 } // namespace dispatch
 292 #endif // DOXYGEN_NO_DISPATCH
 293
 294
 295 }} // namespace boost::geometry
 296
 297
 298 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_SEGMENT_BOX_HPP