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

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

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

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

#include <boost/range.hpp>

#include <boost/geometry/algorithms/area.hpp>
#include <boost/geometry/algorithms/envelope.hpp>
#include <boost/geometry/algorithms/expand.hpp>
#include <boost/geometry/algorithms/detail/partition.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
#include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
#include <boost/geometry/algorithms/covered_by.hpp>

#include <boost/geometry/geometries/box.hpp>

namespace boost { namespace geometry
{


#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{


template
<
    typename Item,
    typename InnerGeometry,
    typename Geometry1, typename Geometry2,
    typename RingCollection,
    typename Strategy
>
static inline bool within_selected_input(Item const& item2,
        InnerGeometry const& inner_geometry,
        ring_identifier const& outer_id,
        Geometry1 const& geometry1, Geometry2 const& geometry2,
        RingCollection const& collection,
        Strategy const& strategy)
{
    typedef typename geometry::tag<Geometry1>::type tag1;
    typedef typename geometry::tag<Geometry2>::type tag2;

    // NOTE: range_in_geometry first checks the item2.point and then
    // if this point is on boundary it checks points of inner_geometry
    // ring until a point inside/outside other geometry ring is found
    switch (outer_id.source_index)
    {
        // covered_by
        case 0 :
            return range_in_geometry(item2.point, inner_geometry,
                get_ring<tag1>::apply(outer_id, geometry1), strategy) >= 0;
        case 1 :
            return range_in_geometry(item2.point, inner_geometry,
                get_ring<tag2>::apply(outer_id, geometry2), strategy) >= 0;
        case 2 :
            return range_in_geometry(item2.point, inner_geometry,
                get_ring<void>::apply(outer_id, collection), strategy) >= 0;
    }
    return false;
}

template
<
    typename Item,
    typename Geometry1, typename Geometry2,
    typename RingCollection,
    typename Strategy
>
static inline bool within_selected_input(Item const& item2,
        ring_identifier const& inner_id, ring_identifier const& outer_id,
        Geometry1 const& geometry1, Geometry2 const& geometry2,
        RingCollection const& collection,
        Strategy const& strategy)
{
    typedef typename geometry::tag<Geometry1>::type tag1;
    typedef typename geometry::tag<Geometry2>::type tag2;

    switch (inner_id.source_index)
    {
        case 0 :
            return within_selected_input(item2,
               get_ring<tag1>::apply(inner_id, geometry1),
               outer_id, geometry1, geometry2, collection, strategy);
        case 1 :
            return within_selected_input(item2,
               get_ring<tag2>::apply(inner_id, geometry2),
               outer_id, geometry1, geometry2, collection, strategy);
        case 2 :
            return within_selected_input(item2,
                get_ring<void>::apply(inner_id, collection),
                outer_id, geometry1, geometry2, collection, strategy);
    }
    return false;
}


template <typename Point, typename AreaType>
struct ring_info_helper
{
    ring_identifier id;
    AreaType real_area;
    AreaType abs_area;
    model::box<Point> envelope;

    inline ring_info_helper()
        : real_area(0), abs_area(0)
    {}

    inline ring_info_helper(ring_identifier i, AreaType const& a)
        : id(i), real_area(a), abs_area(geometry::math::abs(a))
    {}
};


struct ring_info_helper_get_box
{
    template <typename Box, typename InputItem>
    static inline void apply(Box& total, InputItem const& item)
    {
        geometry::expand(total, item.envelope);
    }
};

struct ring_info_helper_ovelaps_box
{
    template <typename Box, typename InputItem>
    static inline bool apply(Box const& box, InputItem const& item)
    {
        return ! geometry::detail::disjoint::disjoint_box_box(box, item.envelope);
    }
};

template
<
    typename Geometry1,
    typename Geometry2,
    typename Collection,
    typename RingMap,
    typename Strategy
>
struct assign_visitor
{
    typedef typename RingMap::mapped_type ring_info_type;

    Geometry1 const& m_geometry1;
    Geometry2 const& m_geometry2;
    Collection const& m_collection;
    RingMap& m_ring_map;
    Strategy const& m_strategy;
    bool m_check_for_orientation;

    inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
                          RingMap& map, Strategy const& strategy, bool check)
        : m_geometry1(g1)
        , m_geometry2(g2)
        , m_collection(c)
        , m_ring_map(map)
        , m_strategy(strategy)
        , m_check_for_orientation(check)
    {}

    template <typename Item>
    inline bool apply(Item const& outer, Item const& inner, bool first = true)
    {
        if (first && outer.abs_area < inner.abs_area)
        {
            // Apply with reversed arguments
            apply(inner, outer, false);
            return true;
        }

        if (m_check_for_orientation
         || (math::larger(outer.real_area, 0)
          && math::smaller(inner.real_area, 0)))
        {
            ring_info_type& inner_in_map = m_ring_map[inner.id];

            if (geometry::covered_by(inner_in_map.point, outer.envelope)
               && within_selected_input(inner_in_map, inner.id, outer.id,
                                        m_geometry1, m_geometry2, m_collection,
                                        m_strategy)
               )
            {
                // Assign a parent if there was no earlier parent, or the newly
                // found parent is smaller than the previous one
                if (inner_in_map.parent.source_index == -1
                    || outer.abs_area < inner_in_map.parent_area)
                {
                    inner_in_map.parent = outer.id;
                    inner_in_map.parent_area = outer.abs_area;
                }
            }
        }

        return true;
    }
};


template
<
    overlay_type OverlayType,
    typename Geometry1, typename Geometry2,
    typename RingCollection,
    typename RingMap,
    typename Strategy
>
inline void assign_parents(Geometry1 const& geometry1,
            Geometry2 const& geometry2,
            RingCollection const& collection,
            RingMap& ring_map,
            Strategy const& strategy)
{
    static bool const is_difference = OverlayType == overlay_difference;
    static bool const is_buffer = OverlayType == overlay_buffer;
    static bool const is_dissolve = OverlayType == overlay_dissolve;
    static bool const check_for_orientation = is_buffer || is_dissolve;

    typedef typename geometry::tag<Geometry1>::type tag1;
    typedef typename geometry::tag<Geometry2>::type tag2;

    typedef typename RingMap::mapped_type ring_info_type;
    typedef typename ring_info_type::point_type point_type;
    typedef model::box<point_type> box_type;
    typedef typename Strategy::template area_strategy
        <
            point_type
        >::type::template result_type<point_type>::type area_result_type;

    typedef typename RingMap::iterator map_iterator_type;

    {
        typedef ring_info_helper<point_type, area_result_type> helper;
        typedef std::vector<helper> vector_type;
        typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;

        std::size_t count_total = ring_map.size();
        std::size_t count_positive = 0;
        std::size_t index_positive = 0; // only used if count_positive>0
        std::size_t index = 0;

        // Copy to vector (with new approach this might be obsolete as well, using the map directly)
        vector_type vector(count_total);

        for (map_iterator_type it = boost::begin(ring_map);
            it != boost::end(ring_map); ++it, ++index)
        {
            vector[index] = helper(it->first, it->second.get_area());
            helper& item = vector[index];
            switch(it->first.source_index)
            {
                case 0 :
                    geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
                                       item.envelope, strategy.get_envelope_strategy());
                    break;
                case 1 :
                    geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
                                       item.envelope, strategy.get_envelope_strategy());
                    break;
                case 2 :
                    geometry::envelope(get_ring<void>::apply(it->first, collection),
                                       item.envelope, strategy.get_envelope_strategy());
                    break;
            }

            // Expand envelope slightly
            expand_by_epsilon(item.envelope);

            if (item.real_area > 0)
            {
                count_positive++;
                index_positive = index;
            }
        }

        if (! check_for_orientation)
        {
            if (count_positive == count_total)
            {
                // Optimization for only positive rings
                // -> no assignment of parents or reversal necessary, ready here.
                return;
            }

            if (count_positive == 1 && ! is_difference && ! is_dissolve)
            {
                // Optimization for one outer ring
                // -> assign this as parent to all others (all interior rings)
                // In unions, this is probably the most occuring case and gives
                //    a dramatic improvement (factor 5 for star_comb testcase)
                // In difference or other cases where interior rings might be
                // located outside the outer ring, this cannot be done
                ring_identifier id_of_positive = vector[index_positive].id;
                ring_info_type& outer = ring_map[id_of_positive];
                index = 0;
                for (vector_iterator_type it = boost::begin(vector);
                    it != boost::end(vector); ++it, ++index)
                {
                    if (index != index_positive)
                    {
                        ring_info_type& inner = ring_map[it->id];
                        inner.parent = id_of_positive;
                        outer.children.push_back(it->id);
                    }
                }
                return;
            }
        }

        assign_visitor
            <
                Geometry1, Geometry2,
                RingCollection, RingMap,
                Strategy
            > visitor(geometry1, geometry2, collection, ring_map, strategy, check_for_orientation);

        geometry::partition
            <
                box_type
            >::apply(vector, visitor, ring_info_helper_get_box(),
                     ring_info_helper_ovelaps_box());
    }

    if (check_for_orientation)
    {
        for (map_iterator_type it = boost::begin(ring_map);
            it != boost::end(ring_map); ++it)
        {
            ring_info_type& info = it->second;
            if (geometry::math::equals(info.get_area(), 0))
            {
                info.discarded = true;
            }
            else if (info.parent.source_index >= 0)
            {
                const ring_info_type& parent = ring_map[info.parent];
                bool const pos = math::larger(info.get_area(), 0);
                bool const parent_pos = math::larger(parent.area, 0);

                bool const double_neg = is_dissolve && ! pos && ! parent_pos;

                if ((pos && parent_pos) || double_neg)
                {
                    // Discard positive inner ring with positive parent
                    // Also, for some cases (dissolve), negative inner ring
                    // with negative parent should be discarded
                    info.discarded = true;
                }

                if (pos || info.discarded)
                {
                    // Remove parent ID from any positive or discarded inner rings
                    info.parent.source_index = -1;
                }
            }
            else if (info.parent.source_index < 0
                    && math::smaller(info.get_area(), 0))
            {
                // Reverse negative ring without parent
                info.reversed = true;
            }
        }
    }

    // Assign childlist
    for (map_iterator_type it = boost::begin(ring_map);
        it != boost::end(ring_map); ++it)
    {
        if (it->second.parent.source_index >= 0)
        {
            ring_map[it->second.parent].children.push_back(it->first);
        }
    }
}


// Version for one geometry (called by buffer/dissolve)
template
<
    overlay_type OverlayType,
    typename Geometry,
    typename RingCollection,
    typename RingMap,
    typename Strategy
>
inline void assign_parents(Geometry const& geometry,
            RingCollection const& collection,
            RingMap& ring_map,
            Strategy const& strategy)
{
    // Call it with an empty geometry as second geometry (source_id == 1)
    // (ring_map should be empty for source_id==1)
    Geometry empty;
    assign_parents<OverlayType>(geometry, empty,
            collection, ring_map, strategy);
}


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


}} // namespace geometry


#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_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.
11fdf7f2	4	// Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
7c673cae	5
b32b8144 FG	6	// This file was modified by Oracle on 2017.
	7	// Modifications copyright (c) 2017 Oracle and/or its affiliates.
	8	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
	9
7c673cae FG	10	// Use, modification and distribution is subject to the Boost Software License,
	11	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	12	// http://www.boost.org/LICENSE_1_0.txt)
	13
	14	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
	15	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
	16
	17	#include <boost/range.hpp>
	18
	19	#include <boost/geometry/algorithms/area.hpp>
	20	#include <boost/geometry/algorithms/envelope.hpp>
	21	#include <boost/geometry/algorithms/expand.hpp>
	22	#include <boost/geometry/algorithms/detail/partition.hpp>
	23	#include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
b32b8144 FG	24	#include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
b32b8144 FG	25	#include <boost/geometry/algorithms/covered_by.hpp>
7c673cae FG	26
	27	#include <boost/geometry/geometries/box.hpp>
	28
	29	namespace boost { namespace geometry
	30	{
	31
	32
	33	#ifndef DOXYGEN_NO_DETAIL
	34	namespace detail { namespace overlay
	35	{
	36
	37
	38
	39	template
	40	<
	41	typename Item,
b32b8144	42	typename InnerGeometry,
7c673cae	43	typename Geometry1, typename Geometry2,
b32b8144 FG	44	typename RingCollection,
b32b8144 FG	45	typename Strategy
7c673cae	46	>
b32b8144 FG	47	static inline bool within_selected_input(Item const& item2,
	48	InnerGeometry const& inner_geometry,
	49	ring_identifier const& outer_id,
7c673cae	50	Geometry1 const& geometry1, Geometry2 const& geometry2,
b32b8144 FG	51	RingCollection const& collection,
b32b8144 FG	52	Strategy const& strategy)
7c673cae FG	53	{
	54	typedef typename geometry::tag<Geometry1>::type tag1;
	55	typedef typename geometry::tag<Geometry2>::type tag2;
	56
b32b8144 FG	57	// NOTE: range_in_geometry first checks the item2.point and then
	58	// if this point is on boundary it checks points of inner_geometry
	59	// ring until a point inside/outside other geometry ring is found
	60	switch (outer_id.source_index)
7c673cae	61	{
b32b8144	62	// covered_by
7c673cae	63	case 0 :
b32b8144 FG	64	return range_in_geometry(item2.point, inner_geometry,
b32b8144 FG	65	get_ring<tag1>::apply(outer_id, geometry1), strategy) >= 0;
7c673cae	66	case 1 :
b32b8144 FG	67	return range_in_geometry(item2.point, inner_geometry,
b32b8144 FG	68	get_ring<tag2>::apply(outer_id, geometry2), strategy) >= 0;
7c673cae	69	case 2 :
b32b8144 FG	70	return range_in_geometry(item2.point, inner_geometry,
b32b8144 FG	71	get_ring<void>::apply(outer_id, collection), strategy) >= 0;
7c673cae FG	72	}
	73	return false;
	74	}
	75
b32b8144 FG	76	template
	77	<
	78	typename Item,
	79	typename Geometry1, typename Geometry2,
	80	typename RingCollection,
	81	typename Strategy
	82	>
	83	static inline bool within_selected_input(Item const& item2,
	84	ring_identifier const& inner_id, ring_identifier const& outer_id,
	85	Geometry1 const& geometry1, Geometry2 const& geometry2,
	86	RingCollection const& collection,
	87	Strategy const& strategy)
	88	{
	89	typedef typename geometry::tag<Geometry1>::type tag1;
	90	typedef typename geometry::tag<Geometry2>::type tag2;
7c673cae	91
b32b8144 FG	92	switch (inner_id.source_index)
	93	{
	94	case 0 :
	95	return within_selected_input(item2,
	96	get_ring<tag1>::apply(inner_id, geometry1),
	97	outer_id, geometry1, geometry2, collection, strategy);
	98	case 1 :
	99	return within_selected_input(item2,
	100	get_ring<tag2>::apply(inner_id, geometry2),
	101	outer_id, geometry1, geometry2, collection, strategy);
	102	case 2 :
	103	return within_selected_input(item2,
	104	get_ring<void>::apply(inner_id, collection),
	105	outer_id, geometry1, geometry2, collection, strategy);
	106	}
	107	return false;
	108	}
	109
	110
	111	template <typename Point, typename AreaType>
7c673cae FG	112	struct ring_info_helper
7c673cae FG	113	{
7c673cae	114	ring_identifier id;
b32b8144 FG	115	AreaType real_area;
b32b8144 FG	116	AreaType abs_area;
7c673cae FG	117	model::box<Point> envelope;
	118
	119	inline ring_info_helper()
	120	: real_area(0), abs_area(0)
	121	{}
	122
b32b8144	123	inline ring_info_helper(ring_identifier i, AreaType const& a)
7c673cae FG	124	: id(i), real_area(a), abs_area(geometry::math::abs(a))
	125	{}
	126	};
	127
	128
	129	struct ring_info_helper_get_box
	130	{
	131	template <typename Box, typename InputItem>
	132	static inline void apply(Box& total, InputItem const& item)
	133	{
	134	geometry::expand(total, item.envelope);
	135	}
	136	};
	137
	138	struct ring_info_helper_ovelaps_box
	139	{
	140	template <typename Box, typename InputItem>
	141	static inline bool apply(Box const& box, InputItem const& item)
	142	{
	143	return ! geometry::detail::disjoint::disjoint_box_box(box, item.envelope);
	144	}
	145	};
	146
b32b8144 FG	147	template
	148	<
	149	typename Geometry1,
	150	typename Geometry2,
	151	typename Collection,
	152	typename RingMap,
	153	typename Strategy
	154	>
7c673cae FG	155	struct assign_visitor
	156	{
	157	typedef typename RingMap::mapped_type ring_info_type;
	158
	159	Geometry1 const& m_geometry1;
	160	Geometry2 const& m_geometry2;
	161	Collection const& m_collection;
	162	RingMap& m_ring_map;
b32b8144	163	Strategy const& m_strategy;
7c673cae FG	164	bool m_check_for_orientation;
7c673cae FG	165
7c673cae	166	inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
b32b8144	167	RingMap& map, Strategy const& strategy, bool check)
7c673cae FG	168	: m_geometry1(g1)
	169	, m_geometry2(g2)
	170	, m_collection(c)
	171	, m_ring_map(map)
b32b8144	172	, m_strategy(strategy)
7c673cae FG	173	, m_check_for_orientation(check)
	174	{}
	175
	176	template <typename Item>
b32b8144	177	inline bool apply(Item const& outer, Item const& inner, bool first = true)
7c673cae FG	178	{
	179	if (first && outer.abs_area < inner.abs_area)
	180	{
	181	// Apply with reversed arguments
	182	apply(inner, outer, false);
b32b8144	183	return true;
7c673cae FG	184	}
	185
	186	if (m_check_for_orientation
	187	\|\| (math::larger(outer.real_area, 0)
	188	&& math::smaller(inner.real_area, 0)))
	189	{
	190	ring_info_type& inner_in_map = m_ring_map[inner.id];
	191
b32b8144 FG	192	if (geometry::covered_by(inner_in_map.point, outer.envelope)
	193	&& within_selected_input(inner_in_map, inner.id, outer.id,
	194	m_geometry1, m_geometry2, m_collection,
	195	m_strategy)
7c673cae FG	196	)
	197	{
	198	// Assign a parent if there was no earlier parent, or the newly
	199	// found parent is smaller than the previous one
	200	if (inner_in_map.parent.source_index == -1
	201	\|\| outer.abs_area < inner_in_map.parent_area)
	202	{
	203	inner_in_map.parent = outer.id;
	204	inner_in_map.parent_area = outer.abs_area;
	205	}
	206	}
	207	}
b32b8144 FG	208
b32b8144 FG	209	return true;
7c673cae FG	210	}
	211	};
	212
	213
7c673cae FG	214	template
7c673cae FG	215	<
11fdf7f2	216	overlay_type OverlayType,
7c673cae FG	217	typename Geometry1, typename Geometry2,
7c673cae FG	218	typename RingCollection,
b32b8144 FG	219	typename RingMap,
b32b8144 FG	220	typename Strategy
7c673cae FG	221	>
	222	inline void assign_parents(Geometry1 const& geometry1,
	223	Geometry2 const& geometry2,
	224	RingCollection const& collection,
	225	RingMap& ring_map,
11fdf7f2	226	Strategy const& strategy)
7c673cae	227	{
11fdf7f2 TL	228	static bool const is_difference = OverlayType == overlay_difference;
	229	static bool const is_buffer = OverlayType == overlay_buffer;
	230	static bool const is_dissolve = OverlayType == overlay_dissolve;
	231	static bool const check_for_orientation = is_buffer \|\| is_dissolve;
	232
7c673cae FG	233	typedef typename geometry::tag<Geometry1>::type tag1;
	234	typedef typename geometry::tag<Geometry2>::type tag2;
	235
	236	typedef typename RingMap::mapped_type ring_info_type;
	237	typedef typename ring_info_type::point_type point_type;
	238	typedef model::box<point_type> box_type;
b32b8144 FG	239	typedef typename Strategy::template area_strategy
	240	<
	241	point_type
11fdf7f2	242	>::type::template result_type<point_type>::type area_result_type;
7c673cae FG	243
	244	typedef typename RingMap::iterator map_iterator_type;
	245
	246	{
b32b8144	247	typedef ring_info_helper<point_type, area_result_type> helper;
7c673cae FG	248	typedef std::vector<helper> vector_type;
	249	typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;
	250
	251	std::size_t count_total = ring_map.size();
	252	std::size_t count_positive = 0;
	253	std::size_t index_positive = 0; // only used if count_positive>0
	254	std::size_t index = 0;
	255
	256	// Copy to vector (with new approach this might be obsolete as well, using the map directly)
	257	vector_type vector(count_total);
	258
	259	for (map_iterator_type it = boost::begin(ring_map);
	260	it != boost::end(ring_map); ++it, ++index)
	261	{
	262	vector[index] = helper(it->first, it->second.get_area());
	263	helper& item = vector[index];
	264	switch(it->first.source_index)
	265	{
	266	case 0 :
	267	geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
b32b8144	268	item.envelope, strategy.get_envelope_strategy());
7c673cae FG	269	break;
	270	case 1 :
	271	geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
b32b8144	272	item.envelope, strategy.get_envelope_strategy());
7c673cae FG	273	break;
	274	case 2 :
	275	geometry::envelope(get_ring<void>::apply(it->first, collection),
b32b8144	276	item.envelope, strategy.get_envelope_strategy());
7c673cae FG	277	break;
7c673cae FG	278	}
b32b8144 FG	279
	280	// Expand envelope slightly
	281	expand_by_epsilon(item.envelope);
	282
7c673cae FG	283	if (item.real_area > 0)
	284	{
	285	count_positive++;
	286	index_positive = index;
	287	}
	288	}
	289
	290	if (! check_for_orientation)
	291	{
	292	if (count_positive == count_total)
	293	{
	294	// Optimization for only positive rings
	295	// -> no assignment of parents or reversal necessary, ready here.
	296	return;
	297	}
	298
11fdf7f2	299	if (count_positive == 1 && ! is_difference && ! is_dissolve)
7c673cae FG	300	{
	301	// Optimization for one outer ring
	302	// -> assign this as parent to all others (all interior rings)
	303	// In unions, this is probably the most occuring case and gives
	304	// a dramatic improvement (factor 5 for star_comb testcase)
11fdf7f2 TL	305	// In difference or other cases where interior rings might be
11fdf7f2 TL	306	// located outside the outer ring, this cannot be done
7c673cae FG	307	ring_identifier id_of_positive = vector[index_positive].id;
	308	ring_info_type& outer = ring_map[id_of_positive];
	309	index = 0;
	310	for (vector_iterator_type it = boost::begin(vector);
	311	it != boost::end(vector); ++it, ++index)
	312	{
	313	if (index != index_positive)
	314	{
	315	ring_info_type& inner = ring_map[it->id];
	316	inner.parent = id_of_positive;
	317	outer.children.push_back(it->id);
	318	}
	319	}
	320	return;
	321	}
	322	}
	323
	324	assign_visitor
	325	<
	326	Geometry1, Geometry2,
b32b8144 FG	327	RingCollection, RingMap,
	328	Strategy
	329	> visitor(geometry1, geometry2, collection, ring_map, strategy, check_for_orientation);
7c673cae FG	330
	331	geometry::partition
	332	<
b32b8144 FG	333	box_type
	334	>::apply(vector, visitor, ring_info_helper_get_box(),
	335	ring_info_helper_ovelaps_box());
7c673cae FG	336	}
	337
	338	if (check_for_orientation)
	339	{
	340	for (map_iterator_type it = boost::begin(ring_map);
	341	it != boost::end(ring_map); ++it)
	342	{
b32b8144 FG	343	ring_info_type& info = it->second;
b32b8144 FG	344	if (geometry::math::equals(info.get_area(), 0))
7c673cae	345	{
b32b8144	346	info.discarded = true;
7c673cae	347	}
b32b8144	348	else if (info.parent.source_index >= 0)
7c673cae	349	{
b32b8144 FG	350	const ring_info_type& parent = ring_map[info.parent];
	351	bool const pos = math::larger(info.get_area(), 0);
	352	bool const parent_pos = math::larger(parent.area, 0);
7c673cae	353
11fdf7f2	354	bool const double_neg = is_dissolve && ! pos && ! parent_pos;
b32b8144 FG	355
b32b8144 FG	356	if ((pos && parent_pos) \|\| double_neg)
7c673cae FG	357	{
7c673cae FG	358	// Discard positive inner ring with positive parent
b32b8144	359	// Also, for some cases (dissolve), negative inner ring
11fdf7f2	360	// with negative parent should be discarded
b32b8144 FG	361	info.discarded = true;
	362	}
	363
	364	if (pos \|\| info.discarded)
	365	{
	366	// Remove parent ID from any positive or discarded inner rings
	367	info.parent.source_index = -1;
7c673cae	368	}
7c673cae	369	}
b32b8144 FG	370	else if (info.parent.source_index < 0
b32b8144 FG	371	&& math::smaller(info.get_area(), 0))
7c673cae FG	372	{
7c673cae FG	373	// Reverse negative ring without parent
b32b8144	374	info.reversed = true;
7c673cae FG	375	}
	376	}
	377	}
	378
	379	// Assign childlist
	380	for (map_iterator_type it = boost::begin(ring_map);
	381	it != boost::end(ring_map); ++it)
	382	{
	383	if (it->second.parent.source_index >= 0)
	384	{
	385	ring_map[it->second.parent].children.push_back(it->first);
	386	}
	387	}
	388	}
	389
	390
b32b8144	391	// Version for one geometry (called by buffer/dissolve)
7c673cae FG	392	template
7c673cae FG	393	<
11fdf7f2	394	overlay_type OverlayType,
7c673cae FG	395	typename Geometry,
7c673cae FG	396	typename RingCollection,
b32b8144 FG	397	typename RingMap,
b32b8144 FG	398	typename Strategy
7c673cae FG	399	>
	400	inline void assign_parents(Geometry const& geometry,
	401	RingCollection const& collection,
	402	RingMap& ring_map,
11fdf7f2	403	Strategy const& strategy)
7c673cae FG	404	{
	405	// Call it with an empty geometry as second geometry (source_id == 1)
	406	// (ring_map should be empty for source_id==1)
7c673cae	407	Geometry empty;
11fdf7f2 TL	408	assign_parents<OverlayType>(geometry, empty,
11fdf7f2 TL	409	collection, ring_map, strategy);
7c673cae FG	410	}
	411
	412
	413	}} // namespace detail::overlay
	414	#endif // DOXYGEN_NO_DETAIL
	415
	416
	417	}} // namespace geometry
	418
	419
	420	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP