[ceph.git] / ceph / src / boost / boost / geometry / algorithms / detail / overlay / traversal_ring_creator.hpp

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

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

// This file was modified by Oracle on 2017-2020.
// Modifications copyright (c) 2017-2020, 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_TRAVERSAL_RING_CREATOR_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP

#include <cstddef>

#include <boost/range/value_type.hpp>

#include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp>
#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/traversal.hpp>
#include <boost/geometry/algorithms/num_points.hpp>
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/core/closure.hpp>

namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{


template
<
    bool Reverse1,
    bool Reverse2,
    overlay_type OverlayType,
    typename Geometry1,
    typename Geometry2,
    typename Turns,
    typename TurnInfoMap,
    typename Clusters,
    typename Strategy,
    typename RobustPolicy,
    typename Visitor,
    typename Backtrack
>
struct traversal_ring_creator
{
    typedef traversal
            <
                Reverse1, Reverse2, OverlayType,
                Geometry1, Geometry2, Turns, Clusters,
                RobustPolicy,
                decltype(std::declval<Strategy>().side()),
                Visitor
            > traversal_type;

    typedef typename boost::range_value<Turns>::type turn_type;
    typedef typename turn_type::turn_operation_type turn_operation_type;

    static const operation_type target_operation
        = operation_from_overlay<OverlayType>::value;

    inline traversal_ring_creator(Geometry1 const& geometry1, Geometry2 const& geometry2,
            Turns& turns, TurnInfoMap& turn_info_map,
            Clusters const& clusters,
            Strategy const& strategy,
            RobustPolicy const& robust_policy, Visitor& visitor)
        : m_trav(geometry1, geometry2, turns, clusters,
                 robust_policy, strategy.side(), visitor)
        , m_geometry1(geometry1)
        , m_geometry2(geometry2)
        , m_turns(turns)
        , m_turn_info_map(turn_info_map)
        , m_clusters(clusters)
        , m_strategy(strategy)
        , m_robust_policy(robust_policy)
        , m_visitor(visitor)
    {
    }

    template <typename Ring>
    inline traverse_error_type travel_to_next_turn(signed_size_type start_turn_index,
                int start_op_index,
                signed_size_type& turn_index,
                int& op_index,
                Ring& current_ring,
                bool is_start)
    {
        int const previous_op_index = op_index;
        signed_size_type const previous_turn_index = turn_index;
        turn_type& previous_turn = m_turns[turn_index];
        turn_operation_type& previous_op = previous_turn.operations[op_index];
        segment_identifier previous_seg_id;

        signed_size_type to_vertex_index = -1;
        if (! m_trav.select_turn_from_enriched(turn_index, previous_seg_id,
                          to_vertex_index, start_turn_index, start_op_index,
                          previous_turn, previous_op, is_start))
        {
            return is_start
                    ? traverse_error_no_next_ip_at_start
                    : traverse_error_no_next_ip;
        }
        if (to_vertex_index >= 0)
        {
            if (previous_op.seg_id.source_index == 0)
            {
                geometry::copy_segments<Reverse1>(m_geometry1,
                        previous_op.seg_id, to_vertex_index,
                        m_strategy, m_robust_policy, current_ring);
            }
            else
            {
                geometry::copy_segments<Reverse2>(m_geometry2,
                        previous_op.seg_id, to_vertex_index,
                        m_strategy, m_robust_policy, current_ring);
            }
        }

        if (m_turns[turn_index].discarded)
        {
            return is_start
                ? traverse_error_dead_end_at_start
                : traverse_error_dead_end;
        }

        if (is_start)
        {
            // Register the start
            previous_op.visited.set_started();
            m_visitor.visit_traverse(m_turns, previous_turn, previous_op, "Start");
        }

        if (! m_trav.select_turn(start_turn_index, start_op_index,
                turn_index, op_index,
                previous_op_index, previous_turn_index, previous_seg_id,
                is_start, current_ring.size() > 1))
        {
            return is_start
                ? traverse_error_no_next_ip_at_start
                : traverse_error_no_next_ip;
        }

        {
            // Check operation (TODO: this might be redundant or should be catched before)
            const turn_type& current_turn = m_turns[turn_index];
            const turn_operation_type& op = current_turn.operations[op_index];
            if (op.visited.finalized()
                || m_trav.is_visited(current_turn, op, turn_index, op_index))
            {
                return traverse_error_visit_again;
            }
        }

        // Update registration and append point
        turn_type& current_turn = m_turns[turn_index];
        turn_operation_type& op = current_turn.operations[op_index];
        detail::overlay::append_no_collinear(current_ring, current_turn.point,
                                             m_strategy, m_robust_policy);

        // Register the visit
        m_trav.set_visited(current_turn, op);
        m_visitor.visit_traverse(m_turns, current_turn, op, "Visit");

        return traverse_error_none;
    }

    template <typename Ring>
    inline traverse_error_type traverse(Ring& ring,
            signed_size_type start_turn_index, int start_op_index)
    {
        turn_type const& start_turn = m_turns[start_turn_index];
        turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index];

        detail::overlay::append_no_collinear(ring, start_turn.point,
                                             m_strategy, m_robust_policy);

        signed_size_type current_turn_index = start_turn_index;
        int current_op_index = start_op_index;

        traverse_error_type error = travel_to_next_turn(start_turn_index,
                    start_op_index,
                    current_turn_index, current_op_index,
                    ring, true);

        if (error != traverse_error_none)
        {
            // This is not necessarily a problem, it happens for clustered turns
            // which are "build in" or otherwise point inwards
            return error;
        }

        if (current_turn_index == start_turn_index)
        {
            start_op.visited.set_finished();
            m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish");
            return traverse_error_none;
        }

        if (start_turn.is_clustered())
        {
            turn_type& turn = m_turns[current_turn_index];
            turn_operation_type& op = turn.operations[current_op_index];
            if (turn.cluster_id == start_turn.cluster_id
                && op.enriched.get_next_turn_index() == start_turn_index)
            {
                op.visited.set_finished();
                m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish (cluster)");
                return traverse_error_none;
            }
        }

        std::size_t const max_iterations = 2 + 2 * m_turns.size();
        for (std::size_t i = 0; i <= max_iterations; i++)
        {
            // We assume clockwise polygons only, non self-intersecting, closed.
            // However, the input might be different, and checking validity
            // is up to the library user.

            // Therefore we make here some sanity checks. If the input
            // violates the assumptions, the output polygon will not be correct
            // but the routine will stop and output the current polygon, and
            // will continue with the next one.

            // Below three reasons to stop.
            error = travel_to_next_turn(start_turn_index, start_op_index,
                    current_turn_index, current_op_index,
                    ring, false);

            if (error != traverse_error_none)
            {
                return error;
            }

            if (current_turn_index == start_turn_index
                    && current_op_index == start_op_index)
            {
                start_op.visited.set_finished();
                m_visitor.visit_traverse(m_turns, start_turn, start_op, "Finish");
                return traverse_error_none;
            }
        }

        return traverse_error_endless_loop;
    }

    template <typename Rings>
    void traverse_with_operation(turn_type const& start_turn,
            std::size_t turn_index, int op_index,
            Rings& rings, std::size_t& finalized_ring_size,
            typename Backtrack::state_type& state)
    {
        typedef typename boost::range_value<Rings>::type ring_type;

        turn_operation_type const& start_op = start_turn.operations[op_index];

        if (! start_op.visited.none()
            || ! start_op.enriched.startable
            || start_op.visited.rejected()
            || ! (start_op.operation == target_operation
                || start_op.operation == detail::overlay::operation_continue))
        {
            return;
        }

        ring_type ring;
        traverse_error_type traverse_error = traverse(ring, turn_index, op_index);

        if (traverse_error == traverse_error_none)
        {
            std::size_t const min_num_points
                    = core_detail::closure::minimum_ring_size
                            <
                                geometry::closure<ring_type>::value
                            >::value;

            if (geometry::num_points(ring) >= min_num_points)
            {
                clean_closing_dups_and_spikes(ring, m_strategy, m_robust_policy);
                rings.push_back(ring);

                m_trav.finalize_visit_info(m_turn_info_map);
                finalized_ring_size++;
            }
        }
        else
        {
            Backtrack::apply(finalized_ring_size,
                             rings, ring, m_turns, start_turn,
                             m_turns[turn_index].operations[op_index],
                             traverse_error,
                             m_geometry1, m_geometry2,
                             m_strategy, m_robust_policy,
                             state, m_visitor);
        }
    }

    int get_operation_index(turn_type const& turn) const
    {
        // When starting with a continue operation, the one
        // with the smallest (for intersection) or largest (for union)
        // remaining distance (#8310b)
        // Also to avoid skipping a turn in between, which can happen
        // in rare cases (e.g. #130)
        static const bool is_union
            = operation_from_overlay<OverlayType>::value == operation_union;

        turn_operation_type const& op0 = turn.operations[0];
        turn_operation_type const& op1 = turn.operations[1];
        return op0.remaining_distance <= op1.remaining_distance
                ? (is_union ? 1 : 0)
                : (is_union ? 0 : 1);
    }

    template <typename Rings>
    void iterate(Rings& rings, std::size_t& finalized_ring_size,
                 typename Backtrack::state_type& state)
    {
        for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
        {
            turn_type const& turn = m_turns[turn_index];

            if (turn.discarded || turn.blocked())
            {
                // Skip discarded and blocked turns
                continue;
            }

            if (turn.both(operation_continue))
            {
                traverse_with_operation(turn, turn_index,
                        get_operation_index(turn),
                        rings, finalized_ring_size, state);
            }
            else
            {
                for (int op_index = 0; op_index < 2; op_index++)
                {
                    traverse_with_operation(turn, turn_index, op_index,
                            rings, finalized_ring_size, state);
                }
            }
        }
    }

    template <typename Rings>
    void iterate_with_preference(std::size_t phase,
                 Rings& rings, std::size_t& finalized_ring_size,
                 typename Backtrack::state_type& state)
    {
        for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
        {
            turn_type const& turn = m_turns[turn_index];

            if (turn.discarded || turn.blocked())
            {
                // Skip discarded and blocked turns
                continue;
            }

            turn_operation_type const& op0 = turn.operations[0];
            turn_operation_type const& op1 = turn.operations[1];

            if (phase == 0)
            {
                if (! op0.enriched.prefer_start && ! op1.enriched.prefer_start)
                {
                    // Not preferred, take next one
                    continue;
                }
            }

            if (turn.both(operation_continue))
            {
                traverse_with_operation(turn, turn_index,
                        get_operation_index(turn),
                        rings, finalized_ring_size, state);
            }
            else
            {
                bool const forward = op0.enriched.prefer_start;

                int op_index = forward ? 0 : 1;
                int const increment = forward ? 1 : -1;

                for (int i = 0; i < 2; i++, op_index += increment)
                {
                    traverse_with_operation(turn, turn_index, op_index,
                            rings, finalized_ring_size, state);
                }
            }
        }
    }

private:
    traversal_type m_trav;

    Geometry1 const& m_geometry1;
    Geometry2 const& m_geometry2;
    Turns& m_turns;
    TurnInfoMap& m_turn_info_map; // contains turn-info information per ring
    Clusters const& m_clusters;
    Strategy const& m_strategy;
    RobustPolicy const& m_robust_policy;
    Visitor& m_visitor;
};

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

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2
	3	// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
	4
20effc67 TL	5	// This file was modified by Oracle on 2017-2020.
20effc67 TL	6	// Modifications copyright (c) 2017-2020, Oracle and/or its affiliates.
b32b8144 FG	7	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
b32b8144 FG	8
7c673cae FG	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_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP
	14	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP
	15
	16	#include <cstddef>
	17
20effc67	18	#include <boost/range/value_type.hpp>
7c673cae	19
92f5a8d4	20	#include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp>
7c673cae FG	21	#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
	22	#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
	23	#include <boost/geometry/algorithms/detail/overlay/traversal.hpp>
	24	#include <boost/geometry/algorithms/num_points.hpp>
	25	#include <boost/geometry/core/access.hpp>
	26	#include <boost/geometry/core/assert.hpp>
	27	#include <boost/geometry/core/closure.hpp>
	28
	29	namespace boost { namespace geometry
	30	{
	31
	32	#ifndef DOXYGEN_NO_DETAIL
	33	namespace detail { namespace overlay
	34	{
	35
	36
	37	template
	38	<
	39	bool Reverse1,
	40	bool Reverse2,
	41	overlay_type OverlayType,
	42	typename Geometry1,
	43	typename Geometry2,
	44	typename Turns,
b32b8144	45	typename TurnInfoMap,
7c673cae	46	typename Clusters,
1e59de90	47	typename Strategy,
7c673cae FG	48	typename RobustPolicy,
	49	typename Visitor,
	50	typename Backtrack
	51	>
	52	struct traversal_ring_creator
	53	{
b32b8144 FG	54	typedef traversal
	55	<
	56	Reverse1, Reverse2, OverlayType,
	57	Geometry1, Geometry2, Turns, Clusters,
1e59de90 TL	58	RobustPolicy,
1e59de90 TL	59	decltype(std::declval<Strategy>().side()),
b32b8144 FG	60	Visitor
b32b8144 FG	61	> traversal_type;
7c673cae FG	62
	63	typedef typename boost::range_value<Turns>::type turn_type;
	64	typedef typename turn_type::turn_operation_type turn_operation_type;
	65
	66	static const operation_type target_operation
	67	= operation_from_overlay<OverlayType>::value;
	68
	69	inline traversal_ring_creator(Geometry1 const& geometry1, Geometry2 const& geometry2,
b32b8144 FG	70	Turns& turns, TurnInfoMap& turn_info_map,
b32b8144 FG	71	Clusters const& clusters,
1e59de90	72	Strategy const& strategy,
7c673cae	73	RobustPolicy const& robust_policy, Visitor& visitor)
b32b8144	74	: m_trav(geometry1, geometry2, turns, clusters,
1e59de90	75	robust_policy, strategy.side(), visitor)
7c673cae FG	76	, m_geometry1(geometry1)
	77	, m_geometry2(geometry2)
	78	, m_turns(turns)
b32b8144	79	, m_turn_info_map(turn_info_map)
7c673cae	80	, m_clusters(clusters)
1e59de90	81	, m_strategy(strategy)
7c673cae FG	82	, m_robust_policy(robust_policy)
7c673cae FG	83	, m_visitor(visitor)
7c673cae	84	{
7c673cae FG	85	}
	86
	87	template <typename Ring>
	88	inline traverse_error_type travel_to_next_turn(signed_size_type start_turn_index,
	89	int start_op_index,
	90	signed_size_type& turn_index,
	91	int& op_index,
	92	Ring& current_ring,
	93	bool is_start)
	94	{
	95	int const previous_op_index = op_index;
	96	signed_size_type const previous_turn_index = turn_index;
	97	turn_type& previous_turn = m_turns[turn_index];
	98	turn_operation_type& previous_op = previous_turn.operations[op_index];
	99	segment_identifier previous_seg_id;
	100
	101	signed_size_type to_vertex_index = -1;
	102	if (! m_trav.select_turn_from_enriched(turn_index, previous_seg_id,
	103	to_vertex_index, start_turn_index, start_op_index,
	104	previous_turn, previous_op, is_start))
	105	{
	106	return is_start
	107	? traverse_error_no_next_ip_at_start
	108	: traverse_error_no_next_ip;
	109	}
	110	if (to_vertex_index >= 0)
	111	{
	112	if (previous_op.seg_id.source_index == 0)
	113	{
	114	geometry::copy_segments<Reverse1>(m_geometry1,
	115	previous_op.seg_id, to_vertex_index,
1e59de90	116	m_strategy, m_robust_policy, current_ring);
7c673cae FG	117	}
	118	else
	119	{
	120	geometry::copy_segments<Reverse2>(m_geometry2,
	121	previous_op.seg_id, to_vertex_index,
1e59de90	122	m_strategy, m_robust_policy, current_ring);
7c673cae FG	123	}
	124	}
	125
	126	if (m_turns[turn_index].discarded)
	127	{
	128	return is_start
	129	? traverse_error_dead_end_at_start
	130	: traverse_error_dead_end;
	131	}
	132
	133	if (is_start)
	134	{
	135	// Register the start
	136	previous_op.visited.set_started();
	137	m_visitor.visit_traverse(m_turns, previous_turn, previous_op, "Start");
	138	}
	139
b32b8144 FG	140	if (! m_trav.select_turn(start_turn_index, start_op_index,
b32b8144 FG	141	turn_index, op_index,
7c673cae	142	previous_op_index, previous_turn_index, previous_seg_id,
92f5a8d4	143	is_start, current_ring.size() > 1))
7c673cae FG	144	{
	145	return is_start
	146	? traverse_error_no_next_ip_at_start
	147	: traverse_error_no_next_ip;
	148	}
	149
	150	{
	151	// Check operation (TODO: this might be redundant or should be catched before)
	152	const turn_type& current_turn = m_turns[turn_index];
	153	const turn_operation_type& op = current_turn.operations[op_index];
	154	if (op.visited.finalized()
	155	\|\| m_trav.is_visited(current_turn, op, turn_index, op_index))
	156	{
	157	return traverse_error_visit_again;
	158	}
	159	}
	160
	161	// Update registration and append point
	162	turn_type& current_turn = m_turns[turn_index];
	163	turn_operation_type& op = current_turn.operations[op_index];
11fdf7f2	164	detail::overlay::append_no_collinear(current_ring, current_turn.point,
1e59de90	165	m_strategy, m_robust_policy);
7c673cae FG	166
	167	// Register the visit
	168	m_trav.set_visited(current_turn, op);
	169	m_visitor.visit_traverse(m_turns, current_turn, op, "Visit");
	170
	171	return traverse_error_none;
	172	}
	173
	174	template <typename Ring>
	175	inline traverse_error_type traverse(Ring& ring,
	176	signed_size_type start_turn_index, int start_op_index)
	177	{
	178	turn_type const& start_turn = m_turns[start_turn_index];
	179	turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index];
	180
11fdf7f2	181	detail::overlay::append_no_collinear(ring, start_turn.point,
1e59de90	182	m_strategy, m_robust_policy);
7c673cae FG	183
	184	signed_size_type current_turn_index = start_turn_index;
	185	int current_op_index = start_op_index;
	186
	187	traverse_error_type error = travel_to_next_turn(start_turn_index,
	188	start_op_index,
	189	current_turn_index, current_op_index,
	190	ring, true);
	191
	192	if (error != traverse_error_none)
	193	{
	194	// This is not necessarily a problem, it happens for clustered turns
	195	// which are "build in" or otherwise point inwards
	196	return error;
	197	}
	198
	199	if (current_turn_index == start_turn_index)
	200	{
	201	start_op.visited.set_finished();
	202	m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish");
	203	return traverse_error_none;
	204	}
	205
b32b8144 FG	206	if (start_turn.is_clustered())
b32b8144 FG	207	{
92f5a8d4 TL	208	turn_type& turn = m_turns[current_turn_index];
	209	turn_operation_type& op = turn.operations[current_op_index];
	210	if (turn.cluster_id == start_turn.cluster_id
	211	&& op.enriched.get_next_turn_index() == start_turn_index)
b32b8144	212	{
b32b8144 FG	213	op.visited.set_finished();
	214	m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish (cluster)");
	215	return traverse_error_none;
	216	}
	217	}
	218
7c673cae FG	219	std::size_t const max_iterations = 2 + 2 * m_turns.size();
	220	for (std::size_t i = 0; i <= max_iterations; i++)
	221	{
	222	// We assume clockwise polygons only, non self-intersecting, closed.
	223	// However, the input might be different, and checking validity
	224	// is up to the library user.
	225
	226	// Therefore we make here some sanity checks. If the input
	227	// violates the assumptions, the output polygon will not be correct
	228	// but the routine will stop and output the current polygon, and
	229	// will continue with the next one.
	230
	231	// Below three reasons to stop.
	232	error = travel_to_next_turn(start_turn_index, start_op_index,
	233	current_turn_index, current_op_index,
	234	ring, false);
	235
	236	if (error != traverse_error_none)
	237	{
	238	return error;
	239	}
	240
	241	if (current_turn_index == start_turn_index
	242	&& current_op_index == start_op_index)
	243	{
	244	start_op.visited.set_finished();
	245	m_visitor.visit_traverse(m_turns, start_turn, start_op, "Finish");
	246	return traverse_error_none;
	247	}
	248	}
	249
	250	return traverse_error_endless_loop;
	251	}
	252
	253	template <typename Rings>
	254	void traverse_with_operation(turn_type const& start_turn,
	255	std::size_t turn_index, int op_index,
	256	Rings& rings, std::size_t& finalized_ring_size,
	257	typename Backtrack::state_type& state)
	258	{
	259	typedef typename boost::range_value<Rings>::type ring_type;
	260
	261	turn_operation_type const& start_op = start_turn.operations[op_index];
	262
	263	if (! start_op.visited.none()
	264	\|\| ! start_op.enriched.startable
	265	\|\| start_op.visited.rejected()
	266	\|\| ! (start_op.operation == target_operation
	267	\|\| start_op.operation == detail::overlay::operation_continue))
	268	{
	269	return;
	270	}
	271
	272	ring_type ring;
	273	traverse_error_type traverse_error = traverse(ring, turn_index, op_index);
	274
	275	if (traverse_error == traverse_error_none)
	276	{
	277	std::size_t const min_num_points
	278	= core_detail::closure::minimum_ring_size
	279	<
	280	geometry::closure<ring_type>::value
	281	>::value;
	282
283	if (geometry::num_points(ring) >= min_num_points)
284	{
1e59de90	285	clean_closing_dups_and_spikes(ring, m_strategy, m_robust_policy);
7c673cae FG	286	rings.push_back(ring);
7c673cae FG	287
b32b8144	288	m_trav.finalize_visit_info(m_turn_info_map);
7c673cae FG	289	finalized_ring_size++;
	290	}
	291	}
	292	else
	293	{
1e59de90 TL	294	Backtrack::apply(finalized_ring_size,
	295	rings, ring, m_turns, start_turn,
	296	m_turns[turn_index].operations[op_index],
	297	traverse_error,
	298	m_geometry1, m_geometry2,
	299	m_strategy, m_robust_policy,
	300	state, m_visitor);
7c673cae FG	301	}
	302	}
	303
92f5a8d4 TL	304	int get_operation_index(turn_type const& turn) const
	305	{
	306	// When starting with a continue operation, the one
	307	// with the smallest (for intersection) or largest (for union)
	308	// remaining distance (#8310b)
	309	// Also to avoid skipping a turn in between, which can happen
	310	// in rare cases (e.g. #130)
	311	static const bool is_union
	312	= operation_from_overlay<OverlayType>::value == operation_union;
	313
	314	turn_operation_type const& op0 = turn.operations[0];
	315	turn_operation_type const& op1 = turn.operations[1];
	316	return op0.remaining_distance <= op1.remaining_distance
	317	? (is_union ? 1 : 0)
	318	: (is_union ? 0 : 1);
	319	}
	320
7c673cae FG	321	template <typename Rings>
7c673cae FG	322	void iterate(Rings& rings, std::size_t& finalized_ring_size,
b32b8144	323	typename Backtrack::state_type& state)
7c673cae	324	{
7c673cae FG	325	for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
7c673cae FG	326	{
b32b8144	327	turn_type const& turn = m_turns[turn_index];
7c673cae	328
b32b8144	329	if (turn.discarded \|\| turn.blocked())
7c673cae FG	330	{
	331	// Skip discarded and blocked turns
	332	continue;
	333	}
7c673cae	334
b32b8144	335	if (turn.both(operation_continue))
7c673cae	336	{
92f5a8d4 TL	337	traverse_with_operation(turn, turn_index,
92f5a8d4 TL	338	get_operation_index(turn),
7c673cae FG	339	rings, finalized_ring_size, state);
7c673cae FG	340	}
b32b8144 FG	341	else
	342	{
	343	for (int op_index = 0; op_index < 2; op_index++)
	344	{
	345	traverse_with_operation(turn, turn_index, op_index,
	346	rings, finalized_ring_size, state);
	347	}
	348	}
7c673cae FG	349	}
	350	}
	351
11fdf7f2 TL	352	template <typename Rings>
	353	void iterate_with_preference(std::size_t phase,
	354	Rings& rings, std::size_t& finalized_ring_size,
	355	typename Backtrack::state_type& state)
	356	{
	357	for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
	358	{
	359	turn_type const& turn = m_turns[turn_index];
	360
	361	if (turn.discarded \|\| turn.blocked())
	362	{
	363	// Skip discarded and blocked turns
	364	continue;
	365	}
	366
	367	turn_operation_type const& op0 = turn.operations[0];
	368	turn_operation_type const& op1 = turn.operations[1];
	369
	370	if (phase == 0)
	371	{
	372	if (! op0.enriched.prefer_start && ! op1.enriched.prefer_start)
	373	{
	374	// Not preferred, take next one
	375	continue;
	376	}
	377	}
	378
	379	if (turn.both(operation_continue))
	380	{
92f5a8d4 TL	381	traverse_with_operation(turn, turn_index,
92f5a8d4 TL	382	get_operation_index(turn),
11fdf7f2 TL	383	rings, finalized_ring_size, state);
	384	}
	385	else
	386	{
	387	bool const forward = op0.enriched.prefer_start;
	388
	389	int op_index = forward ? 0 : 1;
	390	int const increment = forward ? 1 : -1;
	391
	392	for (int i = 0; i < 2; i++, op_index += increment)
	393	{
	394	traverse_with_operation(turn, turn_index, op_index,
	395	rings, finalized_ring_size, state);
	396	}
	397	}
	398	}
	399	}
	400
7c673cae FG	401	private:
	402	traversal_type m_trav;
	403
	404	Geometry1 const& m_geometry1;
	405	Geometry2 const& m_geometry2;
	406	Turns& m_turns;
b32b8144	407	TurnInfoMap& m_turn_info_map; // contains turn-info information per ring
7c673cae	408	Clusters const& m_clusters;
1e59de90	409	Strategy const& m_strategy;
7c673cae FG	410	RobustPolicy const& m_robust_policy;
7c673cae FG	411	Visitor& m_visitor;
7c673cae FG	412	};
	413
	414	}} // namespace detail::overlay
	415	#endif // DOXYGEN_NO_DETAIL
	416
	417	}} // namespace boost::geometry
	418
	419	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP