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