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