boost/geometry/policies/robustness/segment_ratio.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2013 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // This file was modified by Oracle on 2016.
   6 // Modifications copyright (c) 2016 Oracle and/or its affiliates.
   7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   8
   9 // Use, modification and distribution is subject to the Boost Software License,
  10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  11 // http://www.boost.org/LICENSE_1_0.txt)
  12
  13 #ifndef BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP
  14 #define BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP
  15
  16 #include <boost/config.hpp>
  17 #include <boost/rational.hpp>
  18
  19 #include <boost/geometry/core/assert.hpp>
  20 #include <boost/geometry/util/math.hpp>
  21 #include <boost/geometry/util/promote_floating_point.hpp>
  22
  23 namespace boost { namespace geometry
  24 {
  25
  26
  27 namespace detail { namespace segment_ratio
  28 {
  29
  30 template
  31 <
  32     typename Type,
  33     bool IsIntegral = boost::is_integral<Type>::type::value
  34 >
  35 struct less {};
  36
  37 template <typename Type>
  38 struct less<Type, true>
  39 {
  40     template <typename Ratio>
  41     static inline bool apply(Ratio const& lhs, Ratio const& rhs)
  42     {
  43         return boost::rational<Type>(lhs.numerator(), lhs.denominator())
  44              < boost::rational<Type>(rhs.numerator(), rhs.denominator());
  45     }
  46 };
  47
  48 template <typename Type>
  49 struct less<Type, false>
  50 {
  51     template <typename Ratio>
  52     static inline bool apply(Ratio const& lhs, Ratio const& rhs)
  53     {
  54         BOOST_GEOMETRY_ASSERT(lhs.denominator() != 0);
  55         BOOST_GEOMETRY_ASSERT(rhs.denominator() != 0);
  56         Type const a = lhs.numerator() / lhs.denominator();
  57         Type const b = rhs.numerator() / rhs.denominator();
  58         return ! geometry::math::equals(a, b)
  59             && a < b;
  60     }
  61 };
  62
  63 template
  64 <
  65     typename Type,
  66     bool IsIntegral = boost::is_integral<Type>::type::value
  67 >
  68 struct equal {};
  69
  70 template <typename Type>
  71 struct equal<Type, true>
  72 {
  73     template <typename Ratio>
  74     static inline bool apply(Ratio const& lhs, Ratio const& rhs)
  75     {
  76         return boost::rational<Type>(lhs.numerator(), lhs.denominator())
  77             == boost::rational<Type>(rhs.numerator(), rhs.denominator());
  78     }
  79 };
  80
  81 template <typename Type>
  82 struct equal<Type, false>
  83 {
  84     template <typename Ratio>
  85     static inline bool apply(Ratio const& lhs, Ratio const& rhs)
  86     {
  87         BOOST_GEOMETRY_ASSERT(lhs.denominator() != 0);
  88         BOOST_GEOMETRY_ASSERT(rhs.denominator() != 0);
  89         Type const a = lhs.numerator() / lhs.denominator();
  90         Type const b = rhs.numerator() / rhs.denominator();
  91         return geometry::math::equals(a, b);
  92     }
  93 };
  94
  95 }}
  96
  97 //! Small class to keep a ratio (e.g. 1/4)
  98 //! Main purpose is intersections and checking on 0, 1, and smaller/larger
  99 //! The prototype used Boost.Rational. However, we also want to store FP ratios,
 100 //! (so numerator/denominator both in float)
 101 //! and Boost.Rational starts with GCD which we prefer to avoid if not necessary
 102 //! On a segment means: this ratio is between 0 and 1 (both inclusive)
 103 //!
 104 template <typename Type>
 105 class segment_ratio
 106 {
 107 public :
 108     typedef Type numeric_type;
 109
 110     // Type-alias for the type itself
 111     typedef segment_ratio<Type> thistype;
 112
 113     inline segment_ratio()
 114         : m_numerator(0)
 115         , m_denominator(1)
 116         , m_approximation(0)
 117     {}
 118
 119     inline segment_ratio(const Type& nominator, const Type& denominator)
 120         : m_numerator(nominator)
 121         , m_denominator(denominator)
 122     {
 123         initialize();
 124     }
 125
 126     inline Type const& numerator() const { return m_numerator; }
 127     inline Type const& denominator() const { return m_denominator; }
 128
 129     inline void assign(const Type& nominator, const Type& denominator)
 130     {
 131         m_numerator = nominator;
 132         m_denominator = denominator;
 133         initialize();
 134     }
 135
 136     inline void initialize()
 137     {
 138         // Minimal normalization
 139         // 1/-4 => -1/4, -1/-4 => 1/4
 140         if (m_denominator < 0)
 141         {
 142             m_numerator = -m_numerator;
 143             m_denominator = -m_denominator;
 144         }
 145
 146         m_approximation =
 147             m_denominator == 0 ? 0
 148             : (
 149                 boost::numeric_cast<fp_type>(m_numerator) * scale()
 150                 / boost::numeric_cast<fp_type>(m_denominator)
 151             );
 152     }
 153
 154     inline bool is_zero() const { return math::equals(m_numerator, 0); }
 155     inline bool is_one() const { return math::equals(m_numerator, m_denominator); }
 156     inline bool on_segment() const
 157     {
 158         // e.g. 0/4 or 4/4 or 2/4
 159         return m_numerator >= 0 && m_numerator <= m_denominator;
 160     }
 161     inline bool in_segment() const
 162     {
 163         // e.g. 1/4
 164         return m_numerator > 0 && m_numerator < m_denominator;
 165     }
 166     inline bool on_end() const
 167     {
 168         // e.g. 0/4 or 4/4
 169         return is_zero() || is_one();
 170     }
 171     inline bool left() const
 172     {
 173         // e.g. -1/4
 174         return m_numerator < 0;
 175     }
 176     inline bool right() const
 177     {
 178         // e.g. 5/4
 179         return m_numerator > m_denominator;
 180     }
 181
 182     inline bool near_end() const
 183     {
 184         if (left() || right())
 185         {
 186             return false;
 187         }
 188
 189         static fp_type const small_part_of_scale = scale() / 100;
 190         return m_approximation < small_part_of_scale
 191             || m_approximation > scale() - small_part_of_scale;
 192     }
 193
 194     inline bool close_to(thistype const& other) const
 195     {
 196         return geometry::math::abs(m_approximation - other.m_approximation) < 50;
 197     }
 198
 199     inline bool operator< (thistype const& other) const
 200     {
 201         return close_to(other)
 202             ? detail::segment_ratio::less<Type>::apply(*this, other)
 203             : m_approximation < other.m_approximation;
 204     }
 205
 206     inline bool operator== (thistype const& other) const
 207     {
 208         return close_to(other)
 209             && detail::segment_ratio::equal<Type>::apply(*this, other);
 210     }
 211
 212     static inline thistype zero()
 213     {
 214         static thistype result(0, 1);
 215         return result;
 216     }
 217
 218     static inline thistype one()
 219     {
 220         static thistype result(1, 1);
 221         return result;
 222     }
 223
 224 #if defined(BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO)
 225     friend std::ostream& operator<<(std::ostream &os, segment_ratio const& ratio)
 226     {
 227         os << ratio.m_numerator << "/" << ratio.m_denominator
 228            << " (" << (static_cast<double>(ratio.m_numerator)
 229                         / static_cast<double>(ratio.m_denominator))
 230            << ")";
 231         return os;
 232     }
 233 #endif
 234
 235
 236
 237 private :
 238     // NOTE: if this typedef is used then fp_type is non-fundamental type
 239     // if Type is non-fundamental type
 240     //typedef typename promote_floating_point<Type>::type fp_type;
 241
 242     typedef typename boost::mpl::if_c
 243         <
 244             boost::is_float<Type>::value, Type, double
 245         >::type fp_type;
 246
 247     Type m_numerator;
 248     Type m_denominator;
 249
 250     // Contains ratio on scale 0..1000000 (for 0..1)
 251     // This is an approximation for fast and rough comparisons
 252     // Boost.Rational is used if the approximations are close.
 253     // Reason: performance, Boost.Rational does a GCD by default and also the
 254     // comparisons contain while-loops.
 255     fp_type m_approximation;
 256
 257
 258     static inline fp_type scale()
 259     {
 260         return 1000000.0;
 261     }
 262 };
 263
 264
 265 }} // namespace boost::geometry
 266
 267 #endif // BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP