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> applyboost::geometry::detail::segment_ratio::less41 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> applyboost::geometry::detail::segment_ratio::less52 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> applyboost::geometry::detail::segment_ratio::equal74 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> applyboost::geometry::detail::segment_ratio::equal85 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 segment_ratio()113 inline segment_ratio() 114 : m_numerator(0) 115 , m_denominator(1) 116 , m_approximation(0) 117 {} 118 segment_ratio(const Type & nominator,const Type & denominator)119 inline segment_ratio(const Type& nominator, const Type& denominator) 120 : m_numerator(nominator) 121 , m_denominator(denominator) 122 { 123 initialize(); 124 } 125 numerator() const126 inline Type const& numerator() const { return m_numerator; } denominator() const127 inline Type const& denominator() const { return m_denominator; } 128 assign(const Type & nominator,const Type & denominator)129 inline void assign(const Type& nominator, const Type& denominator) 130 { 131 m_numerator = nominator; 132 m_denominator = denominator; 133 initialize(); 134 } 135 initialize()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 is_zero() const154 inline bool is_zero() const { return math::equals(m_numerator, 0); } is_one() const155 inline bool is_one() const { return math::equals(m_numerator, m_denominator); } on_segment() const156 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 } in_segment() const161 inline bool in_segment() const 162 { 163 // e.g. 1/4 164 return m_numerator > 0 && m_numerator < m_denominator; 165 } on_end() const166 inline bool on_end() const 167 { 168 // e.g. 0/4 or 4/4 169 return is_zero() || is_one(); 170 } left() const171 inline bool left() const 172 { 173 // e.g. -1/4 174 return m_numerator < 0; 175 } right() const176 inline bool right() const 177 { 178 // e.g. 5/4 179 return m_numerator > m_denominator; 180 } 181 near_end() const182 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 close_to(thistype const & other) const194 inline bool close_to(thistype const& other) const 195 { 196 return geometry::math::abs(m_approximation - other.m_approximation) < 50; 197 } 198 operator <(thistype const & other) const199 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 operator ==(thistype const & other) const206 inline bool operator== (thistype const& other) const 207 { 208 return close_to(other) 209 && detail::segment_ratio::equal<Type>::apply(*this, other); 210 } 211 zero()212 static inline thistype zero() 213 { 214 static thistype result(0, 1); 215 return result; 216 } 217 one()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) operator <<(std::ostream & os,segment_ratio const & 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 scale()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 268