[ceph.git] / ceph / src / boost / boost / geometry / algorithms / detail / relate / turns.hpp

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

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

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

// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// Contributed and/or modified by Menelaos Karavelas, 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_RELATE_TURNS_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP


#include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>

#include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
#include <boost/geometry/policies/robustness/segment_ratio_type.hpp>

#include <boost/geometry/strategies/cartesian/point_in_point.hpp>
#include <boost/geometry/strategies/spherical/point_in_point.hpp>
#include <boost/geometry/strategies/distance.hpp>


namespace boost { namespace geometry {

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace relate { namespace turns {

template <bool IncludeDegenerate = false>
struct assign_policy
    : overlay::assign_null_policy
{
    static bool const include_degenerate = IncludeDegenerate;
};

// GET_TURNS

template
<
    typename Geometry1,
    typename Geometry2,
    typename GetTurnPolicy = detail::get_turns::get_turn_info_type
        <
            Geometry1, Geometry2, assign_policy<>
        >
>
struct get_turns
{
    typedef typename geometry::point_type<Geometry1>::type point1_type;

    template <typename Strategy>
    struct robust_policy_type
        : geometry::rescale_overlay_policy_type
            <
                Geometry1,
                Geometry2,
                typename Strategy::cs_tag
            >
    {};

    template
    <
        typename Strategy,
        typename RobustPolicy = typename robust_policy_type<Strategy>::type
    >
    struct turn_info_type
    {
        typedef typename segment_ratio_type<point1_type, RobustPolicy>::type ratio_type;
        typedef overlay::turn_info
            <
                point1_type,
                ratio_type,
                typename detail::get_turns::turn_operation_type
                    <
                        Geometry1, Geometry2, ratio_type
                    >::type
            > type;
    };

    template <typename Turns, typename InterruptPolicy, typename Strategy>
    static inline void apply(Turns & turns,
                             Geometry1 const& geometry1,
                             Geometry2 const& geometry2,
                             InterruptPolicy & interrupt_policy,
                             Strategy const& strategy)
    {
        typedef typename robust_policy_type<Strategy>::type robust_policy_t;

        robust_policy_t robust_policy
                = geometry::get_rescale_policy<robust_policy_t>(
                    geometry1, geometry2, strategy);

        apply(turns, geometry1, geometry2, interrupt_policy, strategy, robust_policy);
    }

    template <typename Turns, typename InterruptPolicy, typename Strategy, typename RobustPolicy>
    static inline void apply(Turns & turns,
                             Geometry1 const& geometry1,
                             Geometry2 const& geometry2,
                             InterruptPolicy & interrupt_policy,
                             Strategy const& strategy,
                             RobustPolicy const& robust_policy)
    {
        static const bool reverse1 = detail::overlay::do_reverse
            <
                geometry::point_order<Geometry1>::value
            >::value;

        static const bool reverse2 = detail::overlay::do_reverse
            <
                geometry::point_order<Geometry2>::value
            >::value;

        dispatch::get_turns
            <
                typename geometry::tag<Geometry1>::type,
                typename geometry::tag<Geometry2>::type,
                Geometry1,
                Geometry2,
                reverse1,
                reverse2,
                GetTurnPolicy
            >::apply(0, geometry1, 1, geometry2,
                     strategy, robust_policy,
                     turns, interrupt_policy);
    }
};

// TURNS SORTING AND SEARCHING

template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0>
struct op_to_int
{
    template <typename Operation>
    inline int operator()(Operation const& op) const
    {
        switch(op.operation)
        {
        case detail::overlay::operation_none : return N;
        case detail::overlay::operation_union : return U;
        case detail::overlay::operation_intersection : return I;
        case detail::overlay::operation_blocked : return B;
        case detail::overlay::operation_continue : return C;
        case detail::overlay::operation_opposite : return O;
        }
        return -1;
    }
};

template <std::size_t OpId, typename OpToInt>
struct less_op_xxx_linear
{
    template <typename Turn>
    inline bool operator()(Turn const& left, Turn const& right) const
    {
        static OpToInt op_to_int;
        return op_to_int(left.operations[OpId]) < op_to_int(right.operations[OpId]);
    }
};

template <std::size_t OpId>
struct less_op_linear_linear
    : less_op_xxx_linear< OpId, op_to_int<0,2,3,1,4,0> >
{};

template <std::size_t OpId>
struct less_op_linear_areal_single
{
    template <typename Turn>
    inline bool operator()(Turn const& left, Turn const& right) const
    {
        static const std::size_t other_op_id = (OpId + 1) % 2;
        static turns::op_to_int<0,2,3,1,4,0> op_to_int_xuic;
        static turns::op_to_int<0,3,2,1,4,0> op_to_int_xiuc;

        segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
        segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;

        typedef typename Turn::turn_operation_type operation_type;
        operation_type const& left_operation = left.operations[OpId];
        operation_type const& right_operation = right.operations[OpId];

        if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
        {
            return op_to_int_xuic(left_operation)
                 < op_to_int_xuic(right_operation);
        }
        else
        {
            return op_to_int_xiuc(left_operation)
                 < op_to_int_xiuc(right_operation);
        }
    }
};

template <std::size_t OpId>
struct less_op_areal_linear
    : less_op_xxx_linear< OpId, op_to_int<0,1,0,0,2,0> >
{};

template <std::size_t OpId>
struct less_op_areal_areal
{
    template <typename Turn>
    inline bool operator()(Turn const& left, Turn const& right) const
    {
        static const std::size_t other_op_id = (OpId + 1) % 2;
        static op_to_int<0, 1, 2, 3, 4, 0> op_to_int_uixc;
        static op_to_int<0, 2, 1, 3, 4, 0> op_to_int_iuxc;

        segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
        segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;

        typedef typename Turn::turn_operation_type operation_type;
        operation_type const& left_operation = left.operations[OpId];
        operation_type const& right_operation = right.operations[OpId];

        if ( left_other_seg_id.multi_index == right_other_seg_id.multi_index )
        {
            if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
            {
                return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
            }
            else
            {
                if ( left_other_seg_id.ring_index == -1 )
                {
                    if ( left_operation.operation == overlay::operation_union )
                        return false;
                    else if ( left_operation.operation == overlay::operation_intersection )
                        return true;
                }
                else if ( right_other_seg_id.ring_index == -1 )
                {
                    if ( right_operation.operation == overlay::operation_union )
                        return true;
                    else if ( right_operation.operation == overlay::operation_intersection )
                        return false;
                }
                
                return op_to_int_iuxc(left_operation) < op_to_int_iuxc(right_operation);
            }
        }
        else
        {
            return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
        }
    }
};

template <std::size_t OpId>
struct less_other_multi_index
{
    static const std::size_t other_op_id = (OpId + 1) % 2;

    template <typename Turn>
    inline bool operator()(Turn const& left, Turn const& right) const
    {
        return left.operations[other_op_id].seg_id.multi_index
             < right.operations[other_op_id].seg_id.multi_index;
    }
};

// sort turns by G1 - source_index == 0 by:
// seg_id -> distance and coordinates -> operation
template <std::size_t OpId, typename LessOp, typename CSTag>
struct less
{
    BOOST_STATIC_ASSERT(OpId < 2);

    template <typename Turn>
    static inline bool use_fraction(Turn const& left, Turn const& right)
    {
        typedef typename geometry::strategy::within::services::default_strategy
            <
                typename Turn::point_type, typename Turn::point_type,
                point_tag, point_tag,
                pointlike_tag, pointlike_tag,
                typename tag_cast<CSTag, spherical_tag>::type,
                typename tag_cast<CSTag, spherical_tag>::type
            >::type eq_pp_strategy_type;

        static LessOp less_op;

        // NOTE: Assuming fraction is more permissive and faster than
        //       comparison of points with strategy.
        return geometry::math::equals(left.operations[OpId].fraction,
                                      right.operations[OpId].fraction)
                && eq_pp_strategy_type::apply(left.point, right.point)
             ?
             less_op(left, right)
             :
             (left.operations[OpId].fraction < right.operations[OpId].fraction)
             ;
    }

    template <typename Turn>
    inline bool operator()(Turn const& left, Turn const& right) const
    {
        segment_identifier const& sl = left.operations[OpId].seg_id;
        segment_identifier const& sr = right.operations[OpId].seg_id;

        return sl < sr || ( sl == sr && use_fraction(left, right) );
    }
};

}}} // namespace detail::relate::turns
#endif // DOXYGEN_NO_DETAIL

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2
	3	// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
	4
20effc67 TL	5	// This file was modified by Oracle on 2013-2020.
20effc67 TL	6	// Modifications copyright (c) 2013-2020 Oracle and/or its affiliates.
7c673cae FG	7
	8	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
	9	// Contributed and/or modified by Menelaos Karavelas, 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_RELATE_TURNS_HPP
	16	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP
	17
20effc67	18
7c673cae FG	19	#include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
	20	#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
	21	#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
	22
	23	#include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
92f5a8d4 TL	24	#include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
	25
	26	#include <boost/geometry/strategies/cartesian/point_in_point.hpp>
	27	#include <boost/geometry/strategies/spherical/point_in_point.hpp>
20effc67	28	#include <boost/geometry/strategies/distance.hpp>
7c673cae FG	29
	30
	31	namespace boost { namespace geometry {
	32
	33	#ifndef DOXYGEN_NO_DETAIL
	34	namespace detail { namespace relate { namespace turns {
	35
	36	template <bool IncludeDegenerate = false>
	37	struct assign_policy
	38	: overlay::assign_null_policy
	39	{
	40	static bool const include_degenerate = IncludeDegenerate;
	41	};
	42
	43	// GET_TURNS
	44
	45	template
	46	<
	47	typename Geometry1,
	48	typename Geometry2,
	49	typename GetTurnPolicy = detail::get_turns::get_turn_info_type
	50	<
	51	Geometry1, Geometry2, assign_policy<>
92f5a8d4	52	>
7c673cae FG	53	>
	54	struct get_turns
	55	{
	56	typedef typename geometry::point_type<Geometry1>::type point1_type;
	57
92f5a8d4 TL	58	template <typename Strategy>
	59	struct robust_policy_type
	60	: geometry::rescale_overlay_policy_type
	61	<
	62	Geometry1,
	63	Geometry2,
	64	typename Strategy::cs_tag
	65	>
	66	{};
	67
	68	template
	69	<
	70	typename Strategy,
	71	typename RobustPolicy = typename robust_policy_type<Strategy>::type
	72	>
	73	struct turn_info_type
	74	{
	75	typedef typename segment_ratio_type<point1_type, RobustPolicy>::type ratio_type;
	76	typedef overlay::turn_info
7c673cae FG	77	<
7c673cae FG	78	point1_type,
92f5a8d4	79	ratio_type,
7c673cae FG	80	typename detail::get_turns::turn_operation_type
7c673cae FG	81	<
92f5a8d4	82	Geometry1, Geometry2, ratio_type
7c673cae	83	>::type
92f5a8d4 TL	84	> type;
92f5a8d4 TL	85	};
7c673cae	86
1e59de90	87	template <typename Turns, typename InterruptPolicy, typename Strategy>
7c673cae FG	88	static inline void apply(Turns & turns,
	89	Geometry1 const& geometry1,
	90	Geometry2 const& geometry2,
b32b8144	91	InterruptPolicy & interrupt_policy,
1e59de90	92	Strategy const& strategy)
7c673cae	93	{
1e59de90	94	typedef typename robust_policy_type<Strategy>::type robust_policy_t;
92f5a8d4 TL	95
	96	robust_policy_t robust_policy
	97	= geometry::get_rescale_policy<robust_policy_t>(
1e59de90	98	geometry1, geometry2, strategy);
7c673cae	99
1e59de90	100	apply(turns, geometry1, geometry2, interrupt_policy, strategy, robust_policy);
7c673cae FG	101	}
7c673cae FG	102
1e59de90	103	template <typename Turns, typename InterruptPolicy, typename Strategy, typename RobustPolicy>
7c673cae FG	104	static inline void apply(Turns & turns,
	105	Geometry1 const& geometry1,
	106	Geometry2 const& geometry2,
	107	InterruptPolicy & interrupt_policy,
1e59de90	108	Strategy const& strategy,
7c673cae FG	109	RobustPolicy const& robust_policy)
	110	{
	111	static const bool reverse1 = detail::overlay::do_reverse
	112	<
	113	geometry::point_order<Geometry1>::value
	114	>::value;
	115
	116	static const bool reverse2 = detail::overlay::do_reverse
	117	<
	118	geometry::point_order<Geometry2>::value
	119	>::value;
	120
	121	dispatch::get_turns
	122	<
	123	typename geometry::tag<Geometry1>::type,
	124	typename geometry::tag<Geometry2>::type,
	125	Geometry1,
	126	Geometry2,
	127	reverse1,
	128	reverse2,
	129	GetTurnPolicy
	130	>::apply(0, geometry1, 1, geometry2,
1e59de90	131	strategy, robust_policy,
b32b8144	132	turns, interrupt_policy);
7c673cae FG	133	}
	134	};
	135
	136	// TURNS SORTING AND SEARCHING
	137
	138	template <int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0>
	139	struct op_to_int
	140	{
	141	template <typename Operation>
	142	inline int operator()(Operation const& op) const
	143	{
	144	switch(op.operation)
	145	{
	146	case detail::overlay::operation_none : return N;
	147	case detail::overlay::operation_union : return U;
	148	case detail::overlay::operation_intersection : return I;
	149	case detail::overlay::operation_blocked : return B;
	150	case detail::overlay::operation_continue : return C;
	151	case detail::overlay::operation_opposite : return O;
	152	}
	153	return -1;
	154	}
	155	};
	156
	157	template <std::size_t OpId, typename OpToInt>
	158	struct less_op_xxx_linear
	159	{
	160	template <typename Turn>
	161	inline bool operator()(Turn const& left, Turn const& right) const
	162	{
	163	static OpToInt op_to_int;
	164	return op_to_int(left.operations[OpId]) < op_to_int(right.operations[OpId]);
	165	}
	166	};
	167
	168	template <std::size_t OpId>
	169	struct less_op_linear_linear
	170	: less_op_xxx_linear< OpId, op_to_int<0,2,3,1,4,0> >
	171	{};
	172
	173	template <std::size_t OpId>
	174	struct less_op_linear_areal_single
	175	{
	176	template <typename Turn>
	177	inline bool operator()(Turn const& left, Turn const& right) const
	178	{
	179	static const std::size_t other_op_id = (OpId + 1) % 2;
	180	static turns::op_to_int<0,2,3,1,4,0> op_to_int_xuic;
	181	static turns::op_to_int<0,3,2,1,4,0> op_to_int_xiuc;
	182
	183	segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
	184	segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
	185
	186	typedef typename Turn::turn_operation_type operation_type;
	187	operation_type const& left_operation = left.operations[OpId];
	188	operation_type const& right_operation = right.operations[OpId];
	189
	190	if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
	191	{
	192	return op_to_int_xuic(left_operation)
	193	< op_to_int_xuic(right_operation);
	194	}
	195	else
	196	{
197	return op_to_int_xiuc(left_operation)
198	< op_to_int_xiuc(right_operation);
199	}
200	}
201	};
202
203	template <std::size_t OpId>
204	struct less_op_areal_linear
205	: less_op_xxx_linear< OpId, op_to_int<0,1,0,0,2,0> >
206	{};
207
208	template <std::size_t OpId>
209	struct less_op_areal_areal
210	{
211	template <typename Turn>
212	inline bool operator()(Turn const& left, Turn const& right) const
213	{
214	static const std::size_t other_op_id = (OpId + 1) % 2;
215	static op_to_int<0, 1, 2, 3, 4, 0> op_to_int_uixc;
216	static op_to_int<0, 2, 1, 3, 4, 0> op_to_int_iuxc;
217
218	segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id;
219	segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id;
220
221	typedef typename Turn::turn_operation_type operation_type;
222	operation_type const& left_operation = left.operations[OpId];
223	operation_type const& right_operation = right.operations[OpId];
224
225	if ( left_other_seg_id.multi_index == right_other_seg_id.multi_index )
226	{
227	if ( left_other_seg_id.ring_index == right_other_seg_id.ring_index )
228	{
229	return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
230	}
231	else
232	{
233	if ( left_other_seg_id.ring_index == -1 )
234	{
235	if ( left_operation.operation == overlay::operation_union )
236	return false;
237	else if ( left_operation.operation == overlay::operation_intersection )
238	return true;
239	}
240	else if ( right_other_seg_id.ring_index == -1 )
241	{
242	if ( right_operation.operation == overlay::operation_union )
243	return true;
244	else if ( right_operation.operation == overlay::operation_intersection )
245	return false;
246	}
247
248	return op_to_int_iuxc(left_operation) < op_to_int_iuxc(right_operation);
249	}
250	}
251	else
252	{
253	return op_to_int_uixc(left_operation) < op_to_int_uixc(right_operation);
254	}
255	}
256	};
257
258	template <std::size_t OpId>
259	struct less_other_multi_index
260	{
261	static const std::size_t other_op_id = (OpId + 1) % 2;
262
263	template <typename Turn>
264	inline bool operator()(Turn const& left, Turn const& right) const
265	{
266	return left.operations[other_op_id].seg_id.multi_index
267	< right.operations[other_op_id].seg_id.multi_index;
268	}
269	};
270
271	// sort turns by G1 - source_index == 0 by:
92f5a8d4 TL	272	// seg_id -> distance and coordinates -> operation
92f5a8d4 TL	273	template <std::size_t OpId, typename LessOp, typename CSTag>
7c673cae FG	274	struct less
	275	{
	276	BOOST_STATIC_ASSERT(OpId < 2);
	277
	278	template <typename Turn>
	279	static inline bool use_fraction(Turn const& left, Turn const& right)
	280	{
92f5a8d4 TL	281	typedef typename geometry::strategy::within::services::default_strategy
	282	<
	283	typename Turn::point_type, typename Turn::point_type,
	284	point_tag, point_tag,
	285	pointlike_tag, pointlike_tag,
	286	typename tag_cast<CSTag, spherical_tag>::type,
	287	typename tag_cast<CSTag, spherical_tag>::type
	288	>::type eq_pp_strategy_type;
	289
7c673cae FG	290	static LessOp less_op;
7c673cae FG	291
92f5a8d4 TL	292	// NOTE: Assuming fraction is more permissive and faster than
	293	// comparison of points with strategy.
	294	return geometry::math::equals(left.operations[OpId].fraction,
	295	right.operations[OpId].fraction)
	296	&& eq_pp_strategy_type::apply(left.point, right.point)
	297	?
	298	less_op(left, right)
	299	:
	300	(left.operations[OpId].fraction < right.operations[OpId].fraction)
	301	;
7c673cae FG	302	}
	303
	304	template <typename Turn>
	305	inline bool operator()(Turn const& left, Turn const& right) const
	306	{
	307	segment_identifier const& sl = left.operations[OpId].seg_id;
	308	segment_identifier const& sr = right.operations[OpId].seg_id;
	309
	310	return sl < sr \|\| ( sl == sr && use_fraction(left, right) );
	311	}
	312	};
	313
	314	}}} // namespace detail::relate::turns
	315	#endif // DOXYGEN_NO_DETAIL
	316
	317	}} // namespace boost::geometry
	318
	319	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_TURNS_HPP