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

98.0

include/boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp

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

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

// This file was modified by Oracle on 2017-2024.
// Modifications copyright (c) 2017-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_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP

#include <cstddef>
#include <algorithm>
#include <map>
#include <set>
#include <vector>

#include <boost/core/addressof.hpp>
#include <boost/range/value_type.hpp>

#include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/strategies/side.hpp>

namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{

// Wraps "turn_operation" from turn_info.hpp,
// giving it extra information, necessary for sorting
template <typename TurnOperation>
struct indexed_turn_operation
{
    using type = TurnOperation;

    std::size_t turn_index;
    std::size_t operation_index;
    // use pointers to avoid copies, const& is not possible because of usage in vector
    segment_identifier const* other_seg_id; // segment id of other segment of intersection of two segments
    TurnOperation const* subject;
    bool discarded{false};
    bool skip{false};

    inline indexed_turn_operation(std::size_t ti, std::size_t oi,
                TurnOperation const& sub,
                segment_identifier const& oid,
                bool dc = false)
        : turn_index(ti)
        , operation_index(oi)
        , other_seg_id(&oid)
        , subject(boost::addressof(sub))
        , discarded(dc)
    {}

};

template
<
    typename Turns,
    typename Indexed,
    typename Geometry1, typename Geometry2,
    typename Strategy,
    bool Reverse1, bool Reverse2
>
struct less_by_segment_ratio
{
    inline less_by_segment_ratio(Turns const& turns
            , Geometry1 const& geometry1
            , Geometry2 const& geometry2
            , Strategy const& strategy)
        : m_turns(turns)
        , m_geometry1(geometry1)
        , m_geometry2(geometry2)
        , m_strategy(strategy)
    {
    }

private :

    Turns const& m_turns;
    Geometry1 const& m_geometry1;
    Geometry2 const& m_geometry2;
    Strategy const& m_strategy;

    using point_type = geometry::point_type_t<Geometry1>;

    inline bool default_order(Indexed const& left, Indexed const& right) const
    {
        // We've nothing to sort on. Take the indexes
        return left.turn_index < right.turn_index;
    }

    inline bool consider_relative_order(Indexed const& left,
                    Indexed const& right) const
    {
        point_type pi, pj, ri, rj, si, sj;

        geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
            left.subject->seg_id,
            pi, pj);
        geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
            *left.other_seg_id,
            ri, rj);
        geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
            *right.other_seg_id,
            si, sj);

        auto side_strategy = m_strategy.side();
        int const side_rj_p = side_strategy.apply(pi, pj, rj);
        int const side_sj_p = side_strategy.apply(pi, pj, sj);

        // Put the one turning left (1; right == -1) as last
        if (side_rj_p != side_sj_p)
        {
            return side_rj_p < side_sj_p;
        }

        int const side_sj_r = side_strategy.apply(ri, rj, sj);
        int const side_rj_s = side_strategy.apply(si, sj, rj);

        // If they both turn left: the most left as last
        // If they both turn right: this is not relevant, but take also here most left
        if (side_rj_s != side_sj_r)
        {
            return side_rj_s < side_sj_r;
        }

        return default_order(left, right);
    }


public :

    // Note that left/right do NOT correspond to m_geometry1/m_geometry2
    // but to the "indexed_turn_operation"
    inline bool operator()(Indexed const& left, Indexed const& right) const
    {
        if (! (left.subject->seg_id == right.subject->seg_id))
        {
            return left.subject->seg_id < right.subject->seg_id;
        }

        // Both left and right are located on the SAME segment.

        if (! (left.subject->fraction == right.subject->fraction))
        {
            return left.subject->fraction < right.subject->fraction;
        }

        auto const& left_turn = m_turns[left.turn_index];
        auto const& right_turn = m_turns[right.turn_index];

        // First check "real" intersection (crosses)
        // -> distance zero due to precision, solve it by sorting
        if (left_turn.method == method_crosses
            && right_turn.method == method_crosses)
        {
            return consider_relative_order(left, right);
        }

        bool const left_both_xx = left_turn.both(operation_blocked);
        bool const right_both_xx = right_turn.both(operation_blocked);
        if (left_both_xx && ! right_both_xx)
        {
            return true;
        }
        if (! left_both_xx && right_both_xx)
        {
            return false;
        }

        bool const left_both_uu = left_turn.both(operation_union);
        bool const right_both_uu = right_turn.both(operation_union);
        if (left_both_uu && ! right_both_uu)
        {
            return true;
        }
        if (! left_both_uu && right_both_uu)
        {
            return false;
        }

        return default_order(left, right);
    }
};


}} // namespace detail::overlay
#endif //DOXYGEN_NO_DETAIL


}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP

1	// Boost.Geometry (aka GGL, Generic Geometry Library)
2
3	// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4
5	// This file was modified by Oracle on 2017-2024.
6	// Modifications copyright (c) 2017-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_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
15	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
16
17	#include <cstddef>
18	#include <algorithm>
19	#include <map>
20	#include <set>
21	#include <vector>
22
23	#include <boost/core/addressof.hpp>
24	#include <boost/range/value_type.hpp>
25
26	#include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
27	#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
28	#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
29	#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
30	#include <boost/geometry/strategies/side.hpp>
31
32	namespace boost { namespace geometry
33	{
34
35	#ifndef DOXYGEN_NO_DETAIL
36	namespace detail { namespace overlay
37	{
38
39	// Wraps "turn_operation" from turn_info.hpp,
40	// giving it extra information, necessary for sorting
41	template <typename TurnOperation>
42	struct indexed_turn_operation
43	{
44	using type = TurnOperation;
45
46	std::size_t turn_index;
47	std::size_t operation_index;
48	// use pointers to avoid copies, const& is not possible because of usage in vector
49	segment_identifier const* other_seg_id; // segment id of other segment of intersection of two segments
50	TurnOperation const* subject;
51	bool discarded{false};
52	bool skip{false};
53
54	inline indexed_turn_operation(std::size_t ti, std::size_t oi,	506,048✔
55	TurnOperation const& sub,
56	segment_identifier const& oid,
57	bool dc = false)
58	: turn_index(ti)
59	, operation_index(oi)
60	, other_seg_id(&oid)
61	, subject(boost::addressof(sub))	506,048✔
62	, discarded(dc)	506,048✔
63	{}	506,048✔
64
65	};
66
67	template
68	<
69	typename Turns,
70	typename Indexed,
71	typename Geometry1, typename Geometry2,
72	typename Strategy,
73	bool Reverse1, bool Reverse2
74	>
75	struct less_by_segment_ratio
76	{
77	inline less_by_segment_ratio(Turns const& turns	26,213✔
78	, Geometry1 const& geometry1
79	, Geometry2 const& geometry2
80	, Strategy const& strategy)
81	: m_turns(turns)
82	, m_geometry1(geometry1)
83	, m_geometry2(geometry2)
84	, m_strategy(strategy)	26,213✔
85	{
86	}	26,213✔
87
88	private :
89
90	Turns const& m_turns;
91	Geometry1 const& m_geometry1;
92	Geometry2 const& m_geometry2;
93	Strategy const& m_strategy;
94
95	using point_type = geometry::point_type_t<Geometry1>;
96
97	inline bool default_order(Indexed const& left, Indexed const& right) const	243,981✔
98	{
99	// We've nothing to sort on. Take the indexes
100	return left.turn_index < right.turn_index;	243,981✔
101	}
102
103	inline bool consider_relative_order(Indexed const& left,	44,719✔
104	Indexed const& right) const
105	{
106	point_type pi, pj, ri, rj, si, sj;	×
107
108	geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,	44,719✔
109	left.subject->seg_id,	44,719✔
110	pi, pj);
111	geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,	44,719✔
112	*left.other_seg_id,	44,719✔
113	ri, rj);
114	geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,	44,719✔
115	*right.other_seg_id,	44,719✔
116	si, sj);
117
118	auto side_strategy = m_strategy.side();	44,719✔
119	int const side_rj_p = side_strategy.apply(pi, pj, rj);	44,719✔
120	int const side_sj_p = side_strategy.apply(pi, pj, sj);	44,719✔
121
122	// Put the one turning left (1; right == -1) as last
123	if (side_rj_p != side_sj_p)	44,719✔
124	{
125	return side_rj_p < side_sj_p;	1,242✔
126	}
127
128	int const side_sj_r = side_strategy.apply(ri, rj, sj);	43,477✔
129	int const side_rj_s = side_strategy.apply(si, sj, rj);	43,477✔
130
131	// If they both turn left: the most left as last
132	// If they both turn right: this is not relevant, but take also here most left
133	if (side_rj_s != side_sj_r)	43,477✔
134	{
135	return side_rj_s < side_sj_r;	591✔
136	}
137
138	return default_order(left, right);	42,886✔
139	}
140
141
142	public :
143
144	// Note that left/right do NOT correspond to m_geometry1/m_geometry2
145	// but to the "indexed_turn_operation"
146	inline bool operator()(Indexed const& left, Indexed const& right) const	3,930,575✔
147	{
148	if (! (left.subject->seg_id == right.subject->seg_id))	3,930,575✔
149	{
150	return left.subject->seg_id < right.subject->seg_id;	2,842,702✔
151	}
152
153	// Both left and right are located on the SAME segment.
154
155	if (! (left.subject->fraction == right.subject->fraction))	1,087,873✔
156	{
157	return left.subject->fraction < right.subject->fraction;	817,824✔
158	}
159
160	auto const& left_turn = m_turns[left.turn_index];	270,049✔
161	auto const& right_turn = m_turns[right.turn_index];	270,049✔
162
163	// First check "real" intersection (crosses)
164	// -> distance zero due to precision, solve it by sorting
165	if (left_turn.method == method_crosses	270,049✔
166	&& right_turn.method == method_crosses)	46,033✔
167	{
168	return consider_relative_order(left, right);	44,719✔
169	}
170
171	bool const left_both_xx = left_turn.both(operation_blocked);	225,330✔
172	bool const right_both_xx = right_turn.both(operation_blocked);	225,330✔
173	if (left_both_xx && ! right_both_xx)	225,330✔
174	{
175	return true;	892✔
176	}
177	if (! left_both_xx && right_both_xx)	224,438✔
178	{
179	return false;	1,811✔
180	}
181
182	bool const left_both_uu = left_turn.both(operation_union);	222,627✔
183	bool const right_both_uu = right_turn.both(operation_union);	222,627✔
184	if (left_both_uu && ! right_both_uu)	222,627✔
185	{
186	return true;	14,871✔
187	}
188	if (! left_both_uu && right_both_uu)	207,756✔
189	{
190	return false;	6,661✔
191	}
192
193	return default_order(left, right);	201,095✔
194	}
195	};
196
197
198	}} // namespace detail::overlay
199	#endif //DOXYGEN_NO_DETAIL
200
201
202	}} // namespace boost::geometry
203
204	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_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