20212

Committed 28 Jul 2023 09:16AM UTC coverage: 94.211% (-0.2%) from 94.458%

Build # 20212

Build Type

push

circle-ci

Committed by

vissarion

Commit Message

Merge branch 'develop'

Run Details

39303 of 41718 relevant lines covered (94.21%)

1319371.48 hits per line

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

96.61

include/boost/geometry/algorithms/detail/direction_code.hpp

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

// Copyright (c) 2015-2020 Barend Gehrels, Amsterdam, the Netherlands.

// This file was modified by Oracle on 2015-2020.
// Modifications copyright (c) 2015-2020 Oracle and/or its affiliates.

// Contributed and/or modified by Menelaos Karavelas, 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_ALGORITHMS_DETAIL_DIRECTION_CODE_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIRECTION_CODE_HPP


#include <type_traits>

#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/static_assert.hpp>
#include <boost/geometry/arithmetic/infinite_line_functions.hpp>
#include <boost/geometry/algorithms/detail/make/make.hpp>
#include <boost/geometry/util/math.hpp>
#include <boost/geometry/util/select_coordinate_type.hpp>
#include <boost/geometry/util/normalize_spheroidal_coordinates.hpp>


namespace boost { namespace geometry
{


#ifndef DOXYGEN_NO_DETAIL
namespace detail
{

template <typename CSTag>
struct direction_code_impl
{
    BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
        "Not implemented for this coordinate system.",
        CSTag);
};

template <>
struct direction_code_impl<cartesian_tag>
{
    template <typename PointSegmentA, typename PointSegmentB, typename Point2>
    static inline int apply(PointSegmentA const& segment_a, PointSegmentB const& segment_b,
                            Point2 const& point)
    {
        using calc_t = typename geometry::select_coordinate_type
            <
                PointSegmentA, PointSegmentB, Point2
            >::type;

        using line_type = model::infinite_line<calc_t>;

        // Situation and construction of perpendicular line
        //
        //     P1     a--------------->b   P2
        //                             |
        //                             |
        //                             v
        //
        // P1 is located right of the (directional) perpendicular line
        // and therefore gets a negative side_value, and returns -1.
        // P2 is to the left of the perpendicular line and returns 1.
        // If the specified point is located on top of b, it returns 0.

        line_type const line
            = detail::make::make_perpendicular_line<calc_t>(segment_a,
                segment_b, segment_b);

        if (arithmetic::is_degenerate(line))
        {
            return 0;
        }

        calc_t const sv = arithmetic::side_value(line, point);
        static calc_t const zero = 0;
        return sv == zero ? 0 : sv > zero ? 1 : -1;
    }
};

template <>
struct direction_code_impl<spherical_equatorial_tag>
{
    template <typename PointSegmentA, typename PointSegmentB, typename Point2>
    static inline int apply(PointSegmentA const& segment_a, PointSegmentB const& segment_b,
                            Point2 const& p)
    {
        {
            using units_sa_t =  typename cs_angular_units<PointSegmentA>::type;
            using units_sb_t =  typename cs_angular_units<PointSegmentB>::type;
            using units_p_t = typename cs_angular_units<Point2>::type;
            BOOST_GEOMETRY_STATIC_ASSERT(
                (std::is_same<units_sa_t, units_sb_t>::value),
                "Not implemented for different units.",
                units_sa_t, units_sb_t);
            BOOST_GEOMETRY_STATIC_ASSERT(
                (std::is_same<units_sa_t, units_p_t>::value),
                "Not implemented for different units.",
                units_sa_t, units_p_t);
        }

        using coor_sa_t = typename coordinate_type<PointSegmentA>::type;
        using coor_sb_t = typename coordinate_type<PointSegmentB>::type;
        using coor_p_t = typename coordinate_type<Point2>::type;

        // Declare unit type (equal for all types) and calc type (coerced to most precise)
        using units_t = typename cs_angular_units<Point2>::type;
        using calc_t = typename geometry::select_coordinate_type
            <
                PointSegmentA, PointSegmentB, Point2
            >::type;
        using constants_sa_t = math::detail::constants_on_spheroid<coor_sa_t, units_t>;
        using constants_sb_t = math::detail::constants_on_spheroid<coor_sb_t, units_t>;
        using constants_p_t = math::detail::constants_on_spheroid<coor_p_t, units_t>;

        static coor_sa_t const pi_half_sa = constants_sa_t::max_latitude();
        static coor_sb_t const pi_half_sb = constants_sb_t::max_latitude();
        static coor_p_t const pi_half_p = constants_p_t::max_latitude();
        static calc_t const c0 = 0;

        coor_sa_t const a0 = geometry::get<0>(segment_a);
        coor_sa_t const a1 = geometry::get<1>(segment_a);
        coor_sb_t const b0 = geometry::get<0>(segment_b);
        coor_sb_t const b1 = geometry::get<1>(segment_b);
        coor_p_t const p0 = geometry::get<0>(p);
        coor_p_t const p1 = geometry::get<1>(p);

        if ( (math::equals(b0, a0) && math::equals(b1, a1))
          || (math::equals(b0, p0) && math::equals(b1, p1)) )
        {
            return 0;
        }

        bool const is_a_pole = math::equals(pi_half_sa, math::abs(a1));
        bool const is_b_pole = math::equals(pi_half_sb, math::abs(b1));
        bool const is_p_pole = math::equals(pi_half_p, math::abs(p1));

        if ( is_b_pole && ((is_a_pole && math::sign(b1) == math::sign(a1))
                        || (is_p_pole && math::sign(b1) == math::sign(p1))) )
        {
            return 0;
        }

        // NOTE: as opposed to the implementation for cartesian CS
        // here point b is the origin

        calc_t const dlon1 = math::longitude_distance_signed<units_t, calc_t>(b0, a0);
        calc_t const dlon2 = math::longitude_distance_signed<units_t, calc_t>(b0, p0);

        bool is_antilon1 = false, is_antilon2 = false;
        calc_t const dlat1 = latitude_distance_signed<units_t, calc_t>(b1, a1, dlon1, is_antilon1);
        calc_t const dlat2 = latitude_distance_signed<units_t, calc_t>(b1, p1, dlon2, is_antilon2);

        calc_t const mx = is_a_pole || is_b_pole || is_p_pole
            ? c0
            : (std::min)(is_antilon1 ? c0 : math::abs(dlon1),
                         is_antilon2 ? c0 : math::abs(dlon2));
        calc_t const my = (std::min)(math::abs(dlat1),
                                     math::abs(dlat2));

        int s1 = 0, s2 = 0;
        if (mx >= my)
        {
            s1 = dlon1 > 0 ? 1 : -1;
            s2 = dlon2 > 0 ? 1 : -1;
        }
        else
        {
            s1 = dlat1 > 0 ? 1 : -1;
            s2 = dlat2 > 0 ? 1 : -1;
        }

        return s1 == s2 ? -1 : 1;
    }

    template <typename Units, typename T>
    static inline T latitude_distance_signed(T const& lat1, T const& lat2, T const& lon_ds, bool & is_antilon)
    {
        using constants = math::detail::constants_on_spheroid<T, Units>;
        static T const pi = constants::half_period();
        static T const c0 = 0;

        T res = lat2 - lat1;

        is_antilon = math::equals(math::abs(lon_ds), pi);
        if (is_antilon)
        {
            res = lat2 + lat1;
            if (res >= c0)
                res = pi - res;
            else
                res = -pi - res;
        }

        return res;
    }
};

template <>
struct direction_code_impl<spherical_polar_tag>
{
    template <typename PointSegmentA, typename PointSegmentB, typename Point2>
    static inline int apply(PointSegmentA segment_a, PointSegmentB segment_b,
                            Point2 p)
    {
        using constants_sa_t = math::detail::constants_on_spheroid
            <
                typename coordinate_type<PointSegmentA>::type,
                typename cs_angular_units<PointSegmentA>::type
            >;
        using constants_p_t = math::detail::constants_on_spheroid
            <
                typename coordinate_type<Point2>::type,
                typename cs_angular_units<Point2>::type
            >;

        geometry::set<1>(segment_a,
            constants_sa_t::max_latitude() - geometry::get<1>(segment_a));
        geometry::set<1>(segment_b,
            constants_sa_t::max_latitude() - geometry::get<1>(segment_b));
        geometry::set<1>(p,
            constants_p_t::max_latitude() - geometry::get<1>(p));

        return direction_code_impl
                <
                    spherical_equatorial_tag
                >::apply(segment_a, segment_b, p);
    }
};

// if spherical_tag is passed then pick cs_tag based on PointSegmentA type
// with spherical_equatorial_tag as the default
template <>
struct direction_code_impl<spherical_tag>
{
    template <typename PointSegmentA, typename PointSegmentB, typename Point2>
    static inline int apply(PointSegmentA segment_a, PointSegmentB segment_b,
                            Point2 p)
    {
        return direction_code_impl
            <
                std::conditional_t
                    <
                        std::is_same
                            <
                                typename geometry::cs_tag<PointSegmentA>::type,
                                spherical_polar_tag
                            >::value,
                        spherical_polar_tag,
                        spherical_equatorial_tag
                    >
            >::apply(segment_a, segment_b, p);
    }
};

template <>
struct direction_code_impl<geographic_tag>
    : direction_code_impl<spherical_equatorial_tag>
{};

// Gives sense of direction for point p, collinear w.r.t. segment (a,b)
// Returns -1 if p goes backward w.r.t (a,b), so goes from b in direction of a
// Returns 1 if p goes forward, so extends (a,b)
// Returns 0 if p is equal with b, or if (a,b) is degenerate
// Note that it does not do any collinearity test, that should be done before
// In some cases the "segment" consists of different source points, and therefore
// their types might differ.
template <typename CSTag, typename PointSegmentA, typename PointSegmentB, typename Point2>
inline int direction_code(PointSegmentA const& segment_a, PointSegmentB const& segment_b,
                          Point2 const& p)
{
    return direction_code_impl<CSTag>::apply(segment_a, segment_b, p);
}


} // namespace detail
#endif //DOXYGEN_NO_DETAIL


}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIRECTION_CODE_HPP

1	// Boost.Geometry (aka GGL, Generic Geometry Library)
2
3	// Copyright (c) 2015-2020 Barend Gehrels, Amsterdam, the Netherlands.
4
5	// This file was modified by Oracle on 2015-2020.
6	// Modifications copyright (c) 2015-2020 Oracle and/or its affiliates.
7
8	// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
9	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10
11	// Use, modification and distribution is subject to the Boost Software License,
12	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13	// http://www.boost.org/LICENSE_1_0.txt)
14
15	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIRECTION_CODE_HPP
16	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIRECTION_CODE_HPP
17
18
19	#include <type_traits>
20
21	#include <boost/geometry/core/access.hpp>
22	#include <boost/geometry/core/static_assert.hpp>
23	#include <boost/geometry/arithmetic/infinite_line_functions.hpp>
24	#include <boost/geometry/algorithms/detail/make/make.hpp>
25	#include <boost/geometry/util/math.hpp>
26	#include <boost/geometry/util/select_coordinate_type.hpp>
27	#include <boost/geometry/util/normalize_spheroidal_coordinates.hpp>
28
29
30	namespace boost { namespace geometry
31	{
32
33
34	#ifndef DOXYGEN_NO_DETAIL
35	namespace detail
36	{
37
38	template <typename CSTag>
39	struct direction_code_impl
40	{
41	BOOST_GEOMETRY_STATIC_ASSERT_FALSE(
42	"Not implemented for this coordinate system.",
43	CSTag);
44	};
45
46	template <>
47	struct direction_code_impl<cartesian_tag>
48	{
49	template <typename PointSegmentA, typename PointSegmentB, typename Point2>
50	static inline int apply(PointSegmentA const& segment_a, PointSegmentB const& segment_b,	588,963✔
51	Point2 const& point)
52	{
53	using calc_t = typename geometry::select_coordinate_type
54	<
55	PointSegmentA, PointSegmentB, Point2
56	>::type;
57
58	using line_type = model::infinite_line<calc_t>;
59
60	// Situation and construction of perpendicular line
61	//
62	// P1 a--------------->b P2
63	// \|
64	// \|
65	// v
66	//
67	// P1 is located right of the (directional) perpendicular line
68	// and therefore gets a negative side_value, and returns -1.
69	// P2 is to the left of the perpendicular line and returns 1.
70	// If the specified point is located on top of b, it returns 0.
71
72	line_type const line	37✔
73	= detail::make::make_perpendicular_line<calc_t>(segment_a,	588,932✔
74	segment_b, segment_b);
75
76	if (arithmetic::is_degenerate(line))	588,963✔
77	{
78	return 0;	8✔
79	}
80
81	calc_t const sv = arithmetic::side_value(line, point);	588,955✔
82	static calc_t const zero = 0;	25✔
83	return sv == zero ? 0 : sv > zero ? 1 : -1;	588,955✔
84	}
85	};
86
87	template <>
88	struct direction_code_impl<spherical_equatorial_tag>
89	{
90	template <typename PointSegmentA, typename PointSegmentB, typename Point2>
91	static inline int apply(PointSegmentA const& segment_a, PointSegmentB const& segment_b,	7,605✔
92	Point2 const& p)
93	{
94	{
95	using units_sa_t = typename cs_angular_units<PointSegmentA>::type;
96	using units_sb_t = typename cs_angular_units<PointSegmentB>::type;
97	using units_p_t = typename cs_angular_units<Point2>::type;
98	BOOST_GEOMETRY_STATIC_ASSERT(
99	(std::is_same<units_sa_t, units_sb_t>::value),
100	"Not implemented for different units.",
101	units_sa_t, units_sb_t);
102	BOOST_GEOMETRY_STATIC_ASSERT(
103	(std::is_same<units_sa_t, units_p_t>::value),
104	"Not implemented for different units.",
105	units_sa_t, units_p_t);
106	}
107
108	using coor_sa_t = typename coordinate_type<PointSegmentA>::type;
109	using coor_sb_t = typename coordinate_type<PointSegmentB>::type;
110	using coor_p_t = typename coordinate_type<Point2>::type;
111
112	// Declare unit type (equal for all types) and calc type (coerced to most precise)
113	using units_t = typename cs_angular_units<Point2>::type;
114	using calc_t = typename geometry::select_coordinate_type
115	<
116	PointSegmentA, PointSegmentB, Point2
117	>::type;
118	using constants_sa_t = math::detail::constants_on_spheroid<coor_sa_t, units_t>;
119	using constants_sb_t = math::detail::constants_on_spheroid<coor_sb_t, units_t>;
120	using constants_p_t = math::detail::constants_on_spheroid<coor_p_t, units_t>;
121
122	static coor_sa_t const pi_half_sa = constants_sa_t::max_latitude();	7,605✔
123	static coor_sb_t const pi_half_sb = constants_sb_t::max_latitude();	7,605✔
124	static coor_p_t const pi_half_p = constants_p_t::max_latitude();	7,605✔
125	static calc_t const c0 = 0;
126
127	coor_sa_t const a0 = geometry::get<0>(segment_a);	7,605✔
128	coor_sa_t const a1 = geometry::get<1>(segment_a);	7,605✔
129	coor_sb_t const b0 = geometry::get<0>(segment_b);	7,605✔
130	coor_sb_t const b1 = geometry::get<1>(segment_b);	7,605✔
131	coor_p_t const p0 = geometry::get<0>(p);	7,605✔
132	coor_p_t const p1 = geometry::get<1>(p);	7,605✔
133
134	if ( (math::equals(b0, a0) && math::equals(b1, a1))	7,856✔
135	\|\| (math::equals(b0, p0) && math::equals(b1, p1)) )	7,856✔
136	{
137	return 0;	2,474✔
138	}
139
140	bool const is_a_pole = math::equals(pi_half_sa, math::abs(a1));	5,131✔
141	bool const is_b_pole = math::equals(pi_half_sb, math::abs(b1));	5,131✔
142	bool const is_p_pole = math::equals(pi_half_p, math::abs(p1));	5,131✔
143
144	if ( is_b_pole && ((is_a_pole && math::sign(b1) == math::sign(a1))	5,131✔
145	\|\| (is_p_pole && math::sign(b1) == math::sign(p1))) )	×
146	{
147	return 0;	×
148	}
149
150	// NOTE: as opposed to the implementation for cartesian CS
151	// here point b is the origin
152
153	calc_t const dlon1 = math::longitude_distance_signed<units_t, calc_t>(b0, a0);	5,131✔
154	calc_t const dlon2 = math::longitude_distance_signed<units_t, calc_t>(b0, p0);	5,131✔
155
156	bool is_antilon1 = false, is_antilon2 = false;	5,131✔
157	calc_t const dlat1 = latitude_distance_signed<units_t, calc_t>(b1, a1, dlon1, is_antilon1);	5,131✔
158	calc_t const dlat2 = latitude_distance_signed<units_t, calc_t>(b1, p1, dlon2, is_antilon2);	5,131✔
159
160	calc_t const mx = is_a_pole \|\| is_b_pole \|\| is_p_pole	5,131✔
161	? c0	10,262✔
162	: (std::min)(is_antilon1 ? c0 : math::abs(dlon1),	5,125✔
163	is_antilon2 ? c0 : math::abs(dlon2));	5,125✔
164	calc_t const my = (std::min)(math::abs(dlat1),	5,131✔
165	math::abs(dlat2));	5,131✔
166
167	int s1 = 0, s2 = 0;	5,131✔
168	if (mx >= my)	5,131✔
169	{
170	s1 = dlon1 > 0 ? 1 : -1;	3,814✔
171	s2 = dlon2 > 0 ? 1 : -1;	3,814✔
172	}
173	else
174	{
175	s1 = dlat1 > 0 ? 1 : -1;	1,317✔
176	s2 = dlat2 > 0 ? 1 : -1;	1,317✔
177	}
178
179	return s1 == s2 ? -1 : 1;	5,131✔
180	}
181
182	template <typename Units, typename T>
183	static inline T latitude_distance_signed(T const& lat1, T const& lat2, T const& lon_ds, bool & is_antilon)	10,262✔
184	{
185	using constants = math::detail::constants_on_spheroid<T, Units>;
186	static T const pi = constants::half_period();	10,262✔
187	static T const c0 = 0;
188
189	T res = lat2 - lat1;	10,262✔
190
191	is_antilon = math::equals(math::abs(lon_ds), pi);	10,262✔
192	if (is_antilon)	10,262✔
193	{
194	res = lat2 + lat1;	6✔
195	if (res >= c0)	6✔
196	res = pi - res;	4✔
197	else
198	res = -pi - res;	2✔
199	}
200
201	return res;	10,262✔
202	}
203	};
204
205	template <>
206	struct direction_code_impl<spherical_polar_tag>
207	{
208	template <typename PointSegmentA, typename PointSegmentB, typename Point2>
209	static inline int apply(PointSegmentA segment_a, PointSegmentB segment_b,
210	Point2 p)
211	{
212	using constants_sa_t = math::detail::constants_on_spheroid
213	<
214	typename coordinate_type<PointSegmentA>::type,
215	typename cs_angular_units<PointSegmentA>::type
216	>;
217	using constants_p_t = math::detail::constants_on_spheroid
218	<
219	typename coordinate_type<Point2>::type,
220	typename cs_angular_units<Point2>::type
221	>;
222
223	geometry::set<1>(segment_a,
224	constants_sa_t::max_latitude() - geometry::get<1>(segment_a));
225	geometry::set<1>(segment_b,
226	constants_sa_t::max_latitude() - geometry::get<1>(segment_b));
227	geometry::set<1>(p,
228	constants_p_t::max_latitude() - geometry::get<1>(p));
229
230	return direction_code_impl
231	<
232	spherical_equatorial_tag
233	>::apply(segment_a, segment_b, p);
234	}
235	};
236
237	// if spherical_tag is passed then pick cs_tag based on PointSegmentA type
238	// with spherical_equatorial_tag as the default
239	template <>
240	struct direction_code_impl<spherical_tag>
241	{
242	template <typename PointSegmentA, typename PointSegmentB, typename Point2>
243	static inline int apply(PointSegmentA segment_a, PointSegmentB segment_b,	1,561✔
244	Point2 p)
245	{
246	return direction_code_impl
247	<
248	std::conditional_t
249	<
250	std::is_same
251	<
252	typename geometry::cs_tag<PointSegmentA>::type,
253	spherical_polar_tag
254	>::value,
255	spherical_polar_tag,
256	spherical_equatorial_tag
257	>
258	>::apply(segment_a, segment_b, p);	1,561✔
259	}
260	};
261
262	template <>
263	struct direction_code_impl<geographic_tag>
264	: direction_code_impl<spherical_equatorial_tag>
265	{};
266
267	// Gives sense of direction for point p, collinear w.r.t. segment (a,b)
268	// Returns -1 if p goes backward w.r.t (a,b), so goes from b in direction of a
269	// Returns 1 if p goes forward, so extends (a,b)
270	// Returns 0 if p is equal with b, or if (a,b) is degenerate
271	// Note that it does not do any collinearity test, that should be done before
272	// In some cases the "segment" consists of different source points, and therefore
273	// their types might differ.
274	template <typename CSTag, typename PointSegmentA, typename PointSegmentB, typename Point2>
275	inline int direction_code(PointSegmentA const& segment_a, PointSegmentB const& segment_b,	596,568✔
276	Point2 const& p)
277	{
278	return direction_code_impl<CSTag>::apply(segment_a, segment_b, p);	596,568✔
279	}
280
281
282	} // namespace detail
283	#endif //DOXYGEN_NO_DETAIL
284
285
286	}} // namespace boost::geometry
287
288	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DIRECTION_CODE_HPP

boostorg / geometry / 20212

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