| // Boost.Geometry (aka GGL, Generic Geometry Library) |
| |
| // Copyright (c) 2013 Barend Gehrels, Amsterdam, the Netherlands. |
| |
| // Use, modification and distribution is subject to the Boost Software License, |
| // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| |
| #ifndef BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP |
| #define BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP |
| |
| #include <boost/assert.hpp> |
| #include <boost/config.hpp> |
| #include <boost/rational.hpp> |
| |
| #include <boost/geometry/util/math.hpp> |
| #include <boost/geometry/util/promote_floating_point.hpp> |
| |
| namespace boost { namespace geometry |
| { |
| |
| |
| namespace detail { namespace segment_ratio |
| { |
| |
| template |
| < |
| typename Type, |
| bool IsIntegral = boost::is_integral<Type>::type::value |
| > |
| struct less {}; |
| |
| template <typename Type> |
| struct less<Type, true> |
| { |
| template <typename Ratio> |
| static inline bool apply(Ratio const& lhs, Ratio const& rhs) |
| { |
| return boost::rational<Type>(lhs.numerator(), lhs.denominator()) |
| < boost::rational<Type>(rhs.numerator(), rhs.denominator()); |
| } |
| }; |
| |
| template <typename Type> |
| struct less<Type, false> |
| { |
| template <typename Ratio> |
| static inline bool apply(Ratio const& lhs, Ratio const& rhs) |
| { |
| BOOST_ASSERT(lhs.denominator() != 0); |
| BOOST_ASSERT(rhs.denominator() != 0); |
| return lhs.numerator() * rhs.denominator() |
| < rhs.numerator() * lhs.denominator(); |
| } |
| }; |
| |
| template |
| < |
| typename Type, |
| bool IsIntegral = boost::is_integral<Type>::type::value |
| > |
| struct equal {}; |
| |
| template <typename Type> |
| struct equal<Type, true> |
| { |
| template <typename Ratio> |
| static inline bool apply(Ratio const& lhs, Ratio const& rhs) |
| { |
| return boost::rational<Type>(lhs.numerator(), lhs.denominator()) |
| == boost::rational<Type>(rhs.numerator(), rhs.denominator()); |
| } |
| }; |
| |
| template <typename Type> |
| struct equal<Type, false> |
| { |
| template <typename Ratio> |
| static inline bool apply(Ratio const& lhs, Ratio const& rhs) |
| { |
| BOOST_ASSERT(lhs.denominator() != 0); |
| BOOST_ASSERT(rhs.denominator() != 0); |
| return geometry::math::equals |
| ( |
| lhs.numerator() * rhs.denominator(), |
| rhs.numerator() * lhs.denominator() |
| ); |
| } |
| }; |
| |
| }} |
| |
| //! Small class to keep a ratio (e.g. 1/4) |
| //! Main purpose is intersections and checking on 0, 1, and smaller/larger |
| //! The prototype used Boost.Rational. However, we also want to store FP ratios, |
| //! (so numerator/denominator both in float) |
| //! and Boost.Rational starts with GCD which we prefer to avoid if not necessary |
| //! On a segment means: this ratio is between 0 and 1 (both inclusive) |
| //! |
| template <typename Type> |
| class segment_ratio |
| { |
| public : |
| typedef Type numeric_type; |
| |
| // Type-alias for the type itself |
| typedef segment_ratio<Type> thistype; |
| |
| inline segment_ratio() |
| : m_numerator(0) |
| , m_denominator(1) |
| , m_approximation(0) |
| {} |
| |
| inline segment_ratio(const Type& nominator, const Type& denominator) |
| : m_numerator(nominator) |
| , m_denominator(denominator) |
| { |
| initialize(); |
| } |
| |
| inline Type const& numerator() const { return m_numerator; } |
| inline Type const& denominator() const { return m_denominator; } |
| |
| inline void assign(const Type& nominator, const Type& denominator) |
| { |
| m_numerator = nominator; |
| m_denominator = denominator; |
| initialize(); |
| } |
| |
| inline void initialize() |
| { |
| // Minimal normalization |
| // 1/-4 => -1/4, -1/-4 => 1/4 |
| if (m_denominator < 0) |
| { |
| m_numerator = -m_numerator; |
| m_denominator = -m_denominator; |
| } |
| |
| typedef typename promote_floating_point<Type>::type num_type; |
| static const num_type scale = 1000000.0; |
| m_approximation = |
| m_denominator == 0 ? 0 |
| : boost::numeric_cast<double> |
| ( |
| boost::numeric_cast<num_type>(m_numerator) * scale |
| / boost::numeric_cast<num_type>(m_denominator) |
| ); |
| } |
| |
| inline bool is_zero() const { return math::equals(m_numerator, 0); } |
| inline bool is_one() const { return math::equals(m_numerator, m_denominator); } |
| inline bool on_segment() const |
| { |
| // e.g. 0/4 or 4/4 or 2/4 |
| return m_numerator >= 0 && m_numerator <= m_denominator; |
| } |
| inline bool in_segment() const |
| { |
| // e.g. 1/4 |
| return m_numerator > 0 && m_numerator < m_denominator; |
| } |
| inline bool on_end() const |
| { |
| // e.g. 0/4 or 4/4 |
| return is_zero() || is_one(); |
| } |
| inline bool left() const |
| { |
| // e.g. -1/4 |
| return m_numerator < 0; |
| } |
| inline bool right() const |
| { |
| // e.g. 5/4 |
| return m_numerator > m_denominator; |
| } |
| |
| inline bool close_to(thistype const& other) const |
| { |
| return geometry::math::abs(m_approximation - other.m_approximation) < 2; |
| } |
| |
| inline bool operator< (thistype const& other) const |
| { |
| return close_to(other) |
| ? detail::segment_ratio::less<Type>::apply(*this, other) |
| : m_approximation < other.m_approximation; |
| } |
| |
| inline bool operator== (thistype const& other) const |
| { |
| return close_to(other) |
| && detail::segment_ratio::equal<Type>::apply(*this, other); |
| } |
| |
| static inline thistype zero() |
| { |
| static thistype result(0, 1); |
| return result; |
| } |
| |
| static inline thistype one() |
| { |
| static thistype result(1, 1); |
| return result; |
| } |
| |
| #if defined(BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO) |
| friend std::ostream& operator<<(std::ostream &os, segment_ratio const& ratio) |
| { |
| os << ratio.m_numerator << "/" << ratio.m_denominator |
| << " (" << (static_cast<double>(ratio.m_numerator) |
| / static_cast<double>(ratio.m_denominator)) |
| << ")"; |
| return os; |
| } |
| #endif |
| |
| |
| |
| private : |
| Type m_numerator; |
| Type m_denominator; |
| |
| // Contains ratio on scale 0..1000000 (for 0..1) |
| // This is an approximation for fast and rough comparisons |
| // Boost.Rational is used if the approximations are close. |
| // Reason: performance, Boost.Rational does a GCD by default and also the |
| // comparisons contain while-loops. |
| double m_approximation; |
| }; |
| |
| |
| }} // namespace boost::geometry |
| |
| #endif // BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP |