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