diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp | 347 |
1 files changed, 347 insertions, 0 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp new file mode 100644 index 0000000000..104bd6b8e7 --- /dev/null +++ b/boost/geometry/algorithms/detail/overlay/traversal_ring_creator.hpp @@ -0,0 +1,347 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2007-2012 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_TRAVERSAL_RING_CREATOR_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP + +#include <cstddef> + +#include <boost/range.hpp> + +#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> +#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> +#include <boost/geometry/algorithms/detail/overlay/traversal.hpp> +#include <boost/geometry/algorithms/num_points.hpp> +#include <boost/geometry/core/access.hpp> +#include <boost/geometry/core/assert.hpp> +#include <boost/geometry/core/closure.hpp> + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace overlay +{ + + +template +< + bool Reverse1, + bool Reverse2, + overlay_type OverlayType, + typename Geometry1, + typename Geometry2, + typename Turns, + typename Clusters, + typename RobustPolicy, + typename Visitor, + typename Backtrack +> +struct traversal_ring_creator +{ + typedef traversal<Reverse1, Reverse2, OverlayType, + Geometry1, Geometry2, Turns, Clusters, RobustPolicy, Visitor> + traversal_type; + + typedef typename boost::range_value<Turns>::type turn_type; + typedef typename turn_type::turn_operation_type turn_operation_type; + + static const operation_type target_operation + = operation_from_overlay<OverlayType>::value; + + inline traversal_ring_creator(Geometry1 const& geometry1, Geometry2 const& geometry2, + Turns& turns, Clusters const& clusters, + RobustPolicy const& robust_policy, Visitor& visitor) + : m_trav(geometry1, geometry2, turns, clusters, robust_policy,visitor) + , m_geometry1(geometry1) + , m_geometry2(geometry2) + , m_turns(turns) + , m_clusters(clusters) + , m_robust_policy(robust_policy) + , m_visitor(visitor) + , m_has_uu(false) + { + + } + + template <typename Ring> + inline traverse_error_type travel_to_next_turn(signed_size_type start_turn_index, + int start_op_index, + signed_size_type& turn_index, + int& op_index, + Ring& current_ring, + bool is_start) + { + int const previous_op_index = op_index; + signed_size_type const previous_turn_index = turn_index; + turn_type& previous_turn = m_turns[turn_index]; + turn_operation_type& previous_op = previous_turn.operations[op_index]; + segment_identifier previous_seg_id; + + signed_size_type to_vertex_index = -1; + if (! m_trav.select_turn_from_enriched(turn_index, previous_seg_id, + to_vertex_index, start_turn_index, start_op_index, + previous_turn, previous_op, is_start)) + { + return is_start + ? traverse_error_no_next_ip_at_start + : traverse_error_no_next_ip; + } + if (to_vertex_index >= 0) + { + if (previous_op.seg_id.source_index == 0) + { + geometry::copy_segments<Reverse1>(m_geometry1, + previous_op.seg_id, to_vertex_index, + m_robust_policy, current_ring); + } + else + { + geometry::copy_segments<Reverse2>(m_geometry2, + previous_op.seg_id, to_vertex_index, + m_robust_policy, current_ring); + } + } + + if (m_turns[turn_index].discarded) + { + return is_start + ? traverse_error_dead_end_at_start + : traverse_error_dead_end; + } + + if (is_start) + { + // Register the start + previous_op.visited.set_started(); + m_visitor.visit_traverse(m_turns, previous_turn, previous_op, "Start"); + } + + bool is_touching = false; + if (! m_trav.select_turn(start_turn_index, turn_index, op_index, + is_touching, + previous_op_index, previous_turn_index, previous_seg_id, + is_start)) + { + return is_start + ? traverse_error_no_next_ip_at_start + : traverse_error_no_next_ip; + } + + { + // Check operation (TODO: this might be redundant or should be catched before) + const turn_type& current_turn = m_turns[turn_index]; + const turn_operation_type& op = current_turn.operations[op_index]; + if (op.visited.finalized() + || m_trav.is_visited(current_turn, op, turn_index, op_index)) + { + return traverse_error_visit_again; + } + } + + // Update registration and append point + turn_type& current_turn = m_turns[turn_index]; + turn_operation_type& op = current_turn.operations[op_index]; + detail::overlay::append_no_dups_or_spikes(current_ring, current_turn.point, + m_robust_policy); + + // Register the visit + m_trav.set_visited(current_turn, op); + m_visitor.visit_traverse(m_turns, current_turn, op, "Visit"); + + return traverse_error_none; + } + + template <typename Ring> + inline traverse_error_type traverse(Ring& ring, + signed_size_type start_turn_index, int start_op_index) + { + turn_type const& start_turn = m_turns[start_turn_index]; + turn_operation_type& start_op = m_turns[start_turn_index].operations[start_op_index]; + + detail::overlay::append_no_dups_or_spikes(ring, start_turn.point, + m_robust_policy); + + signed_size_type current_turn_index = start_turn_index; + int current_op_index = start_op_index; + + traverse_error_type error = travel_to_next_turn(start_turn_index, + start_op_index, + current_turn_index, current_op_index, + ring, true); + + if (error != traverse_error_none) + { + // This is not necessarily a problem, it happens for clustered turns + // which are "build in" or otherwise point inwards + return error; + } + + if (current_turn_index == start_turn_index) + { + start_op.visited.set_finished(); + m_visitor.visit_traverse(m_turns, m_turns[current_turn_index], start_op, "Early finish"); + 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++) + { + // We assume clockwise polygons only, non self-intersecting, closed. + // However, the input might be different, and checking validity + // is up to the library user. + + // Therefore we make here some sanity checks. If the input + // violates the assumptions, the output polygon will not be correct + // but the routine will stop and output the current polygon, and + // will continue with the next one. + + // Below three reasons to stop. + error = travel_to_next_turn(start_turn_index, start_op_index, + current_turn_index, current_op_index, + ring, false); + + if (error != traverse_error_none) + { + return error; + } + + if (current_turn_index == start_turn_index + && current_op_index == start_op_index) + { + start_op.visited.set_finished(); + m_visitor.visit_traverse(m_turns, start_turn, start_op, "Finish"); + return traverse_error_none; + } + } + + return traverse_error_endless_loop; + } + + template <typename Rings> + void traverse_with_operation(turn_type const& start_turn, + std::size_t turn_index, int op_index, + Rings& rings, std::size_t& finalized_ring_size, + typename Backtrack::state_type& state) + { + typedef typename boost::range_value<Rings>::type ring_type; + + turn_operation_type const& start_op = start_turn.operations[op_index]; + + if (! start_op.visited.none() + || ! start_op.enriched.startable + || start_op.visited.rejected() + || ! (start_op.operation == target_operation + || start_op.operation == detail::overlay::operation_continue)) + { + return; + } + + ring_type ring; + traverse_error_type traverse_error = traverse(ring, turn_index, op_index); + + if (traverse_error == traverse_error_none) + { + std::size_t const min_num_points + = core_detail::closure::minimum_ring_size + < + geometry::closure<ring_type>::value + >::value; + + if (geometry::num_points(ring) >= min_num_points) + { + clean_closing_dups_and_spikes(ring, m_robust_policy); + rings.push_back(ring); + + m_trav.finalize_visit_info(); + finalized_ring_size++; + } + } + else + { + Backtrack::apply( + finalized_ring_size, + rings, ring, m_turns, start_turn, + m_turns[turn_index].operations[op_index], + traverse_error, + m_geometry1, m_geometry2, m_robust_policy, + state, m_visitor); + } + } + + template <typename Rings> + void iterate(Rings& rings, std::size_t& finalized_ring_size, + typename Backtrack::state_type& state, + int pass) + { + 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]; + + if (start_turn.discarded || start_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, + rings, finalized_ring_size, state); + } + } + } + +private: + traversal_type m_trav; + + Geometry1 const& m_geometry1; + Geometry2 const& m_geometry2; + Turns& m_turns; + 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 +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_RING_CREATOR_HPP |