1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2013 Barend Gehrels, Amsterdam, the Netherlands.
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
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)
13 #ifndef BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP
14 #define BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP
16 #include <boost/config.hpp>
17 #include <boost/rational.hpp>
19 #include <boost/geometry/core/assert.hpp>
20 #include <boost/geometry/util/math.hpp>
21 #include <boost/geometry/util/promote_floating_point.hpp>
23 namespace boost { namespace geometry
27 namespace detail { namespace segment_ratio
33 bool IsIntegral = boost::is_integral<Type>::type::value
37 template <typename Type>
38 struct less<Type, true>
40 template <typename Ratio>
41 static inline bool apply(Ratio const& lhs, Ratio const& rhs)
43 return boost::rational<Type>(lhs.numerator(), lhs.denominator())
44 < boost::rational<Type>(rhs.numerator(), rhs.denominator());
48 template <typename Type>
49 struct less<Type, false>
51 template <typename Ratio>
52 static inline bool apply(Ratio const& lhs, Ratio const& rhs)
54 BOOST_GEOMETRY_ASSERT(lhs.denominator() != 0);
55 BOOST_GEOMETRY_ASSERT(rhs.denominator() != 0);
56 return lhs.numerator() * rhs.denominator()
57 < rhs.numerator() * lhs.denominator();
64 bool IsIntegral = boost::is_integral<Type>::type::value
68 template <typename Type>
69 struct equal<Type, true>
71 template <typename Ratio>
72 static inline bool apply(Ratio const& lhs, Ratio const& rhs)
74 return boost::rational<Type>(lhs.numerator(), lhs.denominator())
75 == boost::rational<Type>(rhs.numerator(), rhs.denominator());
79 template <typename Type>
80 struct equal<Type, false>
82 template <typename Ratio>
83 static inline bool apply(Ratio const& lhs, Ratio const& rhs)
85 BOOST_GEOMETRY_ASSERT(lhs.denominator() != 0);
86 BOOST_GEOMETRY_ASSERT(rhs.denominator() != 0);
87 return geometry::math::equals
89 lhs.numerator() * rhs.denominator(),
90 rhs.numerator() * lhs.denominator()
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)
104 template <typename Type>
108 typedef Type numeric_type;
110 // Type-alias for the type itself
111 typedef segment_ratio<Type> thistype;
113 inline segment_ratio()
119 inline segment_ratio(const Type& nominator, const Type& denominator)
120 : m_numerator(nominator)
121 , m_denominator(denominator)
126 inline Type const& numerator() const { return m_numerator; }
127 inline Type const& denominator() const { return m_denominator; }
129 inline void assign(const Type& nominator, const Type& denominator)
131 m_numerator = nominator;
132 m_denominator = denominator;
136 inline void initialize()
138 // Minimal normalization
139 // 1/-4 => -1/4, -1/-4 => 1/4
140 if (m_denominator < 0)
142 m_numerator = -m_numerator;
143 m_denominator = -m_denominator;
147 m_denominator == 0 ? 0
149 boost::numeric_cast<fp_type>(m_numerator) * scale()
150 / boost::numeric_cast<fp_type>(m_denominator)
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
158 // e.g. 0/4 or 4/4 or 2/4
159 return m_numerator >= 0 && m_numerator <= m_denominator;
161 inline bool in_segment() const
164 return m_numerator > 0 && m_numerator < m_denominator;
166 inline bool on_end() const
169 return is_zero() || is_one();
171 inline bool left() const
174 return m_numerator < 0;
176 inline bool right() const
179 return m_numerator > m_denominator;
182 inline bool near_end() const
184 if (left() || right())
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;
194 inline bool close_to(thistype const& other) const
196 return geometry::math::abs(m_approximation - other.m_approximation) < 50;
199 inline bool operator< (thistype const& other) const
201 return close_to(other)
202 ? detail::segment_ratio::less<Type>::apply(*this, other)
203 : m_approximation < other.m_approximation;
206 inline bool operator== (thistype const& other) const
208 return close_to(other)
209 && detail::segment_ratio::equal<Type>::apply(*this, other);
212 static inline thistype zero()
214 static thistype result(0, 1);
218 static inline thistype one()
220 static thistype result(1, 1);
224 #if defined(BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO)
225 friend std::ostream& operator<<(std::ostream &os, segment_ratio const& ratio)
227 os << ratio.m_numerator << "/" << ratio.m_denominator
228 << " (" << (static_cast<double>(ratio.m_numerator)
229 / static_cast<double>(ratio.m_denominator))
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;
242 typedef typename boost::mpl::if_c
244 boost::is_float<Type>::value, Type, double
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;
258 static inline fp_type scale()
265 }} // namespace boost::geometry
267 #endif // BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP