FM / overlay

/usr/include/boost/geometry/algorithms/detail/overlay/

/usr/include/boost/geometry/algorithms/detail/overlay

Name	Size	Mode	Actions
add_rings.hpp	5964	0644	edit dl rm
append_no_duplicates.hpp	2101	0644	edit dl rm
append_no_dups_or_spikes.hpp	7434	0644	edit dl rm
assign_parents.hpp	14577	0644	edit dl rm
backtrack_check_si.hpp	6371	0644	edit dl rm
check_enrich.hpp	5361	0644	edit dl rm
clip_linestring.hpp	8718	0644	edit dl rm
cluster_exits.hpp	7817	0644	edit dl rm
cluster_info.hpp	1010	0644	edit dl rm
convert_ring.hpp	3113	0644	edit dl rm
copy_segments.hpp	11481	0644	edit dl rm
copy_segment_point.hpp	11107	0644	edit dl rm
debug_turn_info.hpp	1947	0644	edit dl rm
do_reverse.hpp	1246	0644	edit dl rm
enrichment_info.hpp	2343	0644	edit dl rm
enrich_intersection_points.hpp	19008	0644	edit dl rm
follow.hpp	16907	0644	edit dl rm
follow_linear_linear.hpp	15711	0644	edit dl rm
get_distance_measure.hpp	5092	0644	edit dl rm
get_intersection_points.hpp	4265	0644	edit dl rm
get_relative_order.hpp	3260	0644	edit dl rm
get_ring.hpp	3700	0644	edit dl rm
get_turns.hpp	42078	0644	edit dl rm
get_turn_info.hpp	45746	0644	edit dl rm
get_turn_info_for_endpoint.hpp	25337	0644	edit dl rm
get_turn_info_helpers.hpp	19708	0644	edit dl rm
get_turn_info_la.hpp	34941	0644	edit dl rm
get_turn_info_ll.hpp	28380	0644	edit dl rm
handle_colocations.hpp	28604	0644	edit dl rm
handle_self_turns.hpp	9962	0644	edit dl rm
inconsistent_turns_exception.hpp	1043	0644	edit dl rm
intersection_box_box.hpp	2623	0644	edit dl rm
intersection_insert.hpp	47296	0644	edit dl rm
is_self_turn.hpp	1611	0644	edit dl rm
less_by_segment_ratio.hpp	6161	0644	edit dl rm
linear_linear.hpp	9562	0644	edit dl rm
needs_self_turns.hpp	1911	0644	edit dl rm
overlay.hpp	15706	0644	edit dl rm
overlay_type.hpp	1746	0644	edit dl rm
pointlike_areal.hpp	9593	0644	edit dl rm
pointlike_linear.hpp	11547	0644	edit dl rm
pointlike_pointlike.hpp	11878	0644	edit dl rm
range_in_geometry.hpp	5066	0644	edit dl rm
ring_properties.hpp	2135	0644	edit dl rm
segment_as_subrange.hpp	1488	0644	edit dl rm
segment_identifier.hpp	3555	0644	edit dl rm
select_rings.hpp	12362	0644	edit dl rm
self_turn_points.hpp	10814	0644	edit dl rm
sort_by_side.hpp	22216	0644	edit dl rm
stream_info.hpp	2383	0644	edit dl rm
traversal.hpp	34432	0644	edit dl rm
traversal_info.hpp	1469	0644	edit dl rm
traversal_ring_creator.hpp	15319	0644	edit dl rm
traversal_switch_detector.hpp	22642	0644	edit dl rm
traverse.hpp	3256	0644	edit dl rm
turn_info.hpp	4468	0644	edit dl rm
visit_info.hpp	2350	0644	edit dl rm

Edit: /usr/include/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp (28604B)

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

// 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_HANDLE_COLOCATIONS_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP

#include <cstddef>
#include <algorithm>
#include <map>
#include <vector>

#include <boost/core/ignore_unused.hpp>
#include <boost/range.hpp>
#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/core/point_order.hpp>
#include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
#include <boost/geometry/util/condition.hpp>

#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
#  include <iostream>
#  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
#  include <boost/geometry/io/wkt/wkt.hpp>
#  define BOOST_GEOMETRY_DEBUG_IDENTIFIER
#endif

namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{

template <typename SegmentRatio>
struct segment_fraction
{
    segment_identifier seg_id;
    SegmentRatio fraction;

segment_fraction(segment_identifier const& id, SegmentRatio const& fr)
        : seg_id(id)
        , fraction(fr)
    {}

segment_fraction()
    {}

bool operator<(segment_fraction<SegmentRatio> const& other) const
    {
        return seg_id == other.seg_id
                ? fraction < other.fraction
                : seg_id < other.seg_id;
    }

};

struct turn_operation_index
{
    turn_operation_index(signed_size_type ti = -1,
                         signed_size_type oi = -1)
        : turn_index(ti)
        , op_index(oi)
    {}

signed_size_type turn_index;
    signed_size_type op_index; // only 0,1
};

template <typename Turns>
struct less_by_fraction_and_type
{
    inline less_by_fraction_and_type(Turns const& turns)
        : m_turns(turns)
    {
    }

inline bool operator()(turn_operation_index const& left,
                           turn_operation_index const& right) const
    {
        typedef typename boost::range_value<Turns>::type turn_type;
        typedef typename turn_type::turn_operation_type turn_operation_type;

turn_type const& left_turn = m_turns[left.turn_index];
        turn_type const& right_turn = m_turns[right.turn_index];
        turn_operation_type const& left_op
                = left_turn.operations[left.op_index];

turn_operation_type const& right_op
                = right_turn.operations[right.op_index];

if (! (left_op.fraction == right_op.fraction))
        {
            return left_op.fraction < right_op.fraction;
        }

// Order xx first - used to discard any following colocated turn
        bool const left_both_xx = left_turn.both(operation_blocked);
        bool const right_both_xx = right_turn.both(operation_blocked);
        if (left_both_xx && ! right_both_xx)
        {
            return true;
        }
        if (! left_both_xx && right_both_xx)
        {
            return false;
        }

bool const left_both_uu = left_turn.both(operation_union);
        bool const right_both_uu = right_turn.both(operation_union);
        if (left_both_uu && ! right_both_uu)
        {
            return true;
        }
        if (! left_both_uu && right_both_uu)
        {
            return false;
        }

turn_operation_type const& left_other_op
                = left_turn.operations[1 - left.op_index];

turn_operation_type const& right_other_op
                = right_turn.operations[1 - right.op_index];

// Fraction is the same, now sort on ring id, first outer ring,
        // then interior rings
        return left_other_op.seg_id < right_other_op.seg_id;
    }

private:
    Turns const& m_turns;
};

template <typename Operation, typename ClusterPerSegment>
inline signed_size_type get_cluster_id(Operation const& op, ClusterPerSegment const& cluster_per_segment)
{
    typedef typename ClusterPerSegment::key_type segment_fraction_type;

segment_fraction_type seg_frac(op.seg_id, op.fraction);
    typename ClusterPerSegment::const_iterator it
            = cluster_per_segment.find(seg_frac);

if (it == cluster_per_segment.end())
    {
        return -1;
    }
    return it->second;
}

template <typename Operation, typename ClusterPerSegment>
inline void add_cluster_id(Operation const& op,
    ClusterPerSegment& cluster_per_segment, signed_size_type id)
{
    typedef typename ClusterPerSegment::key_type segment_fraction_type;

segment_fraction_type seg_frac(op.seg_id, op.fraction);

cluster_per_segment[seg_frac] = id;
}

template <typename Turn, typename ClusterPerSegment>
inline signed_size_type add_turn_to_cluster(Turn const& turn,
        ClusterPerSegment& cluster_per_segment, signed_size_type& cluster_id)
{
    signed_size_type cid0 = get_cluster_id(turn.operations[0], cluster_per_segment);
    signed_size_type cid1 = get_cluster_id(turn.operations[1], cluster_per_segment);

if (cid0 == -1 && cid1 == -1)
    {
        // Because of this, first cluster ID will be 1
        ++cluster_id;
        add_cluster_id(turn.operations[0], cluster_per_segment, cluster_id);
        add_cluster_id(turn.operations[1], cluster_per_segment, cluster_id);
        return cluster_id;
    }
    else if (cid0 == -1 && cid1 != -1)
    {
        add_cluster_id(turn.operations[0], cluster_per_segment, cid1);
        return cid1;
    }
    else if (cid0 != -1 && cid1 == -1)
    {
        add_cluster_id(turn.operations[1], cluster_per_segment, cid0);
        return cid0;
    }
    else if (cid0 == cid1)
    {
        // Both already added to same cluster, no action
        return cid0;
    }

// Both operations.seg_id/fraction were already part of any cluster, and
    // these clusters are not the same. Merge of two clusters is necessary
#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
    std::cout << " TODO: merge " << cid0 << " and " << cid1 << std::endl;
#endif
    return cid0;
}

template
<
    typename Turns,
    typename ClusterPerSegment,
    typename Operations,
    typename Geometry1,
    typename Geometry2
>
inline void handle_colocation_cluster(Turns& turns,
        signed_size_type& cluster_id,
        ClusterPerSegment& cluster_per_segment,
        Operations const& operations,
        Geometry1 const& /*geometry1*/, Geometry2 const& /*geometry2*/)
{
    typedef typename boost::range_value<Turns>::type turn_type;
    typedef typename turn_type::turn_operation_type turn_operation_type;

std::vector<turn_operation_index>::const_iterator vit = operations.begin();

turn_operation_index ref_toi = *vit;
    signed_size_type ref_id = -1;

for (++vit; vit != operations.end(); ++vit)
    {
        turn_type& ref_turn = turns[ref_toi.turn_index];
        turn_operation_type const& ref_op
                = ref_turn.operations[ref_toi.op_index];

turn_operation_index const& toi = *vit;
        turn_type& turn = turns[toi.turn_index];
        turn_operation_type const& op = turn.operations[toi.op_index];

BOOST_GEOMETRY_ASSERT(ref_op.seg_id == op.seg_id);

if (ref_op.fraction == op.fraction)
        {
            turn_operation_type const& other_op = turn.operations[1 - toi.op_index];

if (ref_id == -1)
            {
                ref_id = add_turn_to_cluster(ref_turn, cluster_per_segment, cluster_id);
            }
            BOOST_GEOMETRY_ASSERT(ref_id != -1);

// ref_turn (both operations) are already added to cluster,
            // so also "op" is already added to cluster,
            // We only need to add other_op
            signed_size_type id = get_cluster_id(other_op, cluster_per_segment);
            if (id != -1 && id != ref_id)
            {
            }
            else if (id == -1)
            {
                // Add to same cluster
                add_cluster_id(other_op, cluster_per_segment, ref_id);
                id = ref_id;
            }
        }
        else
        {
            // Not on same fraction on this segment
            // assign for next
            ref_toi = toi;
            ref_id = -1;
        }
    }
}

template
<
    typename Turns,
    typename Clusters,
    typename ClusterPerSegment
>
inline void assign_cluster_to_turns(Turns& turns,
        Clusters& clusters,
        ClusterPerSegment const& cluster_per_segment)
{
    typedef typename boost::range_value<Turns>::type turn_type;
    typedef typename turn_type::turn_operation_type turn_operation_type;
    typedef typename ClusterPerSegment::key_type segment_fraction_type;

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

if (turn.discarded)
        {
            // They were processed (to create proper map) but will not be added
            // This might leave a cluster with only 1 turn, which will be fixed
            // afterwards
            continue;
        }

for (int i = 0; i < 2; i++)
        {
            turn_operation_type const& op = turn.operations[i];
            segment_fraction_type seg_frac(op.seg_id, op.fraction);
            typename ClusterPerSegment::const_iterator cit = cluster_per_segment.find(seg_frac);
            if (cit != cluster_per_segment.end())
            {
#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
                if (turn.is_clustered()
                        && turn.cluster_id != cit->second)
                {
                    std::cout << " CONFLICT " << std::endl;
                }
#endif
                turn.cluster_id = cit->second;
                clusters[turn.cluster_id].turn_indices.insert(turn_index);
            }
        }
    }
}

template <typename Turns, typename Clusters>
inline void remove_clusters(Turns& turns, Clusters& clusters)
{
    typename Clusters::iterator it = clusters.begin();
    while (it != clusters.end())
    {
        // Hold iterator and increase. We can erase cit, this keeps the
        // iterator valid (cf The standard associative-container erase idiom)
        typename Clusters::iterator current_it = it;
        ++it;

std::set<signed_size_type> const& turn_indices
                = current_it->second.turn_indices;
        if (turn_indices.size() == 1)
        {
            signed_size_type const turn_index = *turn_indices.begin();
            turns[turn_index].cluster_id = -1;
            clusters.erase(current_it);
        }
    }
}

template <typename Turns, typename Clusters>
inline void cleanup_clusters(Turns& turns, Clusters& clusters)
{
    // Removes discarded turns from clusters
    for (typename Clusters::iterator mit = clusters.begin();
         mit != clusters.end(); ++mit)
    {
        cluster_info& cinfo = mit->second;
        std::set<signed_size_type>& ids = cinfo.turn_indices;
        for (std::set<signed_size_type>::iterator sit = ids.begin();
             sit != ids.end(); /* no increment */)
        {
            std::set<signed_size_type>::iterator current_it = sit;
            ++sit;

signed_size_type const turn_index = *current_it;
            if (turns[turn_index].discarded)
            {
                ids.erase(current_it);
            }
        }
    }

remove_clusters(turns, clusters);
}

template <typename Turn, typename IdSet>
inline void discard_ie_turn(Turn& turn, IdSet& ids, signed_size_type id)
{
    turn.discarded = true;
    // Set cluster id to -1, but don't clear colocated flags
    turn.cluster_id = -1;
    // To remove it later from clusters
    ids.insert(id);
}

template <bool Reverse>
inline bool is_interior(segment_identifier const& seg_id)
{
    return Reverse ? seg_id.ring_index == -1 : seg_id.ring_index >= 0;
}

template <bool Reverse0, bool Reverse1>
inline bool is_ie_turn(segment_identifier const& ext_seg_0,
                       segment_identifier const& ext_seg_1,
                       segment_identifier const& int_seg_0,
                       segment_identifier const& other_seg_1)
{
    if (ext_seg_0.source_index == ext_seg_1.source_index)
    {
        // External turn is a self-turn, dont discard internal turn for this
        return false;
    }

// Compares two segment identifiers from two turns (external / one internal)

// From first turn [0], both are from same polygon (multi_index),
    // one is exterior (-1), the other is interior (>= 0),
    // and the second turn [1] handles the same ring

// For difference, where the rings are processed in reversal, all interior
    // rings become exterior and vice versa. But also the multi property changes:
    // rings originally from the same multi should now be considered as from
    // different multi polygons.
    // But this is not always the case, and at this point hard to figure out
    // (not yet implemented, TODO)

bool const same_multi0 = ! Reverse0
                             && ext_seg_0.multi_index == int_seg_0.multi_index;

bool const same_multi1 = ! Reverse1
                             && ext_seg_1.multi_index == other_seg_1.multi_index;

boost::ignore_unused(same_multi1);

return same_multi0
            && same_multi1
            && ! is_interior<Reverse0>(ext_seg_0)
            && is_interior<Reverse0>(int_seg_0)
            && ext_seg_1.ring_index == other_seg_1.ring_index;

// The other way round is tested in another call
}

template
<
    bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior
    typename Turns,
    typename Clusters
>
inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters)
{
    typedef std::set<signed_size_type>::const_iterator set_iterator;
    typedef typename boost::range_value<Turns>::type turn_type;

std::set<signed_size_type> ids_to_remove;

for (typename Clusters::iterator cit = clusters.begin();
         cit != clusters.end(); ++cit)
    {
        cluster_info& cinfo = cit->second;
        std::set<signed_size_type>& ids = cinfo.turn_indices;

ids_to_remove.clear();

for (set_iterator it = ids.begin(); it != ids.end(); ++it)
        {
            turn_type& turn = turns[*it];
            segment_identifier const& seg_0 = turn.operations[0].seg_id;
            segment_identifier const& seg_1 = turn.operations[1].seg_id;

if (! (turn.both(operation_union)
                   || turn.combination(operation_union, operation_blocked)))
            {
                // Not a uu/ux, so cannot be colocated with a iu turn
                continue;
            }

for (set_iterator int_it = ids.begin(); int_it != ids.end(); ++int_it)
            {
                if (*it == *int_it)
                {
                    continue;
                }

// Turn with, possibly, an interior ring involved
                turn_type& int_turn = turns[*int_it];
                segment_identifier const& int_seg_0 = int_turn.operations[0].seg_id;
                segment_identifier const& int_seg_1 = int_turn.operations[1].seg_id;

if (is_ie_turn<Reverse0, Reverse1>(seg_0, seg_1, int_seg_0, int_seg_1))
                {
                    discard_ie_turn(int_turn, ids_to_remove, *int_it);
                }
                if (is_ie_turn<Reverse1, Reverse0>(seg_1, seg_0, int_seg_1, int_seg_0))
                {
                    discard_ie_turn(int_turn, ids_to_remove, *int_it);
                }
            }
        }

// Erase from the ids (which cannot be done above)
        for (set_iterator sit = ids_to_remove.begin();
             sit != ids_to_remove.end(); ++sit)
        {
            ids.erase(*sit);
        }
    }
}

template <typename Geometry0, typename Geometry1>
inline segment_identifier get_preceding_segment_id(segment_identifier const& id,
        Geometry0 const& geometry0, Geometry1 const& geometry1)
{
    segment_identifier result = id;

if (result.segment_index == 0)
    {
        // Assign to segment_count before decrement
        result.segment_index
                = id.source_index == 0
                ? segment_count_on_ring(geometry0, id)
                : segment_count_on_ring(geometry1, id);
    }

result.segment_index--;

return result;
}

template
<
    overlay_type OverlayType,
    typename Turns,
    typename Clusters
>
inline void set_colocation(Turns& turns, Clusters const& clusters)
{
    typedef std::set<signed_size_type>::const_iterator set_iterator;
    typedef typename boost::range_value<Turns>::type turn_type;

for (typename Clusters::const_iterator cit = clusters.begin();
         cit != clusters.end(); ++cit)
    {
        cluster_info const& cinfo = cit->second;
        std::set<signed_size_type> const& ids = cinfo.turn_indices;

bool both_target = false;
        for (set_iterator it = ids.begin(); it != ids.end(); ++it)
        {
            turn_type const& turn = turns[*it];
            if (turn.both(operation_from_overlay<OverlayType>::value))
            {
                both_target = true;
                break;
            }
        }

if (both_target)
        {
            for (set_iterator it = ids.begin(); it != ids.end(); ++it)
            {
                turn_type& turn = turns[*it];
                turn.has_colocated_both = true;
            }
        }
    }
}

template
<
    typename Turns,
    typename Clusters
>
inline void check_colocation(bool& has_blocked,
        signed_size_type cluster_id, Turns const& turns, Clusters const& clusters)
{
    typedef typename boost::range_value<Turns>::type turn_type;

has_blocked = false;

typename Clusters::const_iterator mit = clusters.find(cluster_id);
    if (mit == clusters.end())
    {
        return;
    }

cluster_info const& cinfo = mit->second;

for (std::set<signed_size_type>::const_iterator it
         = cinfo.turn_indices.begin();
         it != cinfo.turn_indices.end(); ++it)
    {
        turn_type const& turn = turns[*it];
        if (turn.any_blocked())
        {
            has_blocked = true;
        }
    }
}

// Checks colocated turns and flags combinations of uu/other, possibly a
// combination of a ring touching another geometry's interior ring which is
// tangential to the exterior ring

// This function can be extended to replace handle_tangencies: at each
// colocation incoming and outgoing vectors should be inspected

template
<
    bool Reverse1, bool Reverse2,
    overlay_type OverlayType,
    typename Turns,
    typename Clusters,
    typename Geometry1,
    typename Geometry2
>
inline bool handle_colocations(Turns& turns, Clusters& clusters,
        Geometry1 const& geometry1, Geometry2 const& geometry2)
{
    static const detail::overlay::operation_type target_operation
            = detail::overlay::operation_from_overlay<OverlayType>::value;
    typedef std::map
        <
            segment_identifier,
            std::vector<turn_operation_index>
        > map_type;

// Create and fill map on segment-identifier Map is sorted on seg_id,
    // meaning it is sorted on ring_identifier too. This means that exterior
    // rings are handled first. If there is a colocation on the exterior ring,
    // that information can be used for the interior ring too
    map_type map;

signed_size_type index = 0;
    for (typename boost::range_iterator<Turns>::type
            it = boost::begin(turns);
         it != boost::end(turns);
         ++it, ++index)
    {
        map[it->operations[0].seg_id].push_back(turn_operation_index(index, 0));
        map[it->operations[1].seg_id].push_back(turn_operation_index(index, 1));
    }

// Check if there are multiple turns on one or more segments,
    // if not then nothing is to be done
    bool colocations = 0;
    for (typename map_type::const_iterator it = map.begin();
         it != map.end();
         ++it)
    {
        if (it->second.size() > 1u)
        {
            colocations = true;
            break;
        }
    }

if (! colocations)
    {
        return false;
    }

// Sort all vectors, per same segment
    less_by_fraction_and_type<Turns> less(turns);
    for (typename map_type::iterator it = map.begin();
         it != map.end(); ++it)
    {
        std::sort(it->second.begin(), it->second.end(), less);
    }

typedef typename boost::range_value<Turns>::type turn_type;
    typedef typename turn_type::segment_ratio_type segment_ratio_type;

typedef std::map
        <
            segment_fraction<segment_ratio_type>,
            signed_size_type
        > cluster_per_segment_type;

cluster_per_segment_type cluster_per_segment;

// Assign to zero, because of pre-increment later the cluster_id
    // effectively starts with 1
    // (and can later be negated to use uniquely with turn_index)
    signed_size_type cluster_id = 0;

for (typename map_type::const_iterator it = map.begin();
         it != map.end(); ++it)
    {
        if (it->second.size() > 1u)
        {
            handle_colocation_cluster(turns, cluster_id, cluster_per_segment,
                it->second, geometry1, geometry2);
        }
    }

assign_cluster_to_turns(turns, clusters, cluster_per_segment);
    // Get colocated information here and not later, to keep information
    // on turns which are discarded afterwards
    set_colocation<OverlayType>(turns, clusters);

if (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection))
    {
        discard_interior_exterior_turns
            <
                do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse1,
                do_reverse<geometry::point_order<Geometry2>::value>::value != Reverse2
            >(turns, clusters);
    }

#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
    std::cout << "*** Colocations " << map.size() << std::endl;
    for (typename map_type::const_iterator it = map.begin();
         it != map.end(); ++it)
    {
        std::cout << it->first << std::endl;
        for (std::vector<turn_operation_index>::const_iterator vit
             = it->second.begin(); vit != it->second.end(); ++vit)
        {
            turn_operation_index const& toi = *vit;
            std::cout << geometry::wkt(turns[toi.turn_index].point)
                << std::boolalpha
                << " discarded=" << turns[toi.turn_index].discarded
                << " colocated(uu)=" << turns[toi.turn_index].colocated_uu
                << " colocated(ii)=" << turns[toi.turn_index].colocated_ii
                << " " << operation_char(turns[toi.turn_index].operations[0].operation)
                << " "  << turns[toi.turn_index].operations[0].seg_id
                << " "  << turns[toi.turn_index].operations[0].fraction
                << " // " << operation_char(turns[toi.turn_index].operations[1].operation)
                << " "  << turns[toi.turn_index].operations[1].seg_id
                << " "  << turns[toi.turn_index].operations[1].fraction
                << std::endl;
        }
    }
#endif // DEBUG

return true;
}

struct is_turn_index
{
    is_turn_index(signed_size_type index)
        : m_index(index)
    {}

template <typename Indexed>
    inline bool operator()(Indexed const& indexed) const
    {
        // Indexed is a indexed_turn_operation<Operation>
        return indexed.turn_index == m_index;
    }

signed_size_type m_index;
};

template
<
    typename Sbs,
    typename Point,
    typename Turns,
    typename Geometry1,
    typename Geometry2
>
inline bool fill_sbs(Sbs& sbs, Point& turn_point,
                     cluster_info const& cinfo,
                     Turns const& turns,
                     Geometry1 const& geometry1, Geometry2 const& geometry2)
{
    typedef typename boost::range_value<Turns>::type turn_type;

std::set<signed_size_type> const& ids = cinfo.turn_indices;

if (ids.empty())
    {
        return false;
    }

bool first = true;
    for (std::set<signed_size_type>::const_iterator sit = ids.begin();
         sit != ids.end(); ++sit)
    {
        signed_size_type turn_index = *sit;
        turn_type const& turn = turns[turn_index];
        if (first )
        {
            turn_point = turn.point;
        }
        for (int i = 0; i < 2; i++)
        {
            sbs.add(turn.operations[i], turn_index, i, geometry1, geometry2, first);
            first = false;
        }
    }
    return true;
}

template
<
    bool Reverse1, bool Reverse2,
    overlay_type OverlayType,
    typename Turns,
    typename Clusters,
    typename Geometry1,
    typename Geometry2,
    typename SideStrategy
>
inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
        operation_type for_operation,
        Geometry1 const& geometry1, Geometry2 const& geometry2,
        SideStrategy const& strategy)
{
    typedef typename boost::range_value<Turns>::type turn_type;
    typedef typename turn_type::point_type point_type;
    typedef typename turn_type::turn_operation_type turn_operation_type;

// Define sorter, sorting counter-clockwise such that polygons are on the
    // right side
    typedef sort_by_side::side_sorter
        <
            Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less<int>
        > sbs_type;

for (typename Clusters::iterator mit = clusters.begin();
         mit != clusters.end(); ++mit)
    {
        cluster_info& cinfo = mit->second;

sbs_type sbs(strategy);
        point_type turn_point; // should be all the same for all turns in cluster
        if (! fill_sbs(sbs, turn_point, cinfo, turns, geometry1, geometry2))
        {
            continue;
        }

sbs.apply(turn_point);

sbs.find_open();
        sbs.assign_zones(for_operation);

cinfo.open_count = sbs.open_count(for_operation);

bool const set_startable = OverlayType != overlay_dissolve;

// Unset the startable flag for all 'closed' zones. This does not
        // apply for self-turns, because those counts are not from both
        // polygons
        for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
        {
            typename sbs_type::rp const& ranked = sbs.m_ranked_points[i];
            turn_type& turn = turns[ranked.turn_index];
            turn_operation_type& op = turn.operations[ranked.operation_index];

if (set_startable
                    && for_operation == operation_union && cinfo.open_count == 0)
            {
                op.enriched.startable = false;
            }

if (ranked.direction != sort_by_side::dir_to)
            {
                continue;
            }

op.enriched.count_left = ranked.count_left;
            op.enriched.count_right = ranked.count_right;
            op.enriched.rank = ranked.rank;
            op.enriched.zone = ranked.zone;

if (! set_startable)
            {
                continue;
            }

if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_difference)
                    && is_self_turn<OverlayType>(turn))
            {
                // Difference needs the self-turns, TODO: investigate
                continue;
            }

if ((for_operation == operation_union
                    && ranked.count_left != 0)
             || (for_operation == operation_intersection
                    && ranked.count_right != 2))
            {
                op.enriched.startable = false;
            }
        }

}
}

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

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP

// Boost.Geometry (aka GGL, Generic Geometry Library) // Copyright (c) 2015 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_HANDLE_COLOCATIONS_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) # include # include # include # define BOOST_GEOMETRY_DEBUG_IDENTIFIER #endif namespace boost { namespace geometry { #ifndef DOXYGEN_NO_DETAIL namespace detail { namespace overlay { template struct segment_fraction { segment_identifier seg_id; SegmentRatio fraction; segment_fraction(segment_identifier const& id, SegmentRatio const& fr) : seg_id(id) , fraction(fr) {} segment_fraction() {} bool operator<(segment_fraction const& other) const { return seg_id == other.seg_id ? fraction < other.fraction : seg_id < other.seg_id; } }; struct turn_operation_index { turn_operation_index(signed_size_type ti = -1, signed_size_type oi = -1) : turn_index(ti) , op_index(oi) {} signed_size_type turn_index; signed_size_type op_index; // only 0,1 }; template struct less_by_fraction_and_type { inline less_by_fraction_and_type(Turns const& turns) : m_turns(turns) { } inline bool operator()(turn_operation_index const& left, turn_operation_index const& right) const { typedef typename boost::range_value::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; turn_type const& left_turn = m_turns[left.turn_index]; turn_type const& right_turn = m_turns[right.turn_index]; turn_operation_type const& left_op = left_turn.operations[left.op_index]; turn_operation_type const& right_op = right_turn.operations[right.op_index]; if (! (left_op.fraction == right_op.fraction)) { return left_op.fraction < right_op.fraction; } // Order xx first - used to discard any following colocated turn bool const left_both_xx = left_turn.both(operation_blocked); bool const right_both_xx = right_turn.both(operation_blocked); if (left_both_xx && ! right_both_xx) { return true; } if (! left_both_xx && right_both_xx) { return false; } bool const left_both_uu = left_turn.both(operation_union); bool const right_both_uu = right_turn.both(operation_union); if (left_both_uu && ! right_both_uu) { return true; } if (! left_both_uu && right_both_uu) { return false; } turn_operation_type const& left_other_op = left_turn.operations[1 - left.op_index]; turn_operation_type const& right_other_op = right_turn.operations[1 - right.op_index]; // Fraction is the same, now sort on ring id, first outer ring, // then interior rings return left_other_op.seg_id < right_other_op.seg_id; } private: Turns const& m_turns; }; template inline signed_size_type get_cluster_id(Operation const& op, ClusterPerSegment const& cluster_per_segment) { typedef typename ClusterPerSegment::key_type segment_fraction_type; segment_fraction_type seg_frac(op.seg_id, op.fraction); typename ClusterPerSegment::const_iterator it = cluster_per_segment.find(seg_frac); if (it == cluster_per_segment.end()) { return -1; } return it->second; } template inline void add_cluster_id(Operation const& op, ClusterPerSegment& cluster_per_segment, signed_size_type id) { typedef typename ClusterPerSegment::key_type segment_fraction_type; segment_fraction_type seg_frac(op.seg_id, op.fraction); cluster_per_segment[seg_frac] = id; } template inline signed_size_type add_turn_to_cluster(Turn const& turn, ClusterPerSegment& cluster_per_segment, signed_size_type& cluster_id) { signed_size_type cid0 = get_cluster_id(turn.operations[0], cluster_per_segment); signed_size_type cid1 = get_cluster_id(turn.operations[1], cluster_per_segment); if (cid0 == -1 && cid1 == -1) { // Because of this, first cluster ID will be 1 ++cluster_id; add_cluster_id(turn.operations[0], cluster_per_segment, cluster_id); add_cluster_id(turn.operations[1], cluster_per_segment, cluster_id); return cluster_id; } else if (cid0 == -1 && cid1 != -1) { add_cluster_id(turn.operations[0], cluster_per_segment, cid1); return cid1; } else if (cid0 != -1 && cid1 == -1) { add_cluster_id(turn.operations[1], cluster_per_segment, cid0); return cid0; } else if (cid0 == cid1) { // Both already added to same cluster, no action return cid0; } // Both operations.seg_id/fraction were already part of any cluster, and // these clusters are not the same. Merge of two clusters is necessary #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) std::cout << " TODO: merge " << cid0 << " and " << cid1 << std::endl; #endif return cid0; } template < typename Turns, typename ClusterPerSegment, typename Operations, typename Geometry1, typename Geometry2 > inline void handle_colocation_cluster(Turns& turns, signed_size_type& cluster_id, ClusterPerSegment& cluster_per_segment, Operations const& operations, Geometry1 const& /*geometry1*/, Geometry2 const& /*geometry2*/) { typedef typename boost::range_value::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; std::vector::const_iterator vit = operations.begin(); turn_operation_index ref_toi = *vit; signed_size_type ref_id = -1; for (++vit; vit != operations.end(); ++vit) { turn_type& ref_turn = turns[ref_toi.turn_index]; turn_operation_type const& ref_op = ref_turn.operations[ref_toi.op_index]; turn_operation_index const& toi = *vit; turn_type& turn = turns[toi.turn_index]; turn_operation_type const& op = turn.operations[toi.op_index]; BOOST_GEOMETRY_ASSERT(ref_op.seg_id == op.seg_id); if (ref_op.fraction == op.fraction) { turn_operation_type const& other_op = turn.operations[1 - toi.op_index]; if (ref_id == -1) { ref_id = add_turn_to_cluster(ref_turn, cluster_per_segment, cluster_id); } BOOST_GEOMETRY_ASSERT(ref_id != -1); // ref_turn (both operations) are already added to cluster, // so also "op" is already added to cluster, // We only need to add other_op signed_size_type id = get_cluster_id(other_op, cluster_per_segment); if (id != -1 && id != ref_id) { } else if (id == -1) { // Add to same cluster add_cluster_id(other_op, cluster_per_segment, ref_id); id = ref_id; } } else { // Not on same fraction on this segment // assign for next ref_toi = toi; ref_id = -1; } } } template < typename Turns, typename Clusters, typename ClusterPerSegment > inline void assign_cluster_to_turns(Turns& turns, Clusters& clusters, ClusterPerSegment const& cluster_per_segment) { typedef typename boost::range_value::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; typedef typename ClusterPerSegment::key_type segment_fraction_type; signed_size_type turn_index = 0; for (typename boost::range_iterator::type it = turns.begin(); it != turns.end(); ++it, ++turn_index) { turn_type& turn = *it; if (turn.discarded) { // They were processed (to create proper map) but will not be added // This might leave a cluster with only 1 turn, which will be fixed // afterwards continue; } for (int i = 0; i < 2; i++) { turn_operation_type const& op = turn.operations[i]; segment_fraction_type seg_frac(op.seg_id, op.fraction); typename ClusterPerSegment::const_iterator cit = cluster_per_segment.find(seg_frac); if (cit != cluster_per_segment.end()) { #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) if (turn.is_clustered() && turn.cluster_id != cit->second) { std::cout << " CONFLICT " << std::endl; } #endif turn.cluster_id = cit->second; clusters[turn.cluster_id].turn_indices.insert(turn_index); } } } } template inline void remove_clusters(Turns& turns, Clusters& clusters) { typename Clusters::iterator it = clusters.begin(); while (it != clusters.end()) { // Hold iterator and increase. We can erase cit, this keeps the // iterator valid (cf The standard associative-container erase idiom) typename Clusters::iterator current_it = it; ++it; std::set const& turn_indices = current_it->second.turn_indices; if (turn_indices.size() == 1) { signed_size_type const turn_index = *turn_indices.begin(); turns[turn_index].cluster_id = -1; clusters.erase(current_it); } } } template inline void cleanup_clusters(Turns& turns, Clusters& clusters) { // Removes discarded turns from clusters for (typename Clusters::iterator mit = clusters.begin(); mit != clusters.end(); ++mit) { cluster_info& cinfo = mit->second; std::set& ids = cinfo.turn_indices; for (std::set::iterator sit = ids.begin(); sit != ids.end(); /* no increment */) { std::set::iterator current_it = sit; ++sit; signed_size_type const turn_index = *current_it; if (turns[turn_index].discarded) { ids.erase(current_it); } } } remove_clusters(turns, clusters); } template inline void discard_ie_turn(Turn& turn, IdSet& ids, signed_size_type id) { turn.discarded = true; // Set cluster id to -1, but don't clear colocated flags turn.cluster_id = -1; // To remove it later from clusters ids.insert(id); } template inline bool is_interior(segment_identifier const& seg_id) { return Reverse ? seg_id.ring_index == -1 : seg_id.ring_index >= 0; } template inline bool is_ie_turn(segment_identifier const& ext_seg_0, segment_identifier const& ext_seg_1, segment_identifier const& int_seg_0, segment_identifier const& other_seg_1) { if (ext_seg_0.source_index == ext_seg_1.source_index) { // External turn is a self-turn, dont discard internal turn for this return false; } // Compares two segment identifiers from two turns (external / one internal) // From first turn [0], both are from same polygon (multi_index), // one is exterior (-1), the other is interior (>= 0), // and the second turn [1] handles the same ring // For difference, where the rings are processed in reversal, all interior // rings become exterior and vice versa. But also the multi property changes: // rings originally from the same multi should now be considered as from // different multi polygons. // But this is not always the case, and at this point hard to figure out // (not yet implemented, TODO) bool const same_multi0 = ! Reverse0 && ext_seg_0.multi_index == int_seg_0.multi_index; bool const same_multi1 = ! Reverse1 && ext_seg_1.multi_index == other_seg_1.multi_index; boost::ignore_unused(same_multi1); return same_multi0 && same_multi1 && ! is_interior(ext_seg_0) && is_interior(int_seg_0) && ext_seg_1.ring_index == other_seg_1.ring_index; // The other way round is tested in another call } template < bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior typename Turns, typename Clusters > inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters) { typedef std::set::const_iterator set_iterator; typedef typename boost::range_value::type turn_type; std::set ids_to_remove; for (typename Clusters::iterator cit = clusters.begin(); cit != clusters.end(); ++cit) { cluster_info& cinfo = cit->second; std::set& ids = cinfo.turn_indices; ids_to_remove.clear(); for (set_iterator it = ids.begin(); it != ids.end(); ++it) { turn_type& turn = turns[*it]; segment_identifier const& seg_0 = turn.operations[0].seg_id; segment_identifier const& seg_1 = turn.operations[1].seg_id; if (! (turn.both(operation_union) || turn.combination(operation_union, operation_blocked))) { // Not a uu/ux, so cannot be colocated with a iu turn continue; } for (set_iterator int_it = ids.begin(); int_it != ids.end(); ++int_it) { if (*it == *int_it) { continue; } // Turn with, possibly, an interior ring involved turn_type& int_turn = turns[*int_it]; segment_identifier const& int_seg_0 = int_turn.operations[0].seg_id; segment_identifier const& int_seg_1 = int_turn.operations[1].seg_id; if (is_ie_turn(seg_0, seg_1, int_seg_0, int_seg_1)) { discard_ie_turn(int_turn, ids_to_remove, *int_it); } if (is_ie_turn(seg_1, seg_0, int_seg_1, int_seg_0)) { discard_ie_turn(int_turn, ids_to_remove, *int_it); } } } // Erase from the ids (which cannot be done above) for (set_iterator sit = ids_to_remove.begin(); sit != ids_to_remove.end(); ++sit) { ids.erase(*sit); } } } template inline segment_identifier get_preceding_segment_id(segment_identifier const& id, Geometry0 const& geometry0, Geometry1 const& geometry1) { segment_identifier result = id; if (result.segment_index == 0) { // Assign to segment_count before decrement result.segment_index = id.source_index == 0 ? segment_count_on_ring(geometry0, id) : segment_count_on_ring(geometry1, id); } result.segment_index--; return result; } template < overlay_type OverlayType, typename Turns, typename Clusters > inline void set_colocation(Turns& turns, Clusters const& clusters) { typedef std::set::const_iterator set_iterator; typedef typename boost::range_value::type turn_type; for (typename Clusters::const_iterator cit = clusters.begin(); cit != clusters.end(); ++cit) { cluster_info const& cinfo = cit->second; std::set const& ids = cinfo.turn_indices; bool both_target = false; for (set_iterator it = ids.begin(); it != ids.end(); ++it) { turn_type const& turn = turns[*it]; if (turn.both(operation_from_overlay::value)) { both_target = true; break; } } if (both_target) { for (set_iterator it = ids.begin(); it != ids.end(); ++it) { turn_type& turn = turns[*it]; turn.has_colocated_both = true; } } } } template < typename Turns, typename Clusters > inline void check_colocation(bool& has_blocked, signed_size_type cluster_id, Turns const& turns, Clusters const& clusters) { typedef typename boost::range_value::type turn_type; has_blocked = false; typename Clusters::const_iterator mit = clusters.find(cluster_id); if (mit == clusters.end()) { return; } cluster_info const& cinfo = mit->second; for (std::set::const_iterator it = cinfo.turn_indices.begin(); it != cinfo.turn_indices.end(); ++it) { turn_type const& turn = turns[*it]; if (turn.any_blocked()) { has_blocked = true; } } } // Checks colocated turns and flags combinations of uu/other, possibly a // combination of a ring touching another geometry's interior ring which is // tangential to the exterior ring // This function can be extended to replace handle_tangencies: at each // colocation incoming and outgoing vectors should be inspected template < bool Reverse1, bool Reverse2, overlay_type OverlayType, typename Turns, typename Clusters, typename Geometry1, typename Geometry2 > inline bool handle_colocations(Turns& turns, Clusters& clusters, Geometry1 const& geometry1, Geometry2 const& geometry2) { static const detail::overlay::operation_type target_operation = detail::overlay::operation_from_overlay::value; typedef std::map < segment_identifier, std::vector > map_type; // Create and fill map on segment-identifier Map is sorted on seg_id, // meaning it is sorted on ring_identifier too. This means that exterior // rings are handled first. If there is a colocation on the exterior ring, // that information can be used for the interior ring too map_type map; signed_size_type index = 0; for (typename boost::range_iterator::type it = boost::begin(turns); it != boost::end(turns); ++it, ++index) { map[it->operations[0].seg_id].push_back(turn_operation_index(index, 0)); map[it->operations[1].seg_id].push_back(turn_operation_index(index, 1)); } // Check if there are multiple turns on one or more segments, // if not then nothing is to be done bool colocations = 0; for (typename map_type::const_iterator it = map.begin(); it != map.end(); ++it) { if (it->second.size() > 1u) { colocations = true; break; } } if (! colocations) { return false; } // Sort all vectors, per same segment less_by_fraction_and_type less(turns); for (typename map_type::iterator it = map.begin(); it != map.end(); ++it) { std::sort(it->second.begin(), it->second.end(), less); } typedef typename boost::range_value::type turn_type; typedef typename turn_type::segment_ratio_type segment_ratio_type; typedef std::map < segment_fraction, signed_size_type > cluster_per_segment_type; cluster_per_segment_type cluster_per_segment; // Assign to zero, because of pre-increment later the cluster_id // effectively starts with 1 // (and can later be negated to use uniquely with turn_index) signed_size_type cluster_id = 0; for (typename map_type::const_iterator it = map.begin(); it != map.end(); ++it) { if (it->second.size() > 1u) { handle_colocation_cluster(turns, cluster_id, cluster_per_segment, it->second, geometry1, geometry2); } } assign_cluster_to_turns(turns, clusters, cluster_per_segment); // Get colocated information here and not later, to keep information // on turns which are discarded afterwards set_colocation(turns, clusters); if (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection)) { discard_interior_exterior_turns < do_reverse::value>::value != Reverse1, do_reverse::value>::value != Reverse2 >(turns, clusters); } #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) std::cout << "*** Colocations " << map.size() << std::endl; for (typename map_type::const_iterator it = map.begin(); it != map.end(); ++it) { std::cout << it->first << std::endl; for (std::vector::const_iterator vit = it->second.begin(); vit != it->second.end(); ++vit) { turn_operation_index const& toi = *vit; std::cout << geometry::wkt(turns[toi.turn_index].point) << std::boolalpha << " discarded=" << turns[toi.turn_index].discarded << " colocated(uu)=" << turns[toi.turn_index].colocated_uu << " colocated(ii)=" << turns[toi.turn_index].colocated_ii << " " << operation_char(turns[toi.turn_index].operations[0].operation) << " " << turns[toi.turn_index].operations[0].seg_id << " " << turns[toi.turn_index].operations[0].fraction << " // " << operation_char(turns[toi.turn_index].operations[1].operation) << " " << turns[toi.turn_index].operations[1].seg_id << " " << turns[toi.turn_index].operations[1].fraction << std::endl; } } #endif // DEBUG return true; } struct is_turn_index { is_turn_index(signed_size_type index) : m_index(index) {} template inline bool operator()(Indexed const& indexed) const { // Indexed is a indexed_turn_operation return indexed.turn_index == m_index; } signed_size_type m_index; }; template < typename Sbs, typename Point, typename Turns, typename Geometry1, typename Geometry2 > inline bool fill_sbs(Sbs& sbs, Point& turn_point, cluster_info const& cinfo, Turns const& turns, Geometry1 const& geometry1, Geometry2 const& geometry2) { typedef typename boost::range_value::type turn_type; std::set const& ids = cinfo.turn_indices; if (ids.empty()) { return false; } bool first = true; for (std::set::const_iterator sit = ids.begin(); sit != ids.end(); ++sit) { signed_size_type turn_index = *sit; turn_type const& turn = turns[turn_index]; if (first ) { turn_point = turn.point; } for (int i = 0; i < 2; i++) { sbs.add(turn.operations[i], turn_index, i, geometry1, geometry2, first); first = false; } } return true; } template < bool Reverse1, bool Reverse2, overlay_type OverlayType, typename Turns, typename Clusters, typename Geometry1, typename Geometry2, typename SideStrategy > inline void gather_cluster_properties(Clusters& clusters, Turns& turns, operation_type for_operation, Geometry1 const& geometry1, Geometry2 const& geometry2, SideStrategy const& strategy) { typedef typename boost::range_value::type turn_type; typedef typename turn_type::point_type point_type; typedef typename turn_type::turn_operation_type turn_operation_type; // Define sorter, sorting counter-clockwise such that polygons are on the // right side typedef sort_by_side::side_sorter < Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less > sbs_type; for (typename Clusters::iterator mit = clusters.begin(); mit != clusters.end(); ++mit) { cluster_info& cinfo = mit->second; sbs_type sbs(strategy); point_type turn_point; // should be all the same for all turns in cluster if (! fill_sbs(sbs, turn_point, cinfo, turns, geometry1, geometry2)) { continue; } sbs.apply(turn_point); sbs.find_open(); sbs.assign_zones(for_operation); cinfo.open_count = sbs.open_count(for_operation); bool const set_startable = OverlayType != overlay_dissolve; // Unset the startable flag for all 'closed' zones. This does not // apply for self-turns, because those counts are not from both // polygons for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) { typename sbs_type::rp const& ranked = sbs.m_ranked_points[i]; turn_type& turn = turns[ranked.turn_index]; turn_operation_type& op = turn.operations[ranked.operation_index]; if (set_startable && for_operation == operation_union && cinfo.open_count == 0) { op.enriched.startable = false; } if (ranked.direction != sort_by_side::dir_to) { continue; } op.enriched.count_left = ranked.count_left; op.enriched.count_right = ranked.count_right; op.enriched.rank = ranked.rank; op.enriched.zone = ranked.zone; if (! set_startable) { continue; } if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_difference) && is_self_turn(turn)) { // Difference needs the self-turns, TODO: investigate continue; } if ((for_operation == operation_union && ranked.count_left != 0) || (for_operation == operation_intersection && ranked.count_right != 2)) { op.enriched.startable = false; } } } } }} // namespace detail::overlay #endif //DOXYGEN_NO_DETAIL }} // namespace boost::geometry #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP