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

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

// Copyright (c) 2014-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

// Licensed under the Boost Software License version 1.0.
// http://www.boost.org/users/license.html

#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP

#include <algorithm>
#include <vector>

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

#include <boost/geometry/core/tag.hpp>
#include <boost/geometry/core/tags.hpp>

#include <boost/geometry/algorithms/detail/relate/turns.hpp>

#include <boost/geometry/algorithms/detail/turns/compare_turns.hpp>
#include <boost/geometry/algorithms/detail/turns/filter_continue_turns.hpp>
#include <boost/geometry/algorithms/detail/turns/remove_duplicate_turns.hpp>

#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
#include <boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp>

#include <boost/geometry/algorithms/convert.hpp>


namespace boost { namespace geometry
{


#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{


template
<
    typename LineStringOut,
    overlay_type OverlayType,
    typename Geometry,
    typename GeometryTag
>
struct linear_linear_no_intersections;


template <typename LineStringOut, typename LineString>
struct linear_linear_no_intersections
    <
        LineStringOut, overlay_difference, LineString, linestring_tag
    >
{
    template <typename OutputIterator>
    static inline OutputIterator apply(LineString const& linestring,
                                       OutputIterator oit)
    {
        LineStringOut ls_out;
        geometry::convert(linestring, ls_out);
        *oit++ = ls_out;
        return oit;
    }
};


template <typename LineStringOut, typename MultiLineString>
struct linear_linear_no_intersections
    <
        LineStringOut,
        overlay_difference,
        MultiLineString,
        multi_linestring_tag
    >
{
    template <typename OutputIterator>
    static inline OutputIterator apply(MultiLineString const& multilinestring,
                                       OutputIterator oit)
    {
        for (typename boost::range_iterator<MultiLineString const>::type
                 it = boost::begin(multilinestring);
             it != boost::end(multilinestring); ++it)
        {
            LineStringOut ls_out;
            geometry::convert(*it, ls_out);
            *oit++ = ls_out;
        }
        return oit;
    }
};


template <typename LineStringOut, typename Geometry, typename GeometryTag>
struct linear_linear_no_intersections
    <
        LineStringOut, overlay_intersection, Geometry, GeometryTag
    >
{
    template <typename OutputIterator>
    static inline OutputIterator apply(Geometry const&,
                                       OutputIterator oit)
    {
        return oit;
    }
};


template
<
    typename Linear1,
    typename Linear2,
    typename LinestringOut,
    overlay_type OverlayType,
    bool EnableFilterContinueTurns = false,
    bool EnableRemoveDuplicateTurns = false,
    bool EnableDegenerateTurns = true,
#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
    bool EnableFollowIsolatedPoints = false
#else
    bool EnableFollowIsolatedPoints = true
#endif
>
class linear_linear_linestring
{
protected:
    struct assign_policy
    {
        static bool const include_no_turn = false;
        static bool const include_degenerate = EnableDegenerateTurns;
        static bool const include_opposite = false;
        static bool const include_start_turn = false;
    };


    template
    <
        typename Turns,
        typename LinearGeometry1,
        typename LinearGeometry2,
        typename Strategy,
        typename RobustPolicy
    >
    static inline void compute_turns(Turns& turns,
                                     LinearGeometry1 const& linear1,
                                     LinearGeometry2 const& linear2,
                                     Strategy const& strategy,
                                     RobustPolicy const& robust_policy)
    {
        turns.clear();

        detail::get_turns::no_interrupt_policy interrupt_policy;

        geometry::detail::relate::turns::get_turns
            <
                LinearGeometry1,
                LinearGeometry2,
                detail::get_turns::get_turn_info_type
                <
                    LinearGeometry1,
                    LinearGeometry2,
                    assign_policy
                >
            >::apply(turns, linear1, linear2, interrupt_policy, strategy, robust_policy);
    }


    template
    <
        overlay_type OverlayTypeForFollow,
        bool FollowIsolatedPoints,
        typename Turns,
        typename LinearGeometry1,
        typename LinearGeometry2,
        typename OutputIterator,
        typename Strategy
    >
    static inline OutputIterator
    sort_and_follow_turns(Turns& turns,
                          LinearGeometry1 const& linear1,
                          LinearGeometry2 const& linear2,
                          OutputIterator oit,
                          Strategy const& strategy)
    {
        // remove turns that have no added value
        turns::filter_continue_turns
            <
                Turns,
                EnableFilterContinueTurns && OverlayType != overlay_intersection
            >::apply(turns);

        // sort by seg_id, distance, and operation
        std::sort(boost::begin(turns), boost::end(turns),
                  detail::turns::less_seg_fraction_other_op<>());

        // remove duplicate turns
        turns::remove_duplicate_turns
            <
                Turns, EnableRemoveDuplicateTurns
            >::apply(turns);

        return detail::overlay::following::linear::follow
            <
                LinestringOut,
                LinearGeometry1,
                LinearGeometry2,
                OverlayTypeForFollow,
                FollowIsolatedPoints,
                !EnableFilterContinueTurns || OverlayType == overlay_intersection
            >::apply(linear1, linear2, boost::begin(turns), boost::end(turns),
                     oit, strategy);
    }

public:
    template
    <
        typename RobustPolicy, typename OutputIterator, typename Strategy
    >
    static inline OutputIterator apply(Linear1 const& linear1,
                                       Linear2 const& linear2,
                                       RobustPolicy const& robust_policy,
                                       OutputIterator oit,
                                       Strategy const& strategy)
    {
        typedef typename detail::relate::turns::get_turns
            <
                Linear1,
                Linear2,
                detail::get_turns::get_turn_info_type
                    <
                        Linear1,
                        Linear2,
                        assign_policy
                    >
            >::template turn_info_type<Strategy, RobustPolicy>::type turn_info;

        typedef std::vector<turn_info> turns_container;

        turns_container turns;
        compute_turns(turns, linear1, linear2, strategy, robust_policy);

        if ( turns.empty() )
        {
            // the two linear geometries are disjoint
            return linear_linear_no_intersections
                <
                    LinestringOut,
                    OverlayType,
                    Linear1,
                    typename tag<Linear1>::type
                >::apply(linear1, oit);
        }

        return sort_and_follow_turns
            <
                OverlayType,
                EnableFollowIsolatedPoints
                && OverlayType == overlay_intersection
            >(turns, linear1, linear2, oit, strategy);
    }
};


template
<
    typename Linear1,
    typename Linear2,
    typename LinestringOut,
    bool EnableFilterContinueTurns,
    bool EnableRemoveDuplicateTurns,
    bool EnableDegenerateTurns,
    bool EnableFollowIsolatedPoints
>
struct linear_linear_linestring
    <
        Linear1, Linear2, LinestringOut, overlay_union,
        EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
        EnableDegenerateTurns, EnableFollowIsolatedPoints
    >
{
    template
    <
        typename RobustPolicy, typename OutputIterator, typename Strategy
    >
    static inline OutputIterator apply(Linear1 const& linear1,
                                       Linear2 const& linear2,
                                       RobustPolicy const& robust_policy,
                                       OutputIterator oit,
                                       Strategy const& strategy)
    {
        oit = linear_linear_no_intersections
            <
                LinestringOut,
                overlay_difference,
                Linear1,
                typename tag<Linear1>::type
            >::apply(linear1, oit);

        return linear_linear_linestring
            <
                Linear2, Linear1, LinestringOut, overlay_difference,
                EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
                EnableDegenerateTurns, EnableFollowIsolatedPoints
            >::apply(linear2, linear1, robust_policy, oit, strategy);
    }
};


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


}} // namespace boost::geometry


#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
7c673cae FG	2
20effc67	3	// Copyright (c) 2014-2020, Oracle and/or its affiliates.
7c673cae	4	// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
b32b8144	5	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
7c673cae	6
20effc67 TL	7	// Licensed under the Boost Software License version 1.0.
20effc67 TL	8	// http://www.boost.org/users/license.html
7c673cae FG	9
	10	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
	11	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
	12
	13	#include <algorithm>
	14	#include <vector>
	15
20effc67 TL	16	#include <boost/range/begin.hpp>
20effc67 TL	17	#include <boost/range/end.hpp>
7c673cae FG	18
	19	#include <boost/geometry/core/tag.hpp>
	20	#include <boost/geometry/core/tags.hpp>
	21
	22	#include <boost/geometry/algorithms/detail/relate/turns.hpp>
	23
	24	#include <boost/geometry/algorithms/detail/turns/compare_turns.hpp>
	25	#include <boost/geometry/algorithms/detail/turns/filter_continue_turns.hpp>
	26	#include <boost/geometry/algorithms/detail/turns/remove_duplicate_turns.hpp>
	27
	28	#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
	29	#include <boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp>
	30
	31	#include <boost/geometry/algorithms/convert.hpp>
	32
	33
	34
	35	namespace boost { namespace geometry
	36	{
	37
	38
	39	#ifndef DOXYGEN_NO_DETAIL
	40	namespace detail { namespace overlay
	41	{
	42
	43
	44	template
	45	<
	46	typename LineStringOut,
	47	overlay_type OverlayType,
	48	typename Geometry,
	49	typename GeometryTag
	50	>
	51	struct linear_linear_no_intersections;
	52
	53
	54	template <typename LineStringOut, typename LineString>
	55	struct linear_linear_no_intersections
	56	<
	57	LineStringOut, overlay_difference, LineString, linestring_tag
	58	>
	59	{
	60	template <typename OutputIterator>
	61	static inline OutputIterator apply(LineString const& linestring,
	62	OutputIterator oit)
	63	{
	64	LineStringOut ls_out;
	65	geometry::convert(linestring, ls_out);
	66	*oit++ = ls_out;
	67	return oit;
	68	}
	69	};
	70
	71
	72	template <typename LineStringOut, typename MultiLineString>
	73	struct linear_linear_no_intersections
	74	<
	75	LineStringOut,
	76	overlay_difference,
	77	MultiLineString,
	78	multi_linestring_tag
	79	>
	80	{
	81	template <typename OutputIterator>
82	static inline OutputIterator apply(MultiLineString const& multilinestring,
83	OutputIterator oit)
84	{
85	for (typename boost::range_iterator<MultiLineString const>::type
86	it = boost::begin(multilinestring);
87	it != boost::end(multilinestring); ++it)
88	{
89	LineStringOut ls_out;
90	geometry::convert(*it, ls_out);
91	*oit++ = ls_out;
92	}
93	return oit;
94	}
95	};
96
97
98	template <typename LineStringOut, typename Geometry, typename GeometryTag>
99	struct linear_linear_no_intersections
100	<
101	LineStringOut, overlay_intersection, Geometry, GeometryTag
102	>
103	{
104	template <typename OutputIterator>
105	static inline OutputIterator apply(Geometry const&,
106	OutputIterator oit)
107	{
108	return oit;
109	}
110	};
111
112
113
114
115
116
117
118	template
119	<
120	typename Linear1,
121	typename Linear2,
122	typename LinestringOut,
123	overlay_type OverlayType,
124	bool EnableFilterContinueTurns = false,
125	bool EnableRemoveDuplicateTurns = false,
126	bool EnableDegenerateTurns = true,
127	#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
128	bool EnableFollowIsolatedPoints = false
129	#else
130	bool EnableFollowIsolatedPoints = true
131	#endif
132	>
133	class linear_linear_linestring
134	{
135	protected:
136	struct assign_policy
137	{
138	static bool const include_no_turn = false;
139	static bool const include_degenerate = EnableDegenerateTurns;
140	static bool const include_opposite = false;
20effc67	141	static bool const include_start_turn = false;
7c673cae FG	142	};
	143
	144
	145	template
	146	<
	147	typename Turns,
	148	typename LinearGeometry1,
	149	typename LinearGeometry2,
1e59de90	150	typename Strategy,
7c673cae FG	151	typename RobustPolicy
	152	>
	153	static inline void compute_turns(Turns& turns,
	154	LinearGeometry1 const& linear1,
	155	LinearGeometry2 const& linear2,
1e59de90	156	Strategy const& strategy,
7c673cae FG	157	RobustPolicy const& robust_policy)
	158	{
	159	turns.clear();
	160
	161	detail::get_turns::no_interrupt_policy interrupt_policy;
	162
	163	geometry::detail::relate::turns::get_turns
	164	<
	165	LinearGeometry1,
	166	LinearGeometry2,
	167	detail::get_turns::get_turn_info_type
	168	<
	169	LinearGeometry1,
	170	LinearGeometry2,
	171	assign_policy
92f5a8d4	172	>
b32b8144	173	>::apply(turns, linear1, linear2, interrupt_policy, strategy, robust_policy);
7c673cae FG	174	}
	175
	176
	177	template
	178	<
	179	overlay_type OverlayTypeForFollow,
	180	bool FollowIsolatedPoints,
	181	typename Turns,
	182	typename LinearGeometry1,
	183	typename LinearGeometry2,
b32b8144	184	typename OutputIterator,
1e59de90	185	typename Strategy
7c673cae FG	186	>
	187	static inline OutputIterator
	188	sort_and_follow_turns(Turns& turns,
	189	LinearGeometry1 const& linear1,
	190	LinearGeometry2 const& linear2,
b32b8144	191	OutputIterator oit,
1e59de90	192	Strategy const& strategy)
7c673cae FG	193	{
	194	// remove turns that have no added value
	195	turns::filter_continue_turns
	196	<
	197	Turns,
	198	EnableFilterContinueTurns && OverlayType != overlay_intersection
	199	>::apply(turns);
	200
	201	// sort by seg_id, distance, and operation
	202	std::sort(boost::begin(turns), boost::end(turns),
	203	detail::turns::less_seg_fraction_other_op<>());
	204
	205	// remove duplicate turns
	206	turns::remove_duplicate_turns
	207	<
	208	Turns, EnableRemoveDuplicateTurns
	209	>::apply(turns);
	210
	211	return detail::overlay::following::linear::follow
	212	<
	213	LinestringOut,
	214	LinearGeometry1,
	215	LinearGeometry2,
	216	OverlayTypeForFollow,
	217	FollowIsolatedPoints,
	218	!EnableFilterContinueTurns \|\| OverlayType == overlay_intersection
	219	>::apply(linear1, linear2, boost::begin(turns), boost::end(turns),
1e59de90	220	oit, strategy);
7c673cae FG	221	}
	222
	223	public:
	224	template
	225	<
	226	typename RobustPolicy, typename OutputIterator, typename Strategy
	227	>
	228	static inline OutputIterator apply(Linear1 const& linear1,
	229	Linear2 const& linear2,
	230	RobustPolicy const& robust_policy,
	231	OutputIterator oit,
b32b8144	232	Strategy const& strategy)
7c673cae FG	233	{
	234	typedef typename detail::relate::turns::get_turns
	235	<
	236	Linear1,
	237	Linear2,
	238	detail::get_turns::get_turn_info_type
92f5a8d4 TL	239	<
	240	Linear1,
	241	Linear2,
	242	assign_policy
	243	>
	244	>::template turn_info_type<Strategy, RobustPolicy>::type turn_info;
7c673cae FG	245
	246	typedef std::vector<turn_info> turns_container;
	247
	248	turns_container turns;
b32b8144	249	compute_turns(turns, linear1, linear2, strategy, robust_policy);
7c673cae FG	250
	251	if ( turns.empty() )
	252	{
	253	// the two linear geometries are disjoint
	254	return linear_linear_no_intersections
	255	<
	256	LinestringOut,
	257	OverlayType,
	258	Linear1,
	259	typename tag<Linear1>::type
	260	>::apply(linear1, oit);
	261	}
	262
	263	return sort_and_follow_turns
	264	<
	265	OverlayType,
	266	EnableFollowIsolatedPoints
	267	&& OverlayType == overlay_intersection
b32b8144	268	>(turns, linear1, linear2, oit, strategy);
7c673cae FG	269	}
	270	};
	271
	272
	273
	274
	275	template
	276	<
	277	typename Linear1,
	278	typename Linear2,
	279	typename LinestringOut,
	280	bool EnableFilterContinueTurns,
	281	bool EnableRemoveDuplicateTurns,
	282	bool EnableDegenerateTurns,
	283	bool EnableFollowIsolatedPoints
	284	>
	285	struct linear_linear_linestring
	286	<
	287	Linear1, Linear2, LinestringOut, overlay_union,
	288	EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
	289	EnableDegenerateTurns, EnableFollowIsolatedPoints
	290	>
	291	{
	292	template
	293	<
	294	typename RobustPolicy, typename OutputIterator, typename Strategy
	295	>
	296	static inline OutputIterator apply(Linear1 const& linear1,
	297	Linear2 const& linear2,
	298	RobustPolicy const& robust_policy,
	299	OutputIterator oit,
	300	Strategy const& strategy)
	301	{
	302	oit = linear_linear_no_intersections
	303	<
	304	LinestringOut,
	305	overlay_difference,
	306	Linear1,
	307	typename tag<Linear1>::type
	308	>::apply(linear1, oit);
	309
	310	return linear_linear_linestring
	311	<
	312	Linear2, Linear1, LinestringOut, overlay_difference,
	313	EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
	314	EnableDegenerateTurns, EnableFollowIsolatedPoints
	315	>::apply(linear2, linear1, robust_policy, oit, strategy);
	316	}
	317	};
	318
	319
	320
	321
	322	}} // namespace detail::overlay
	323	#endif // DOXYGEN_NO_DETAIL
	324
	325
	326	}} // namespace boost::geometry
	327
	328
	329
	330	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP