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