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

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

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

// This file was modified by Oracle on 2018-2020.
// Modifications copyright (c) 2018-2020 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_TRAVERSAL_SWITCH_DETECTOR_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP

#include <cstddef>
#include <map>

#include <boost/range/value_type.hpp>

#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/util/condition.hpp>

namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{

template
<
    bool Reverse1,
    bool Reverse2,
    overlay_type OverlayType,
    typename Geometry1,
    typename Geometry2,
    typename Turns,
    typename Clusters,
    typename RobustPolicy,
    typename Visitor
>
struct traversal_switch_detector
{
    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;

    enum isolation_type
    {
        isolation_unknown = -1,
        isolation_no = 0,
        isolation_yes = 1,
        isolation_multiple = 2
    };

    typedef typename boost::range_value<Turns>::type turn_type;
    typedef typename turn_type::turn_operation_type turn_operation_type;
    typedef std::set<signed_size_type> set_type;

    // Per ring, first turns are collected (in turn_indices), and later
    // a region_id is assigned
    struct merged_ring_properties
    {
        signed_size_type region_id;
        set_type turn_indices;

        merged_ring_properties()
            : region_id(-1)
        {}
    };

    struct connection_properties
    {
        std::size_t count;
        // Contains turn-index OR, if clustered, minus-cluster_id
        set_type unique_turn_ids;
        connection_properties()
            : count(0)
        {}
    };

    typedef std::map<signed_size_type, connection_properties> connection_map;

    // Per region, a set of properties is maintained, including its connections
    // to other regions
    struct region_properties
    {
        signed_size_type region_id;
        isolation_type isolated;
        set_type unique_turn_ids;

        // Maps from connected region_id to their properties
        connection_map connected_region_counts;

        region_properties()
            : region_id(-1)
            , isolated(isolation_unknown)
        {}
    };

    // Keeps turn indices per ring
    typedef std::map<ring_identifier, merged_ring_properties > merge_map;
    typedef std::map<signed_size_type, region_properties> region_connection_map;

    typedef set_type::const_iterator set_iterator;

    inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2,
            Turns& turns, Clusters& clusters,
            RobustPolicy const& robust_policy, Visitor& visitor)
        : m_geometry1(geometry1)
        , m_geometry2(geometry2)
        , m_turns(turns)
        , m_clusters(clusters)
        , m_robust_policy(robust_policy)
        , m_visitor(visitor)
    {
    }

    bool one_connection_to_another_region(region_properties const& region) const
    {
        // For example:
        // +----------------------+
        // |                   __ |
        // |                  /  \|
        // |                 |    x
        // |                  \__/|
        // |                      |
        // +----------------------+

        if (region.connected_region_counts.size() == 1)
        {
            connection_properties const& cprop = region.connected_region_counts.begin()->second;
            return cprop.count <= 1;
        }
        return region.connected_region_counts.empty();
    }

    // TODO: might be combined with previous
    bool multiple_connections_to_one_region(region_properties const& region) const
    {
        // For example:
        // +----------------------+
        // |                   __ |
        // |                  /  \|
        // |                 |    x
        // |                  \  /|
        // |                  /  \|
        // |                 |    x
        // |                  \__/|
        // |                      |
        // +----------------------+

        if (region.connected_region_counts.size() == 1)
        {
            connection_properties const& cprop = region.connected_region_counts.begin()->second;
            return cprop.count > 1;
        }
        return false;
    }

    bool one_connection_to_multiple_regions(region_properties const& region) const
    {
        // For example:
        // +----------------------+
        // |                   __ | __
        // |                  /  \|/  |
        // |                 |    x   |
        // |                  \__/|\__|
        // |                      |
        // +----------------------+

        bool first = true;
        signed_size_type first_turn_id = 0;
        for (typename connection_map::const_iterator it = region.connected_region_counts.begin();
             it != region.connected_region_counts.end(); ++it)
        {
            connection_properties const& cprop = it->second;

            if (cprop.count != 1)
            {
                return false;
            }
            signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin();
            if (first)
            {
                first_turn_id = unique_turn_id;
                first = false;
            }
            else if (first_turn_id != unique_turn_id)
            {
                return false;
            }
        }
        return true;
    }

    bool ii_turn_connects_two_regions(region_properties const& region,
            region_properties const& connected_region,
            signed_size_type turn_index) const
    {
        turn_type const& turn = m_turns[turn_index];
        if (! turn.both(operation_intersection))
        {
            return false;
        }

        signed_size_type const id0 = turn.operations[0].enriched.region_id;
        signed_size_type const id1 = turn.operations[1].enriched.region_id;

        return (id0 == region.region_id && id1 == connected_region.region_id)
            || (id1 == region.region_id && id0 == connected_region.region_id);
    }


    bool isolated_multiple_connection(region_properties const& region,
            region_properties const& connected_region) const
    {
        if (connected_region.isolated != isolation_multiple)
        {
            return false;
        }

        // First step: compare turns of regions with turns of connected region
        set_type turn_ids = region.unique_turn_ids;
        for (set_iterator sit = connected_region.unique_turn_ids.begin();
             sit != connected_region.unique_turn_ids.end(); ++sit)
        {
            turn_ids.erase(*sit);
        }

        // There should be one connection (turn or cluster) left
        if (turn_ids.size() != 1)
        {
            return false;
        }

        for (set_iterator sit = connected_region.unique_turn_ids.begin();
             sit != connected_region.unique_turn_ids.end(); ++sit)
        {
            signed_size_type const id_or_index = *sit;
            if (id_or_index >= 0)
            {
                if (! ii_turn_connects_two_regions(region, connected_region, id_or_index))
                {
                    return false;
                }
            }
            else
            {
                signed_size_type const cluster_id = -id_or_index;
                typename Clusters::const_iterator it = m_clusters.find(cluster_id);
                if (it != m_clusters.end())
                {
                    cluster_info const& cinfo = it->second;
                    for (set_iterator cit = cinfo.turn_indices.begin();
                         cit != cinfo.turn_indices.end(); ++cit)
                    {
                        if (! ii_turn_connects_two_regions(region, connected_region, *cit))
                        {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }

    bool has_only_isolated_children(region_properties const& region) const
    {
        bool first_with_turn = true;
        signed_size_type first_turn_id = 0;

        for (typename connection_map::const_iterator it = region.connected_region_counts.begin();
             it != region.connected_region_counts.end(); ++it)
        {
            signed_size_type const region_id = it->first;
            connection_properties const& cprop = it->second;

            typename region_connection_map::const_iterator mit = m_connected_regions.find(region_id);
            if (mit == m_connected_regions.end())
            {
                // Should not occur
                return false;
            }

            region_properties const& connected_region = mit->second;

            if (cprop.count != 1)
            {
                // If there are more connections, check their isolation
                if (! isolated_multiple_connection(region, connected_region))
                {
                    return false;
                }
            }

            if (connected_region.isolated != isolation_yes
                && connected_region.isolated != isolation_multiple)
            {
                signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin();
                if (first_with_turn)
                {
                    first_turn_id = unique_turn_id;
                    first_with_turn = false;
                }
                else if (first_turn_id != unique_turn_id)
                {
                    return false;
                }
            }
        }

        // If there is only one connection (with a 'parent'), and all other
        // connections are itself isolated, it is isolated
        return true;
    }

    void get_isolated_regions()
    {
        typedef typename region_connection_map::iterator it_type;

        // First time: check regions isolated (one connection only),
        // semi-isolated (multiple connections between same region),
        // and complex isolated (connection with multiple rings but all
        // at same point)
        for (it_type it = m_connected_regions.begin();
             it != m_connected_regions.end(); ++it)
        {
            region_properties& properties = it->second;
            if (one_connection_to_another_region(properties))
            {
                properties.isolated = isolation_yes;
            }
            else if (multiple_connections_to_one_region(properties))
            {
                properties.isolated = isolation_multiple;
            }
            else if (one_connection_to_multiple_regions(properties))
            {
                properties.isolated = isolation_yes;
            }
        }

        // Propagate isolation to next level
        // TODO: should be optimized
        std::size_t defensive_check = 0;
        bool changed = true;
        while (changed && defensive_check++ < m_connected_regions.size())
        {
            changed = false;
            for (it_type it = m_connected_regions.begin();
                 it != m_connected_regions.end(); ++it)
            {
                region_properties& properties = it->second;

                if (properties.isolated == isolation_unknown
                        && has_only_isolated_children(properties))
                {
                    properties.isolated = isolation_yes;
                    changed = true;
                }
            }
        }
    }

    void assign_isolation()
    {
        for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
        {
            turn_type& turn = m_turns[turn_index];

            for (int op_index = 0; op_index < 2; op_index++)
            {
                turn_operation_type& op = turn.operations[op_index];
                typename region_connection_map::const_iterator mit = m_connected_regions.find(op.enriched.region_id);
                if (mit != m_connected_regions.end())
                {
                    region_properties const& prop = mit->second;
                    op.enriched.isolated = prop.isolated == isolation_yes;
                }
            }
        }
    }

    void assign_region_ids()
    {
        for (typename merge_map::const_iterator it
             = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
        {
            ring_identifier const& ring_id = it->first;
            merged_ring_properties const& properties = it->second;

            for (set_iterator sit = properties.turn_indices.begin();
                 sit != properties.turn_indices.end(); ++sit)
            {
                turn_type& turn = m_turns[*sit];

                if (! acceptable(turn))
                {
                    // No assignment necessary
                    continue;
                }

                for (int i = 0; i < 2; i++)
                {
                    turn_operation_type& op = turn.operations[i];
                    if (ring_id_by_seg_id(op.seg_id) == ring_id)
                    {
                        op.enriched.region_id = properties.region_id;
                    }
                }
            }
        }
    }

    void assign_connected_regions()
    {
        for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
        {
            turn_type const& turn = m_turns[turn_index];

            signed_size_type const unique_turn_id
                    = turn.is_clustered() ? -turn.cluster_id : turn_index;

            turn_operation_type op0 = turn.operations[0];
            turn_operation_type op1 = turn.operations[1];

            signed_size_type const& id0 = op0.enriched.region_id;
            signed_size_type const& id1 = op1.enriched.region_id;

            // Add region (by assigning) and add involved turns
            if (id0 != -1)
            {
                m_connected_regions[id0].region_id = id0;
                m_connected_regions[id0].unique_turn_ids.insert(unique_turn_id);
            }
            if (id1 != -1 && id0 != id1)
            {
                m_connected_regions[id1].region_id = id1;
                m_connected_regions[id1].unique_turn_ids.insert(unique_turn_id);
            }

            if (id0 != id1 && id0 != -1 && id1 != -1)
            {
                // Assign connections
                connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1];
                connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0];

                // Reference this turn or cluster to later check uniqueness on ring
                if (prop0.unique_turn_ids.count(unique_turn_id) == 0)
                {
                    prop0.count++;
                    prop0.unique_turn_ids.insert(unique_turn_id);
                }
                if (prop1.unique_turn_ids.count(unique_turn_id) == 0)
                {
                    prop1.count++;
                    prop1.unique_turn_ids.insert(unique_turn_id);
                }
            }
        }
    }

    inline bool acceptable(turn_type const& turn) const
    {
        // Discarded turns don't connect rings to the same region
        // Also xx are not relevant
        // (otherwise discarded colocated uu turn could make a connection)
        return ! turn.discarded
            && ! turn.both(operation_blocked);
    }

    inline bool connects_same_region(turn_type const& turn) const
    {
        if (! acceptable(turn))
        {
            return false;
        }

        if (! turn.is_clustered())
        {
            // If it is a uu/ii-turn (non clustered), it is never same region
            return ! (turn.both(operation_union) || turn.both(operation_intersection));
        }

        if (BOOST_GEOMETRY_CONDITION(target_operation == operation_union))
        {
            // It is a cluster, check zones
            // (assigned by sort_by_side/handle colocations) of both operations
            return turn.operations[0].enriched.zone
                    == turn.operations[1].enriched.zone;
        }

        // For an intersection, two regions connect if they are not ii
        // (ii-regions are isolated) or, in some cases, not iu (for example
        // when a multi-polygon is inside an interior ring and connecting it)
        return ! (turn.both(operation_intersection)
                  || turn.combination(operation_intersection, operation_union));
    }


    inline signed_size_type get_region_id(turn_operation_type const& op) const
    {
        return op.enriched.region_id;
    }


    void create_region(signed_size_type& new_region_id, ring_identifier const& ring_id,
                merged_ring_properties& properties, signed_size_type region_id = -1)
    {
        if (properties.region_id > 0)
        {
            // Already handled
            return;
        }

        // Assign new id if this is a new region
        if (region_id == -1)
        {
            region_id = new_region_id++;
        }

        // Assign this ring to specified region
        properties.region_id = region_id;

#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
        std::cout << " ADD " << ring_id << "  TO REGION " << region_id << std::endl;
#endif

        // Find connecting rings, recursively
        for (set_iterator sit = properties.turn_indices.begin();
             sit != properties.turn_indices.end(); ++sit)
        {
            signed_size_type const turn_index = *sit;
            turn_type const& turn = m_turns[turn_index];
            if (! connects_same_region(turn))
            {
                // This is a non clustered uu/ii-turn, or a cluster connecting different 'zones'
                continue;
            }

            // Union: This turn connects two rings (interior connected), create the region
            // Intersection: This turn connects two rings, set same regions for these two rings
            for (int op_index = 0; op_index < 2; op_index++)
            {
                turn_operation_type const& op = turn.operations[op_index];
                ring_identifier connected_ring_id = ring_id_by_seg_id(op.seg_id);
                if (connected_ring_id != ring_id)
                {
                    propagate_region(new_region_id, connected_ring_id, region_id);
                }
            }
        }
    }

    void propagate_region(signed_size_type& new_region_id,
            ring_identifier const& ring_id, signed_size_type region_id)
    {
        typename merge_map::iterator it = m_turns_per_ring.find(ring_id);
        if (it != m_turns_per_ring.end())
        {
            create_region(new_region_id, ring_id, it->second, region_id);
        }
    }


    void iterate()
    {
#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
        std::cout << "BEGIN ITERATION GETTING REGION_IDS" << std::endl;
#endif

        // Collect turns per ring
        m_turns_per_ring.clear();
        m_connected_regions.clear();

        for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
        {
            turn_type const& turn = m_turns[turn_index];

            if (turn.discarded
                && BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection))
            {
                // Discarded turn (union currently still needs it to determine regions)
                continue;
            }

            for (int op_index = 0; op_index < 2; op_index++)
            {
                turn_operation_type const& op = turn.operations[op_index];
                m_turns_per_ring[ring_id_by_seg_id(op.seg_id)].turn_indices.insert(turn_index);
            }
        }

        // All rings having turns are in turns/ring map. Process them.
        {
            signed_size_type new_region_id = 1;
            for (typename merge_map::iterator it
                 = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
            {
                create_region(new_region_id, it->first, it->second);
            }

            assign_region_ids();
            assign_connected_regions();
            get_isolated_regions();
            assign_isolation();
        }

#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
        std::cout << "END ITERATION GETTIN REGION_IDS" << std::endl;

        for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
        {
            turn_type const& turn = m_turns[turn_index];

            if ((turn.both(operation_union) || turn.both(operation_intersection))
                 && ! turn.is_clustered())
            {
                std::cout << "UU/II RESULT "
                             << turn_index << " -> "
                          << turn.operations[0].enriched.region_id
                          << " " << turn.operations[1].enriched.region_id
                          << std::endl;
            }
        }

        for (typename Clusters::const_iterator it = m_clusters.begin(); it != m_clusters.end(); ++it)
        {
            cluster_info const& cinfo = it->second;
            std::cout << "CL RESULT " << it->first
                         << " -> " << cinfo.open_count << std::endl;
        }
#endif

    }

private:

    Geometry1 const& m_geometry1;
    Geometry2 const& m_geometry2;
    Turns& m_turns;
    Clusters& m_clusters;
    merge_map m_turns_per_ring;
    region_connection_map m_connected_regions;
    RobustPolicy const& m_robust_policy;
    Visitor& m_visitor;
};

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

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP
Commit	Line	Data
b32b8144 FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2
	3	// Copyright (c) 2015-2016 Barend Gehrels, Amsterdam, the Netherlands.
	4
20effc67 TL	5	// This file was modified by Oracle on 2018-2020.
20effc67 TL	6	// Modifications copyright (c) 2018-2020 Oracle and/or its affiliates.
92f5a8d4 TL	7
	8	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
	9
b32b8144 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_TRAVERSAL_SWITCH_DETECTOR_HPP
	15	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP
	16
	17	#include <cstddef>
92f5a8d4	18	#include <map>
b32b8144	19
20effc67	20	#include <boost/range/value_type.hpp>
b32b8144 FG	21
	22	#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
	23	#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
	24	#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
	25	#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
	26	#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
	27	#include <boost/geometry/core/access.hpp>
	28	#include <boost/geometry/core/assert.hpp>
11fdf7f2	29	#include <boost/geometry/util/condition.hpp>
b32b8144 FG	30
	31	namespace boost { namespace geometry
	32	{
	33
	34	#ifndef DOXYGEN_NO_DETAIL
	35	namespace detail { namespace overlay
	36	{
	37
b32b8144 FG	38	template
	39	<
	40	bool Reverse1,
	41	bool Reverse2,
	42	overlay_type OverlayType,
	43	typename Geometry1,
	44	typename Geometry2,
	45	typename Turns,
	46	typename Clusters,
	47	typename RobustPolicy,
	48	typename Visitor
	49	>
	50	struct traversal_switch_detector
	51	{
11fdf7f2 TL	52	static const operation_type target_operation
	53	= operation_from_overlay<OverlayType>::value;
	54	static const operation_type opposite_operation
	55	= target_operation == operation_union
	56	? operation_intersection
	57	: operation_union;
	58
b32b8144 FG	59	enum isolation_type
	60	{
	61	isolation_unknown = -1,
	62	isolation_no = 0,
	63	isolation_yes = 1,
	64	isolation_multiple = 2
	65	};
	66
	67	typedef typename boost::range_value<Turns>::type turn_type;
	68	typedef typename turn_type::turn_operation_type turn_operation_type;
	69	typedef std::set<signed_size_type> set_type;
	70
	71	// Per ring, first turns are collected (in turn_indices), and later
	72	// a region_id is assigned
	73	struct merged_ring_properties
	74	{
	75	signed_size_type region_id;
	76	set_type turn_indices;
	77
	78	merged_ring_properties()
	79	: region_id(-1)
	80	{}
	81	};
	82
	83	struct connection_properties
	84	{
	85	std::size_t count;
	86	// Contains turn-index OR, if clustered, minus-cluster_id
	87	set_type unique_turn_ids;
	88	connection_properties()
	89	: count(0)
	90	{}
	91	};
	92
	93	typedef std::map<signed_size_type, connection_properties> connection_map;
	94
	95	// Per region, a set of properties is maintained, including its connections
	96	// to other regions
	97	struct region_properties
	98	{
	99	signed_size_type region_id;
	100	isolation_type isolated;
	101	set_type unique_turn_ids;
	102
	103	// Maps from connected region_id to their properties
	104	connection_map connected_region_counts;
	105
	106	region_properties()
	107	: region_id(-1)
	108	, isolated(isolation_unknown)
	109	{}
	110	};
	111
	112	// Keeps turn indices per ring
	113	typedef std::map<ring_identifier, merged_ring_properties > merge_map;
	114	typedef std::map<signed_size_type, region_properties> region_connection_map;
	115
	116	typedef set_type::const_iterator set_iterator;
	117
	118	inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2,
	119	Turns& turns, Clusters& clusters,
	120	RobustPolicy const& robust_policy, Visitor& visitor)
	121	: m_geometry1(geometry1)
	122	, m_geometry2(geometry2)
123	, m_turns(turns)
124	, m_clusters(clusters)
125	, m_robust_policy(robust_policy)
126	, m_visitor(visitor)
127	{
128	}
129
b32b8144 FG	130	bool one_connection_to_another_region(region_properties const& region) const
	131	{
	132	// For example:
	133	// +----------------------+
	134	// \| __ \|
	135	// \| / \\|
	136	// \| \| x
	137	// \| \__/\|
	138	// \| \|
	139	// +----------------------+
	140
	141	if (region.connected_region_counts.size() == 1)
	142	{
	143	connection_properties const& cprop = region.connected_region_counts.begin()->second;
	144	return cprop.count <= 1;
	145	}
	146	return region.connected_region_counts.empty();
	147	}
	148
	149	// TODO: might be combined with previous
	150	bool multiple_connections_to_one_region(region_properties const& region) const
	151	{
	152	// For example:
	153	// +----------------------+
	154	// \| __ \|
	155	// \| / \\|
	156	// \| \| x
	157	// \| \ /\|
	158	// \| / \\|
	159	// \| \| x
	160	// \| \__/\|
	161	// \| \|
	162	// +----------------------+
	163
	164	if (region.connected_region_counts.size() == 1)
	165	{
	166	connection_properties const& cprop = region.connected_region_counts.begin()->second;
	167	return cprop.count > 1;
	168	}
	169	return false;
	170	}
	171
	172	bool one_connection_to_multiple_regions(region_properties const& region) const
	173	{
	174	// For example:
	175	// +----------------------+
	176	// \| __ \| __
	177	// \| / \\|/ \|
	178	// \| \| x \|
	179	// \| \__/\|\__\|
	180	// \| \|
	181	// +----------------------+
	182
	183	bool first = true;
	184	signed_size_type first_turn_id = 0;
	185	for (typename connection_map::const_iterator it = region.connected_region_counts.begin();
	186	it != region.connected_region_counts.end(); ++it)
	187	{
	188	connection_properties const& cprop = it->second;
	189
	190	if (cprop.count != 1)
	191	{
	192	return false;
	193	}
194	signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin();
195	if (first)
196	{
197	first_turn_id = unique_turn_id;
198	first = false;
199	}
200	else if (first_turn_id != unique_turn_id)
201	{
202	return false;
203	}
204	}
205	return true;
206	}
207
11fdf7f2 TL	208	bool ii_turn_connects_two_regions(region_properties const& region,
	209	region_properties const& connected_region,
	210	signed_size_type turn_index) const
	211	{
	212	turn_type const& turn = m_turns[turn_index];
	213	if (! turn.both(operation_intersection))
	214	{
	215	return false;
	216	}
	217
	218	signed_size_type const id0 = turn.operations[0].enriched.region_id;
	219	signed_size_type const id1 = turn.operations[1].enriched.region_id;
	220
	221	return (id0 == region.region_id && id1 == connected_region.region_id)
	222	\|\| (id1 == region.region_id && id0 == connected_region.region_id);
	223	}
	224
	225
	226	bool isolated_multiple_connection(region_properties const& region,
	227	region_properties const& connected_region) const
	228	{
	229	if (connected_region.isolated != isolation_multiple)
	230	{
	231	return false;
	232	}
	233
	234	// First step: compare turns of regions with turns of connected region
	235	set_type turn_ids = region.unique_turn_ids;
	236	for (set_iterator sit = connected_region.unique_turn_ids.begin();
	237	sit != connected_region.unique_turn_ids.end(); ++sit)
	238	{
	239	turn_ids.erase(*sit);
	240	}
	241
	242	// There should be one connection (turn or cluster) left
	243	if (turn_ids.size() != 1)
	244	{
	245	return false;
	246	}
	247
	248	for (set_iterator sit = connected_region.unique_turn_ids.begin();
	249	sit != connected_region.unique_turn_ids.end(); ++sit)
	250	{
	251	signed_size_type const id_or_index = *sit;
	252	if (id_or_index >= 0)
	253	{
	254	if (! ii_turn_connects_two_regions(region, connected_region, id_or_index))
	255	{
	256	return false;
	257	}
	258	}
	259	else
	260	{
	261	signed_size_type const cluster_id = -id_or_index;
	262	typename Clusters::const_iterator it = m_clusters.find(cluster_id);
	263	if (it != m_clusters.end())
	264	{
	265	cluster_info const& cinfo = it->second;
	266	for (set_iterator cit = cinfo.turn_indices.begin();
	267	cit != cinfo.turn_indices.end(); ++cit)
	268	{
	269	if (! ii_turn_connects_two_regions(region, connected_region, *cit))
	270	{
	271	return false;
272	}
273	}
274	}
275	}
276	}
277
278	return true;
279	}
280
b32b8144 FG	281	bool has_only_isolated_children(region_properties const& region) const
	282	{
	283	bool first_with_turn = true;
b32b8144	284	signed_size_type first_turn_id = 0;
b32b8144 FG	285
	286	for (typename connection_map::const_iterator it = region.connected_region_counts.begin();
	287	it != region.connected_region_counts.end(); ++it)
	288	{
	289	signed_size_type const region_id = it->first;
	290	connection_properties const& cprop = it->second;
	291
	292	typename region_connection_map::const_iterator mit = m_connected_regions.find(region_id);
	293	if (mit == m_connected_regions.end())
	294	{
	295	// Should not occur
	296	return false;
	297	}
	298
	299	region_properties const& connected_region = mit->second;
	300
b32b8144 FG	301	if (cprop.count != 1)
b32b8144 FG	302	{
11fdf7f2 TL	303	// If there are more connections, check their isolation
11fdf7f2 TL	304	if (! isolated_multiple_connection(region, connected_region))
b32b8144 FG	305	{
	306	return false;
	307	}
b32b8144 FG	308	}
b32b8144 FG	309
11fdf7f2 TL	310	if (connected_region.isolated != isolation_yes
11fdf7f2 TL	311	&& connected_region.isolated != isolation_multiple)
b32b8144 FG	312	{
	313	signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin();
	314	if (first_with_turn)
	315	{
	316	first_turn_id = unique_turn_id;
	317	first_with_turn = false;
	318	}
	319	else if (first_turn_id != unique_turn_id)
	320	{
	321	return false;
	322	}
	323	}
	324	}
11fdf7f2	325
b32b8144 FG	326	// If there is only one connection (with a 'parent'), and all other
	327	// connections are itself isolated, it is isolated
	328	return true;
	329	}
	330
	331	void get_isolated_regions()
	332	{
	333	typedef typename region_connection_map::iterator it_type;
	334
	335	// First time: check regions isolated (one connection only),
	336	// semi-isolated (multiple connections between same region),
	337	// and complex isolated (connection with multiple rings but all
	338	// at same point)
	339	for (it_type it = m_connected_regions.begin();
	340	it != m_connected_regions.end(); ++it)
	341	{
	342	region_properties& properties = it->second;
	343	if (one_connection_to_another_region(properties))
	344	{
	345	properties.isolated = isolation_yes;
	346	}
	347	else if (multiple_connections_to_one_region(properties))
	348	{
	349	properties.isolated = isolation_multiple;
	350	}
	351	else if (one_connection_to_multiple_regions(properties))
	352	{
	353	properties.isolated = isolation_yes;
	354	}
	355	}
	356
	357	// Propagate isolation to next level
	358	// TODO: should be optimized
	359	std::size_t defensive_check = 0;
	360	bool changed = true;
	361	while (changed && defensive_check++ < m_connected_regions.size())
	362	{
	363	changed = false;
	364	for (it_type it = m_connected_regions.begin();
	365	it != m_connected_regions.end(); ++it)
	366	{
	367	region_properties& properties = it->second;
	368
	369	if (properties.isolated == isolation_unknown
	370	&& has_only_isolated_children(properties))
	371	{
	372	properties.isolated = isolation_yes;
	373	changed = true;
	374	}
	375	}
	376	}
	377	}
	378
	379	void assign_isolation()
	380	{
	381	for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
	382	{
	383	turn_type& turn = m_turns[turn_index];
	384
	385	for (int op_index = 0; op_index < 2; op_index++)
	386	{
	387	turn_operation_type& op = turn.operations[op_index];
	388	typename region_connection_map::const_iterator mit = m_connected_regions.find(op.enriched.region_id);
	389	if (mit != m_connected_regions.end())
390	{
391	region_properties const& prop = mit->second;
392	op.enriched.isolated = prop.isolated == isolation_yes;
393	}
394	}
395	}
396	}
397
398	void assign_region_ids()
399	{
400	for (typename merge_map::const_iterator it
401	= m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
402	{
403	ring_identifier const& ring_id = it->first;
404	merged_ring_properties const& properties = it->second;
405
406	for (set_iterator sit = properties.turn_indices.begin();
407	sit != properties.turn_indices.end(); ++sit)
408	{
409	turn_type& turn = m_turns[*sit];
410
11fdf7f2 TL	411	if (! acceptable(turn))
	412	{
	413	// No assignment necessary
	414	continue;
	415	}
	416
b32b8144 FG	417	for (int i = 0; i < 2; i++)
	418	{
	419	turn_operation_type& op = turn.operations[i];
	420	if (ring_id_by_seg_id(op.seg_id) == ring_id)
	421	{
	422	op.enriched.region_id = properties.region_id;
	423	}
	424	}
	425	}
	426	}
	427	}
	428
	429	void assign_connected_regions()
	430	{
	431	for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
	432	{
	433	turn_type const& turn = m_turns[turn_index];
	434
	435	signed_size_type const unique_turn_id
	436	= turn.is_clustered() ? -turn.cluster_id : turn_index;
	437
	438	turn_operation_type op0 = turn.operations[0];
	439	turn_operation_type op1 = turn.operations[1];
	440
	441	signed_size_type const& id0 = op0.enriched.region_id;
	442	signed_size_type const& id1 = op1.enriched.region_id;
	443
	444	// Add region (by assigning) and add involved turns
	445	if (id0 != -1)
	446	{
	447	m_connected_regions[id0].region_id = id0;
	448	m_connected_regions[id0].unique_turn_ids.insert(unique_turn_id);
	449	}
	450	if (id1 != -1 && id0 != id1)
	451	{
	452	m_connected_regions[id1].region_id = id1;
	453	m_connected_regions[id1].unique_turn_ids.insert(unique_turn_id);
	454	}
	455
	456	if (id0 != id1 && id0 != -1 && id1 != -1)
	457	{
	458	// Assign connections
	459	connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1];
	460	connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0];
	461
	462	// Reference this turn or cluster to later check uniqueness on ring
	463	if (prop0.unique_turn_ids.count(unique_turn_id) == 0)
	464	{
	465	prop0.count++;
	466	prop0.unique_turn_ids.insert(unique_turn_id);
	467	}
	468	if (prop1.unique_turn_ids.count(unique_turn_id) == 0)
	469	{
	470	prop1.count++;
	471	prop1.unique_turn_ids.insert(unique_turn_id);
	472	}
	473	}
	474	}
	475	}
	476
11fdf7f2 TL	477	inline bool acceptable(turn_type const& turn) const
	478	{
	479	// Discarded turns don't connect rings to the same region
	480	// Also xx are not relevant
	481	// (otherwise discarded colocated uu turn could make a connection)
	482	return ! turn.discarded
	483	&& ! turn.both(operation_blocked);
	484	}
	485
b32b8144 FG	486	inline bool connects_same_region(turn_type const& turn) const
b32b8144 FG	487	{
11fdf7f2	488	if (! acceptable(turn))
b32b8144	489	{
b32b8144 FG	490	return false;
	491	}
	492
	493	if (! turn.is_clustered())
	494	{
	495	// If it is a uu/ii-turn (non clustered), it is never same region
	496	return ! (turn.both(operation_union) \|\| turn.both(operation_intersection));
	497	}
	498
11fdf7f2	499	if (BOOST_GEOMETRY_CONDITION(target_operation == operation_union))
b32b8144 FG	500	{
	501	// It is a cluster, check zones
	502	// (assigned by sort_by_side/handle colocations) of both operations
	503	return turn.operations[0].enriched.zone
	504	== turn.operations[1].enriched.zone;
	505	}
	506
	507	// For an intersection, two regions connect if they are not ii
	508	// (ii-regions are isolated) or, in some cases, not iu (for example
	509	// when a multi-polygon is inside an interior ring and connecting it)
	510	return ! (turn.both(operation_intersection)
	511	\|\| turn.combination(operation_intersection, operation_union));
	512	}
	513
	514
	515	inline signed_size_type get_region_id(turn_operation_type const& op) const
	516	{
	517	return op.enriched.region_id;
	518	}
	519
	520
	521	void create_region(signed_size_type& new_region_id, ring_identifier const& ring_id,
	522	merged_ring_properties& properties, signed_size_type region_id = -1)
	523	{
	524	if (properties.region_id > 0)
	525	{
	526	// Already handled
	527	return;
	528	}
	529
	530	// Assign new id if this is a new region
	531	if (region_id == -1)
	532	{
	533	region_id = new_region_id++;
	534	}
	535
	536	// Assign this ring to specified region
	537	properties.region_id = region_id;
	538
	539	#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
	540	std::cout << " ADD " << ring_id << " TO REGION " << region_id << std::endl;
	541	#endif
	542
	543	// Find connecting rings, recursively
	544	for (set_iterator sit = properties.turn_indices.begin();
	545	sit != properties.turn_indices.end(); ++sit)
	546	{
	547	signed_size_type const turn_index = *sit;
	548	turn_type const& turn = m_turns[turn_index];
	549	if (! connects_same_region(turn))
	550	{
	551	// This is a non clustered uu/ii-turn, or a cluster connecting different 'zones'
	552	continue;
	553	}
	554
	555	// Union: This turn connects two rings (interior connected), create the region
	556	// Intersection: This turn connects two rings, set same regions for these two rings
	557	for (int op_index = 0; op_index < 2; op_index++)
	558	{
	559	turn_operation_type const& op = turn.operations[op_index];
	560	ring_identifier connected_ring_id = ring_id_by_seg_id(op.seg_id);
	561	if (connected_ring_id != ring_id)
	562	{
	563	propagate_region(new_region_id, connected_ring_id, region_id);
564	}
565	}
566	}
567	}
568
569	void propagate_region(signed_size_type& new_region_id,
570	ring_identifier const& ring_id, signed_size_type region_id)
571	{
572	typename merge_map::iterator it = m_turns_per_ring.find(ring_id);
573	if (it != m_turns_per_ring.end())
574	{
575	create_region(new_region_id, ring_id, it->second, region_id);
576	}
577	}
578
579
580	void iterate()
581	{
582	#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
11fdf7f2	583	std::cout << "BEGIN ITERATION GETTING REGION_IDS" << std::endl;
b32b8144 FG	584	#endif
	585
	586	// Collect turns per ring
	587	m_turns_per_ring.clear();
	588	m_connected_regions.clear();
	589
	590	for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
	591	{
	592	turn_type const& turn = m_turns[turn_index];
	593
	594	if (turn.discarded
11fdf7f2	595	&& BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection))
b32b8144 FG	596	{
	597	// Discarded turn (union currently still needs it to determine regions)
	598	continue;
	599	}
	600
	601	for (int op_index = 0; op_index < 2; op_index++)
	602	{
	603	turn_operation_type const& op = turn.operations[op_index];
	604	m_turns_per_ring[ring_id_by_seg_id(op.seg_id)].turn_indices.insert(turn_index);
	605	}
	606	}
	607
	608	// All rings having turns are in turns/ring map. Process them.
	609	{
	610	signed_size_type new_region_id = 1;
	611	for (typename merge_map::iterator it
	612	= m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
	613	{
	614	create_region(new_region_id, it->first, it->second);
	615	}
	616
	617	assign_region_ids();
	618	assign_connected_regions();
	619	get_isolated_regions();
	620	assign_isolation();
	621	}
	622
b32b8144	623	#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
11fdf7f2	624	std::cout << "END ITERATION GETTIN REGION_IDS" << std::endl;
b32b8144 FG	625
	626	for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
	627	{
	628	turn_type const& turn = m_turns[turn_index];
	629
	630	if ((turn.both(operation_union) \|\| turn.both(operation_intersection))
	631	&& ! turn.is_clustered())
	632	{
11fdf7f2	633	std::cout << "UU/II RESULT "
b32b8144	634	<< turn_index << " -> "
11fdf7f2 TL	635	<< turn.operations[0].enriched.region_id
	636	<< " " << turn.operations[1].enriched.region_id
	637	<< std::endl;
b32b8144 FG	638	}
	639	}
	640
	641	for (typename Clusters::const_iterator it = m_clusters.begin(); it != m_clusters.end(); ++it)
	642	{
	643	cluster_info const& cinfo = it->second;
11fdf7f2 TL	644	std::cout << "CL RESULT " << it->first
11fdf7f2 TL	645	<< " -> " << cinfo.open_count << std::endl;
b32b8144 FG	646	}
	647	#endif
	648
	649	}
	650
	651	private:
	652
	653	Geometry1 const& m_geometry1;
	654	Geometry2 const& m_geometry2;
	655	Turns& m_turns;
	656	Clusters& m_clusters;
	657	merge_map m_turns_per_ring;
	658	region_connection_map m_connected_regions;
	659	RobustPolicy const& m_robust_policy;
	660	Visitor& m_visitor;
	661	};
	662
	663	}} // namespace detail::overlay
	664	#endif // DOXYGEN_NO_DETAIL
	665
	666	}} // namespace boost::geometry
	667
	668	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP