]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
41 | 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> | |
52 | 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); | |
92f5a8d4 TL |
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; | |
7c673cae FG |
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> | |
74 | 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> | |
85 | 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); | |
92f5a8d4 TL |
89 | Type const a = lhs.numerator() / lhs.denominator(); |
90 | Type const b = rhs.numerator() / rhs.denominator(); | |
91 | return geometry::math::equals(a, b); | |
7c673cae FG |
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 | ||
113 | inline segment_ratio() | |
114 | : m_numerator(0) | |
115 | , m_denominator(1) | |
116 | , m_approximation(0) | |
117 | {} | |
118 | ||
119 | inline segment_ratio(const Type& nominator, const Type& denominator) | |
120 | : m_numerator(nominator) | |
121 | , m_denominator(denominator) | |
122 | { | |
123 | initialize(); | |
124 | } | |
125 | ||
126 | inline Type const& numerator() const { return m_numerator; } | |
127 | inline Type const& denominator() const { return m_denominator; } | |
128 | ||
129 | inline void assign(const Type& nominator, const Type& denominator) | |
130 | { | |
131 | m_numerator = nominator; | |
132 | m_denominator = denominator; | |
133 | initialize(); | |
134 | } | |
135 | ||
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 | |
b32b8144 FG |
148 | : ( |
149 | boost::numeric_cast<fp_type>(m_numerator) * scale() | |
150 | / boost::numeric_cast<fp_type>(m_denominator) | |
151 | ); | |
7c673cae FG |
152 | } |
153 | ||
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 | |
157 | { | |
158 | // e.g. 0/4 or 4/4 or 2/4 | |
159 | return m_numerator >= 0 && m_numerator <= m_denominator; | |
160 | } | |
161 | inline bool in_segment() const | |
162 | { | |
163 | // e.g. 1/4 | |
164 | return m_numerator > 0 && m_numerator < m_denominator; | |
165 | } | |
166 | inline bool on_end() const | |
167 | { | |
168 | // e.g. 0/4 or 4/4 | |
169 | return is_zero() || is_one(); | |
170 | } | |
171 | inline bool left() const | |
172 | { | |
173 | // e.g. -1/4 | |
174 | return m_numerator < 0; | |
175 | } | |
176 | inline bool right() const | |
177 | { | |
178 | // e.g. 5/4 | |
179 | return m_numerator > m_denominator; | |
180 | } | |
181 | ||
182 | inline bool near_end() const | |
183 | { | |
184 | if (left() || right()) | |
185 | { | |
186 | return false; | |
187 | } | |
188 | ||
b32b8144 | 189 | static fp_type const small_part_of_scale = scale() / 100; |
7c673cae FG |
190 | return m_approximation < small_part_of_scale |
191 | || m_approximation > scale() - small_part_of_scale; | |
192 | } | |
193 | ||
194 | inline bool close_to(thistype const& other) const | |
195 | { | |
196 | return geometry::math::abs(m_approximation - other.m_approximation) < 50; | |
197 | } | |
198 | ||
199 | 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 | ||
206 | inline bool operator== (thistype const& other) const | |
207 | { | |
208 | return close_to(other) | |
209 | && detail::segment_ratio::equal<Type>::apply(*this, other); | |
210 | } | |
211 | ||
212 | static inline thistype zero() | |
213 | { | |
214 | static thistype result(0, 1); | |
215 | return result; | |
216 | } | |
217 | ||
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) | |
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 : | |
b32b8144 FG |
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; | |
7c673cae FG |
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 | ||
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 |