strategies/cartesian/disjoint_segment_box.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2008-2014 Bruno Lalande, Paris, France.
0005 // Copyright (c) 2009-2014 Mateusz Loskot, London, UK.
0006 // Copyright (c) 2013-2014 Adam Wulkiewicz, Lodz, Poland.
0007
0008 // This file was modified by Oracle on 2013-2019.
0009 // Modifications copyright (c) 2013-2019, Oracle and/or its affiliates.
0010
0011 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0012 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0013 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0014
0015 // Use, modification and distribution is subject to the Boost Software License,
0016 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0017 // http://www.boost.org/LICENSE_1_0.txt)
0018
0019 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP
0020 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP
0021
0022
0023 #include <cstddef>
0024 #include <utility>
0025
0026 #include <boost/geometry/core/access.hpp>
0027 #include <boost/geometry/core/tags.hpp>
0028 #include <boost/geometry/core/coordinate_dimension.hpp>
0029 #include <boost/geometry/core/point_type.hpp>
0030
0031 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
0032
0033 #include <boost/geometry/strategies/cartesian/point_in_box.hpp>
0034 #include <boost/geometry/strategies/disjoint.hpp>
0035
0036 #include <boost/geometry/util/math.hpp>
0037 #include <boost/geometry/util/numeric_cast.hpp>
0038 #include <boost/geometry/util/calculation_type.hpp>
0039
0040 namespace boost { namespace geometry { namespace strategy { namespace disjoint
0041 {
0042
0043 namespace detail
0044 {
0045
0046 template <std::size_t I>
0047 struct compute_tmin_tmax_per_dim
0048 {
0049     template <typename SegmentPoint, typename Box, typename RelativeDistance>
0050     static inline void apply(SegmentPoint const& p0,
0051                              SegmentPoint const& p1,
0052                              Box const& box,
0053                              RelativeDistance& ti_min,
0054                              RelativeDistance& ti_max,
0055                              RelativeDistance& diff)
0056     {
0057         typedef typename coordinate_type<Box>::type box_coordinate_type;
0058         typedef typename coordinate_type
0059             <
0060                 SegmentPoint
0061             >::type point_coordinate_type;
0062
0063         RelativeDistance c_p0 = util::numeric_cast
0064             <
0065                 point_coordinate_type
0066             >( geometry::get<I>(p0) );
0067
0068         RelativeDistance c_p1 = util::numeric_cast
0069             <
0070                 point_coordinate_type
0071             >( geometry::get<I>(p1) );
0072
0073         RelativeDistance c_b_min = util::numeric_cast
0074             <
0075                 box_coordinate_type
0076             >( geometry::get<geometry::min_corner, I>(box) );
0077
0078         RelativeDistance c_b_max = util::numeric_cast
0079             <
0080                 box_coordinate_type
0081             >( geometry::get<geometry::max_corner, I>(box) );
0082
0083         if ( geometry::get<I>(p1) >= geometry::get<I>(p0) )
0084         {
0085             diff = c_p1 - c_p0;
0086             ti_min = c_b_min - c_p0;
0087             ti_max = c_b_max - c_p0;
0088         }
0089         else
0090         {
0091             diff = c_p0 - c_p1;
0092             ti_min = c_p0 - c_b_max;
0093             ti_max = c_p0 - c_b_min;
0094         }
0095     }
0096 };
0097
0098
0099 template
0100 <
0101     typename RelativeDistance,
0102     typename SegmentPoint,
0103     typename Box,
0104     std::size_t I,
0105     std::size_t Dimension
0106 >
0107 struct disjoint_segment_box_impl
0108 {
0109     template <typename RelativeDistancePair>
0110     static inline bool apply(SegmentPoint const& p0,
0111                              SegmentPoint const& p1,
0112                              Box const& box,
0113                              RelativeDistancePair& t_min,
0114                              RelativeDistancePair& t_max)
0115     {
0116         RelativeDistance ti_min, ti_max, diff;
0117
0118         compute_tmin_tmax_per_dim<I>::apply(p0, p1, box, ti_min, ti_max, diff);
0119
0120         if ( geometry::math::equals(diff, 0) )
0121         {
0122             if ( (geometry::math::equals(t_min.second, 0)
0123                   && t_min.first > ti_max)
0124                  ||
0125                  (geometry::math::equals(t_max.second, 0)
0126                   && t_max.first < ti_min)
0127                  ||
0128                  (math::sign(ti_min) * math::sign(ti_max) > 0) )
0129             {
0130                 return true;
0131             }
0132         }
0133
0134         RelativeDistance t_min_x_diff = t_min.first * diff;
0135         RelativeDistance t_max_x_diff = t_max.first * diff;
0136
0137         if ( t_min_x_diff > ti_max * t_min.second
0138              || t_max_x_diff < ti_min * t_max.second )
0139         {
0140             return true;
0141         }
0142
0143         if ( ti_min * t_min.second > t_min_x_diff )
0144         {
0145             t_min.first = ti_min;
0146             t_min.second = diff;
0147         }
0148         if ( ti_max * t_max.second < t_max_x_diff )
0149         {
0150             t_max.first = ti_max;
0151             t_max.second = diff;
0152         }
0153
0154         if ( t_min.first > t_min.second || t_max.first < 0 )
0155         {
0156             return true;
0157         }
0158
0159         return disjoint_segment_box_impl
0160             <
0161                 RelativeDistance,
0162                 SegmentPoint,
0163                 Box,
0164                 I + 1,
0165                 Dimension
0166             >::apply(p0, p1, box, t_min, t_max);
0167     }
0168 };
0169
0170
0171 template
0172 <
0173     typename RelativeDistance,
0174     typename SegmentPoint,
0175     typename Box,
0176     std::size_t Dimension
0177 >
0178 struct disjoint_segment_box_impl
0179     <
0180         RelativeDistance, SegmentPoint, Box, 0, Dimension
0181     >
0182 {
0183     static inline bool apply(SegmentPoint const& p0,
0184                              SegmentPoint const& p1,
0185                              Box const& box)
0186     {
0187         std::pair<RelativeDistance, RelativeDistance> t_min, t_max;
0188         RelativeDistance diff;
0189
0190         compute_tmin_tmax_per_dim<0>::apply(p0, p1, box,
0191                                             t_min.first, t_max.first, diff);
0192
0193         if ( geometry::math::equals(diff, 0) )
0194         {
0195             if ( geometry::math::equals(t_min.first, 0) ) { t_min.first = -1; }
0196             if ( geometry::math::equals(t_max.first, 0) ) { t_max.first = 1; }
0197
0198             if (math::sign(t_min.first) * math::sign(t_max.first) > 0)
0199             {
0200                 return true;
0201             }
0202         }
0203
0204         if ( t_min.first > diff || t_max.first < 0 )
0205         {
0206             return true;
0207         }
0208
0209         t_min.second = t_max.second = diff;
0210
0211         return disjoint_segment_box_impl
0212             <
0213                 RelativeDistance, SegmentPoint, Box, 1, Dimension
0214             >::apply(p0, p1, box, t_min, t_max);
0215     }
0216 };
0217
0218
0219 template
0220 <
0221     typename RelativeDistance,
0222     typename SegmentPoint,
0223     typename Box,
0224     std::size_t Dimension
0225 >
0226 struct disjoint_segment_box_impl
0227     <
0228         RelativeDistance, SegmentPoint, Box, Dimension, Dimension
0229     >
0230 {
0231     template <typename RelativeDistancePair>
0232     static inline bool apply(SegmentPoint const&, SegmentPoint const&,
0233                              Box const&,
0234                              RelativeDistancePair&, RelativeDistancePair&)
0235     {
0236         return false;
0237     }
0238 };
0239
0240 } // namespace detail
0241
0242 // NOTE: This may be temporary place for this or corresponding strategy
0243 // It seems to be more appropriate to implement the opposite of it
0244 // e.g. intersection::segment_box because in disjoint() algorithm
0245 // other strategies that are used are intersection and covered_by strategies.
0246 struct segment_box
0247 {
0248     typedef covered_by::cartesian_point_box disjoint_point_box_strategy_type;
0249
0250     static inline disjoint_point_box_strategy_type get_disjoint_point_box_strategy()
0251     {
0252         return disjoint_point_box_strategy_type();
0253     }
0254
0255     template <typename Segment, typename Box>
0256     static inline bool apply(Segment const& segment, Box const& box)
0257     {
0258         assert_dimension_equal<Segment, Box>();
0259
0260         typedef typename util::calculation_type::geometric::binary
0261             <
0262                 Segment, Box, void
0263             >::type relative_distance_type;
0264
0265         typedef typename point_type<Segment>::type segment_point_type;
0266         segment_point_type p0, p1;
0267         geometry::detail::assign_point_from_index<0>(segment, p0);
0268         geometry::detail::assign_point_from_index<1>(segment, p1);
0269
0270         return detail::disjoint_segment_box_impl
0271             <
0272                 relative_distance_type, segment_point_type, Box,
0273                 0, dimension<Box>::value
0274             >::apply(p0, p1, box);
0275     }
0276 };
0277
0278
0279 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
0280
0281
0282 namespace services
0283 {
0284
0285 template <typename Linear, typename Box, typename LinearTag>
0286 struct default_strategy<Linear, Box, LinearTag, box_tag, 1, 2, cartesian_tag, cartesian_tag>
0287 {
0288     typedef disjoint::segment_box type;
0289 };
0290
0291 template <typename Box, typename Linear, typename LinearTag>
0292 struct default_strategy<Box, Linear, box_tag, LinearTag, 2, 1, cartesian_tag, cartesian_tag>
0293 {
0294     typedef disjoint::segment_box type;
0295 };
0296
0297
0298 } // namespace services
0299
0300
0301 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
0302
0303
0304 }}}} // namespace boost::geometry::strategy::disjoint
0305
0306
0307 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_DISJOINT_SEGMENT_BOX_HPP