diff options
author | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:05:34 +0900 |
---|---|---|
committer | DongHun Kwak <dh0128.kwak@samsung.com> | 2017-09-13 11:06:28 +0900 |
commit | 34bd32e225e2a8a94104489b31c42e5801cc1f4a (patch) | |
tree | d021b579a0c190354819974e1eaf0baa54b551f3 /boost/geometry/algorithms/detail/overlay | |
parent | f763a99a501650eff2c60288aa6f10ef916d769e (diff) | |
download | boost-34bd32e225e2a8a94104489b31c42e5801cc1f4a.tar.gz boost-34bd32e225e2a8a94104489b31c42e5801cc1f4a.tar.bz2 boost-34bd32e225e2a8a94104489b31c42e5801cc1f4a.zip |
Imported Upstream version 1.63.0upstream/1.63.0
Change-Id: Iac85556a04b7e58d63ba636dedb0986e3555714a
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay')
9 files changed, 465 insertions, 166 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp b/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp new file mode 100644 index 0000000000..df62a1f2f6 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp @@ -0,0 +1,100 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2016 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_AGGREGATE_OPERATIONS_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_AGGREGATE_OPERATIONS_HPP + +#include <set> + +#include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay { namespace sort_by_side +{ + +struct ring_with_direction +{ + ring_identifier ring_id; + direction_type direction; + bool only_turn_on_ring; + + + inline bool operator<(ring_with_direction const& other) const + { + return this->ring_id != other.ring_id + ? this->ring_id < other.ring_id + : this->direction < other.direction; + } + + ring_with_direction() + : direction(dir_unknown) + , only_turn_on_ring(false) + {} +}; + +struct rank_with_rings +{ + std::size_t rank; + std::set<ring_with_direction> rings; + + rank_with_rings() + : rank(0) + { + } + + inline bool all_to() const + { + for (std::set<ring_with_direction>::const_iterator it = rings.begin(); + it != rings.end(); ++it) + { + if (it->direction == sort_by_side::dir_from) + { + return false; + } + } + return true; + } +}; + +template <typename Sbs> +inline void aggregate_operations(Sbs const& sbs, std::vector<rank_with_rings>& aggregation) +{ + aggregation.clear(); + for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) + { + typename Sbs::rp const& ranked_point = sbs.m_ranked_points[i]; + + if (aggregation.empty() || aggregation.back().rank != ranked_point.rank) + { + rank_with_rings current; + current.rank = ranked_point.rank; + aggregation.push_back(current); + } + + ring_with_direction rwd; + segment_identifier const& sid = ranked_point.seg_id; + rwd.ring_id = ring_identifier(sid.source_index, sid.multi_index, sid.ring_index); + rwd.direction = ranked_point.direction; + rwd.only_turn_on_ring = ranked_point.only_turn_on_ring; + + + aggregation.back().rings.insert(rwd); + } +} + + +}}} // namespace detail::overlay::sort_by_side +#endif //DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_AGGREGATE_OPERATIONS_HPP diff --git a/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp b/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp index cc55414870..2643415343 100644 --- a/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/enrichment_info.hpp @@ -38,6 +38,7 @@ struct enrichment_info , count_left(0) , count_right(0) , zone(-1) + , only_turn_on_ring(false) {} // vertex to which is free travel after this IP, @@ -57,6 +58,7 @@ struct enrichment_info std::size_t count_left; std::size_t count_right; signed_size_type zone; // open zone, in cluster + bool only_turn_on_ring; // True if it is the only turn on a ring (for clusters) }; diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp index 110e1be2f1..400ed3b881 100644 --- a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp +++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp @@ -14,6 +14,7 @@ #include <map> #include <vector> +#include <boost/core/ignore_unused.hpp> #include <boost/range.hpp> #include <boost/geometry/core/point_order.hpp> #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> @@ -198,7 +199,9 @@ inline signed_size_type add_turn_to_cluster(Turn const& turn, // 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; } @@ -314,11 +317,13 @@ inline void assign_cluster_to_turns(Turns& turns, typename ClusterPerSegment::const_iterator it = cluster_per_segment.find(seg_frac); if (it != cluster_per_segment.end()) { +#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) if (turn.cluster_id != -1 && turn.cluster_id != it->second) { std::cout << " CONFLICT " << std::endl; } +#endif turn.cluster_id = it->second; clusters[turn.cluster_id].turn_indices.insert(turn_index); } @@ -392,6 +397,8 @@ inline bool is_ie_turn(segment_identifier const& ext_seg_0, 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) @@ -680,6 +687,7 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, sbs.apply(turn_point); sbs.find_open(); + sbs.assign_zones(for_operation); // Unset the startable flag for all 'closed' zones for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) @@ -706,7 +714,7 @@ inline void gather_cluster_properties(Clusters& clusters, Turns& turns, } } - cinfo.open_count = sbs.open_count(turns); + cinfo.open_count = sbs.open_count(for_operation); } } diff --git a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp index 91b0f8ae24..bbba623eee 100644 --- a/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp +++ b/boost/geometry/algorithms/detail/overlay/sort_by_side.hpp @@ -37,10 +37,12 @@ struct ranked_point , count_left(0) , count_right(0) , operation(operation_none) + , only_turn_on_ring(false) {} - ranked_point(const Point& p, signed_size_type ti, signed_size_type oi, - direction_type d, operation_type op, segment_identifier sid) + template <typename Op> + ranked_point(const Point& p, signed_size_type ti, int oi, + direction_type d, Op op) : point(p) , rank(0) , zone(-1) @@ -49,20 +51,22 @@ struct ranked_point , direction(d) , count_left(0) , count_right(0) - , operation(op) - , seg_id(sid) + , operation(op.operation) + , seg_id(op.seg_id) + , only_turn_on_ring(op.enriched.only_turn_on_ring) {} Point point; std::size_t rank; signed_size_type zone; // index of closed zone, in uu turn there would be 2 zones signed_size_type turn_index; - signed_size_type operation_index; + int operation_index; // 0,1 direction_type direction; std::size_t count_left; std::size_t count_right; operation_type operation; segment_identifier seg_id; + bool only_turn_on_ring; }; struct less_by_turn_index @@ -181,11 +185,36 @@ private : Point m_p1, m_p2; }; +// Sorts vectors in counter clockwise order (by default) template <bool Reverse1, bool Reverse2, typename Point, typename Compare> struct side_sorter { typedef ranked_point<Point> rp; +private : + struct include_union + { + inline bool operator()(rp const& ranked_point) const + { + // New candidate if there are no polygons on left side, + // but there are on right side + return ranked_point.count_left == 0 + && ranked_point.count_right > 0; + } + }; + + struct include_intersection + { + inline bool operator()(rp const& ranked_point) const + { + // New candidate if there are two polygons on right side, + // and less on the left side + return ranked_point.count_left < 2 + && ranked_point.count_right >= 2; + } + }; + +public : inline void set_origin(Point const& origin) { m_origin = origin; @@ -202,8 +231,8 @@ struct side_sorter op.seg_id, point1, point2, point3); Point const& point_to = op.fraction.is_one() ? point3 : point2; - m_ranked_points.push_back(rp(point1, turn_index, op_index, dir_from, op.operation, op.seg_id)); - m_ranked_points.push_back(rp(point_to, turn_index, op_index, dir_to, op.operation, op.seg_id)); + m_ranked_points.push_back(rp(point1, turn_index, op_index, dir_from, op)); + m_ranked_points.push_back(rp(point_to, turn_index, op_index, dir_to, op)); if (is_origin) { @@ -292,8 +321,6 @@ struct side_sorter &segment_identifier::source_index >(handled); } - - assign_zones(); } void reverse() @@ -303,7 +330,7 @@ struct side_sorter return; } - int const last = 1 + m_ranked_points.back().rank; + std::size_t const last = 1 + m_ranked_points.back().rank; // Move iterator after rank==0 bool has_first = false; @@ -334,13 +361,18 @@ struct side_sorter } } +//private : + + typedef std::vector<rp> container_type; + container_type m_ranked_points; + Point m_origin; + +private : + //! Check how many open spaces there are - template <typename Turns> - std::size_t open_count(Turns const& turns) const + template <typename Include> + inline std::size_t open_count(Include const& include_functor) const { - typedef typename boost::range_value<Turns>::type turn_type; - typedef typename turn_type::turn_operation_type turn_operation_type; - std::size_t result = 0; std::size_t last_rank = 0; for (std::size_t i = 0; i < m_ranked_points.size(); i++) @@ -348,31 +380,16 @@ struct side_sorter rp const& ranked_point = m_ranked_points[i]; if (ranked_point.rank > last_rank - && ranked_point.direction == sort_by_side::dir_to) + && ranked_point.direction == sort_by_side::dir_to + && include_functor(ranked_point)) { - // TODO: take count-left / count_right from rank itself - turn_type const& ranked_turn = turns[ranked_point.turn_index]; - turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.operation_index]; - if (ranked_op.enriched.count_left == 0 - && ranked_op.enriched.count_right > 0) - { - result++; - last_rank = ranked_point.rank; - } + result++; + last_rank = ranked_point.rank; } } return result; } -//protected : - - typedef std::vector<rp> container_type; - container_type m_ranked_points; - Point m_origin; - -private : - - std::size_t move(std::size_t index) const { std::size_t const result = index + 1; @@ -458,7 +475,8 @@ private : } //! Find closed zones and assign it - void assign_zones() + template <typename Include> + std::size_t assign_zones(Include const& include_functor) { // Find a starting point (the first rank after an outgoing rank // with no polygons on the left side) @@ -473,8 +491,7 @@ private : max_rank = ranked_point.rank; } if (ranked_point.direction == sort_by_side::dir_to - && ranked_point.count_left == 0 - && ranked_point.count_right > 0) + && include_functor(ranked_point)) { start_rank = ranked_point.rank + 1; } @@ -510,8 +527,7 @@ private : } if (ranked_point.direction == sort_by_side::dir_to - && ranked_point.count_left == 0 - && ranked_point.count_right > 0) + && include_functor(ranked_point)) { rank_at_next_zone = ranked_point.rank + 1; if (rank_at_next_zone > max_rank) @@ -525,8 +541,25 @@ private : ranked_point.zone = zone_id; } + return zone_id; } +public : + inline std::size_t open_count(operation_type for_operation) const + { + return for_operation == operation_union + ? open_count(include_union()) + : open_count(include_intersection()) + ; + } + + inline std::size_t assign_zones(operation_type for_operation) + { + return for_operation == operation_union + ? assign_zones(include_union()) + : assign_zones(include_intersection()) + ; + } }; diff --git a/boost/geometry/algorithms/detail/overlay/traversal.hpp b/boost/geometry/algorithms/detail/overlay/traversal.hpp index 1156644bc3..5adc0fcf69 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal.hpp @@ -13,6 +13,7 @@ #include <boost/range.hpp> +#include <boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp> #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> #include <boost/geometry/core/access.hpp> @@ -152,8 +153,8 @@ struct traversal } } - inline bool is_visited(turn_type const& turn, turn_operation_type const& op, - signed_size_type turn_index, int op_index) const + inline bool is_visited(turn_type const& , turn_operation_type const& op, + signed_size_type , int) const { return op.visited.visited(); } @@ -162,39 +163,30 @@ struct traversal segment_identifier const& seg_id1, segment_identifier const& seg_id2) const { - if (target_operation == operation_intersection) + // For uu/ii, only switch sources if indicated + turn_type const& turn = m_turns[turn_index]; + + if (OverlayType == overlay_buffer) { - // For intersections always switch sources - return seg_id1.source_index != seg_id2.source_index; + // 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; } - else if (target_operation == operation_union) - { - // For uu, only switch sources if indicated - turn_type const& turn = m_turns[turn_index]; - - if (OverlayType == overlay_buffer) - { - // 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; - } #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) - if (turn.switch_source == 1) - { - std::cout << "Switch source at " << turn_index << std::endl; - } - else - { - std::cout << "DON'T SWITCH SOURCES at " << turn_index << std::endl; - } -#endif - return turn.switch_source - ? seg_id1.source_index != seg_id2.source_index - : seg_id1.source_index == seg_id2.source_index; + if (turn.switch_source) + { + std::cout << "Switch source at " << turn_index << std::endl; } - return false; + else + { + std::cout << "DON'T SWITCH SOURCES at " << turn_index << std::endl; + } +#endif + return turn.switch_source + ? seg_id1.source_index != seg_id2.source_index + : seg_id1.source_index == seg_id2.source_index; } inline @@ -273,10 +265,6 @@ struct traversal segment_identifier const& seg_id, int& selected_op_index) const { - // For "ii", take the other one (alternate) - // UNLESS the other one is already visited - // For "uu", take the same one (see above); - bool result = false; for (int i = 0; i < 2; i++) @@ -347,13 +335,10 @@ struct traversal return true; } - inline bool select_from_cluster(signed_size_type& turn_index, + 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 { - bool const is_union = target_operation == operation_union; - bool const is_intersection = target_operation == operation_intersection; - std::size_t selected_rank = 0; std::size_t min_rank = 0; bool result = false; @@ -386,11 +371,8 @@ struct traversal && (ranked_point.rank > min_rank || ranked_turn.both(operation_continue))) { - if ((is_union - && ranked_op.enriched.count_left == 0 + if (ranked_op.enriched.count_left == 0 && ranked_op.enriched.count_right > 0) - || (is_intersection - && ranked_op.enriched.count_right == 2)) { if (result && ranked_point.turn_index != start_turn_index) { @@ -401,16 +383,6 @@ struct traversal turn_index = ranked_point.turn_index; op_index = ranked_point.operation_index; - if (is_intersection - && ranked_turn.both(operation_intersection) - && ranked_op.visited.finalized()) - { - // Override: - // For a ii turn, even though one operation might be selected, - // it should take the other one if the first one is used in a completed ring - op_index = 1 - ranked_point.operation_index; - } - result = true; selected_rank = ranked_point.rank; } @@ -423,10 +395,94 @@ struct traversal return result; } + inline bool analyze_cluster_intersection(signed_size_type& turn_index, + int& op_index, + sbs_type const& sbs) const + { + std::vector<sort_by_side::rank_with_rings> aggregation; + sort_by_side::aggregate_operations(sbs, aggregation); + + std::size_t selected_rank = 0; + + for (std::size_t i = 0; i < aggregation.size(); i++) + { + sort_by_side::rank_with_rings const& rwr = aggregation[i]; + + if (i > 1 + && i - 1 == selected_rank + && rwr.rings.size() == 1) + { + sort_by_side::ring_with_direction const& rwd = *rwr.rings.begin(); + + if (rwd.only_turn_on_ring) + { + // 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]; + + 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_to()) + { + if (selected_rank == 0) + { + // Take the first (= right) where segments leave, + // having the polygon on the right side + selected_rank = rwr.rank; + } + } + } + + if (selected_rank > 0) + { + std::size_t selected_index = sbs.m_ranked_points.size(); + for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) + { + typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i]; + + if (ranked_point.rank == selected_rank) + { + 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 (ranked_op.visited.finalized()) + { + // This direction is already traveled before, the same + // cannot be traveled again + return false; + } + + // Take the last turn from this rank + selected_index = i; + } + } + + if (selected_index < sbs.m_ranked_points.size()) + { + typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[selected_index]; + turn_index = ranked_point.turn_index; + op_index = ranked_point.operation_index; + return true; + } + } + + return false; + } + inline bool select_turn_from_cluster(signed_size_type& turn_index, int& op_index, bool& is_touching, signed_size_type start_turn_index, - segment_identifier const& previous_seg_id) const + segment_identifier const& previous_seg_id, + bool is_start) const { bool const is_union = target_operation == operation_union; @@ -488,30 +544,76 @@ struct traversal sbs.apply(turn.point); -#if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) - is_touching = is_union && cinfo.open_count > 1; - if (is_touching) + bool result = false; + + if (is_union) { - if (cinfo.switch_source) + #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) + is_touching = cinfo.open_count > 1; + if (is_touching) { - is_touching = false; - std::cout << "CLUSTER: SWITCH SOURCES at " << turn_index << std::endl; + 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 + #else + is_touching = cinfo.open_count > 1 && ! cinfo.switch_source; + #endif + + if (is_touching) { - std::cout << "CLUSTER: CONTINUE at " << turn_index << std::endl; + sbs.reverse(); } + + result = select_from_cluster_union(turn_index, op_index, start_turn_index, sbs, + is_touching); } -#else - is_touching = is_union && cinfo.open_count > 1 && ! cinfo.switch_source; -#endif - if (is_touching) + else { - sbs.reverse(); + 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; + } - return select_from_cluster(turn_index, op_index, start_turn_index, sbs, - is_touching); + inline bool analyze_ii_intersection(signed_size_type& turn_index, int& op_index, + turn_type const& current_turn, + segment_identifier const& previous_seg_id) + { + sbs_type sbs; + + // 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); + } + + if (! has_origin) + { + return false; + } + + sbs.apply(current_turn.point); + return analyze_cluster_intersection(turn_index, op_index, sbs); } inline void change_index_for_self_turn(signed_size_type& to_vertex_index, @@ -607,7 +709,7 @@ struct traversal return true; } - bool select_turn(signed_size_type start_turn_index, + bool select_turn(signed_size_type start_turn_index, int start_op_index, signed_size_type& turn_index, int& op_index, bool& is_touching, @@ -616,10 +718,37 @@ struct traversal segment_identifier const& previous_seg_id, bool is_start) { - if (m_turns[turn_index].cluster_id >= 0) + turn_type const& current_turn = m_turns[turn_index]; + + if (target_operation == operation_intersection) + { + bool const back_at_start_cluster + = current_turn.cluster_id >= 0 + && m_turns[start_turn_index].cluster_id == current_turn.cluster_id; + + if (turn_index == start_turn_index || back_at_start_cluster) + { + // Intersection can always be finished if returning + turn_index = start_turn_index; + op_index = start_op_index; + return true; + } + + if (current_turn.cluster_id < 0 + && current_turn.both(operation_intersection)) + { + if (analyze_ii_intersection(turn_index, op_index, current_turn, + previous_seg_id)) + { + return true; + } + } + } + + if (current_turn.cluster_id >= 0) { if (! select_turn_from_cluster(turn_index, op_index, is_touching, - start_turn_index, previous_seg_id)) + start_turn_index, previous_seg_id, is_start)) { return false; } @@ -631,8 +760,6 @@ struct traversal } else { - turn_type const& current_turn = m_turns[turn_index]; - op_index = starting_operation_index(current_turn); if (op_index == -1) { diff --git a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp index 104bd6b8e7..e0dfee19a8 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp @@ -64,9 +64,7 @@ struct traversal_ring_creator , m_clusters(clusters) , m_robust_policy(robust_policy) , m_visitor(visitor) - , m_has_uu(false) { - } template <typename Ring> @@ -123,7 +121,8 @@ struct traversal_ring_creator } bool is_touching = false; - if (! m_trav.select_turn(start_turn_index, turn_index, op_index, + if (! m_trav.select_turn(start_turn_index, start_op_index, + turn_index, op_index, is_touching, previous_op_index, previous_turn_index, previous_seg_id, is_start)) @@ -189,6 +188,18 @@ struct traversal_ring_creator return traverse_error_none; } + if (start_turn.cluster_id >= 0) + { + turn_type const& turn = m_turns[current_turn_index]; + if (turn.cluster_id == start_turn.cluster_id) + { + turn_operation_type& op = m_turns[start_turn_index].operations[current_op_index]; + op.visited.set_finished(); + m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish (cluster)"); + return traverse_error_none; + } + } + std::size_t const max_iterations = 2 + 2 * m_turns.size(); for (std::size_t i = 0; i <= max_iterations; i++) { @@ -276,49 +287,21 @@ struct traversal_ring_creator template <typename Rings> void iterate(Rings& rings, std::size_t& finalized_ring_size, - typename Backtrack::state_type& state, - int pass) + typename Backtrack::state_type& state) { - if (pass == 1) - { - if (target_operation == operation_intersection) - { - // Second pass currently only used for uu - return; - } - if (! m_has_uu) - { - // There is no uu found in first pass - return; - } - } - - // Iterate through all unvisited points for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) { - turn_type const& start_turn = m_turns[turn_index]; + turn_type const& turn = m_turns[turn_index]; - if (start_turn.discarded || start_turn.blocked()) + if (turn.discarded || turn.blocked()) { // Skip discarded and blocked turns continue; } - if (target_operation == operation_union) - { - if (start_turn.both(operation_union)) - { - // Start with a uu-turn only in the second pass - m_has_uu = true; - if (pass == 0) - { - continue; - } - } - } for (int op_index = 0; op_index < 2; op_index++) { - traverse_with_operation(start_turn, turn_index, op_index, + traverse_with_operation(turn, turn_index, op_index, rings, finalized_ring_size, state); } } @@ -333,10 +316,6 @@ private: Clusters const& m_clusters; RobustPolicy const& m_robust_policy; Visitor& m_visitor; - - // Next member is only used for operation union - bool m_has_uu; - }; }} // namespace detail::overlay diff --git a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp index 9381c66e0e..183131c74b 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp @@ -71,8 +71,8 @@ struct traversal_switch_detector { if (turn.cluster_id == -1) { - // If it is a uu-turn (non clustered), it is never same zone - return ! turn.both(operation_union); + // If it is a uu/ii-turn (non clustered), it is never same zone + return ! (turn.both(operation_union) || turn.both(operation_intersection)); } // It is a cluster, check zones of both operations @@ -110,11 +110,11 @@ struct traversal_switch_detector for (set_iterator sit = ring_turn_indices.begin(); sit != ring_turn_indices.end(); ++sit) { - int const turn_index = *sit; + signed_size_type const turn_index = *sit; turn_type const& turn = m_turns[turn_index]; if (! connects_same_zone(turn)) { - // This is a non clustered uu-turn, or a cluster connecting different 'zones' + // This is a non clustered uu/ii-turn, or a cluster connecting different 'zones' continue; } @@ -132,6 +132,56 @@ struct traversal_switch_detector } } + void check_turns_per_ring(ring_identifier const& ring_id, + std::set<signed_size_type> const& ring_turn_indices) + { + bool only_turn_on_ring = true; + if (ring_turn_indices.size() > 1) + { + // More turns on this ring. Only leave only_turn_on_ring true + // if they are all of the same cluster + int cluster_id = -1; + for (set_iterator sit = ring_turn_indices.begin(); + sit != ring_turn_indices.end(); ++sit) + { + turn_type const& turn = m_turns[*sit]; + if (turn.cluster_id == -1) + { + // Unclustered turn - and there are 2 or more turns + // so the ring has different turns + only_turn_on_ring = false; + break; + } + + // Clustered turn, check if it is the first or same as previous + if (cluster_id == -1) + { + cluster_id = turn.cluster_id; + } + else if (turn.cluster_id != cluster_id) + { + only_turn_on_ring = false; + break; + } + } + } + + // Assign result to matching operation (a turn is always on two rings) + for (set_iterator sit = ring_turn_indices.begin(); + sit != ring_turn_indices.end(); ++sit) + { + turn_type& turn = m_turns[*sit]; + for (int i = 0; i < 2; i++) + { + turn_operation_type& op = turn.operations[i]; + if (ring_id_by_seg_id(op.seg_id) == ring_id) + { + op.enriched.only_turn_on_ring = only_turn_on_ring; + } + } + } + } + void propagate_region(ring_identifier const& ring_id, int region_id) { std::map<ring_identifier, std::set<signed_size_type> >::const_iterator it = m_turns_per_ring.find(ring_id); @@ -168,6 +218,7 @@ struct traversal_switch_detector = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it) { create_region(it->first, it->second); + check_turns_per_ring(it->first, it->second); } // Now that all regions are filled, assign switch_source property @@ -204,7 +255,7 @@ struct traversal_switch_detector cinfo.switch_source = regions.size() == 1; } - // Iterate through all uu turns (non-clustered) + // Iterate through all uu/ii turns (non-clustered) for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) { turn_type& turn = m_turns[turn_index]; @@ -212,9 +263,9 @@ struct traversal_switch_detector if (turn.discarded || turn.blocked() || turn.cluster_id >= 0 - || ! turn.both(operation_union)) + || ! (turn.both(operation_union) || turn.both(operation_intersection))) { - // Skip discarded, blocked, non-uu and clustered turns + // Skip discarded, blocked, non-uu/ii and clustered turns continue; } @@ -242,9 +293,10 @@ struct traversal_switch_detector { turn_type const& turn = m_turns[turn_index]; - if (turn.both(operation_union) && turn.cluster_id < 0) + if ((turn.both(operation_union) || turn.both(operation_intersection)) + && turn.cluster_id < 0) { - std::cout << "UU SWITCH RESULT " + std::cout << "UU/II SWITCH RESULT " << turn_index << " -> " << turn.switch_source << std::endl; } diff --git a/boost/geometry/algorithms/detail/overlay/traverse.hpp b/boost/geometry/algorithms/detail/overlay/traverse.hpp index 2d2933ebdd..f01e50eb03 100644 --- a/boost/geometry/algorithms/detail/overlay/traverse.hpp +++ b/boost/geometry/algorithms/detail/overlay/traverse.hpp @@ -97,10 +97,7 @@ public : typename Backtrack::state_type state; - for (int pass = 0; pass < 2; pass++) - { - trav.iterate(rings, finalized_ring_size, state, pass); - } + trav.iterate(rings, finalized_ring_size, state); } }; diff --git a/boost/geometry/algorithms/detail/overlay/turn_info.hpp b/boost/geometry/algorithms/detail/overlay/turn_info.hpp index 73f266a04a..e09af126c6 100644 --- a/boost/geometry/algorithms/detail/overlay/turn_info.hpp +++ b/boost/geometry/algorithms/detail/overlay/turn_info.hpp @@ -13,6 +13,7 @@ #include <boost/array.hpp> #include <boost/geometry/core/coordinate_type.hpp> +#include <boost/geometry/algorithms/detail/signed_size_type.hpp> #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> @@ -88,7 +89,7 @@ struct turn_info Point point; method_type method; - int cluster_id; + signed_size_type cluster_id; // For multiple turns on same location, >= 0. Else -1 bool discarded; bool colocated; bool switch_source; // For u/u turns which can either switch or not |