24470

Committed 13 May 2025 08:17PM UTC coverage: 94.253% (-0.03%) from 94.286%

Build # 24470

Build Type

push

circleci

Committed by

barendgehrels

Commit Message

fix: consider clusters in turn_in_piece_visitor

Run Details

39085 of 41468 relevant lines covered (94.25%)

1274129.49 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

92.08

include/boost/geometry/policies/robustness/segment_ratio.hpp

// Boost.Geometry (aka GGL, Generic Geometry Library)

// Copyright (c) 2013 Barend Gehrels, Amsterdam, the Netherlands.

// This file was modified by Oracle on 2016-2024.
// Modifications copyright (c) 2016-2024 Oracle and/or its affiliates.
// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle

// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP
#define BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP

#include <type_traits>

#include <boost/config.hpp>
#include <boost/rational.hpp>

#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/core/coordinate_promotion.hpp>
#include <boost/geometry/util/math.hpp>
#include <boost/geometry/util/numeric_cast.hpp>


namespace boost { namespace geometry
{


namespace detail { namespace segment_ratio
{

template
<
    typename Type,
    bool IsIntegral = std::is_integral<Type>::type::value
>
struct less {};

template <typename Type>
struct less<Type, true>
{
    template <typename Ratio>
    static inline bool apply(Ratio const& lhs, Ratio const& rhs)
    {
        return boost::rational<Type>(lhs.numerator(), lhs.denominator())
             < boost::rational<Type>(rhs.numerator(), rhs.denominator());
    }
};

template <typename Type>
struct less<Type, false>
{
    template <typename Ratio>
    static inline bool apply(Ratio const& lhs, Ratio const& rhs)
    {
        BOOST_GEOMETRY_ASSERT(lhs.denominator() != Type(0));
        BOOST_GEOMETRY_ASSERT(rhs.denominator() != Type(0));
        Type const a = lhs.numerator() / lhs.denominator();
        Type const b = rhs.numerator() / rhs.denominator();
        return ! geometry::math::equals(a, b)
            && a < b;
    }
};

template
<
    typename Type,
    bool IsIntegral = std::is_integral<Type>::type::value
>
struct equal {};

template <typename Type>
struct equal<Type, true>
{
    template <typename Ratio>
    static inline bool apply(Ratio const& lhs, Ratio const& rhs)
    {
        return boost::rational<Type>(lhs.numerator(), lhs.denominator())
            == boost::rational<Type>(rhs.numerator(), rhs.denominator());
    }
};

template <typename Type>
struct equal<Type, false>
{
    template <typename Ratio>
    static inline bool apply(Ratio const& lhs, Ratio const& rhs)
    {
        BOOST_GEOMETRY_ASSERT(lhs.denominator() != Type(0));
        BOOST_GEOMETRY_ASSERT(rhs.denominator() != Type(0));
        Type const a = lhs.numerator() / lhs.denominator();
        Type const b = rhs.numerator() / rhs.denominator();
        return geometry::math::equals(a, b);
    }
};

template
<
    typename Type,
    bool IsFloatingPoint = std::is_floating_point<Type>::type::value
>
struct possibly_collinear {};

template <typename Type>
struct possibly_collinear<Type, true>
{
    template <typename Ratio, typename Threshold>
    static inline bool apply(Ratio const& ratio, Threshold threshold)
    {
        return std::abs(ratio.denominator()) < threshold;
    }
};

// Any ratio based on non-floating point (or user defined floating point)
// is collinear if the denominator is exactly zero
template <typename Type>
struct possibly_collinear<Type, false>
{
    template <typename Ratio, typename Threshold>
    static inline bool apply(Ratio const& ratio, Threshold)
    {
        static Type const zero = 0;
        return ratio.denominator() == zero;
    }
};

}}

//! Small class to keep a ratio (e.g. 1/4)
//! Main purpose is intersections and checking on 0, 1, and smaller/larger
//! The prototype used Boost.Rational. However, we also want to store FP ratios,
//! (so numerator/denominator both in float)
//! and Boost.Rational starts with GCD which we prefer to avoid if not necessary
//! On a segment means: this ratio is between 0 and 1 (both inclusive)
//!
template <typename Type>
class segment_ratio
{
    // Type used for the approximation (a helper value)
    // and for the edge value (0..1) (a helper function).
    using floating_point_type =
        typename detail::promoted_to_floating_point<Type>::type;

    // Type-alias for the type itself
    using thistype = segment_ratio<Type>;

public:
    using int_type = Type;

    inline segment_ratio()
        : m_numerator(0)
        , m_denominator(1)
        , m_approximation(0)
    {}

    inline segment_ratio(Type const& numerator, Type const& denominator)
        : m_numerator(numerator)
        , m_denominator(denominator)
    {
        initialize();
    }

    segment_ratio(segment_ratio const&) = default;
    segment_ratio& operator=(segment_ratio const&) = default;
    segment_ratio(segment_ratio&&) = default;
    segment_ratio& operator=(segment_ratio&&) = default;

    // These are needed because in intersection strategies ratios are assigned
    // in fractions and if a user passes CalculationType then ratio Type in
    // turns is taken from geometry coordinate_type and the one used in
    // a strategy uses Type selected using CalculationType.
    // See: detail::overlay::intersection_info_base
    // and  policies::relate::segments_intersection_points
    //      in particular segments_collinear() where ratios are assigned.
    template<typename T> friend class segment_ratio;
    template <typename T>
    segment_ratio(segment_ratio<T> const& r)
        : m_numerator(r.m_numerator)
        , m_denominator(r.m_denominator)
    {
        initialize();
    }
    template <typename T>
    segment_ratio& operator=(segment_ratio<T> const& r)
    {
        m_numerator = r.m_numerator;
        m_denominator = r.m_denominator;
        initialize();
        return *this;
    }
    template <typename T>
    segment_ratio(segment_ratio<T> && r)
        : m_numerator(std::move(r.m_numerator))
        , m_denominator(std::move(r.m_denominator))
    {
        initialize();
    }
    template <typename T>
    segment_ratio& operator=(segment_ratio<T> && r)
    {
        m_numerator = std::move(r.m_numerator);
        m_denominator = std::move(r.m_denominator);
        initialize();
        return *this;
    }

    inline Type const& numerator() const { return m_numerator; }
    inline Type const& denominator() const { return m_denominator; }

    inline void assign(Type const& numerator, Type const& denominator)
    {
        m_numerator = numerator;
        m_denominator = denominator;
        initialize();
    }

    inline void initialize()
    {
        // Minimal normalization
        // 1/-4 => -1/4, -1/-4 => 1/4
        if (m_denominator < zero_instance())
        {
            m_numerator = -m_numerator;
            m_denominator = -m_denominator;
        }

        m_approximation =
            m_denominator == zero_instance() ? floating_point_type{0}
            : (
                util::numeric_cast<floating_point_type>(m_numerator) * scale()
                / util::numeric_cast<floating_point_type>(m_denominator)
            );
    }

    inline bool is_zero() const { return math::equals(m_numerator, Type(0)); }
    inline bool is_one() const { return math::equals(m_numerator, m_denominator); }
    inline bool on_segment() const
    {
        // e.g. 0/4 or 4/4 or 2/4
        return m_numerator >= zero_instance() && m_numerator <= m_denominator;
    }
    inline bool in_segment() const
    {
        // e.g. 1/4
        return m_numerator > zero_instance() && m_numerator < m_denominator;
    }
    inline bool on_end() const
    {
        // e.g. 0/4 or 4/4
        return is_zero() || is_one();
    }
    inline bool left() const
    {
        // e.g. -1/4
        return m_numerator < zero_instance();
    }
    inline bool right() const
    {
        // e.g. 5/4
        return m_numerator > m_denominator;
    }

    //! Returns a value between 0.0 and 1.0
    //! 0.0 means: exactly in the middle
    //! 1.0 means: exactly on one of the edges (or even over it)
    inline floating_point_type edge_value() const
    {
        using fp = floating_point_type;
        fp const one{1.0};
        floating_point_type const result
                = fp(2) * geometry::math::abs(fp(0.5) - m_approximation / scale());
        return result > one ? one : result;
    }

    template <typename Threshold>
    inline bool possibly_collinear(Threshold threshold) const
    {
        return detail::segment_ratio::possibly_collinear<Type>::apply(*this, threshold);
    }

    inline bool operator< (thistype const& other) const
    {
        return close_to(other)
            ? detail::segment_ratio::less<Type>::apply(*this, other)
            : m_approximation < other.m_approximation;
    }

    inline bool operator== (thistype const& other) const
    {
        return close_to(other)
            && detail::segment_ratio::equal<Type>::apply(*this, other);
    }

    static inline thistype zero()
    {
        static thistype result(0, 1);
        return result;
    }

    static inline thistype one()
    {
        static thistype result(1, 1);
        return result;
    }

#if defined(BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO)
    friend std::ostream& operator<<(std::ostream &os, segment_ratio const& ratio)
    {
        os << ratio.m_numerator << "/" << ratio.m_denominator
           << " (" << (static_cast<double>(ratio.m_numerator)
                        / static_cast<double>(ratio.m_denominator))
           << ")";
        return os;
    }
#endif

private :

    Type m_numerator;
    Type m_denominator;

    // Contains ratio on scale 0..1000000 (for 0..1)
    // This is an approximation for fast and rough comparisons
    // Boost.Rational is used if the approximations are close.
    // Reason: performance, Boost.Rational does a GCD by default and also the
    // comparisons contain while-loops.
    floating_point_type m_approximation;

    inline bool close_to(thistype const& other) const
    {
        static floating_point_type const threshold{50.0};
        return geometry::math::abs(m_approximation - other.m_approximation)
                < threshold;
    }

    static inline floating_point_type scale()
    {
        static floating_point_type const fp_scale{1000000.0};
        return fp_scale;
    }

    static inline Type zero_instance()
    {
        return 0;
    }
};

template <typename Point>
struct segment_ratio_type
{
    using type = segment_ratio<geometry::coordinate_type_t<Point>>;
};

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP

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-2024.
6	// Modifications copyright (c) 2016-2024 Oracle and/or its affiliates.
7	// Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
8	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9
10	// Use, modification and distribution is subject to the Boost Software License,
11	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12	// http://www.boost.org/LICENSE_1_0.txt)
13
14	#ifndef BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP
15	#define BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP
16
17	#include <type_traits>
18
19	#include <boost/config.hpp>
20	#include <boost/rational.hpp>
21
22	#include <boost/geometry/core/assert.hpp>
23	#include <boost/geometry/core/coordinate_promotion.hpp>
24	#include <boost/geometry/util/math.hpp>
25	#include <boost/geometry/util/numeric_cast.hpp>
26
27
28	namespace boost { namespace geometry
29	{
30
31
32	namespace detail { namespace segment_ratio
33	{
34
35	template
36	<
37	typename Type,
38	bool IsIntegral = std::is_integral<Type>::type::value
39	>
40	struct less {};
41
42	template <typename Type>
43	struct less<Type, true>
44	{
45	template <typename Ratio>
46	static inline bool apply(Ratio const& lhs, Ratio const& rhs)	×
47	{
48	return boost::rational<Type>(lhs.numerator(), lhs.denominator())
49	< boost::rational<Type>(rhs.numerator(), rhs.denominator());	×
50	}
51	};
52
53	template <typename Type>
54	struct less<Type, false>
55	{
56	template <typename Ratio>
57	static inline bool apply(Ratio const& lhs, Ratio const& rhs)	3,251✔
58	{
59	BOOST_GEOMETRY_ASSERT(lhs.denominator() != Type(0));	3,251✔
60	BOOST_GEOMETRY_ASSERT(rhs.denominator() != Type(0));	3,251✔
61	Type const a = lhs.numerator() / lhs.denominator();	3,251✔
62	Type const b = rhs.numerator() / rhs.denominator();	3,251✔
63	return ! geometry::math::equals(a, b)	3,251✔
64	&& a < b;	3,251✔
65	}
66	};
67
68	template
69	<
70	typename Type,
71	bool IsIntegral = std::is_integral<Type>::type::value
72	>
73	struct equal {};
74
75	template <typename Type>
76	struct equal<Type, true>
77	{
78	template <typename Ratio>
79	static inline bool apply(Ratio const& lhs, Ratio const& rhs)	7,548✔
80	{
81	return boost::rational<Type>(lhs.numerator(), lhs.denominator())
82	== boost::rational<Type>(rhs.numerator(), rhs.denominator());	7,548✔
83	}
84	};
85
86	template <typename Type>
87	struct equal<Type, false>
88	{
89	template <typename Ratio>
90	static inline bool apply(Ratio const& lhs, Ratio const& rhs)	301,605✔
91	{
92	BOOST_GEOMETRY_ASSERT(lhs.denominator() != Type(0));	301,605✔
93	BOOST_GEOMETRY_ASSERT(rhs.denominator() != Type(0));	301,605✔
94	Type const a = lhs.numerator() / lhs.denominator();	301,605✔
95	Type const b = rhs.numerator() / rhs.denominator();	301,605✔
96	return geometry::math::equals(a, b);	603,210✔
97	}
98	};
99
100	template
101	<
102	typename Type,
103	bool IsFloatingPoint = std::is_floating_point<Type>::type::value
104	>
105	struct possibly_collinear {};
106
107	template <typename Type>
108	struct possibly_collinear<Type, true>
109	{
110	template <typename Ratio, typename Threshold>
111	static inline bool apply(Ratio const& ratio, Threshold threshold)	202,642✔
112	{
113	return std::abs(ratio.denominator()) < threshold;	202,642✔
114	}
115	};
116
117	// Any ratio based on non-floating point (or user defined floating point)
118	// is collinear if the denominator is exactly zero
119	template <typename Type>
120	struct possibly_collinear<Type, false>
121	{
122	template <typename Ratio, typename Threshold>
123	static inline bool apply(Ratio const& ratio, Threshold)	4,704✔
124	{
125	static Type const zero = 0;	42✔
126	return ratio.denominator() == zero;	4,704✔
127	}
128	};
129
130	}}
131
132	//! Small class to keep a ratio (e.g. 1/4)
133	//! Main purpose is intersections and checking on 0, 1, and smaller/larger
134	//! The prototype used Boost.Rational. However, we also want to store FP ratios,
135	//! (so numerator/denominator both in float)
136	//! and Boost.Rational starts with GCD which we prefer to avoid if not necessary
137	//! On a segment means: this ratio is between 0 and 1 (both inclusive)
138	//!
139	template <typename Type>
140	class segment_ratio	484✔
141	{
142	// Type used for the approximation (a helper value)
143	// and for the edge value (0..1) (a helper function).
144	using floating_point_type =
145	typename detail::promoted_to_floating_point<Type>::type;
146
147	// Type-alias for the type itself
148	using thistype = segment_ratio<Type>;
149
150	public:
151	using int_type = Type;
152
153	inline segment_ratio()	17,340,182✔
154	: m_numerator(0)	5,296✔
155	, m_denominator(1)	6,920✔
156	, m_approximation(0)	17,340,182✔
157	{}	17,340,182✔
158
159	inline segment_ratio(Type const& numerator, Type const& denominator)	901,818✔
160	: m_numerator(numerator)
161	, m_denominator(denominator)	901,818✔
162	{
163	initialize();	901,818✔
164	}	901,818✔
165
166	segment_ratio(segment_ratio const&) = default;	2,038✔
167	segment_ratio& operator=(segment_ratio const&) = default;
168	segment_ratio(segment_ratio&&) = default;	1,552✔
169	segment_ratio& operator=(segment_ratio&&) = default;
170
171	// These are needed because in intersection strategies ratios are assigned
172	// in fractions and if a user passes CalculationType then ratio Type in
173	// turns is taken from geometry coordinate_type and the one used in
174	// a strategy uses Type selected using CalculationType.
175	// See: detail::overlay::intersection_info_base
176	// and policies::relate::segments_intersection_points
177	// in particular segments_collinear() where ratios are assigned.
178	template<typename T> friend class segment_ratio;
179	template <typename T>
180	segment_ratio(segment_ratio<T> const& r)	14✔
181	: m_numerator(r.m_numerator)	14✔
182	, m_denominator(r.m_denominator)	14✔
183	{
184	initialize();	14✔
185	}	14✔
186	template <typename T>
187	segment_ratio& operator=(segment_ratio<T> const& r)	52✔
188	{
189	m_numerator = r.m_numerator;	52✔
190	m_denominator = r.m_denominator;	52✔
191	initialize();	52✔
192	return *this;	52✔
193	}
194	template <typename T>
195	segment_ratio(segment_ratio<T> && r)	14✔
196	: m_numerator(std::move(r.m_numerator))	14✔
197	, m_denominator(std::move(r.m_denominator))	14✔
198	{
199	initialize();	14✔
200	}	14✔
201	template <typename T>
202	segment_ratio& operator=(segment_ratio<T> && r)
203	{
204	m_numerator = std::move(r.m_numerator);
205	m_denominator = std::move(r.m_denominator);
206	initialize();
207	return *this;
208	}
209
210	inline Type const& numerator() const { return m_numerator; }	801,668✔
211	inline Type const& denominator() const { return m_denominator; }	1,797,106✔
212
213	inline void assign(Type const& numerator, Type const& denominator)	1,638,364✔
214	{
215	m_numerator = numerator;	1,638,364✔
216	m_denominator = denominator;	1,638,364✔
217	initialize();	1,638,364✔
218	}	1,638,364✔
219
220	inline void initialize()	2,540,262✔
221	{
222	// Minimal normalization
223	// 1/-4 => -1/4, -1/-4 => 1/4
224	if (m_denominator < zero_instance())	2,540,262✔
225	{
226	m_numerator = -m_numerator;	840,433✔
227	m_denominator = -m_denominator;	840,433✔
228	}
229
230	m_approximation =	2,540,262✔
231	m_denominator == zero_instance() ? floating_point_type{0}	2,540,560✔
232	: (
233	util::numeric_cast<floating_point_type>(m_numerator) * scale()	2,540,260✔
234	/ util::numeric_cast<floating_point_type>(m_denominator)	2,540,260✔
235	);
236	}	2,540,262✔
237
238	inline bool is_zero() const { return math::equals(m_numerator, Type(0)); }	7,132✔
239	inline bool is_one() const { return math::equals(m_numerator, m_denominator); }
240	inline bool on_segment() const	153,313✔
241	{
242	// e.g. 0/4 or 4/4 or 2/4
243	return m_numerator >= zero_instance() && m_numerator <= m_denominator;	153,313✔
244	}
245	inline bool in_segment() const
246	{
247	// e.g. 1/4
248	return m_numerator > zero_instance() && m_numerator < m_denominator;
249	}
250	inline bool on_end() const
251	{
252	// e.g. 0/4 or 4/4
253	return is_zero() \|\| is_one();
254	}
255	inline bool left() const
256	{
257	// e.g. -1/4
258	return m_numerator < zero_instance();
259	}
260	inline bool right() const
261	{
262	// e.g. 5/4
263	return m_numerator > m_denominator;
264	}
265
266	//! Returns a value between 0.0 and 1.0
267	//! 0.0 means: exactly in the middle
268	//! 1.0 means: exactly on one of the edges (or even over it)
269	inline floating_point_type edge_value() const	353,720✔
270	{
271	using fp = floating_point_type;
272	fp const one{1.0};	353,720✔
273	floating_point_type const result	353,780✔
274	= fp(2) * geometry::math::abs(fp(0.5) - m_approximation / scale());	353,750✔
275	return result > one ? one : result;	353,750✔
276	}
277
278	template <typename Threshold>
279	inline bool possibly_collinear(Threshold threshold) const	207,346✔
280	{
281	return detail::segment_ratio::possibly_collinear<Type>::apply(*this, threshold);	207,346✔
282	}
283
284	inline bool operator< (thistype const& other) const	1,124,837✔
285	{
286	return close_to(other)
287	? detail::segment_ratio::less<Type>::apply(*this, other)	1,124,837✔
288	: m_approximation < other.m_approximation;	1,124,837✔
289	}
290
291	inline bool operator== (thistype const& other) const	1,246,860✔
292	{
293	return close_to(other)
294	&& detail::segment_ratio::equal<Type>::apply(*this, other);	1,246,860✔
295	}
296
297	static inline thistype zero()	229,918✔
298	{
299	static thistype result(0, 1);	229,918✔
300	return result;	229,918✔
301	}
302
303	static inline thistype one()	227,119✔
304	{
305	static thistype result(1, 1);	227,119✔
306	return result;	227,119✔
307	}
308
309	#if defined(BOOST_GEOMETRY_DEFINE_STREAM_OPERATOR_SEGMENT_RATIO)
310	friend std::ostream& operator<<(std::ostream &os, segment_ratio const& ratio)	×
311	{
312	os << ratio.m_numerator << "/" << ratio.m_denominator	×
313	<< " (" << (static_cast<double>(ratio.m_numerator)	×
314	/ static_cast<double>(ratio.m_denominator))	×
315	<< ")";	×
316	return os;	×
317	}
318	#endif
319
320	private :
321
322	Type m_numerator;
323	Type m_denominator;
324
325	// Contains ratio on scale 0..1000000 (for 0..1)
326	// This is an approximation for fast and rough comparisons
327	// Boost.Rational is used if the approximations are close.
328	// Reason: performance, Boost.Rational does a GCD by default and also the
329	// comparisons contain while-loops.
330	floating_point_type m_approximation;
331
332	inline bool close_to(thistype const& other) const	2,371,701✔
333	{
334	static floating_point_type const threshold{50.0};	33✔
335	return geometry::math::abs(m_approximation - other.m_approximation)	2,371,701✔
336	< threshold;	2,371,701✔
337	}
338
339	static inline floating_point_type scale()	2,893,980✔
340	{
341	static floating_point_type const fp_scale{1000000.0};	139✔
342	return fp_scale;	2,893,980✔
343	}
344
345	static inline Type zero_instance()	5,233,837✔
346	{
347	return 0;	5,233,837✔
348	}
349	};
350
351	template <typename Point>
352	struct segment_ratio_type
353	{
354	using type = segment_ratio<geometry::coordinate_type_t<Point>>;
355	};
356
357	}} // namespace boost::geometry
358
359	#endif // BOOST_GEOMETRY_POLICIES_ROBUSTNESS_SEGMENT_RATIO_HPP

boostorg / geometry / 24470

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous