]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2013 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
20effc67 TL |
5 | // This file was modified by Oracle on 2016-2020. |
6 | // Modifications copyright (c) 2016-2020 Oracle and/or its affiliates. | |
7c673cae FG |
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 | ||
20effc67 TL |
16 | #include <type_traits> |
17 | ||
7c673cae FG |
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, | |
20effc67 | 35 | bool IsIntegral = std::is_integral<Type>::type::value |
7c673cae FG |
36 | > |
37 | struct less {}; | |
38 | ||
39 | template <typename Type> | |
40 | struct less<Type, true> | |
41 | { | |
42 | template <typename Ratio> | |
43 | 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> | |
54 | 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); | |
92f5a8d4 TL |
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; | |
7c673cae FG |
62 | } |
63 | }; | |
64 | ||
65 | template | |
66 | < | |
67 | typename Type, | |
20effc67 | 68 | bool IsIntegral = std::is_integral<Type>::type::value |
7c673cae FG |
69 | > |
70 | struct equal {}; | |
71 | ||
72 | template <typename Type> | |
73 | struct equal<Type, true> | |
74 | { | |
75 | template <typename Ratio> | |
76 | 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> | |
87 | 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); | |
92f5a8d4 TL |
91 | Type const a = lhs.numerator() / lhs.denominator(); |
92 | Type const b = rhs.numerator() / rhs.denominator(); | |
93 | return geometry::math::equals(a, b); | |
7c673cae FG |
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 | ||
115 | inline segment_ratio() | |
116 | : m_numerator(0) | |
117 | , m_denominator(1) | |
118 | , m_approximation(0) | |
119 | {} | |
120 | ||
121 | inline segment_ratio(const Type& nominator, const Type& denominator) | |
122 | : m_numerator(nominator) | |
123 | , m_denominator(denominator) | |
124 | { | |
125 | initialize(); | |
126 | } | |
127 | ||
128 | inline Type const& numerator() const { return m_numerator; } | |
129 | inline Type const& denominator() const { return m_denominator; } | |
130 | ||
131 | inline void assign(const Type& nominator, const Type& denominator) | |
132 | { | |
133 | m_numerator = nominator; | |
134 | m_denominator = denominator; | |
135 | initialize(); | |
136 | } | |
137 | ||
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 | |
b32b8144 FG |
150 | : ( |
151 | boost::numeric_cast<fp_type>(m_numerator) * scale() | |
152 | / boost::numeric_cast<fp_type>(m_denominator) | |
153 | ); | |
7c673cae FG |
154 | } |
155 | ||
156 | inline bool is_zero() const { return math::equals(m_numerator, 0); } | |
157 | inline bool is_one() const { return math::equals(m_numerator, m_denominator); } | |
158 | 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 | } | |
163 | inline bool in_segment() const | |
164 | { | |
165 | // e.g. 1/4 | |
166 | return m_numerator > 0 && m_numerator < m_denominator; | |
167 | } | |
168 | inline bool on_end() const | |
169 | { | |
170 | // e.g. 0/4 or 4/4 | |
171 | return is_zero() || is_one(); | |
172 | } | |
173 | inline bool left() const | |
174 | { | |
175 | // e.g. -1/4 | |
176 | return m_numerator < 0; | |
177 | } | |
178 | inline bool right() const | |
179 | { | |
180 | // e.g. 5/4 | |
181 | return m_numerator > m_denominator; | |
182 | } | |
183 | ||
184 | inline bool near_end() const | |
185 | { | |
186 | if (left() || right()) | |
187 | { | |
188 | return false; | |
189 | } | |
190 | ||
b32b8144 | 191 | static fp_type const small_part_of_scale = scale() / 100; |
7c673cae FG |
192 | return m_approximation < small_part_of_scale |
193 | || m_approximation > scale() - small_part_of_scale; | |
194 | } | |
195 | ||
196 | inline bool close_to(thistype const& other) const | |
197 | { | |
198 | return geometry::math::abs(m_approximation - other.m_approximation) < 50; | |
199 | } | |
200 | ||
201 | 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 | ||
208 | inline bool operator== (thistype const& other) const | |
209 | { | |
210 | return close_to(other) | |
211 | && detail::segment_ratio::equal<Type>::apply(*this, other); | |
212 | } | |
213 | ||
214 | static inline thistype zero() | |
215 | { | |
216 | static thistype result(0, 1); | |
217 | return result; | |
218 | } | |
219 | ||
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) | |
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 : | |
b32b8144 FG |
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 | ||
20effc67 TL |
244 | // TODO: What with user-defined numeric types? |
245 | // Shouldn't here is_integral be checked? | |
246 | typedef std::conditional_t | |
b32b8144 | 247 | < |
20effc67 TL |
248 | std::is_floating_point<Type>::value, Type, double |
249 | > fp_type; | |
7c673cae FG |
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 | ||
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 |