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