summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/handle_colocations.hpp')
-rw-r--r--boost/geometry/algorithms/detail/overlay/handle_colocations.hpp148
1 files changed, 111 insertions, 37 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp
index 400ed3b881..f3311b34e9 100644
--- a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp
+++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp
@@ -2,6 +2,11 @@
// Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands.
+// 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)
@@ -262,15 +267,6 @@ inline void handle_colocation_cluster(Turns& turns,
add_cluster_id(other_op, cluster_per_segment, ref_id);
id = ref_id;
}
-
- // In case of colocated xx turns, all other turns may NOT be
- // followed at all. xx cannot be discarded (otherwise colocated
- // turns are followed).
- if (ref_turn.both(operation_blocked))
- {
- turn.discarded = true;
- // We can either set or not set colocated because it is not effective on blocked turns
- }
}
else
{
@@ -331,11 +327,7 @@ inline void assign_cluster_to_turns(Turns& turns,
}
}
-template
-<
- typename Turns,
- typename Clusters
->
+template <typename Turns, typename Clusters>
inline void remove_clusters(Turns& turns, Clusters& clusters)
{
typename Clusters::iterator it = clusters.begin();
@@ -350,17 +342,44 @@ inline void remove_clusters(Turns& turns, Clusters& clusters)
= current_it->second.turn_indices;
if (turn_indices.size() == 1)
{
- signed_size_type turn_index = *turn_indices.begin();
+ 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);
@@ -378,6 +397,13 @@ inline bool is_ie_turn(segment_identifier const& ext_seg_0,
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),
@@ -411,6 +437,7 @@ inline bool is_ie_turn(segment_identifier const& ext_seg_0,
template
<
bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior
+ overlay_type OverlayType,
typename Turns,
typename Clusters
>
@@ -435,19 +462,6 @@ inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters)
segment_identifier const& seg_0 = turn.operations[0].seg_id;
segment_identifier const& seg_1 = turn.operations[1].seg_id;
- if (turn.both(operation_intersection)
- && Reverse0 == Reverse1)
- {
- if ( is_interior<Reverse0>(seg_0)
- && is_interior<Reverse1>(seg_1))
- {
- // ii touch with, two interior rings
- discard_ie_turn(turn, ids_to_remove, *it);
- }
-
- continue;
- }
-
if (! (turn.both(operation_union)
|| turn.combination(operation_union, operation_blocked)))
{
@@ -487,6 +501,53 @@ inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters)
}
}
+template
+<
+ 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 has_ii = false;
+ bool has_uu = false;
+ for (set_iterator it = ids.begin(); it != ids.end(); ++it)
+ {
+ turn_type const& turn = turns[*it];
+ if (turn.both(operation_intersection))
+ {
+ has_ii = true;
+ }
+ if (turn.both(operation_union) || turn.combination(operation_union, operation_blocked))
+ {
+ has_uu = true;
+ }
+ }
+ if (has_ii || has_uu)
+ {
+ for (set_iterator it = ids.begin(); it != ids.end(); ++it)
+ {
+ turn_type& turn = turns[*it];
+ if (has_ii)
+ {
+ turn.colocated_ii = true;
+ }
+ if (has_uu)
+ {
+ turn.colocated_uu = true;
+ }
+ }
+ }
+ }
+}
// Checks colocated turns and flags combinations of uu/other, possibly a
// combination of a ring touching another geometry's interior ring which is
@@ -498,6 +559,7 @@ inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters)
template
<
bool Reverse1, bool Reverse2,
+ overlay_type OverlayType,
typename Turns,
typename Clusters,
typename Geometry1,
@@ -578,12 +640,13 @@ inline bool handle_colocations(Turns& turns, Clusters& clusters,
}
assign_cluster_to_turns(turns, clusters, cluster_per_segment);
+ set_colocation(turns, clusters);
discard_interior_exterior_turns
<
do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse1,
- do_reverse<geometry::point_order<Geometry2>::value>::value != Reverse2
+ do_reverse<geometry::point_order<Geometry2>::value>::value != Reverse2,
+ OverlayType
>(turns, clusters);
- remove_clusters(turns, clusters);
#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
std::cout << "*** Colocations " << map.size() << std::endl;
@@ -598,7 +661,8 @@ inline bool handle_colocations(Turns& turns, Clusters& clusters,
std::cout << geometry::wkt(turns[toi.turn_index].point)
<< std::boolalpha
<< " discarded=" << turns[toi.turn_index].discarded
- << " colocated=" << turns[toi.turn_index].colocated
+ << " 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
@@ -634,14 +698,17 @@ struct is_turn_index
template
<
bool Reverse1, bool Reverse2,
+ overlay_type OverlayType,
typename Turns,
typename Clusters,
typename Geometry1,
- typename Geometry2
+ typename Geometry2,
+ typename SideStrategy
>
inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
operation_type for_operation,
- Geometry1 const& geometry1, Geometry2 const& geometry2)
+ 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;
@@ -651,7 +718,7 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
// right side
typedef sort_by_side::side_sorter
<
- Reverse1, Reverse2, point_type, std::less<int>
+ Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less<int>
> sbs_type;
for (typename Clusters::iterator mit = clusters.begin();
@@ -664,11 +731,11 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
continue;
}
- sbs_type sbs;
+ sbs_type sbs(strategy);
point_type turn_point; // should be all the same for all turns in cluster
bool first = true;
- for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
+ for (std::set<signed_size_type>::const_iterator sit = ids.begin();
sit != ids.end(); ++sit)
{
signed_size_type turn_index = *sit;
@@ -689,6 +756,8 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
sbs.find_open();
sbs.assign_zones(for_operation);
+ cinfo.open_count = sbs.open_count(for_operation);
+
// Unset the startable flag for all 'closed' zones
for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
{
@@ -696,6 +765,11 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
turn_type& turn = turns[ranked.turn_index];
turn_operation_type& op = turn.operations[ranked.operation_index];
+ if (for_operation == operation_union && cinfo.open_count == 0)
+ {
+ op.enriched.startable = false;
+ }
+
if (ranked.direction != sort_by_side::dir_to)
{
continue;
@@ -703,6 +777,7 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
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 ((for_operation == operation_union
@@ -714,7 +789,6 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns,
}
}
- cinfo.open_count = sbs.open_count(for_operation);
}
}