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

97.83

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

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

// Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
// Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.

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

// 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_HANDLE_SELF_TURNS_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP

#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/value_type.hpp>

#include <boost/geometry/algorithms/detail/covered_by/implementation.hpp>
#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
#include <boost/geometry/algorithms/detail/within/implementation.hpp>

namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{

template <overlay_type OverlayType>
struct check_within
{
    template
    <
        typename Turn, typename Geometry0, typename Geometry1,
        typename UmbrellaStrategy
    >
    static inline
    bool apply(Turn const& turn, Geometry0 const& geometry0,
               Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
    {
        // Operations 0 and 1 have the same source index in self-turns
        return turn.operations[0].seg_id.source_index == 0
            ? geometry::within(turn.point, geometry1, strategy)
            : geometry::within(turn.point, geometry0, strategy);
    }

};

template <>
struct check_within<overlay_buffer>
{
    template
    <
        typename Turn, typename Geometry0, typename Geometry1,
        typename UmbrellaStrategy
    >
    static inline
    bool apply(Turn const& turn, Geometry0 const& geometry0,
               Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
    {
        return false;
    }
};

template <>
struct check_within<overlay_difference>
{
    template
    <
        typename Turn, typename Geometry0, typename Geometry1,
        typename UmbrellaStrategy
    >
    static inline
    bool apply(Turn const& turn, Geometry0 const& geometry0,
               Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
    {
        // difference = intersection(a, reverse(b))
        // therefore we should reverse the meaning of within for geometry1
        return turn.operations[0].seg_id.source_index == 0
            ? ! geometry::covered_by(turn.point, geometry1, strategy)
            : geometry::within(turn.point, geometry0, strategy);
    }
};

struct discard_turns
{
    template
    <
        typename Turns, typename Clusters,
        typename Geometry0, typename Geometry1,
        typename Strategy
    >
    static inline
    void apply(Turns& , Clusters const& ,
               Geometry0 const& , Geometry1 const& ,
               Strategy const& )
    {}
};

template <overlay_type OverlayType, operation_type OperationType>
struct discard_closed_turns : discard_turns {};

// It is only implemented for operation_union, not in buffer
template <>
struct discard_closed_turns<overlay_union, operation_union>
{
    // Point in Geometry Strategy
    template
    <
        typename Turns, typename Clusters,
        typename Geometry0, typename Geometry1,
        typename Strategy
    >
    static inline
    void apply(Turns& turns, Clusters const& /*clusters*/,
               Geometry0 const& geometry0, Geometry1 const& geometry1,
               Strategy const& strategy)
    {
        for (auto& turn : turns)
        {
            if (! turn.discarded
                && is_self_turn<overlay_union>(turn)
                && check_within<overlay_union>::apply(turn, geometry0,
                                                      geometry1, strategy))
            {
                // Turn is in the interior of other geometry
                turn.discarded = true;
            }
        }
    }
};

template <overlay_type OverlayType>
struct discard_self_intersection_turns
{
private :

    template <typename Turns, typename Clusters>
    static inline
    bool is_self_cluster(signed_size_type cluster_id,
            Turns const& turns, Clusters const& clusters)
    {
        auto cit = clusters.find(cluster_id);
        if (cit == clusters.end())
        {
            return false;
        }

        cluster_info const& cinfo = cit->second;
        for (auto index : cinfo.turn_indices)
        {
            if (! is_self_turn<OverlayType>(turns[index]))
            {
                return false;
            }
        }

        return true;
    }

    template <typename Turns, typename Clusters,
              typename Geometry0, typename Geometry1, typename Strategy>
    static inline
    void discard_clusters(Turns& turns, Clusters const& clusters,
            Geometry0 const& geometry0, Geometry1 const& geometry1,
            Strategy const& strategy)
    {
        for (auto const& pair : clusters)
        {
            signed_size_type const cluster_id = pair.first;
            cluster_info const& cinfo = pair.second;

            // If there are only self-turns in the cluster, the cluster should
            // be located within the other geometry, for intersection
            if (! cinfo.turn_indices.empty()
                && is_self_cluster(cluster_id, turns, clusters))
            {
                signed_size_type const first_index = *cinfo.turn_indices.begin();
                if (! check_within<OverlayType>::apply(turns[first_index],
                                                       geometry0, geometry1,
                                                       strategy))
                {
                    // Discard all turns in cluster
                    for (auto index : cinfo.turn_indices)
                    {
                        turns[index].discarded = true;
                    }
                }
            }
        }
    }

public :

    template <typename Turns, typename Clusters,
              typename Geometry0, typename Geometry1, typename Strategy>
    static inline
    void apply(Turns& turns, Clusters const& clusters,
            Geometry0 const& geometry0, Geometry1 const& geometry1,
            Strategy const& strategy)
    {
        discard_clusters(turns, clusters, geometry0, geometry1, strategy);

        for (auto& turn : turns)
        {
            // It is a ii self-turn
            // Check if it is within the other geometry
            if (! turn.discarded
                && is_self_turn<overlay_intersection>(turn)
                && ! check_within<OverlayType>::apply(turn, geometry0,
                                                      geometry1, strategy))
            {
                // It is not within another geometry, set it as non startable.
                // It still might be traveled (#case_recursive_boxes_70)
                turn.operations[0].enriched.startable = false;
                turn.operations[1].enriched.startable = false;
            }
        }
    }
};


template <overlay_type OverlayType, operation_type OperationType>
struct discard_open_turns : discard_turns {};

// Handler for intersection
template <>
struct discard_open_turns<overlay_intersection, operation_intersection>
        : discard_self_intersection_turns<overlay_intersection> {};

// Handler for difference, with different meaning of 'within'
template <>
struct discard_open_turns<overlay_difference, operation_intersection>
        : discard_self_intersection_turns<overlay_difference> {};

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


}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP

1	// Boost.Geometry (aka GGL, Generic Geometry Library)
2
3	// Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
4	// Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.
5
6	// This file was modified by Oracle on 2019-2022.
7	// Modifications copyright (c) 2019-2022 Oracle and/or its affiliates.
8
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_OVERLAY_HANDLE_SELF_TURNS_HPP
16	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
17
18	#include <boost/range/begin.hpp>
19	#include <boost/range/end.hpp>
20	#include <boost/range/value_type.hpp>
21
22	#include <boost/geometry/algorithms/detail/covered_by/implementation.hpp>
23	#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
24	#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
25	#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
26	#include <boost/geometry/algorithms/detail/within/implementation.hpp>
27
28	namespace boost { namespace geometry
29	{
30
31	#ifndef DOXYGEN_NO_DETAIL
32	namespace detail { namespace overlay
33	{
34
35	template <overlay_type OverlayType>
36	struct check_within
37	{
38	template
39	<
40	typename Turn, typename Geometry0, typename Geometry1,
41	typename UmbrellaStrategy
42	>
43	static inline
44	bool apply(Turn const& turn, Geometry0 const& geometry0,	4,097✔
45	Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
46	{
47	// Operations 0 and 1 have the same source index in self-turns
48	return turn.operations[0].seg_id.source_index == 0	4,097✔
49	? geometry::within(turn.point, geometry1, strategy)	4,097✔
50	: geometry::within(turn.point, geometry0, strategy);	4,097✔
51	}
52
53	};
54
55	template <>
56	struct check_within<overlay_buffer>
57	{
58	template
59	<
60	typename Turn, typename Geometry0, typename Geometry1,
61	typename UmbrellaStrategy
62	>
63	static inline
64	bool apply(Turn const& turn, Geometry0 const& geometry0,
65	Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
66	{
67	return false;
68	}
69	};
70
71	template <>
72	struct check_within<overlay_difference>
73	{
74	template
75	<
76	typename Turn, typename Geometry0, typename Geometry1,
77	typename UmbrellaStrategy
78	>
79	static inline
80	bool apply(Turn const& turn, Geometry0 const& geometry0,	3,898✔
81	Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
82	{
83	// difference = intersection(a, reverse(b))
84	// therefore we should reverse the meaning of within for geometry1
85	return turn.operations[0].seg_id.source_index == 0	3,898✔
86	? ! geometry::covered_by(turn.point, geometry1, strategy)	3,898✔
87	: geometry::within(turn.point, geometry0, strategy);	3,898✔
88	}
89	};
90
91	struct discard_turns
92	{
93	template
94	<
95	typename Turns, typename Clusters,
96	typename Geometry0, typename Geometry1,
97	typename Strategy
98	>
99	static inline
100	void apply(Turns& , Clusters const& ,	10,065✔
101	Geometry0 const& , Geometry1 const& ,
102	Strategy const& )
103	{}	10,065✔
104	};
105
106	template <overlay_type OverlayType, operation_type OperationType>
107	struct discard_closed_turns : discard_turns {};
108
109	// It is only implemented for operation_union, not in buffer
110	template <>
111	struct discard_closed_turns<overlay_union, operation_union>
112	{
113	// Point in Geometry Strategy
114	template
115	<
116	typename Turns, typename Clusters,
117	typename Geometry0, typename Geometry1,
118	typename Strategy
119	>
120	static inline
121	void apply(Turns& turns, Clusters const& /clusters/,	1,272✔
122	Geometry0 const& geometry0, Geometry1 const& geometry1,
123	Strategy const& strategy)
124	{
125	for (auto& turn : turns)	20,554✔
126	{
127	if (! turn.discarded	38,564✔
128	&& is_self_turn<overlay_union>(turn)	15,953✔
129	&& check_within<overlay_union>::apply(turn, geometry0,	35,235✔
130	geometry1, strategy))
131	{
132	// Turn is in the interior of other geometry
133	turn.discarded = true;	101✔
134	}
135	}
136	}	1,272✔
137	};
138
139	template <overlay_type OverlayType>
140	struct discard_self_intersection_turns
141	{
142	private :
143
144	template <typename Turns, typename Clusters>
145	static inline
146	bool is_self_cluster(signed_size_type cluster_id,	9,466✔
147	Turns const& turns, Clusters const& clusters)
148	{
149	auto cit = clusters.find(cluster_id);	9,466✔
150	if (cit == clusters.end())	9,466✔
151	{
152	return false;	×
153	}
154
155	cluster_info const& cinfo = cit->second;	9,466✔
156	for (auto index : cinfo.turn_indices)	10,032✔
157	{
158	if (! is_self_turn<OverlayType>(turns[index]))	9,787✔
159	{
160	return false;	9,221✔
161	}
162	}
163
164	return true;	245✔
165	}
166
167	template <typename Turns, typename Clusters,
168	typename Geometry0, typename Geometry1, typename Strategy>
169	static inline
170	void discard_clusters(Turns& turns, Clusters const& clusters,	2,843✔
171	Geometry0 const& geometry0, Geometry1 const& geometry1,
172	Strategy const& strategy)
173	{
174	for (auto const& pair : clusters)	12,309✔
175	{
176	signed_size_type const cluster_id = pair.first;	9,466✔
177	cluster_info const& cinfo = pair.second;	9,466✔
178
179	// If there are only self-turns in the cluster, the cluster should
180	// be located within the other geometry, for intersection
181	if (! cinfo.turn_indices.empty()	9,466✔
182	&& is_self_cluster(cluster_id, turns, clusters))	9,466✔
183	{
184	signed_size_type const first_index = *cinfo.turn_indices.begin();	245✔
185	if (! check_within<OverlayType>::apply(turns[first_index],	245✔
186	geometry0, geometry1,
187	strategy))
188	{
189	// Discard all turns in cluster
190	for (auto index : cinfo.turn_indices)	375✔
191	{
192	turns[index].discarded = true;	262✔
193	}
194	}
195	}
196	}
197	}	2,843✔
198
199	public :
200
201	template <typename Turns, typename Clusters,
202	typename Geometry0, typename Geometry1, typename Strategy>
203	static inline
204	void apply(Turns& turns, Clusters const& clusters,	2,843✔
205	Geometry0 const& geometry0, Geometry1 const& geometry1,
206	Strategy const& strategy)
207	{
208	discard_clusters(turns, clusters, geometry0, geometry1, strategy);	2,843✔
209
210	for (auto& turn : turns)	56,822✔
211	{
212	// It is a ii self-turn
213	// Check if it is within the other geometry
214	if (! turn.discarded	107,958✔
215	&& is_self_turn<overlay_intersection>(turn)	35,441✔
216	&& ! check_within<OverlayType>::apply(turn, geometry0,	89,420✔
217	geometry1, strategy))
218	{
219	// It is not within another geometry, set it as non startable.
220	// It still might be traveled (#case_recursive_boxes_70)
221	turn.operations[0].enriched.startable = false;	3,777✔
222	turn.operations[1].enriched.startable = false;	3,777✔
223	}
224	}
225	}	2,843✔
226	};
227
228
229	template <overlay_type OverlayType, operation_type OperationType>
230	struct discard_open_turns : discard_turns {};
231
232	// Handler for intersection
233	template <>
234	struct discard_open_turns<overlay_intersection, operation_intersection>
235	: discard_self_intersection_turns<overlay_intersection> {};
236
237	// Handler for difference, with different meaning of 'within'
238	template <>
239	struct discard_open_turns<overlay_difference, operation_intersection>
240	: discard_self_intersection_turns<overlay_difference> {};
241
242	}} // namespace detail::overlay
243	#endif //DOXYGEN_NO_DETAIL
244
245
246	}} // namespace boost::geometry
247
248	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_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