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

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

// Copyright (c) 2007-2017 Barend Gehrels, Amsterdam, the Netherlands.

// 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_INTERSECTION_PATTERNS_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP

#include <cstddef>
#include <vector>

#include <boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp>
#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>

namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{

inline bool check_pairs(std::vector<sort_by_side::rank_with_rings> const& aggregation,
                        signed_size_type incoming_region_id,
                        std::size_t first, std::size_t last)
{
    // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy

    for (std::size_t i = first; i <= last; i += 2)
    {
        sort_by_side::rank_with_rings const& curr = aggregation[i];
        sort_by_side::rank_with_rings const& next = aggregation[i + 1];
        signed_size_type const curr_id = curr.region_id();
        signed_size_type const next_id = next.region_id();

        bool const possible =
                curr.rings.size() == 2
                && curr.is_isolated()
                && curr.has_unique_region_id()
                && next.rings.size() == 2
                && next.is_isolated()
                && next.has_unique_region_id()
                && curr_id == next_id
                && curr_id != incoming_region_id;

        if (! possible)
        {
            return false;
        }
    }

    return true;
}

inline bool intersection_pattern_common_interior1(std::size_t& selected_rank,
           std::vector<sort_by_side::rank_with_rings> const& aggregation)
{
    // Pattern: coming from exterior ring, encountering an isolated
    // parallel interior ring, which should be skipped, and the first
    // left (normally intersection takes first right) should be taken.
    // Solves cases #case_133_multi
    // and #case_recursive_boxes_49

    std::size_t const n = aggregation.size();
    if (n < 4)
    {
        return false;
    }

    sort_by_side::rank_with_rings const& incoming = aggregation.front();
    sort_by_side::rank_with_rings const& outgoing = aggregation.back();

    bool const incoming_ok =
        incoming.all_from()
        && incoming.rings.size() == 1
        && incoming.has_only(operation_intersection);

    if (! incoming_ok)
    {
        return false;
    }

    bool const outgoing_ok =
        outgoing.all_to()
        && outgoing.rings.size() == 1
        && outgoing.has_only(operation_intersection)
        && outgoing.region_id() == incoming.region_id();

    if (! outgoing_ok)
    {
        return false;
    }

    if (check_pairs(aggregation, incoming.region_id(), 1, n - 2))
    {
        selected_rank = n - 1;
        return true;
    }
    return false;
}

inline bool intersection_pattern_common_interior2(std::size_t& selected_rank,
           std::vector<sort_by_side::rank_with_rings> const& aggregation)
{
    // Pattern: coming from two exterior rings, encountering two isolated
    // equal interior rings

    // See (for example, for ii) #case_recursive_boxes_53:

    // INCOMING:
    // Rank 0  {11[0] (s:0, m:0) i F rgn: 1 ISO}             {13[1] (s:1, m:0) i F rgn: 1 ISO}

    // PAIR:
    // Rank 1  {13[0] (s:0, r:1, m:0) i T rgn: 3 ISO ->16}   {11[1] (s:1, r:5, m:0) i T rgn: 3 ISO ->16}
    // Rank 2  {13[0] (s:0, r:1, m:0) i F rgn: 3 ISO}        {11[1] (s:1, r:5, m:0) i F rgn: 3 ISO}

    // LEAVING (in the same direction, take last one)
    // Rank 3  {11[0] (s:0, m:0) i T rgn: 1 ISO ->10}        {13[1] (s:1, m:0) i T rgn: 1 ISO ->10}


    std::size_t const n = aggregation.size();
    if (n < 4)
    {
        return false;
    }

    sort_by_side::rank_with_rings const& incoming = aggregation.front();
    sort_by_side::rank_with_rings const& outgoing = aggregation.back();

    bool const incoming_ok =
        incoming.all_from()
        && incoming.rings.size() == 2
        && incoming.has_unique_region_id();

    if (! incoming_ok)
    {
        return false;
    }

    bool const outgoing_ok =
        outgoing.all_to()
        && outgoing.rings.size() == 2
        && outgoing.has_unique_region_id()
        && outgoing.region_id() == incoming.region_id();

    if (! outgoing_ok)
    {
        return false;
    }

    bool const operation_ok =
            (incoming.has_only(operation_continue) && outgoing.has_only(operation_continue))
             || (incoming.has_only(operation_intersection) && outgoing.has_only(operation_intersection));

    if (! operation_ok)
    {
        return false;
    }

    // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
    if (check_pairs(aggregation, incoming.region_id(), 1, n - 2))
    {
        selected_rank = n - 1;
        return true;
    }
    return false;
}

inline bool intersection_pattern_common_interior3(std::size_t& selected_rank,
           std::vector<sort_by_side::rank_with_rings> const& aggregation)
{
    // Pattern: approaches colocated turn (exterior+interior) from two
    // different directions, and both leaves in the same direction

    // See #case_136_multi:
    // INCOMING:
    //Rank 0  {10[0] (s:0, m:0) c F rgn: 1 ISO}

    // PAIR:
    //Rank 1  {14[0] (s:0, r:0, m:0) i T rgn: 2 ISO ->16} {11[1] (s:1, r:1, m:0) i T rgn: 2 ISO ->16}
    //Rank 2  {14[0] (s:0, r:0, m:0) i F rgn: 2 ISO}      {11[1] (s:1, r:1, m:0) i F rgn: 2 ISO}

    // LEAVING (select this one):
    //Rank 3  {10[0] (s:0, m:0) c T rgn: 1 ISO ->12}      {10[1] (s:1, m:0) c T rgn: 1 ISO ->12}

    // ADDITIONALLY: (other polygon coming in)
    //Rank 4  {10[1] (s:1, m:0) c F rgn: 1 ISO}

    std::size_t const n = aggregation.size();
    if (n < 4)
    {
        return false;
    }

    sort_by_side::rank_with_rings const& incoming = aggregation.front();
    sort_by_side::rank_with_rings const& outgoing = aggregation[n - 2];
    sort_by_side::rank_with_rings const& last = aggregation.back();

    bool const incoming_ok =
        incoming.all_from()
        && incoming.rings.size() == 1
        && incoming.has_only(operation_continue);

    if (! incoming_ok)
    {
        return false;
    }

    bool const outgoing_ok =
        outgoing.all_to()
        && outgoing.rings.size() == 2
        && outgoing.has_only(operation_continue)
        && outgoing.has_unique_region_id()
        && outgoing.region_id() == incoming.region_id()
        && last.all_from()
        && last.rings.size() == 1
        && last.region_id() == incoming.region_id()
        && last.all_from();

    if (! outgoing_ok)
    {
        return false;
    }

    // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
    if (check_pairs(aggregation, incoming.region_id(), 1, n - 3))
    {
        selected_rank = n - 2;
        return true;
    }
    return false;
}


inline bool intersection_pattern_common_interior4(std::size_t& selected_rank,
           std::vector<sort_by_side::rank_with_rings> const& aggregation)
{
    // Pattern: approaches colocated turn (exterior+interior) from same
    // direction, but leaves in two different directions

    // See #case_137_multi:

    // INCOMING:
    //Rank 0  {11[0] (s:0, m:0) i F rgn: 1 ISO}            {10[1] (s:1, m:0) i F rgn: 1 ISO}

    // PAIR:
    //Rank 1  {13[0] (s:0, r:0, m:0) i T rgn: 2 ISO ->15}  {11[1] (s:1, r:1, m:0) i T rgn: 2 ISO ->15}
    //Rank 2  {13[0] (s:0, r:0, m:0) i F rgn: 2 ISO}       {11[1] (s:1, r:1, m:0) i F rgn: 2 ISO}

    // LEAVING (in two different directions, take penultimate one)
    //Rank 3  {10[1] (s:1, m:0) i T rgn: 1 ISO ->0}
    //Rank 4  {11[0] (s:0, m:0) i T rgn: 1 ISO ->12}

    std::size_t const n = aggregation.size();
    if (n < 4)
    {
        return false;
    }

    sort_by_side::rank_with_rings const& incoming = aggregation.front();
    sort_by_side::rank_with_rings const& extra = aggregation[n - 2];
    sort_by_side::rank_with_rings const& outgoing = aggregation.back();

    bool const incoming_ok =
        incoming.all_from()
        && incoming.rings.size() == 2
        && incoming.has_unique_region_id()
        && incoming.has_only(operation_intersection);

    if (! incoming_ok)
    {
        return false;
    }

    bool const outgoing_ok =
        outgoing.all_to()
        && outgoing.rings.size() == 1
        && outgoing.has_only(operation_intersection)
        && outgoing.region_id() == incoming.region_id()
        && extra.all_to()
        && extra.rings.size() == 1
        && extra.has_only(operation_intersection)
        && extra.region_id() == incoming.region_id();

    if (! outgoing_ok)
    {
        return false;
    }

    // Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
    if (check_pairs(aggregation, incoming.region_id(), 1, n - 3))
    {
        selected_rank = n - 2;
        return true;
    }
    return false;
}

inline bool intersection_pattern_common_interior5(std::size_t& selected_rank,
           std::vector<sort_by_side::rank_with_rings> const& aggregation)
{
    // Pattern: isolated regions

    // See #case_recursive_boxes_65

    // INCOMING:
    //    Rank 0  {19[0] (s:0, r:2, m:0) i F rgn: 4 ISO}

    //    Rank 1  {19[1] (s:1, m:0) i T rgn: 1 ISO FIN ->18 (2.5)}
    //    Rank 2  {21[1] (s:1, m:2) i F rgn: 1 ISO}
    //    Rank 3  {21[1] (s:1, m:2) i T rgn: 1 ISO ->17 (2)}
    //    Rank 4  {19[1] (s:1, m:0) i F rgn: 1 ISO FIN}

    // LEAVING (take this one):
    //    Rank 5  {19[0] (s:0, r:2, m:0) i T rgn: 4 ISO ->22 (1)}

    std::size_t const n = aggregation.size();
    if (n < 3)
    {
        return false;
    }

    sort_by_side::rank_with_rings const& incoming = aggregation.front();
    sort_by_side::rank_with_rings const& outgoing = aggregation.back();

    bool const incoming_ok =
        incoming.all_from()
        && incoming.has_unique_region_id()
        && incoming.is_isolated();

    if (! incoming_ok)
    {
        return false;
    }

    signed_size_type const incoming_region_id = incoming.region_id();

    bool const outgoing_ok =
        outgoing.all_to()
        && outgoing.has_unique_region_id()
        && outgoing.is_isolated()
        && outgoing.region_id() == incoming_region_id;

    if (! outgoing_ok)
    {
        return false;
    }

    selected_rank = n - 1;
    bool other_region = true;

    // Assumed is that other regions go (T) and come back (F)
    for (std::size_t i = 1; i < n - 1; i++)
    {
        sort_by_side::rank_with_rings const& rwr = aggregation[i];
        if (! rwr.has_unique_region_id() || ! rwr.is_isolated())
        {
            return false;
        }
        signed_size_type const region_id = rwr.region_id();
        if (other_region && region_id != incoming_region_id)
        {
            // OK
        }
        else if (other_region && region_id == incoming_region_id)
        {
            // OK, next phase (same region as incoming region)
            selected_rank = i;
            other_region = false;
        }
        else if (! other_region && region_id != incoming_region_id)
        {
            // After that the region is the same is incoming, it should
            // stay like that
            return false;
        }
    }

    return true;
}

inline bool intersection_pattern_common_interior6(std::size_t& selected_rank,
           std::vector<sort_by_side::rank_with_rings> const& aggregation)
{
    // Pattern: isolated regions in between

    // See #case_recursive_boxes_75

    // Incoming: one region
    // In between: several rings having isolated region, all the same
    // Outging == incoming

    std::size_t const n = aggregation.size();
    if (n < 3)
    {
        return false;
    }

    sort_by_side::rank_with_rings const& incoming = aggregation.front();
    sort_by_side::rank_with_rings const& outgoing = aggregation.back();
    sort_by_side::rank_with_rings const& first_isolated = aggregation[2];

    bool const incoming_ok =
        incoming.all_from()
        && incoming.has_unique_region_id()
        && ! incoming.is_isolated();

    if (! incoming_ok)
    {
        return false;
    }

    signed_size_type const incoming_region_id = incoming.region_id();

    bool const outgoing_ok =
        outgoing.all_to()
        && outgoing.has_unique_region_id()
        && ! outgoing.is_isolated()
        && outgoing.region_id() == incoming_region_id;

    if (! outgoing_ok)
    {
        return false;
    }

    const signed_size_type isolated_region_id = first_isolated.region_id();

    for (std::size_t i = 1; i < n - 1; i++)
    {
        sort_by_side::rank_with_rings const& rwr = aggregation[i];
        if (! rwr.has_unique_region_id()
                || ! rwr.is_isolated()
                || rwr.region_id() != isolated_region_id)
        {
            return false;
        }
    }

    selected_rank = n - 1;

    return true;
}

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

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP
Commit	Line	Data
b32b8144 FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2
	3	// Copyright (c) 2007-2017 Barend Gehrels, Amsterdam, the Netherlands.
	4
	5	// Use, modification and distribution is subject to the Boost Software License,
	6	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	7	// http://www.boost.org/LICENSE_1_0.txt)
	8
	9	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP
	10	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP
	11
	12	#include <cstddef>
	13	#include <vector>
	14
	15	#include <boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp>
	16	#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
	17
	18	namespace boost { namespace geometry
	19	{
	20
	21	#ifndef DOXYGEN_NO_DETAIL
	22	namespace detail { namespace overlay
	23	{
	24
	25	inline bool check_pairs(std::vector<sort_by_side::rank_with_rings> const& aggregation,
	26	signed_size_type incoming_region_id,
	27	std::size_t first, std::size_t last)
	28	{
	29	// Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
	30
	31	for (std::size_t i = first; i <= last; i += 2)
	32	{
	33	sort_by_side::rank_with_rings const& curr = aggregation[i];
	34	sort_by_side::rank_with_rings const& next = aggregation[i + 1];
	35	signed_size_type const curr_id = curr.region_id();
	36	signed_size_type const next_id = next.region_id();
	37
	38	bool const possible =
	39	curr.rings.size() == 2
	40	&& curr.is_isolated()
	41	&& curr.has_unique_region_id()
	42	&& next.rings.size() == 2
	43	&& next.is_isolated()
	44	&& next.has_unique_region_id()
	45	&& curr_id == next_id
	46	&& curr_id != incoming_region_id;
	47
	48	if (! possible)
	49	{
	50	return false;
	51	}
	52	}
	53
	54	return true;
	55	}
	56
	57	inline bool intersection_pattern_common_interior1(std::size_t& selected_rank,
	58	std::vector<sort_by_side::rank_with_rings> const& aggregation)
	59	{
	60	// Pattern: coming from exterior ring, encountering an isolated
	61	// parallel interior ring, which should be skipped, and the first
	62	// left (normally intersection takes first right) should be taken.
	63	// Solves cases #case_133_multi
	64	// and #case_recursive_boxes_49
65
66	std::size_t const n = aggregation.size();
67	if (n < 4)
68	{
69	return false;
70	}
71
72	sort_by_side::rank_with_rings const& incoming = aggregation.front();
73	sort_by_side::rank_with_rings const& outgoing = aggregation.back();
74
75	bool const incoming_ok =
76	incoming.all_from()
77	&& incoming.rings.size() == 1
78	&& incoming.has_only(operation_intersection);
79
80	if (! incoming_ok)
81	{
82	return false;
83	}
84
85	bool const outgoing_ok =
86	outgoing.all_to()
87	&& outgoing.rings.size() == 1
88	&& outgoing.has_only(operation_intersection)
89	&& outgoing.region_id() == incoming.region_id();
90
91	if (! outgoing_ok)
92	{
93	return false;
94	}
95
96	if (check_pairs(aggregation, incoming.region_id(), 1, n - 2))
97	{
98	selected_rank = n - 1;
99	return true;
100	}
101	return false;
102	}
103
104	inline bool intersection_pattern_common_interior2(std::size_t& selected_rank,
105	std::vector<sort_by_side::rank_with_rings> const& aggregation)
106	{
107	// Pattern: coming from two exterior rings, encountering two isolated
108	// equal interior rings
109
110	// See (for example, for ii) #case_recursive_boxes_53:
111
112	// INCOMING:
113	// Rank 0 {11[0] (s:0, m:0) i F rgn: 1 ISO} {13[1] (s:1, m:0) i F rgn: 1 ISO}
114
115	// PAIR:
116	// Rank 1 {13[0] (s:0, r:1, m:0) i T rgn: 3 ISO ->16} {11[1] (s:1, r:5, m:0) i T rgn: 3 ISO ->16}
117	// Rank 2 {13[0] (s:0, r:1, m:0) i F rgn: 3 ISO} {11[1] (s:1, r:5, m:0) i F rgn: 3 ISO}
118
119	// LEAVING (in the same direction, take last one)
120	// Rank 3 {11[0] (s:0, m:0) i T rgn: 1 ISO ->10} {13[1] (s:1, m:0) i T rgn: 1 ISO ->10}
121
122
123	std::size_t const n = aggregation.size();
124	if (n < 4)
125	{
126	return false;
127	}
128
129	sort_by_side::rank_with_rings const& incoming = aggregation.front();
130	sort_by_side::rank_with_rings const& outgoing = aggregation.back();
131
132	bool const incoming_ok =
133	incoming.all_from()
134	&& incoming.rings.size() == 2
135	&& incoming.has_unique_region_id();
136
137	if (! incoming_ok)
138	{
139	return false;
140	}
141
142	bool const outgoing_ok =
143	outgoing.all_to()
144	&& outgoing.rings.size() == 2
145	&& outgoing.has_unique_region_id()
146	&& outgoing.region_id() == incoming.region_id();
147
148	if (! outgoing_ok)
149	{
150	return false;
151	}
152
153	bool const operation_ok =
154	(incoming.has_only(operation_continue) && outgoing.has_only(operation_continue))
155	\|\| (incoming.has_only(operation_intersection) && outgoing.has_only(operation_intersection));
156
157	if (! operation_ok)
158	{
159	return false;
160	}
161
162	// Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
163	if (check_pairs(aggregation, incoming.region_id(), 1, n - 2))
164	{
165	selected_rank = n - 1;
166	return true;
167	}
168	return false;
169	}
170
171	inline bool intersection_pattern_common_interior3(std::size_t& selected_rank,
172	std::vector<sort_by_side::rank_with_rings> const& aggregation)
173	{
174	// Pattern: approaches colocated turn (exterior+interior) from two
175	// different directions, and both leaves in the same direction
176
177	// See #case_136_multi:
178	// INCOMING:
179	//Rank 0 {10[0] (s:0, m:0) c F rgn: 1 ISO}
180
181	// PAIR:
182	//Rank 1 {14[0] (s:0, r:0, m:0) i T rgn: 2 ISO ->16} {11[1] (s:1, r:1, m:0) i T rgn: 2 ISO ->16}
183	//Rank 2 {14[0] (s:0, r:0, m:0) i F rgn: 2 ISO} {11[1] (s:1, r:1, m:0) i F rgn: 2 ISO}
184
185	// LEAVING (select this one):
186	//Rank 3 {10[0] (s:0, m:0) c T rgn: 1 ISO ->12} {10[1] (s:1, m:0) c T rgn: 1 ISO ->12}
187
188	// ADDITIONALLY: (other polygon coming in)
189	//Rank 4 {10[1] (s:1, m:0) c F rgn: 1 ISO}
190
191	std::size_t const n = aggregation.size();
192	if (n < 4)
193	{
194	return false;
195	}
196
197	sort_by_side::rank_with_rings const& incoming = aggregation.front();
198	sort_by_side::rank_with_rings const& outgoing = aggregation[n - 2];
199	sort_by_side::rank_with_rings const& last = aggregation.back();
200
201	bool const incoming_ok =
202	incoming.all_from()
203	&& incoming.rings.size() == 1
204	&& incoming.has_only(operation_continue);
205
206	if (! incoming_ok)
207	{
208	return false;
209	}
210
211	bool const outgoing_ok =
212	outgoing.all_to()
213	&& outgoing.rings.size() == 2
214	&& outgoing.has_only(operation_continue)
215	&& outgoing.has_unique_region_id()
216	&& outgoing.region_id() == incoming.region_id()
217	&& last.all_from()
218	&& last.rings.size() == 1
219	&& last.region_id() == incoming.region_id()
220	&& last.all_from();
221
222	if (! outgoing_ok)
223	{
224	return false;
225	}
226
227	// Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
228	if (check_pairs(aggregation, incoming.region_id(), 1, n - 3))
229	{
230	selected_rank = n - 2;
231	return true;
232	}
233	return false;
234	}
235
236
237	inline bool intersection_pattern_common_interior4(std::size_t& selected_rank,
238	std::vector<sort_by_side::rank_with_rings> const& aggregation)
239	{
240	// Pattern: approaches colocated turn (exterior+interior) from same
241	// direction, but leaves in two different directions
242
243	// See #case_137_multi:
244
245	// INCOMING:
246	//Rank 0 {11[0] (s:0, m:0) i F rgn: 1 ISO} {10[1] (s:1, m:0) i F rgn: 1 ISO}
247
248	// PAIR:
249	//Rank 1 {13[0] (s:0, r:0, m:0) i T rgn: 2 ISO ->15} {11[1] (s:1, r:1, m:0) i T rgn: 2 ISO ->15}
250	//Rank 2 {13[0] (s:0, r:0, m:0) i F rgn: 2 ISO} {11[1] (s:1, r:1, m:0) i F rgn: 2 ISO}
251
252	// LEAVING (in two different directions, take penultimate one)
253	//Rank 3 {10[1] (s:1, m:0) i T rgn: 1 ISO ->0}
254	//Rank 4 {11[0] (s:0, m:0) i T rgn: 1 ISO ->12}
255
256	std::size_t const n = aggregation.size();
257	if (n < 4)
258	{
259	return false;
260	}
261
262	sort_by_side::rank_with_rings const& incoming = aggregation.front();
263	sort_by_side::rank_with_rings const& extra = aggregation[n - 2];
264	sort_by_side::rank_with_rings const& outgoing = aggregation.back();
265
266	bool const incoming_ok =
267	incoming.all_from()
268	&& incoming.rings.size() == 2
269	&& incoming.has_unique_region_id()
270	&& incoming.has_only(operation_intersection);
271
272	if (! incoming_ok)
273	{
274	return false;
275	}
276
277	bool const outgoing_ok =
278	outgoing.all_to()
279	&& outgoing.rings.size() == 1
280	&& outgoing.has_only(operation_intersection)
281	&& outgoing.region_id() == incoming.region_id()
282	&& extra.all_to()
283	&& extra.rings.size() == 1
284	&& extra.has_only(operation_intersection)
285	&& extra.region_id() == incoming.region_id();
286
287	if (! outgoing_ok)
288	{
289	return false;
290	}
291
292	// Check if pairs 1,2 (and possibly 3,4 and 5,6 etc) satisfy
293	if (check_pairs(aggregation, incoming.region_id(), 1, n - 3))
294	{
295	selected_rank = n - 2;
296	return true;
297	}
298	return false;
299	}
300
301	inline bool intersection_pattern_common_interior5(std::size_t& selected_rank,
302	std::vector<sort_by_side::rank_with_rings> const& aggregation)
303	{
304	// Pattern: isolated regions
305
306	// See #case_recursive_boxes_65
307
308	// INCOMING:
309	// Rank 0 {19[0] (s:0, r:2, m:0) i F rgn: 4 ISO}
310
311	// Rank 1 {19[1] (s:1, m:0) i T rgn: 1 ISO FIN ->18 (2.5)}
312	// Rank 2 {21[1] (s:1, m:2) i F rgn: 1 ISO}
313	// Rank 3 {21[1] (s:1, m:2) i T rgn: 1 ISO ->17 (2)}
314	// Rank 4 {19[1] (s:1, m:0) i F rgn: 1 ISO FIN}
315
316	// LEAVING (take this one):
317	// Rank 5 {19[0] (s:0, r:2, m:0) i T rgn: 4 ISO ->22 (1)}
318
319	std::size_t const n = aggregation.size();
320	if (n < 3)
321	{
322	return false;
323	}
324
325	sort_by_side::rank_with_rings const& incoming = aggregation.front();
326	sort_by_side::rank_with_rings const& outgoing = aggregation.back();
327
328	bool const incoming_ok =
329	incoming.all_from()
330	&& incoming.has_unique_region_id()
331	&& incoming.is_isolated();
332
333	if (! incoming_ok)
334	{
335	return false;
336	}
337
338	signed_size_type const incoming_region_id = incoming.region_id();
339
340	bool const outgoing_ok =
341	outgoing.all_to()
342	&& outgoing.has_unique_region_id()
343	&& outgoing.is_isolated()
344	&& outgoing.region_id() == incoming_region_id;
345
346	if (! outgoing_ok)
347	{
348	return false;
349	}
350
351	selected_rank = n - 1;
352	bool other_region = true;
353
354	// Assumed is that other regions go (T) and come back (F)
355	for (std::size_t i = 1; i < n - 1; i++)
356	{
357	sort_by_side::rank_with_rings const& rwr = aggregation[i];
358	if (! rwr.has_unique_region_id() \|\| ! rwr.is_isolated())
359	{
360	return false;
361	}
362	signed_size_type const region_id = rwr.region_id();
363	if (other_region && region_id != incoming_region_id)
364	{
365	// OK
366	}
367	else if (other_region && region_id == incoming_region_id)
368	{
369	// OK, next phase (same region as incoming region)
370	selected_rank = i;
371	other_region = false;
372	}
373	else if (! other_region && region_id != incoming_region_id)
374	{
375	// After that the region is the same is incoming, it should
376	// stay like that
377	return false;
378	}
379	}
380
381	return true;
382	}
383
384	inline bool intersection_pattern_common_interior6(std::size_t& selected_rank,
385	std::vector<sort_by_side::rank_with_rings> const& aggregation)
386	{
387	// Pattern: isolated regions in between
388
389	// See #case_recursive_boxes_75
390
391	// Incoming: one region
392	// In between: several rings having isolated region, all the same
393	// Outging == incoming
394
395	std::size_t const n = aggregation.size();
396	if (n < 3)
397	{
398	return false;
399	}
400
401	sort_by_side::rank_with_rings const& incoming = aggregation.front();
402	sort_by_side::rank_with_rings const& outgoing = aggregation.back();
403	sort_by_side::rank_with_rings const& first_isolated = aggregation[2];
404
405	bool const incoming_ok =
406	incoming.all_from()
407	&& incoming.has_unique_region_id()
408	&& ! incoming.is_isolated();
409
410	if (! incoming_ok)
411	{
412	return false;
413	}
414
415	signed_size_type const incoming_region_id = incoming.region_id();
416
417	bool const outgoing_ok =
418	outgoing.all_to()
419	&& outgoing.has_unique_region_id()
420	&& ! outgoing.is_isolated()
421	&& outgoing.region_id() == incoming_region_id;
422
423	if (! outgoing_ok)
424	{
425	return false;
426	}
427
428	const signed_size_type isolated_region_id = first_isolated.region_id();
429
430	for (std::size_t i = 1; i < n - 1; i++)
431	{
432	sort_by_side::rank_with_rings const& rwr = aggregation[i];
433	if (! rwr.has_unique_region_id()
434	\|\| ! rwr.is_isolated()
435	\|\| rwr.region_id() != isolated_region_id)
436	{
437	return false;
438	}
439	}
440
441	selected_rank = n - 1;
442
443	return true;
444	}
445
446	}} // namespace detail::overlay
447	#endif // DOXYGEN_NO_DETAIL
448
449	}} // namespace boost::geometry
450
451	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_INTERSECTION_PATTERNS_HPP