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-2020. 6 // Modifications copyright (c) 2016-2020 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 <type_traits> 17 18 #include <boost/config.hpp> 19 #include <boost/rational.hpp> 20 21 #include <boost/geometry/core/assert.hpp> 22 #include <boost/geometry/util/math.hpp> 23 #include <boost/geometry/util/promote_floating_point.hpp> 24 25 namespace boost { namespace geometry 26 { 27 28 29 namespace detail { namespace segment_ratio 30 { 31 32 template 33 < 34 typename Type, 35 bool IsIntegral = std::is_integral<Type>::type::value 36 > 37 struct less {}; 38 39 template <typename Type> 40 struct less<Type, true> 41 { 42 template <typename Ratio> applyboost::geometry::detail::segment_ratio::less43 static inline bool apply(Ratio const& lhs, Ratio const& rhs) 44 { 45 return boost::rational<Type>(lhs.numerator(), lhs.denominator()) 46 < boost::rational<Type>(rhs.numerator(), rhs.denominator()); 47 } 48 }; 49 50 template <typename Type> 51 struct less<Type, false> 52 { 53 template <typename Ratio> applyboost::geometry::detail::segment_ratio::less54 static inline bool apply(Ratio const& lhs, Ratio const& rhs) 55 { 56 BOOST_GEOMETRY_ASSERT(lhs.denominator() != 0); 57 BOOST_GEOMETRY_ASSERT(rhs.denominator() != 0); 58 Type const a = lhs.numerator() / lhs.denominator(); 59 Type const b = rhs.numerator() / rhs.denominator(); 60 return ! geometry::math::equals(a, b) 61 && a < b; 62 } 63 }; 64 65 template 66 < 67 typename Type, 68 bool IsIntegral = std::is_integral<Type>::type::value 69 > 70 struct equal {}; 71 72 template <typename Type> 73 struct equal<Type, true> 74 { 75 template <typename Ratio> applyboost::geometry::detail::segment_ratio::equal76 static inline bool apply(Ratio const& lhs, Ratio const& rhs) 77 { 78 return boost::rational<Type>(lhs.numerator(), lhs.denominator()) 79 == boost::rational<Type>(rhs.numerator(), rhs.denominator()); 80 } 81 }; 82 83 template <typename Type> 84 struct equal<Type, false> 85 { 86 template <typename Ratio> applyboost::geometry::detail::segment_ratio::equal87 static inline bool apply(Ratio const& lhs, Ratio const& rhs) 88 { 89 BOOST_GEOMETRY_ASSERT(lhs.denominator() != 0); 90 BOOST_GEOMETRY_ASSERT(rhs.denominator() != 0); 91 Type const a = lhs.numerator() / lhs.denominator(); 92 Type const b = rhs.numerator() / rhs.denominator(); 93 return geometry::math::equals(a, b); 94 } 95 }; 96 97 }} 98 99 //! Small class to keep a ratio (e.g. 1/4) 100 //! Main purpose is intersections and checking on 0, 1, and smaller/larger 101 //! The prototype used Boost.Rational. However, we also want to store FP ratios, 102 //! (so numerator/denominator both in float) 103 //! and Boost.Rational starts with GCD which we prefer to avoid if not necessary 104 //! On a segment means: this ratio is between 0 and 1 (both inclusive) 105 //! 106 template <typename Type> 107 class segment_ratio 108 { 109 public : 110 typedef Type numeric_type; 111 112 // Type-alias for the type itself 113 typedef segment_ratio<Type> thistype; 114 segment_ratio()115 inline segment_ratio() 116 : m_numerator(0) 117 , m_denominator(1) 118 , m_approximation(0) 119 {} 120 segment_ratio(const Type & nominator,const Type & denominator)121 inline segment_ratio(const Type& nominator, const Type& denominator) 122 : m_numerator(nominator) 123 , m_denominator(denominator) 124 { 125 initialize(); 126 } 127 numerator() const128 inline Type const& numerator() const { return m_numerator; } denominator() const129 inline Type const& denominator() const { return m_denominator; } 130 assign(const Type & nominator,const Type & denominator)131 inline void assign(const Type& nominator, const Type& denominator) 132 { 133 m_numerator = nominator; 134 m_denominator = denominator; 135 initialize(); 136 } 137 initialize()138 inline void initialize() 139 { 140 // Minimal normalization 141 // 1/-4 => -1/4, -1/-4 => 1/4 142 if (m_denominator < 0) 143 { 144 m_numerator = -m_numerator; 145 m_denominator = -m_denominator; 146 } 147 148 m_approximation = 149 m_denominator == 0 ? 0 150 : ( 151 boost::numeric_cast<fp_type>(m_numerator) * scale() 152 / boost::numeric_cast<fp_type>(m_denominator) 153 ); 154 } 155 is_zero() const156 inline bool is_zero() const { return math::equals(m_numerator, 0); } is_one() const157 inline bool is_one() const { return math::equals(m_numerator, m_denominator); } on_segment() const158 inline bool on_segment() const 159 { 160 // e.g. 0/4 or 4/4 or 2/4 161 return m_numerator >= 0 && m_numerator <= m_denominator; 162 } in_segment() const163 inline bool in_segment() const 164 { 165 // e.g. 1/4 166 return m_numerator > 0 && m_numerator < m_denominator; 167 } on_end() const168 inline bool on_end() const 169 { 170 // e.g. 0/4 or 4/4 171 return is_zero() || is_one(); 172 } left() const173 inline bool left() const 174 { 175 // e.g. -1/4 176 return m_numerator < 0; 177 } right() const178 inline bool right() const 179 { 180 // e.g. 5/4 181 return m_numerator > m_denominator; 182 } 183 near_end() const184 inline bool near_end() const 185 { 186 if (left() || right()) 187 { 188 return false; 189 } 190 191 static fp_type const small_part_of_scale = scale() / 100; 192 return m_approximation < small_part_of_scale 193 || m_approximation > scale() - small_part_of_scale; 194 } 195 close_to(thistype const & other) const196 inline bool close_to(thistype const& other) const 197 { 198 return geometry::math::abs(m_approximation - other.m_approximation) < 50; 199 } 200 operator <(thistype const & other) const201 inline bool operator< (thistype const& other) const 202 { 203 return close_to(other) 204 ? detail::segment_ratio::less<Type>::apply(*this, other) 205 : m_approximation < other.m_approximation; 206 } 207 operator ==(thistype const & other) const208 inline bool operator== (thistype const& other) const 209 { 210 return close_to(other) 211 && detail::segment_ratio::equal<Type>::apply(*this, other); 212 } 213 zero()214 static inline thistype zero() 215 { 216 static thistype result(0, 1); 217 return result; 218 } 219 one()220 static inline thistype one() 221 { 222 static thistype result(1, 1); 223 return result; 224 } 225 226 #if defined(BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO) operator <<(std::ostream & os,segment_ratio const & ratio)227 friend std::ostream& operator<<(std::ostream &os, segment_ratio const& ratio) 228 { 229 os << ratio.m_numerator << "/" << ratio.m_denominator 230 << " (" << (static_cast<double>(ratio.m_numerator) 231 / static_cast<double>(ratio.m_denominator)) 232 << ")"; 233 return os; 234 } 235 #endif 236 237 238 239 private : 240 // NOTE: if this typedef is used then fp_type is non-fundamental type 241 // if Type is non-fundamental type 242 //typedef typename promote_floating_point<Type>::type fp_type; 243 244 // TODO: What with user-defined numeric types? 245 // Shouldn't here is_integral be checked? 246 typedef std::conditional_t 247 < 248 std::is_floating_point<Type>::value, Type, double 249 > fp_type; 250 251 Type m_numerator; 252 Type m_denominator; 253 254 // Contains ratio on scale 0..1000000 (for 0..1) 255 // This is an approximation for fast and rough comparisons 256 // Boost.Rational is used if the approximations are close. 257 // Reason: performance, Boost.Rational does a GCD by default and also the 258 // comparisons contain while-loops. 259 fp_type m_approximation; 260 261 scale()262 static inline fp_type scale() 263 { 264 return 1000000.0; 265 } 266 }; 267 268 269 }} // namespace boost::geometry 270 271 #endif // BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP 272