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

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

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

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

// 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_OVERLAY_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP


#include <deque>
#include <map>

#include <boost/range.hpp>
#include <boost/mpl/assert.hpp>


#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
#include <boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>

#include <boost/geometry/algorithms/detail/recalculate.hpp>

#include <boost/geometry/algorithms/is_empty.hpp>
#include <boost/geometry/algorithms/reverse.hpp>

#include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
#include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
#include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
#include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>

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

#include <boost/geometry/util/condition.hpp>

#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
#  include <boost/geometry/io/dsv/write.hpp>
#endif


namespace boost { namespace geometry
{


#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{


//! Default visitor for overlay, doing nothing
struct overlay_null_visitor
{
    void print(char const* ) {}

    template <typename Turns>
    void print(char const* , Turns const& , int) {}

    template <typename Turns>
    void print(char const* , Turns const& , int , int ) {}

    template <typename Turns>
    void visit_turns(int , Turns const& ) {}

    template <typename Clusters, typename Turns>
    void visit_clusters(Clusters const& , Turns const& ) {}

    template <typename Turns, typename Turn, typename Operation>
    void visit_traverse(Turns const& , Turn const& , Operation const& , char const*)
    {}

    template <typename Turns, typename Turn, typename Operation>
    void visit_traverse_reject(Turns const& , Turn const& , Operation const& , traverse_error_type )
    {}

    template <typename Rings>
    void visit_generated_rings(Rings const& )
    {}
};

template
<
    overlay_type OverlayType,
    typename TurnInfoMap,
    typename Turns,
    typename Clusters
>
inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns, Clusters const& clusters)
{
    typedef typename boost::range_value<Turns>::type turn_type;
    typedef typename turn_type::turn_operation_type turn_operation_type;
    typedef typename turn_type::container_type container_type;

    static const operation_type target_operation
            = operation_from_overlay<OverlayType>::value;
    static const operation_type opposite_operation
            = target_operation == operation_union
            ? operation_intersection
            : operation_union;

    for (typename boost::range_iterator<Turns const>::type
            it = boost::begin(turns);
         it != boost::end(turns);
         ++it)
    {
        turn_type const& turn = *it;

        bool cluster_checked = false;
        bool has_blocked = false;

        for (typename boost::range_iterator<container_type const>::type
                op_it = boost::begin(turn.operations);
            op_it != boost::end(turn.operations);
            ++op_it)
        {
            turn_operation_type const& op = *op_it;
            ring_identifier const ring_id
                (
                    op.seg_id.source_index,
                    op.seg_id.multi_index,
                    op.seg_id.ring_index
                );

            if (! is_self_turn<OverlayType>(turn)
                && (
                    (BOOST_GEOMETRY_CONDITION(target_operation == operation_union)
                      && op.enriched.count_left > 0)
                  || (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection)
                      && op.enriched.count_right <= 2)))
            {
                // Avoid including untraversed rings which have polygons on
                // their left side (union) or not two on their right side (int)
                // This can only be done for non-self-turns because of count
                // information
                turn_info_map[ring_id].has_blocked_turn = true;
                continue;
            }

            if (turn.any_blocked())
            {
                turn_info_map[ring_id].has_blocked_turn = true;
            }
            if (turn_info_map[ring_id].has_traversed_turn
                    || turn_info_map[ring_id].has_blocked_turn)
            {
                continue;
            }

            // Check information in colocated turns
            if (! cluster_checked && turn.is_clustered())
            {
                check_colocation(has_blocked, turn.cluster_id, turns, clusters);
                cluster_checked = true;
            }

            // Block rings where any other turn is blocked,
            // and (with exceptions): i for union and u for intersection
            // Exceptions: don't block self-uu for intersection
            //             don't block self-ii for union
            //             don't block (for union) i/u if there is an self-ii too
            if (has_blocked
                || (op.operation == opposite_operation
                    && ! turn.has_colocated_both
                    && ! (turn.both(opposite_operation)
                          && is_self_turn<OverlayType>(turn))))
            {
                turn_info_map[ring_id].has_blocked_turn = true;
            }
        }
    }
}

template
<
    typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
    typename Geometry1, typename Geometry2,
    typename OutputIterator, typename Strategy
>
inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
            Geometry2 const& geometry2,
            OutputIterator out, Strategy const& strategy)
{
    typedef std::deque
        <
            typename geometry::ring_type<GeometryOut>::type
        > ring_container_type;

    typedef typename geometry::point_type<Geometry1>::type point_type1;

    typedef ring_properties
        <
            point_type1,
            typename Strategy::template area_strategy
                <
                    point_type1
                >::type::template result_type<point_type1>::type
        > properties;

// Silence warning C4127: conditional expression is constant
#if defined(_MSC_VER)
#pragma warning(push)
#pragma warning(disable : 4127)
#endif

    // Union: return either of them
    // Intersection: return nothing
    // Difference: return first of them
    if (OverlayType == overlay_intersection
        || (OverlayType == overlay_difference && geometry::is_empty(geometry1)))
    {
        return out;
    }

#if defined(_MSC_VER)
#pragma warning(pop)
#endif


    std::map<ring_identifier, ring_turn_info> empty;
    std::map<ring_identifier, properties> all_of_one_of_them;

    select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them, strategy);
    ring_container_type rings;
    assign_parents<OverlayType>(geometry1, geometry2, rings, all_of_one_of_them, strategy);
    return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out,
                                  strategy.template get_area_strategy<point_type1>());
}


template
<
    typename Geometry1, typename Geometry2,
    bool Reverse1, bool Reverse2, bool ReverseOut,
    typename GeometryOut,
    overlay_type OverlayType
>
struct overlay
{
    template <typename RobustPolicy, typename OutputIterator, typename Strategy, typename Visitor>
    static inline OutputIterator apply(
                Geometry1 const& geometry1, Geometry2 const& geometry2,
                RobustPolicy const& robust_policy,
                OutputIterator out,
                Strategy const& strategy,
                Visitor& visitor)
    {
        bool const is_empty1 = geometry::is_empty(geometry1);
        bool const is_empty2 = geometry::is_empty(geometry2);

        if (is_empty1 && is_empty2)
        {
            return out;
        }

        if (is_empty1 || is_empty2)
        {
            return return_if_one_input_is_empty
                <
                    GeometryOut, OverlayType, ReverseOut
                >(geometry1, geometry2, out, strategy);
        }

        typedef typename geometry::point_type<GeometryOut>::type point_type;
        typedef detail::overlay::traversal_turn_info
        <
            point_type,
            typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
        > turn_info;
        typedef std::deque<turn_info> turn_container_type;

        typedef std::deque
            <
                typename geometry::ring_type<GeometryOut>::type
            > ring_container_type;

        // Define the clusters, mapping cluster_id -> turns
        typedef std::map
            <
                signed_size_type,
                cluster_info
            > cluster_type;

        turn_container_type turns;

#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "get turns" << std::endl;
#endif
        detail::get_turns::no_interrupt_policy policy;
        geometry::get_turns
            <
                Reverse1, Reverse2,
                detail::overlay::assign_null_policy
            >(geometry1, geometry2, strategy, robust_policy, turns, policy);

        visitor.visit_turns(1, turns);

#if ! defined(BOOST_GEOMETRY_NO_SELF_TURNS)
        if (needs_self_turns<Geometry1>::apply(geometry1))
        {
            self_get_turn_points::self_turns<Reverse1, assign_null_policy>(geometry1,
                strategy, robust_policy, turns, policy, 0);
        }
        if (needs_self_turns<Geometry2>::apply(geometry2))
        {
            self_get_turn_points::self_turns<Reverse2, assign_null_policy>(geometry2,
                strategy, robust_policy, turns, policy, 1);
        }
#endif


#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "enrich" << std::endl;
#endif
        typename Strategy::side_strategy_type side_strategy = strategy.get_side_strategy();
        cluster_type clusters;
        std::map<ring_identifier, ring_turn_info> turn_info_per_ring;

        geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
                clusters, geometry1, geometry2,
                    robust_policy,
                    side_strategy);

        visitor.visit_turns(2, turns);

        visitor.visit_clusters(clusters, turns);

#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
std::cout << "traverse" << std::endl;
#endif
        // Traverse through intersection/turn points and create rings of them.
        // Note that these rings are always in clockwise order, even in CCW polygons,
        // and are marked as "to be reversed" below
        ring_container_type rings;
        traverse<Reverse1, Reverse2, Geometry1, Geometry2, OverlayType>::apply
                (
                    geometry1, geometry2,
                    strategy,
                    robust_policy,
                    turns, rings,
                    turn_info_per_ring,
                    clusters,
                    visitor
                );
        visitor.visit_turns(3, turns);

        get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters);

        typedef typename Strategy::template area_strategy<point_type>::type area_strategy_type;

        typedef ring_properties
            <
                point_type,
                typename area_strategy_type::template result_type<point_type>::type
            > properties;

        // Select all rings which are NOT touched by any intersection point
        std::map<ring_identifier, properties> selected_ring_properties;
        select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring,
                selected_ring_properties, strategy);

        // Add rings created during traversal
        area_strategy_type const area_strategy = strategy.template get_area_strategy<point_type>();
        {
            ring_identifier id(2, 0, -1);
            for (typename boost::range_iterator<ring_container_type>::type
                    it = boost::begin(rings);
                 it != boost::end(rings);
                 ++it)
            {
                selected_ring_properties[id] = properties(*it, area_strategy);
                selected_ring_properties[id].reversed = ReverseOut;
                id.multi_index++;
            }
        }

        assign_parents<OverlayType>(geometry1, geometry2,
            rings, selected_ring_properties, strategy);

        // NOTE: There is no need to check result area for union because
        // as long as the polygons in the input are valid the resulting
        // polygons should be valid as well.
        // By default the area is checked (this is old behavior) however this
        // can be changed with #define. This may be important in non-cartesian CSes.
        // The result may be too big, so the area is negative. In this case either
        // it can be returned or an exception can be thrown.
        return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out,
                                      area_strategy,
                                      OverlayType == overlay_union ? 
#if defined(BOOST_GEOMETRY_UNION_THROW_INVALID_OUTPUT_EXCEPTION)
                                      add_rings_throw_if_reversed
#elif defined(BOOST_GEOMETRY_UNION_RETURN_INVALID)
                                      add_rings_add_unordered
#else
                                      add_rings_ignore_unordered
#endif
                                      : add_rings_ignore_unordered);
    }

    template <typename RobustPolicy, typename OutputIterator, typename Strategy>
    static inline OutputIterator apply(
                Geometry1 const& geometry1, Geometry2 const& geometry2,
                RobustPolicy const& robust_policy,
                OutputIterator out,
                Strategy const& strategy)
    {
        overlay_null_visitor visitor;
        return apply(geometry1, geometry2, robust_policy, out, strategy, visitor);
    }
};


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


}} // namespace boost::geometry


#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_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.
11fdf7f2	4	// Copyright (c) 2013-2017 Adam Wulkiewicz, Lodz, Poland
7c673cae	5
b32b8144 FG	6	// This file was modified by Oracle on 2015, 2017.
b32b8144 FG	7	// Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
7c673cae FG	8
7c673cae FG	9	// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
b32b8144	10	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
7c673cae FG	11
	12	// Use, modification and distribution is subject to the Boost Software License,
	13	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	14	// http://www.boost.org/LICENSE_1_0.txt)
	15
	16	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
	17	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
	18
	19
	20	#include <deque>
	21	#include <map>
	22
	23	#include <boost/range.hpp>
	24	#include <boost/mpl/assert.hpp>
	25
	26
	27	#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
	28	#include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
	29	#include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
	30	#include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
b32b8144 FG	31	#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
b32b8144 FG	32	#include <boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp>
7c673cae FG	33	#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
	34	#include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
	35	#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
b32b8144	36	#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
7c673cae FG	37	#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
	38
	39	#include <boost/geometry/algorithms/detail/recalculate.hpp>
	40
	41	#include <boost/geometry/algorithms/is_empty.hpp>
	42	#include <boost/geometry/algorithms/reverse.hpp>
	43
	44	#include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
	45	#include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
	46	#include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
	47	#include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
	48	#include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
	49
	50	#include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
	51
11fdf7f2	52	#include <boost/geometry/util/condition.hpp>
7c673cae FG	53
	54	#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
	55	# include <boost/geometry/io/dsv/write.hpp>
	56	#endif
	57
	58
	59	namespace boost { namespace geometry
	60	{
	61
	62
	63	#ifndef DOXYGEN_NO_DETAIL
	64	namespace detail { namespace overlay
	65	{
	66
	67
	68	//! Default visitor for overlay, doing nothing
	69	struct overlay_null_visitor
	70	{
	71	void print(char const* ) {}
	72
	73	template <typename Turns>
	74	void print(char const* , Turns const& , int) {}
	75
	76	template <typename Turns>
	77	void print(char const* , Turns const& , int , int ) {}
	78
	79	template <typename Turns>
	80	void visit_turns(int , Turns const& ) {}
	81
	82	template <typename Clusters, typename Turns>
	83	void visit_clusters(Clusters const& , Turns const& ) {}
	84
	85	template <typename Turns, typename Turn, typename Operation>
	86	void visit_traverse(Turns const& , Turn const& , Operation const& , char const*)
	87	{}
	88
	89	template <typename Turns, typename Turn, typename Operation>
	90	void visit_traverse_reject(Turns const& , Turn const& , Operation const& , traverse_error_type )
	91	{}
11fdf7f2 TL	92
	93	template <typename Rings>
	94	void visit_generated_rings(Rings const& )
	95	{}
7c673cae FG	96	};
7c673cae FG	97
b32b8144 FG	98	template
	99	<
	100	overlay_type OverlayType,
	101	typename TurnInfoMap,
	102	typename Turns,
	103	typename Clusters
	104	>
	105	inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns, Clusters const& clusters)
7c673cae FG	106	{
7c673cae FG	107	typedef typename boost::range_value<Turns>::type turn_type;
b32b8144	108	typedef typename turn_type::turn_operation_type turn_operation_type;
7c673cae FG	109	typedef typename turn_type::container_type container_type;
7c673cae FG	110
b32b8144 FG	111	static const operation_type target_operation
	112	= operation_from_overlay<OverlayType>::value;
	113	static const operation_type opposite_operation
	114	= target_operation == operation_union
	115	? operation_intersection
	116	: operation_union;
	117
7c673cae FG	118	for (typename boost::range_iterator<Turns const>::type
	119	it = boost::begin(turns);
	120	it != boost::end(turns);
	121	++it)
	122	{
b32b8144	123	turn_type const& turn = *it;
7c673cae	124
b32b8144 FG	125	bool cluster_checked = false;
b32b8144 FG	126	bool has_blocked = false;
7c673cae FG	127
7c673cae FG	128	for (typename boost::range_iterator<container_type const>::type
b32b8144 FG	129	op_it = boost::begin(turn.operations);
b32b8144 FG	130	op_it != boost::end(turn.operations);
7c673cae FG	131	++op_it)
7c673cae FG	132	{
b32b8144	133	turn_operation_type const& op = *op_it;
7c673cae FG	134	ring_identifier const ring_id
7c673cae FG	135	(
b32b8144 FG	136	op.seg_id.source_index,
	137	op.seg_id.multi_index,
	138	op.seg_id.ring_index
7c673cae	139	);
b32b8144 FG	140
	141	if (! is_self_turn<OverlayType>(turn)
	142	&& (
11fdf7f2	143	(BOOST_GEOMETRY_CONDITION(target_operation == operation_union)
b32b8144	144	&& op.enriched.count_left > 0)
11fdf7f2	145	\|\| (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection)
b32b8144 FG	146	&& op.enriched.count_right <= 2)))
	147	{
	148	// Avoid including untraversed rings which have polygons on
	149	// their left side (union) or not two on their right side (int)
	150	// This can only be done for non-self-turns because of count
	151	// information
	152	turn_info_map[ring_id].has_blocked_turn = true;
	153	continue;
	154	}
	155
	156	if (turn.any_blocked())
	157	{
	158	turn_info_map[ring_id].has_blocked_turn = true;
	159	}
	160	if (turn_info_map[ring_id].has_traversed_turn
	161	\|\| turn_info_map[ring_id].has_blocked_turn)
	162	{
	163	continue;
	164	}
	165
	166	// Check information in colocated turns
	167	if (! cluster_checked && turn.is_clustered())
	168	{
	169	check_colocation(has_blocked, turn.cluster_id, turns, clusters);
	170	cluster_checked = true;
	171	}
	172
	173	// Block rings where any other turn is blocked,
	174	// and (with exceptions): i for union and u for intersection
	175	// Exceptions: don't block self-uu for intersection
	176	// don't block self-ii for union
	177	// don't block (for union) i/u if there is an self-ii too
	178	if (has_blocked
	179	\|\| (op.operation == opposite_operation
	180	&& ! turn.has_colocated_both
	181	&& ! (turn.both(opposite_operation)
	182	&& is_self_turn<OverlayType>(turn))))
	183	{
	184	turn_info_map[ring_id].has_blocked_turn = true;
	185	}
7c673cae FG	186	}
	187	}
	188	}
	189
7c673cae FG	190	template
	191	<
	192	typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
	193	typename Geometry1, typename Geometry2,
b32b8144	194	typename OutputIterator, typename Strategy
7c673cae FG	195	>
	196	inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
	197	Geometry2 const& geometry2,
b32b8144	198	OutputIterator out, Strategy const& strategy)
7c673cae FG	199	{
	200	typedef std::deque
	201	<
	202	typename geometry::ring_type<GeometryOut>::type
	203	> ring_container_type;
	204
b32b8144 FG	205	typedef typename geometry::point_type<Geometry1>::type point_type1;
	206
	207	typedef ring_properties
	208	<
	209	point_type1,
	210	typename Strategy::template area_strategy
	211	<
	212	point_type1
11fdf7f2	213	>::type::template result_type<point_type1>::type
b32b8144	214	> properties;
7c673cae FG	215
	216	// Silence warning C4127: conditional expression is constant
	217	#if defined(_MSC_VER)
	218	#pragma warning(push)
	219	#pragma warning(disable : 4127)
	220	#endif
	221
	222	// Union: return either of them
	223	// Intersection: return nothing
	224	// Difference: return first of them
	225	if (OverlayType == overlay_intersection
	226	\|\| (OverlayType == overlay_difference && geometry::is_empty(geometry1)))
	227	{
	228	return out;
	229	}
	230
	231	#if defined(_MSC_VER)
	232	#pragma warning(pop)
	233	#endif
	234
	235
	236	std::map<ring_identifier, ring_turn_info> empty;
	237	std::map<ring_identifier, properties> all_of_one_of_them;
	238
b32b8144	239	select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them, strategy);
7c673cae	240	ring_container_type rings;
11fdf7f2	241	assign_parents<OverlayType>(geometry1, geometry2, rings, all_of_one_of_them, strategy);
b32b8144 FG	242	return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out,
b32b8144 FG	243	strategy.template get_area_strategy<point_type1>());
7c673cae FG	244	}
	245
	246
	247	template
	248	<
	249	typename Geometry1, typename Geometry2,
	250	bool Reverse1, bool Reverse2, bool ReverseOut,
	251	typename GeometryOut,
	252	overlay_type OverlayType
	253	>
	254	struct overlay
	255	{
	256	template <typename RobustPolicy, typename OutputIterator, typename Strategy, typename Visitor>
	257	static inline OutputIterator apply(
	258	Geometry1 const& geometry1, Geometry2 const& geometry2,
	259	RobustPolicy const& robust_policy,
	260	OutputIterator out,
b32b8144	261	Strategy const& strategy,
7c673cae FG	262	Visitor& visitor)
	263	{
	264	bool const is_empty1 = geometry::is_empty(geometry1);
	265	bool const is_empty2 = geometry::is_empty(geometry2);
	266
	267	if (is_empty1 && is_empty2)
	268	{
	269	return out;
	270	}
	271
	272	if (is_empty1 \|\| is_empty2)
	273	{
	274	return return_if_one_input_is_empty
	275	<
	276	GeometryOut, OverlayType, ReverseOut
b32b8144	277	>(geometry1, geometry2, out, strategy);
7c673cae FG	278	}
	279
	280	typedef typename geometry::point_type<GeometryOut>::type point_type;
	281	typedef detail::overlay::traversal_turn_info
	282	<
	283	point_type,
	284	typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
	285	> turn_info;
	286	typedef std::deque<turn_info> turn_container_type;
	287
	288	typedef std::deque
	289	<
	290	typename geometry::ring_type<GeometryOut>::type
	291	> ring_container_type;
	292
	293	// Define the clusters, mapping cluster_id -> turns
	294	typedef std::map
	295	<
	296	signed_size_type,
	297	cluster_info
	298	> cluster_type;
	299
	300	turn_container_type turns;
	301
	302	#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
	303	std::cout << "get turns" << std::endl;
	304	#endif
	305	detail::get_turns::no_interrupt_policy policy;
	306	geometry::get_turns
	307	<
	308	Reverse1, Reverse2,
	309	detail::overlay::assign_null_policy
b32b8144	310	>(geometry1, geometry2, strategy, robust_policy, turns, policy);
7c673cae FG	311
	312	visitor.visit_turns(1, turns);
	313
11fdf7f2	314	#if ! defined(BOOST_GEOMETRY_NO_SELF_TURNS)
b32b8144 FG	315	if (needs_self_turns<Geometry1>::apply(geometry1))
	316	{
	317	self_get_turn_points::self_turns<Reverse1, assign_null_policy>(geometry1,
	318	strategy, robust_policy, turns, policy, 0);
	319	}
	320	if (needs_self_turns<Geometry2>::apply(geometry2))
	321	{
	322	self_get_turn_points::self_turns<Reverse2, assign_null_policy>(geometry2,
	323	strategy, robust_policy, turns, policy, 1);
	324	}
	325	#endif
	326
	327
7c673cae FG	328	#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
	329	std::cout << "enrich" << std::endl;
	330	#endif
b32b8144	331	typename Strategy::side_strategy_type side_strategy = strategy.get_side_strategy();
7c673cae	332	cluster_type clusters;
b32b8144	333	std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
7c673cae FG	334
	335	geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
	336	clusters, geometry1, geometry2,
	337	robust_policy,
	338	side_strategy);
	339
	340	visitor.visit_turns(2, turns);
	341
	342	visitor.visit_clusters(clusters, turns);
	343
	344	#ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
	345	std::cout << "traverse" << std::endl;
	346	#endif
	347	// Traverse through intersection/turn points and create rings of them.
	348	// Note that these rings are always in clockwise order, even in CCW polygons,
	349	// and are marked as "to be reversed" below
	350	ring_container_type rings;
	351	traverse<Reverse1, Reverse2, Geometry1, Geometry2, OverlayType>::apply
	352	(
	353	geometry1, geometry2,
b32b8144	354	strategy,
7c673cae FG	355	robust_policy,
7c673cae FG	356	turns, rings,
b32b8144	357	turn_info_per_ring,
7c673cae FG	358	clusters,
	359	visitor
	360	);
b32b8144	361	visitor.visit_turns(3, turns);
7c673cae	362
b32b8144 FG	363	get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters);
	364
	365	typedef typename Strategy::template area_strategy<point_type>::type area_strategy_type;
7c673cae FG	366
7c673cae FG	367	typedef ring_properties
b32b8144 FG	368	<
b32b8144 FG	369	point_type,
11fdf7f2	370	typename area_strategy_type::template result_type<point_type>::type
b32b8144	371	> properties;
7c673cae FG	372
	373	// Select all rings which are NOT touched by any intersection point
	374	std::map<ring_identifier, properties> selected_ring_properties;
	375	select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring,
b32b8144	376	selected_ring_properties, strategy);
7c673cae FG	377
7c673cae FG	378	// Add rings created during traversal
b32b8144	379	area_strategy_type const area_strategy = strategy.template get_area_strategy<point_type>();
7c673cae FG	380	{
	381	ring_identifier id(2, 0, -1);
	382	for (typename boost::range_iterator<ring_container_type>::type
	383	it = boost::begin(rings);
	384	it != boost::end(rings);
	385	++it)
	386	{
b32b8144	387	selected_ring_properties[id] = properties(*it, area_strategy);
7c673cae FG	388	selected_ring_properties[id].reversed = ReverseOut;
	389	id.multi_index++;
	390	}
	391	}
	392
11fdf7f2 TL	393	assign_parents<OverlayType>(geometry1, geometry2,
11fdf7f2 TL	394	rings, selected_ring_properties, strategy);
b32b8144 FG	395
	396	// NOTE: There is no need to check result area for union because
	397	// as long as the polygons in the input are valid the resulting
	398	// polygons should be valid as well.
	399	// By default the area is checked (this is old behavior) however this
	400	// can be changed with #define. This may be important in non-cartesian CSes.
	401	// The result may be too big, so the area is negative. In this case either
	402	// it can be returned or an exception can be thrown.
	403	return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out,
	404	area_strategy,
	405	OverlayType == overlay_union ?
	406	#if defined(BOOST_GEOMETRY_UNION_THROW_INVALID_OUTPUT_EXCEPTION)
	407	add_rings_throw_if_reversed
	408	#elif defined(BOOST_GEOMETRY_UNION_RETURN_INVALID)
	409	add_rings_add_unordered
	410	#else
	411	add_rings_ignore_unordered
	412	#endif
	413	: add_rings_ignore_unordered);
7c673cae FG	414	}
	415
	416	template <typename RobustPolicy, typename OutputIterator, typename Strategy>
	417	static inline OutputIterator apply(
	418	Geometry1 const& geometry1, Geometry2 const& geometry2,
	419	RobustPolicy const& robust_policy,
	420	OutputIterator out,
	421	Strategy const& strategy)
	422	{
	423	overlay_null_visitor visitor;
	424	return apply(geometry1, geometry2, robust_policy, out, strategy, visitor);
	425	}
	426	};
	427
	428
	429	}} // namespace detail::overlay
	430	#endif // DOXYGEN_NO_DETAIL
	431
	432
	433	}} // namespace boost::geometry
	434
	435
	436	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP