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