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

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

// Copyright (c) 2014-2019, Oracle and/or its affiliates.

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

// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle


#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.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;
    };


    template
    <
        typename Turns,
        typename LinearGeometry1,
        typename LinearGeometry2,
        typename IntersectionStrategy,
        typename RobustPolicy
    >
    static inline void compute_turns(Turns& turns,
                                     LinearGeometry1 const& linear1,
                                     LinearGeometry2 const& linear2,
                                     IntersectionStrategy 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 IntersectionStrategy
    >
    static inline OutputIterator
    sort_and_follow_turns(Turns& turns,
                          LinearGeometry1 const& linear1,
                          LinearGeometry2 const& linear2,
                          OutputIterator oit,
                          IntersectionStrategy 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.get_side_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
92f5a8d4	3	// Copyright (c) 2014-2019, Oracle and/or its affiliates.
7c673cae FG	4
	5	// Licensed under the Boost Software License version 1.0.
	6	// http://www.boost.org/users/license.html
	7
	8	// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
b32b8144	9	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
7c673cae FG	10
	11
	12	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
	13	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
	14
	15	#include <algorithm>
	16	#include <vector>
	17
	18	#include <boost/range.hpp>
	19
	20	#include <boost/geometry/core/tag.hpp>
	21	#include <boost/geometry/core/tags.hpp>
	22
	23	#include <boost/geometry/algorithms/detail/relate/turns.hpp>
	24
	25	#include <boost/geometry/algorithms/detail/turns/compare_turns.hpp>
	26	#include <boost/geometry/algorithms/detail/turns/filter_continue_turns.hpp>
	27	#include <boost/geometry/algorithms/detail/turns/remove_duplicate_turns.hpp>
	28
	29	#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
	30	#include <boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp>
	31
	32	#include <boost/geometry/algorithms/convert.hpp>
	33
	34
	35
	36	namespace boost { namespace geometry
	37	{
	38
	39
	40	#ifndef DOXYGEN_NO_DETAIL
	41	namespace detail { namespace overlay
	42	{
	43
	44
	45	template
	46	<
	47	typename LineStringOut,
	48	overlay_type OverlayType,
	49	typename Geometry,
	50	typename GeometryTag
	51	>
	52	struct linear_linear_no_intersections;
	53
	54
	55	template <typename LineStringOut, typename LineString>
	56	struct linear_linear_no_intersections
	57	<
	58	LineStringOut, overlay_difference, LineString, linestring_tag
	59	>
	60	{
	61	template <typename OutputIterator>
	62	static inline OutputIterator apply(LineString const& linestring,
	63	OutputIterator oit)
	64	{
	65	LineStringOut ls_out;
	66	geometry::convert(linestring, ls_out);
	67	*oit++ = ls_out;
	68	return oit;
	69	}
	70	};
	71
	72
	73	template <typename LineStringOut, typename MultiLineString>
74	struct linear_linear_no_intersections
75	<
76	LineStringOut,
77	overlay_difference,
78	MultiLineString,
79	multi_linestring_tag
80	>
81	{
82	template <typename OutputIterator>
83	static inline OutputIterator apply(MultiLineString const& multilinestring,
84	OutputIterator oit)
85	{
86	for (typename boost::range_iterator<MultiLineString const>::type
87	it = boost::begin(multilinestring);
88	it != boost::end(multilinestring); ++it)
89	{
90	LineStringOut ls_out;
91	geometry::convert(*it, ls_out);
92	*oit++ = ls_out;
93	}
94	return oit;
95	}
96	};
97
98
99	template <typename LineStringOut, typename Geometry, typename GeometryTag>
100	struct linear_linear_no_intersections
101	<
102	LineStringOut, overlay_intersection, Geometry, GeometryTag
103	>
104	{
105	template <typename OutputIterator>
106	static inline OutputIterator apply(Geometry const&,
107	OutputIterator oit)
108	{
109	return oit;
110	}
111	};
112
113
114
115
116
117
118
119	template
120	<
121	typename Linear1,
122	typename Linear2,
123	typename LinestringOut,
124	overlay_type OverlayType,
125	bool EnableFilterContinueTurns = false,
126	bool EnableRemoveDuplicateTurns = false,
127	bool EnableDegenerateTurns = true,
128	#ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
129	bool EnableFollowIsolatedPoints = false
130	#else
131	bool EnableFollowIsolatedPoints = true
132	#endif
133	>
134	class linear_linear_linestring
135	{
136	protected:
137	struct assign_policy
138	{
139	static bool const include_no_turn = false;
140	static bool const include_degenerate = EnableDegenerateTurns;
141	static bool const include_opposite = false;
7c673cae FG	142	};
	143
	144
	145	template
	146	<
	147	typename Turns,
	148	typename LinearGeometry1,
	149	typename LinearGeometry2,
b32b8144	150	typename IntersectionStrategy,
7c673cae FG	151	typename RobustPolicy
	152	>
	153	static inline void compute_turns(Turns& turns,
	154	LinearGeometry1 const& linear1,
	155	LinearGeometry2 const& linear2,
b32b8144	156	IntersectionStrategy 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 FG	184	typename OutputIterator,
b32b8144 FG	185	typename IntersectionStrategy
7c673cae FG	186	>
	187	static inline OutputIterator
	188	sort_and_follow_turns(Turns& turns,
	189	LinearGeometry1 const& linear1,
	190	LinearGeometry2 const& linear2,
b32b8144 FG	191	OutputIterator oit,
b32b8144 FG	192	IntersectionStrategy 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),
b32b8144	220	oit, strategy.get_side_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