diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/traversal.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/overlay/traversal.hpp | 434 |
1 files changed, 241 insertions, 193 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/traversal.hpp b/boost/geometry/algorithms/detail/overlay/traversal.hpp index bc828920e9..69d62b788b 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal.hpp @@ -2,6 +2,11 @@ // Copyright (c) 2007-2012 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) @@ -14,7 +19,9 @@ #include <boost/range.hpp> #include <boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp> +#include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> +#include <boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> #include <boost/geometry/core/access.hpp> #include <boost/geometry/core/assert.hpp> @@ -37,9 +44,13 @@ namespace detail { namespace overlay template <typename Turn, typename Operation> #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE inline void debug_traverse(Turn const& turn, Operation op, - std::string const& header) + std::string const& header, bool condition = true) { - std::cout << header + if (! condition) + { + return; + } + std::cout << " " << header << " at " << op.seg_id << " meth: " << method_char(turn.method) << " op: " << operation_char(op.operation) @@ -55,7 +66,7 @@ inline void debug_traverse(Turn const& turn, Operation op, } } #else -inline void debug_traverse(Turn const& , Operation, const char*) +inline void debug_traverse(Turn const& , Operation, const char*, bool = true) { } #endif @@ -88,6 +99,7 @@ template typename Turns, typename Clusters, typename RobustPolicy, + typename SideStrategy, typename Visitor > struct traversal @@ -101,18 +113,20 @@ struct traversal typedef typename geometry::point_type<Geometry1>::type point_type; typedef sort_by_side::side_sorter < - Reverse1, Reverse2, - point_type, side_compare_type + Reverse1, Reverse2, OverlayType, + point_type, SideStrategy, side_compare_type > sbs_type; inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2, Turns& turns, Clusters const& clusters, - RobustPolicy const& robust_policy, Visitor& visitor) + RobustPolicy const& robust_policy, SideStrategy const& strategy, + Visitor& visitor) : m_geometry1(geometry1) , m_geometry2(geometry2) , m_turns(turns) , m_clusters(clusters) , m_robust_policy(robust_policy) + , m_strategy(strategy) , m_visitor(visitor) { } @@ -133,11 +147,38 @@ struct traversal } } + //! Sets visited for ALL turns traveling to the same turn + inline void set_visited_in_cluster(signed_size_type cluster_id, + signed_size_type rank) + { + typename Clusters::const_iterator mit = m_clusters.find(cluster_id); + BOOST_ASSERT(mit != m_clusters.end()); + + cluster_info const& cinfo = mit->second; + std::set<signed_size_type> const& ids = cinfo.turn_indices; + + for (typename std::set<signed_size_type>::const_iterator it = ids.begin(); + it != ids.end(); ++it) + { + signed_size_type const turn_index = *it; + turn_type& turn = m_turns[turn_index]; + + for (int i = 0; i < 2; i++) + { + turn_operation_type& op = turn.operations[i]; + if (op.visited.none() + && op.enriched.rank == rank) + { + op.visited.set_visited(); + } + } + } + } inline void set_visited(turn_type& turn, turn_operation_type& op) { - // On "continue", set "visited" for ALL directions in this turn if (op.operation == detail::overlay::operation_continue) { + // On "continue", all go in same direction so set "visited" for ALL for (int i = 0; i < 2; i++) { turn_operation_type& turn_op = turn.operations[i]; @@ -151,6 +192,10 @@ struct traversal { op.visited.set_visited(); } + if (turn.cluster_id >= 0) + { + set_visited_in_cluster(turn.cluster_id, op.enriched.rank); + } } inline bool is_visited(turn_type const& , turn_operation_type const& op, @@ -160,8 +205,8 @@ struct traversal } inline bool select_source(signed_size_type turn_index, - segment_identifier const& seg_id1, - segment_identifier const& seg_id2) const + segment_identifier const& candidate_seg_id, + segment_identifier const& previous_seg_id) const { // For uu/ii, only switch sources if indicated turn_type const& turn = m_turns[turn_index]; @@ -170,8 +215,16 @@ struct traversal { // Buffer does not use source_index (always 0) return turn.switch_source - ? seg_id1.multi_index != seg_id2.multi_index - : seg_id1.multi_index == seg_id2.multi_index; + ? candidate_seg_id.multi_index != previous_seg_id.multi_index + : candidate_seg_id.multi_index == previous_seg_id.multi_index; + } + + if (is_self_turn<OverlayType>(turn)) + { + // Also, if it is a self-turn, stay on same ring (multi/ring) + return turn.switch_source + ? candidate_seg_id.multi_index != previous_seg_id.multi_index + : candidate_seg_id.multi_index == previous_seg_id.multi_index; } #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) @@ -185,16 +238,8 @@ struct traversal } #endif return turn.switch_source - ? seg_id1.source_index != seg_id2.source_index - : seg_id1.source_index == seg_id2.source_index; - } - - inline - signed_size_type get_next_turn_index(turn_operation_type const& op) const - { - return op.enriched.next_ip_index == -1 - ? op.enriched.travels_to_ip_index - : op.enriched.next_ip_index; + ? candidate_seg_id.source_index != previous_seg_id.source_index + : candidate_seg_id.source_index == previous_seg_id.source_index; } inline bool traverse_possible(signed_size_type turn_index) const @@ -220,39 +265,39 @@ struct traversal { // For "cc", take either one, but if there is a starting one, // take that one. If next is dead end, skip that one. + // If both are valid candidates, take the one with minimal remaining + // distance (important for #mysql_23023665 in buffer). - bool result = false; - + // Initialize with 0, automatically assigned on first result typename turn_operation_type::comparable_distance_type - max_remaining_distance = 0; + min_remaining_distance = 0; + + bool result = false; for (int i = 0; i < 2; i++) { turn_operation_type const& op = turn.operations[i]; - signed_size_type const next_turn_index = get_next_turn_index(op); + signed_size_type const next_turn_index = op.enriched.get_next_turn_index(); - if (! result && traverse_possible(next_turn_index)) + if (! traverse_possible(next_turn_index)) { - max_remaining_distance = op.remaining_distance; - selected_op_index = i; - debug_traverse(turn, op, " Candidate"); - result = true; + continue; } - if (result) + if (! result + || next_turn_index == start_turn_index + || op.remaining_distance < min_remaining_distance) { - if (next_turn_index == start_turn_index) - { - selected_op_index = i; - debug_traverse(turn, op, " Candidate cc override (start)"); - } - else if (op.remaining_distance > max_remaining_distance) - { - max_remaining_distance = op.remaining_distance; - selected_op_index = i; - debug_traverse(turn, op, " Candidate cc override (remaining)"); - } + debug_traverse(turn, op, "First candidate cc", ! result); + debug_traverse(turn, op, "Candidate cc override (start)", + result && next_turn_index == start_turn_index); + debug_traverse(turn, op, "Candidate cc override (remaining)", + result && op.remaining_distance < min_remaining_distance); + + selected_op_index = i; + min_remaining_distance = op.remaining_distance; + result = true; } } @@ -262,7 +307,7 @@ struct traversal inline bool select_noncc_operation(turn_type const& turn, signed_size_type turn_index, - segment_identifier const& seg_id, + segment_identifier const& previous_seg_id, int& selected_op_index) const { bool result = false; @@ -273,10 +318,10 @@ struct traversal if (op.operation == target_operation && ! op.visited.finished() - && (! result || select_source(turn_index, op.seg_id, seg_id))) + && (! result || select_source(turn_index, op.seg_id, previous_seg_id))) { selected_op_index = i; - debug_traverse(turn, op, " Candidate"); + debug_traverse(turn, op, "Candidate"); result = true; } } @@ -305,7 +350,7 @@ struct traversal } if (result) { - debug_traverse(turn, turn.operations[selected_op_index], " Accepted"); + debug_traverse(turn, turn.operations[selected_op_index], "Accepted"); } return result; @@ -336,108 +381,164 @@ struct traversal } inline bool select_from_cluster_union(signed_size_type& turn_index, - int& op_index, signed_size_type start_turn_index, - sbs_type const& sbs, bool is_touching) const + int& op_index, sbs_type& sbs) const { + std::vector<sort_by_side::rank_with_rings> aggregation; + sort_by_side::aggregate_operations(sbs, aggregation, m_turns, operation_union); + + + sort_by_side::rank_with_rings const& incoming = aggregation.front(); + + // Take the first one outgoing for the incoming region std::size_t selected_rank = 0; - std::size_t min_rank = 0; - bool result = false; - for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) + for (std::size_t i = 1; i < aggregation.size(); i++) + { + sort_by_side::rank_with_rings const& rwr = aggregation[i]; + if (rwr.all_to() + && rwr.region_id() == incoming.region_id()) + { + selected_rank = rwr.rank; + break; + } + } + + for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++) { typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i]; - if (result && ranked_point.rank > selected_rank) + if (ranked_point.rank == selected_rank + && ranked_point.direction == sort_by_side::dir_to) { - return result; + turn_index = ranked_point.turn_index; + op_index = ranked_point.operation_index; + + turn_type const& turn = m_turns[turn_index]; + turn_operation_type const& op = turn.operations[op_index]; + + if (op.enriched.count_left == 0 + && op.enriched.count_right > 0 + && ! op.visited.finalized()) + { + // In some cases interior rings might be generated with polygons + // on both sides + + // TODO: this should be finetuned such that checking + // finalized is not necessary + return true; + } } + } + return false; + } - turn_type const& ranked_turn = m_turns[ranked_point.turn_index]; - turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.operation_index]; - if (result && ranked_op.visited.finalized()) + inline bool all_operations_of_type(sort_by_side::rank_with_rings const& rwr, + operation_type op_type, + sort_by_side::direction_type dir) const + { + typedef std::set<sort_by_side::ring_with_direction>::const_iterator sit_type; + for (sit_type it = rwr.rings.begin(); it != rwr.rings.end(); ++it) + { + sort_by_side::ring_with_direction const& rwd = *it; + if (rwd.direction != dir) { - // One of the arcs in the same direction as the selected result - // is already traversed. return false; } - - if (! is_touching && ranked_op.visited.finalized()) + turn_type const& turn = m_turns[rwd.turn_index]; + if (! turn.both(op_type)) { - // Skip this one, go to next - min_rank = ranked_point.rank; - continue; + return false; } - if (ranked_point.direction == sort_by_side::dir_to - && (ranked_point.rank > min_rank - || ranked_turn.both(operation_continue))) + // Check if this is not yet taken + turn_operation_type const& op = turn.operations[rwd.operation_index]; + if (op.visited.finalized()) { - if (ranked_op.enriched.count_left == 0 - && ranked_op.enriched.count_right > 0) - { - if (result && ranked_point.turn_index != start_turn_index) - { - // Don't override - only override if arrive at start - continue; - } - - turn_index = ranked_point.turn_index; - op_index = ranked_point.operation_index; - - result = true; - selected_rank = ranked_point.rank; - } - else if (! is_touching) - { - return result; - } + return false; } + } - return result; + return true; } inline bool analyze_cluster_intersection(signed_size_type& turn_index, - int& op_index, - sbs_type const& sbs) const + int& op_index, sbs_type const& sbs) const { std::vector<sort_by_side::rank_with_rings> aggregation; - sort_by_side::aggregate_operations(sbs, aggregation); + sort_by_side::aggregate_operations(sbs, aggregation, m_turns, operation_intersection); std::size_t selected_rank = 0; - for (std::size_t i = 0; i < aggregation.size(); i++) + + // Detect specific pattern(s) + bool const detected + = intersection_pattern_common_interior1(selected_rank, aggregation) + || intersection_pattern_common_interior2(selected_rank, aggregation) + || intersection_pattern_common_interior3(selected_rank, aggregation) + || intersection_pattern_common_interior4(selected_rank, aggregation) + ; + + if (! detected) { - sort_by_side::rank_with_rings const& rwr = aggregation[i]; + int incoming_region_id = 0; + std::set<int> outgoing_region_ids; - if (i > 1 - && i - 1 == selected_rank - && rwr.rings.size() == 1) + for (std::size_t i = 0; i < aggregation.size(); i++) { - sort_by_side::ring_with_direction const& rwd = *rwr.rings.begin(); + sort_by_side::rank_with_rings const& rwr = aggregation[i]; - if (rwd.only_turn_on_ring) + if (rwr.all_to() + && rwr.traversable(m_turns) + && selected_rank == 0) { - // Find if this arriving ring was leaving previously - sort_by_side::ring_with_direction leaving = rwd; - leaving.direction = sort_by_side::dir_to; - - sort_by_side::rank_with_rings const& previous = aggregation[i - 1]; + // Take the first (= right) where segments leave, + // having the polygon on the right side + selected_rank = rwr.rank; + } - if (previous.rings.size() == 1 - && previous.rings.count(leaving) == 1) - { - // It arrives back - if this is one of the selected, unselect it - selected_rank = 0; - } + if (rwr.all_from() + && selected_rank > 0 + && outgoing_region_ids.empty()) + { + // Incoming + break; } - } - if (rwr.all_to()) - { - if (selected_rank == 0) + if (incoming_region_id == 0) { - // Take the first (= right) where segments leave, - // having the polygon on the right side - selected_rank = rwr.rank; + sort_by_side::ring_with_direction const& rwd = *rwr.rings.begin(); + turn_type const& turn = m_turns[rwd.turn_index]; + incoming_region_id = turn.operations[rwd.operation_index].enriched.region_id; + } + else + { + if (rwr.rings.size() == 1) + { + sort_by_side::ring_with_direction const& rwd = *rwr.rings.begin(); + turn_type const& turn = m_turns[rwd.turn_index]; + if (rwd.direction == sort_by_side::dir_to + && turn.both(operation_intersection)) + { + + turn_operation_type const& op = turn.operations[rwd.operation_index]; + if (op.enriched.region_id != incoming_region_id + && op.enriched.isolated) + { + outgoing_region_ids.insert(op.enriched.region_id); + } + } + else if (! outgoing_region_ids.empty()) + { + for (int i = 0; i < 2; i++) + { + int const region_id = turn.operations[i].enriched.region_id; + if (outgoing_region_ids.count(region_id) == 1) + { + selected_rank = 0; + outgoing_region_ids.erase(region_id); + } + } + } + } } } } @@ -458,7 +559,7 @@ struct traversal { // This direction is already traveled before, the same // cannot be traveled again - return false; + continue; } // Take the last turn from this rank @@ -479,10 +580,9 @@ struct traversal } inline bool select_turn_from_cluster(signed_size_type& turn_index, - int& op_index, bool& is_touching, + int& op_index, signed_size_type start_turn_index, - segment_identifier const& previous_seg_id, - bool is_start) const + segment_identifier const& previous_seg_id) const { bool const is_union = target_operation == operation_union; @@ -495,15 +595,14 @@ struct traversal cluster_info const& cinfo = mit->second; std::set<signed_size_type> const& ids = cinfo.turn_indices; - sbs_type sbs; - - bool has_origin = false; + sbs_type sbs(m_strategy); for (typename std::set<signed_size_type>::const_iterator sit = ids.begin(); sit != ids.end(); ++sit) { signed_size_type cluster_turn_index = *sit; turn_type const& cluster_turn = m_turns[cluster_turn_index]; + bool const departure_turn = cluster_turn_index == turn_index; if (cluster_turn.discarded) { // Defensive check, discarded turns should not be in cluster @@ -512,79 +611,27 @@ struct traversal for (int i = 0; i < 2; i++) { - turn_operation_type const& op = cluster_turn.operations[i]; - bool is_origin = false; - if (cluster_turn_index == turn_index) - { - // Check if this is the origin - if (OverlayType == overlay_buffer) - { - is_origin = op.seg_id.multi_index == previous_seg_id.multi_index; - } - else - { - is_origin = op.seg_id.source_index - == previous_seg_id.source_index; - } - if (is_origin) - { - has_origin = true; - } - } - - sbs.add(op, cluster_turn_index, i, m_geometry1, m_geometry2, - is_origin); + sbs.add(cluster_turn.operations[i], + cluster_turn_index, i, previous_seg_id, + m_geometry1, m_geometry2, + departure_turn); } } - if (! has_origin) + if (! sbs.has_origin()) { return false; } - sbs.apply(turn.point); bool result = false; if (is_union) { - #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) - is_touching = cinfo.open_count > 1; - if (is_touching) - { - if (cinfo.switch_source) - { - is_touching = false; - std::cout << "CLUSTER: SWITCH SOURCES at " << turn_index << std::endl; - } - else - { - std::cout << "CLUSTER: CONTINUE at " << turn_index << std::endl; - } - } - #else - is_touching = cinfo.open_count > 1 && ! cinfo.switch_source; - #endif - - if (is_touching) - { - sbs.reverse(); - } - - result = select_from_cluster_union(turn_index, op_index, start_turn_index, sbs, - is_touching); + result = select_from_cluster_union(turn_index, op_index, sbs); } else { - if (is_start - && turn.both(operation_intersection) - && turn.operations[op_index].enriched.only_turn_on_ring) - { - // For an ii (usually interior ring), only turn on ring, - // reverse to take first exit - sbs.reverse(); - } - result = analyze_cluster_intersection(turn_index, op_index, sbs); } return result; @@ -594,26 +641,27 @@ struct traversal turn_type const& current_turn, segment_identifier const& previous_seg_id) { - sbs_type sbs; + sbs_type sbs(m_strategy); // Add this turn to the sort-by-side sorter - bool has_origin = false; for (int i = 0; i < 2; i++) { - turn_operation_type const& op = current_turn.operations[i]; - bool const is_origin = op.seg_id.source_index - == previous_seg_id.source_index; - has_origin = has_origin || is_origin; - sbs.add(op, turn_index, i, m_geometry1, m_geometry2, is_origin); + sbs.add(current_turn.operations[i], + turn_index, i, previous_seg_id, + m_geometry1, m_geometry2, + true); } - if (! has_origin) + if (! sbs.has_origin()) { return false; } sbs.apply(current_turn.point); - return analyze_cluster_intersection(turn_index, op_index, sbs); + + bool result = analyze_cluster_intersection(turn_index, op_index, sbs); + + return result; } inline void change_index_for_self_turn(signed_size_type& to_vertex_index, @@ -712,7 +760,6 @@ struct traversal bool select_turn(signed_size_type start_turn_index, int start_op_index, signed_size_type& turn_index, int& op_index, - bool& is_touching, int previous_op_index, signed_size_type previous_turn_index, segment_identifier const& previous_seg_id, @@ -737,8 +784,8 @@ struct traversal if (current_turn.cluster_id < 0 && current_turn.both(operation_intersection)) { - if (analyze_ii_intersection(turn_index, op_index, current_turn, - previous_seg_id)) + if (analyze_ii_intersection(turn_index, op_index, + current_turn, previous_seg_id)) { return true; } @@ -747,8 +794,8 @@ struct traversal if (current_turn.cluster_id >= 0) { - if (! select_turn_from_cluster(turn_index, op_index, is_touching, - start_turn_index, previous_seg_id, is_start)) + if (! select_turn_from_cluster(turn_index, op_index, + start_turn_index, previous_seg_id)) { return false; } @@ -786,6 +833,7 @@ private : Turns& m_turns; Clusters const& m_clusters; RobustPolicy const& m_robust_policy; + SideStrategy m_strategy; Visitor& m_visitor; }; |