policies/robustness/segment_ratio.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2013 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2016-2021.
0006 // Modifications copyright (c) 2016-2021 Oracle and/or its affiliates.
0007 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0008
0009 // Use, modification and distribution is subject to the Boost Software License,
0010 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0011 // http://www.boost.org/LICENSE_1_0.txt)
0012
0013 #ifndef BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP
0014 #define BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP
0015
0016 #include <type_traits>
0017
0018 #include <boost/config.hpp>
0019 #include <boost/rational.hpp>
0020
0021 #include <boost/geometry/core/assert.hpp>
0022 #include <boost/geometry/core/coordinate_promotion.hpp>
0023 #include <boost/geometry/util/math.hpp>
0024 #include <boost/geometry/util/numeric_cast.hpp>
0025
0026
0027 namespace boost { namespace geometry
0028 {
0029
0030
0031 namespace detail { namespace segment_ratio
0032 {
0033
0034 template
0035 <
0036     typename Type,
0037     bool IsIntegral = std::is_integral<Type>::type::value
0038 >
0039 struct less {};
0040
0041 template <typename Type>
0042 struct less<Type, true>
0043 {
0044     template <typename Ratio>
0045     static inline bool apply(Ratio const& lhs, Ratio const& rhs)
0046     {
0047         return boost::rational<Type>(lhs.numerator(), lhs.denominator())
0048              < boost::rational<Type>(rhs.numerator(), rhs.denominator());
0049     }
0050 };
0051
0052 template <typename Type>
0053 struct less<Type, false>
0054 {
0055     template <typename Ratio>
0056     static inline bool apply(Ratio const& lhs, Ratio const& rhs)
0057     {
0058         BOOST_GEOMETRY_ASSERT(lhs.denominator() != Type(0));
0059         BOOST_GEOMETRY_ASSERT(rhs.denominator() != Type(0));
0060         Type const a = lhs.numerator() / lhs.denominator();
0061         Type const b = rhs.numerator() / rhs.denominator();
0062         return ! geometry::math::equals(a, b)
0063             && a < b;
0064     }
0065 };
0066
0067 template
0068 <
0069     typename Type,
0070     bool IsIntegral = std::is_integral<Type>::type::value
0071 >
0072 struct equal {};
0073
0074 template <typename Type>
0075 struct equal<Type, true>
0076 {
0077     template <typename Ratio>
0078     static inline bool apply(Ratio const& lhs, Ratio const& rhs)
0079     {
0080         return boost::rational<Type>(lhs.numerator(), lhs.denominator())
0081             == boost::rational<Type>(rhs.numerator(), rhs.denominator());
0082     }
0083 };
0084
0085 template <typename Type>
0086 struct equal<Type, false>
0087 {
0088     template <typename Ratio>
0089     static inline bool apply(Ratio const& lhs, Ratio const& rhs)
0090     {
0091         BOOST_GEOMETRY_ASSERT(lhs.denominator() != Type(0));
0092         BOOST_GEOMETRY_ASSERT(rhs.denominator() != Type(0));
0093         Type const a = lhs.numerator() / lhs.denominator();
0094         Type const b = rhs.numerator() / rhs.denominator();
0095         return geometry::math::equals(a, b);
0096     }
0097 };
0098
0099 template
0100 <
0101     typename Type,
0102     bool IsFloatingPoint = std::is_floating_point<Type>::type::value
0103 >
0104 struct possibly_collinear {};
0105
0106 template <typename Type>
0107 struct possibly_collinear<Type, true>
0108 {
0109     template <typename Ratio, typename Threshold>
0110     static inline bool apply(Ratio const& ratio, Threshold threshold)
0111     {
0112         return std::abs(ratio.denominator()) < threshold;
0113     }
0114 };
0115
0116 // Any ratio based on non-floating point (or user defined floating point)
0117 // is collinear if the denominator is exactly zero
0118 template <typename Type>
0119 struct possibly_collinear<Type, false>
0120 {
0121     template <typename Ratio, typename Threshold>
0122     static inline bool apply(Ratio const& ratio, Threshold)
0123     {
0124         static Type const zero = 0;
0125         return ratio.denominator() == zero;
0126     }
0127 };
0128
0129 }}
0130
0131 //! Small class to keep a ratio (e.g. 1/4)
0132 //! Main purpose is intersections and checking on 0, 1, and smaller/larger
0133 //! The prototype used Boost.Rational. However, we also want to store FP ratios,
0134 //! (so numerator/denominator both in float)
0135 //! and Boost.Rational starts with GCD which we prefer to avoid if not necessary
0136 //! On a segment means: this ratio is between 0 and 1 (both inclusive)
0137 //!
0138 template <typename Type>
0139 class segment_ratio
0140 {
0141     // Type used for the approximation (a helper value)
0142     // and for the edge value (0..1) (a helper function).
0143     using floating_point_type =
0144         typename detail::promoted_to_floating_point<Type>::type;
0145
0146     // Type-alias for the type itself
0147     using thistype = segment_ratio<Type>;
0148
0149 public:
0150     using int_type = Type;
0151
0152     inline segment_ratio()
0153         : m_numerator(0)
0154         , m_denominator(1)
0155         , m_approximation(0)
0156     {}
0157
0158     inline segment_ratio(Type const& numerator, Type const& denominator)
0159         : m_numerator(numerator)
0160         , m_denominator(denominator)
0161     {
0162         initialize();
0163     }
0164
0165     segment_ratio(segment_ratio const&) = default;
0166     segment_ratio& operator=(segment_ratio const&) = default;
0167     segment_ratio(segment_ratio&&) = default;
0168     segment_ratio& operator=(segment_ratio&&) = default;
0169
0170     // These are needed because in intersection strategies ratios are assigned
0171     // in fractions and if a user passes CalculationType then ratio Type in
0172     // turns is taken from geometry coordinate_type and the one used in
0173     // a strategy uses Type selected using CalculationType.
0174     // See: detail::overlay::intersection_info_base
0175     // and  policies::relate::segments_intersection_points
0176     //      in particular segments_collinear() where ratios are assigned.
0177     template<typename T> friend class segment_ratio;
0178     template <typename T>
0179     segment_ratio(segment_ratio<T> const& r)
0180         : m_numerator(r.m_numerator)
0181         , m_denominator(r.m_denominator)
0182     {
0183         initialize();
0184     }
0185     template <typename T>
0186     segment_ratio& operator=(segment_ratio<T> const& r)
0187     {
0188         m_numerator = r.m_numerator;
0189         m_denominator = r.m_denominator;
0190         initialize();
0191         return *this;
0192     }
0193     template <typename T>
0194     segment_ratio(segment_ratio<T> && r)
0195         : m_numerator(std::move(r.m_numerator))
0196         , m_denominator(std::move(r.m_denominator))
0197     {
0198         initialize();
0199     }
0200     template <typename T>
0201     segment_ratio& operator=(segment_ratio<T> && r)
0202     {
0203         m_numerator = std::move(r.m_numerator);
0204         m_denominator = std::move(r.m_denominator);
0205         initialize();
0206         return *this;
0207     }
0208
0209     inline Type const& numerator() const { return m_numerator; }
0210     inline Type const& denominator() const { return m_denominator; }
0211
0212     inline void assign(Type const& numerator, Type const& denominator)
0213     {
0214         m_numerator = numerator;
0215         m_denominator = denominator;
0216         initialize();
0217     }
0218
0219     inline void initialize()
0220     {
0221         // Minimal normalization
0222         // 1/-4 => -1/4, -1/-4 => 1/4
0223         if (m_denominator < zero_instance())
0224         {
0225             m_numerator = -m_numerator;
0226             m_denominator = -m_denominator;
0227         }
0228
0229         m_approximation =
0230             m_denominator == zero_instance() ? floating_point_type{0}
0231             : (
0232                 util::numeric_cast<floating_point_type>(m_numerator) * scale()
0233                 / util::numeric_cast<floating_point_type>(m_denominator)
0234             );
0235     }
0236
0237     inline bool is_zero() const { return math::equals(m_numerator, Type(0)); }
0238     inline bool is_one() const { return math::equals(m_numerator, m_denominator); }
0239     inline bool on_segment() const
0240     {
0241         // e.g. 0/4 or 4/4 or 2/4
0242         return m_numerator >= zero_instance() && m_numerator <= m_denominator;
0243     }
0244     inline bool in_segment() const
0245     {
0246         // e.g. 1/4
0247         return m_numerator > zero_instance() && m_numerator < m_denominator;
0248     }
0249     inline bool on_end() const
0250     {
0251         // e.g. 0/4 or 4/4
0252         return is_zero() || is_one();
0253     }
0254     inline bool left() const
0255     {
0256         // e.g. -1/4
0257         return m_numerator < zero_instance();
0258     }
0259     inline bool right() const
0260     {
0261         // e.g. 5/4
0262         return m_numerator > m_denominator;
0263     }
0264
0265     //! Returns a value between 0.0 and 1.0
0266     //! 0.0 means: exactly in the middle
0267     //! 1.0 means: exactly on one of the edges (or even over it)
0268     inline floating_point_type edge_value() const
0269     {
0270         using fp = floating_point_type;
0271         fp const one{1.0};
0272         floating_point_type const result
0273                 = fp(2) * geometry::math::abs(fp(0.5) - m_approximation / scale());
0274         return result > one ? one : result;
0275     }
0276
0277     template <typename Threshold>
0278     inline bool possibly_collinear(Threshold threshold) const
0279     {
0280         return detail::segment_ratio::possibly_collinear<Type>::apply(*this, threshold);
0281     }
0282
0283     inline bool operator< (thistype const& other) const
0284     {
0285         return close_to(other)
0286             ? detail::segment_ratio::less<Type>::apply(*this, other)
0287             : m_approximation < other.m_approximation;
0288     }
0289
0290     inline bool operator== (thistype const& other) const
0291     {
0292         return close_to(other)
0293             && detail::segment_ratio::equal<Type>::apply(*this, other);
0294     }
0295
0296     static inline thistype zero()
0297     {
0298         static thistype result(0, 1);
0299         return result;
0300     }
0301
0302     static inline thistype one()
0303     {
0304         static thistype result(1, 1);
0305         return result;
0306     }
0307
0308 #if defined(BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO)
0309     friend std::ostream& operator<<(std::ostream &os, segment_ratio const& ratio)
0310     {
0311         os << ratio.m_numerator << "/" << ratio.m_denominator
0312            << " (" << (static_cast<double>(ratio.m_numerator)
0313                         / static_cast<double>(ratio.m_denominator))
0314            << ")";
0315         return os;
0316     }
0317 #endif
0318
0319 private :
0320
0321     Type m_numerator;
0322     Type m_denominator;
0323
0324     // Contains ratio on scale 0..1000000 (for 0..1)
0325     // This is an approximation for fast and rough comparisons
0326     // Boost.Rational is used if the approximations are close.
0327     // Reason: performance, Boost.Rational does a GCD by default and also the
0328     // comparisons contain while-loops.
0329     floating_point_type m_approximation;
0330
0331     inline bool close_to(thistype const& other) const
0332     {
0333         static floating_point_type const threshold{50.0};
0334         return geometry::math::abs(m_approximation - other.m_approximation)
0335                 < threshold;
0336     }
0337
0338     static inline floating_point_type scale()
0339     {
0340         static floating_point_type const fp_scale{1000000.0};
0341         return fp_scale;
0342     }
0343
0344     static inline Type zero_instance()
0345     {
0346         return 0;
0347     }
0348 };
0349
0350
0351 }} // namespace boost::geometry
0352
0353 #endif // BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP