diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/traversal.hpp')
-rw-r--r-- | boost/geometry/algorithms/detail/overlay/traversal.hpp | 175 |
1 files changed, 94 insertions, 81 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/traversal.hpp b/boost/geometry/algorithms/detail/overlay/traversal.hpp index a0149789c6..22ae1a2de8 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal.hpp @@ -123,12 +123,8 @@ public : template <typename TurnInfoMap> inline void finalize_visit_info(TurnInfoMap& turn_info_map) { - for (typename boost::range_iterator<Turns>::type - it = boost::begin(m_turns); - it != boost::end(m_turns); - ++it) + for (auto& turn : m_turns) { - turn_type& turn = *it; for (int i = 0; i < 2; i++) { turn_operation_type& op = turn.operations[i]; @@ -158,23 +154,18 @@ public : 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); + auto 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) + for (auto turn_index : cinfo.turn_indices) { - signed_size_type const turn_index = *it; turn_type& turn = m_turns[turn_index]; - for (int i = 0; i < 2; i++) + for (auto& op : turn.operations) { - turn_operation_type& op = turn.operations[i]; - if (op.visited.none() - && op.enriched.rank == rank) + if (op.visited.none() && op.enriched.rank == rank) { op.visited.set_visited(); } @@ -621,31 +612,32 @@ public : return m_turns[rp.turn_index].operations[rp.operation_index]; } - inline sort_by_side::rank_type select_rank(sbs_type const& sbs, - bool skip_isolated) const + inline sort_by_side::rank_type select_rank(sbs_type const& sbs) const { + static bool const is_intersection + = target_operation == operation_intersection; + // Take the first outgoing rank corresponding to incoming region, // or take another region if it is not isolated - turn_operation_type const& incoming_op - = operation_from_rank(sbs.m_ranked_points.front()); + auto const& in_op = operation_from_rank(sbs.m_ranked_points.front()); for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) { - typename sbs_type::rp const& rp = sbs.m_ranked_points[i]; + auto const& rp = sbs.m_ranked_points[i]; if (rp.rank == 0 || rp.direction == sort_by_side::dir_from) { continue; } - turn_operation_type const& op = operation_from_rank(rp); + auto const& out_op = operation_from_rank(rp); - if (op.operation != target_operation - && op.operation != operation_continue) + if (out_op.operation != target_operation + && out_op.operation != operation_continue) { continue; } - if (op.enriched.region_id == incoming_op.enriched.region_id - || (skip_isolated && ! op.enriched.isolated)) + if (in_op.enriched.region_id == out_op.enriched.region_id + || (is_intersection && ! out_op.enriched.isolated)) { // Region corresponds to incoming region, or (for intersection) // there is a non-isolated other region which should be taken @@ -660,7 +652,7 @@ public : int& op_index, sbs_type const& sbs, signed_size_type start_turn_index, int start_op_index) const { - sort_by_side::rank_type const selected_rank = select_rank(sbs, false); + sort_by_side::rank_type const selected_rank = select_rank(sbs); int current_priority = 0; for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++) @@ -688,49 +680,59 @@ public : inline bool analyze_cluster_intersection(signed_size_type& turn_index, int& op_index, sbs_type const& sbs) const { - sort_by_side::rank_type const selected_rank = select_rank(sbs, true); + // Select the rank based on regions and isolation + sort_by_side::rank_type const selected_rank = select_rank(sbs); - if (selected_rank > 0) + if (selected_rank <= 0) { - typename turn_operation_type::comparable_distance_type - min_remaining_distance = 0; + return false; + } - std::size_t selected_index = sbs.m_ranked_points.size(); - for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) + // From these ranks, select the index: the first, or the one with + // the smallest remaining distance + typename turn_operation_type::comparable_distance_type + min_remaining_distance = 0; + + std::size_t selected_index = sbs.m_ranked_points.size(); + for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) + { + auto const& ranked_point = sbs.m_ranked_points[i]; + + if (ranked_point.rank > selected_rank) { - typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i]; + break; + } + else if (ranked_point.rank == selected_rank) + { + auto const& op = operation_from_rank(ranked_point); - if (ranked_point.rank == selected_rank) + if (op.visited.finalized()) { - turn_operation_type const& op = operation_from_rank(ranked_point); - - if (op.visited.finalized()) - { - // This direction is already traveled before, the same - // cannot be traveled again - continue; - } - - // Take turn with the smallest remaining distance - if (selected_index == sbs.m_ranked_points.size() - || op.remaining_distance < min_remaining_distance) - { - selected_index = i; - min_remaining_distance = op.remaining_distance; - } + // This direction is already traveled, + // it cannot be traveled again + continue; } - } - 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; + if (selected_index == sbs.m_ranked_points.size() + || op.remaining_distance < min_remaining_distance) + { + // It was unassigned or it is better + selected_index = i; + min_remaining_distance = op.remaining_distance; + } } } - return false; + if (selected_index == sbs.m_ranked_points.size()) + { + // Should not happen, there must be points with the selected rank + return false; + } + + auto const& ranked_point = sbs.m_ranked_points[selected_index]; + turn_index = ranked_point.turn_index; + op_index = ranked_point.operation_index; + return true; } inline bool fill_sbs(sbs_type& sbs, @@ -778,21 +780,19 @@ public : turn_type const& turn = m_turns[turn_index]; BOOST_ASSERT(turn.is_clustered()); - typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id); + auto mit = m_clusters.find(turn.cluster_id); BOOST_ASSERT(mit != m_clusters.end()); cluster_info const& cinfo = mit->second; - std::set<signed_size_type> const& cluster_indices = cinfo.turn_indices; sbs_type sbs(m_strategy); - - if (! fill_sbs(sbs, turn_index, cluster_indices, previous_seg_id)) + if (! fill_sbs(sbs, turn_index, cinfo.turn_indices, previous_seg_id)) { return false; } - cluster_exits<OverlayType, Turns, sbs_type> exits(m_turns, cluster_indices, sbs); + cluster_exits<OverlayType, Turns, sbs_type> exits(m_turns, cinfo.turn_indices, sbs); if (exits.apply(turn_index, op_index)) { @@ -803,7 +803,7 @@ public : if (is_union) { - result = select_from_cluster_union(turn_index, cluster_indices, + result = select_from_cluster_union(turn_index, cinfo.turn_indices, op_index, sbs, start_turn_index, start_op_index); if (! result) @@ -819,6 +819,7 @@ public : return result; } + // Analyzes a non-clustered "ii" intersection, as if it is clustered. inline bool analyze_ii_intersection(signed_size_type& turn_index, int& op_index, turn_type const& current_turn, segment_identifier const& previous_seg_id) @@ -956,31 +957,43 @@ public : { turn_type const& current_turn = m_turns[turn_index]; + bool const back_at_start_cluster + = has_points + && current_turn.is_clustered() + && m_turns[start_turn_index].cluster_id == current_turn.cluster_id; if (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection)) { - if (has_points) - { - bool const back_at_start_cluster - = current_turn.is_clustered() - && m_turns[start_turn_index].cluster_id == current_turn.cluster_id; + // Intersection or difference - 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 (has_points && (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.is_clustered() - && current_turn.both(operation_intersection)) - { - if (analyze_ii_intersection(turn_index, op_index, + && current_turn.both(operation_intersection) + && analyze_ii_intersection(turn_index, op_index, current_turn, previous_seg_id)) - { - return true; - } + { + return true; + } + } + else if (turn_index == start_turn_index || back_at_start_cluster) + { + // Union or buffer: cannot return immediately to starting turn, because it then + // might miss a formed multi polygon with a touching point. + auto const& current_op = current_turn.operations[op_index]; + signed_size_type const next_turn_index = current_op.enriched.get_next_turn_index(); + bool const to_other_turn = next_turn_index >= 0 && m_turns[next_turn_index].cluster_id != current_turn.cluster_id; + if (! to_other_turn) + { + // Return to starting point + turn_index = start_turn_index; + op_index = start_op_index; + return true; } } |