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