diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp')
-rw-r--r-- | boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp | 152 |
1 files changed, 111 insertions, 41 deletions
diff --git a/boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp b/boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp index 395921ccaa..6a3daa282e 100644 --- a/boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp +++ b/boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp @@ -16,6 +16,7 @@ #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> +#include <boost/geometry/algorithms/detail/sections/section_functions.hpp> namespace boost { namespace geometry @@ -27,32 +28,16 @@ namespace detail { namespace buffer { -struct piece_get_box -{ - template <typename Box, typename Piece> - static inline void apply(Box& total, Piece const& piece) - { - geometry::expand(total, piece.robust_envelope); - } -}; - -struct piece_ovelaps_box -{ - template <typename Box, typename Piece> - static inline bool apply(Box const& box, Piece const& piece) - { - return ! geometry::detail::disjoint::disjoint_box_box(box, piece.robust_envelope); - } -}; - template < + typename Pieces, typename Rings, typename Turns, typename RobustPolicy > class piece_turn_visitor { + Pieces const& m_pieces; Rings const& m_rings; Turns& m_turns; RobustPolicy const& m_robust_policy; @@ -69,6 +54,17 @@ class piece_turn_visitor || piece1.index == piece2.right_index; } + template <typename Piece> + inline bool is_on_same_convex_ring(Piece const& piece1, Piece const& piece2) const + { + if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index) + { + return false; + } + + return ! m_rings[piece1.first_seg_id.multi_index].has_concave; + } + template <typename Range, typename Iterator> inline void move_to_next_point(Range const& range, Iterator& next) const { @@ -93,46 +89,110 @@ class piece_turn_visitor return result; } - template <typename Piece> - inline void calculate_turns(Piece const& piece1, Piece const& piece2) + template <std::size_t Dimension, typename Iterator, typename Box> + inline void move_begin_iterator(Iterator& it_begin, Iterator it_beyond, + int& index, int dir, Box const& other_bounding_box) + { + for(; it_begin != it_beyond + && it_begin + 1 != it_beyond + && detail::section::preceding<Dimension>(dir, *(it_begin + 1), + other_bounding_box, m_robust_policy); + ++it_begin, index++) + {} + } + + template <std::size_t Dimension, typename Iterator, typename Box> + inline void move_end_iterator(Iterator it_begin, Iterator& it_beyond, + int dir, Box const& other_bounding_box) + { + while (it_beyond != it_begin + && it_beyond - 1 != it_begin + && it_beyond - 2 != it_begin) + { + if (detail::section::exceeding<Dimension>(dir, *(it_beyond - 2), + other_bounding_box, m_robust_policy)) + { + --it_beyond; + } + else + { + return; + } + } + } + + template <typename Piece, typename Section> + inline void calculate_turns(Piece const& piece1, Piece const& piece2, + Section const& section1, Section const& section2) { typedef typename boost::range_value<Rings const>::type ring_type; typedef typename boost::range_value<Turns const>::type turn_type; typedef typename boost::range_iterator<ring_type const>::type iterator; - segment_identifier seg_id1 = piece1.first_seg_id; - segment_identifier seg_id2 = piece2.first_seg_id; - - if (seg_id1.segment_index < 0 || seg_id2.segment_index < 0) + int const piece1_first_index = piece1.first_seg_id.segment_index; + int const piece2_first_index = piece2.first_seg_id.segment_index; + if (piece1_first_index < 0 || piece2_first_index < 0) { return; } - ring_type const& ring1 = m_rings[seg_id1.multi_index]; - iterator it1_first = boost::begin(ring1) + seg_id1.segment_index; - iterator it1_last = boost::begin(ring1) + piece1.last_segment_index; - - ring_type const& ring2 = m_rings[seg_id2.multi_index]; - iterator it2_first = boost::begin(ring2) + seg_id2.segment_index; - iterator it2_last = boost::begin(ring2) + piece2.last_segment_index; + // Get indices of part of offsetted_rings for this monotonic section: + int const sec1_first_index = piece1_first_index + section1.begin_index; + int const sec2_first_index = piece2_first_index + section2.begin_index; + + // index of last point in section, beyond-end is one further + int const sec1_last_index = piece1_first_index + section1.end_index; + int const sec2_last_index = piece2_first_index + section2.end_index; + + // get geometry and iterators over these sections + ring_type const& ring1 = m_rings[piece1.first_seg_id.multi_index]; + iterator it1_first = boost::begin(ring1) + sec1_first_index; + iterator it1_beyond = boost::begin(ring1) + sec1_last_index + 1; + + ring_type const& ring2 = m_rings[piece2.first_seg_id.multi_index]; + iterator it2_first = boost::begin(ring2) + sec2_first_index; + iterator it2_beyond = boost::begin(ring2) + sec2_last_index + 1; + + // Set begin/end of monotonic ranges, in both x/y directions + int index1 = sec1_first_index; + move_begin_iterator<0>(it1_first, it1_beyond, index1, + section1.directions[0], section2.bounding_box); + move_end_iterator<0>(it1_first, it1_beyond, + section1.directions[0], section2.bounding_box); + move_begin_iterator<1>(it1_first, it1_beyond, index1, + section1.directions[1], section2.bounding_box); + move_end_iterator<1>(it1_first, it1_beyond, + section1.directions[1], section2.bounding_box); + + int index2 = sec2_first_index; + move_begin_iterator<0>(it2_first, it2_beyond, index2, + section2.directions[0], section1.bounding_box); + move_end_iterator<0>(it2_first, it2_beyond, + section2.directions[0], section1.bounding_box); + move_begin_iterator<1>(it2_first, it2_beyond, index2, + section2.directions[1], section1.bounding_box); + move_end_iterator<1>(it2_first, it2_beyond, + section2.directions[1], section1.bounding_box); turn_type the_model; the_model.operations[0].piece_index = piece1.index; the_model.operations[0].seg_id = piece1.first_seg_id; + the_model.operations[0].seg_id.segment_index = index1; // override iterator it1 = it1_first; for (iterator prev1 = it1++; - it1 != it1_last; + it1 != it1_beyond; prev1 = it1++, the_model.operations[0].seg_id.segment_index++) { the_model.operations[1].piece_index = piece2.index; the_model.operations[1].seg_id = piece2.first_seg_id; + the_model.operations[1].seg_id.segment_index = index2; // override iterator next1 = next_point(ring1, it1); iterator it2 = it2_first; for (iterator prev2 = it2++; - it2 != it2_last; + it2 != it2_beyond; prev2 = it2++, the_model.operations[1].seg_id.segment_index++) { iterator next2 = next_point(ring2, it2); @@ -158,26 +218,36 @@ class piece_turn_visitor public: - piece_turn_visitor(Rings const& ring_collection, + piece_turn_visitor(Pieces const& pieces, + Rings const& ring_collection, Turns& turns, RobustPolicy const& robust_policy) - : m_rings(ring_collection) + : m_pieces(pieces) + , m_rings(ring_collection) , m_turns(turns) , m_robust_policy(robust_policy) {} - template <typename Piece> - inline void apply(Piece const& piece1, Piece const& piece2, + template <typename Section> + inline void apply(Section const& section1, Section const& section2, bool first = true) { boost::ignore_unused_variable_warning(first); - if ( is_adjacent(piece1, piece2) - || detail::disjoint::disjoint_box_box(piece1.robust_envelope, - piece2.robust_envelope)) + + typedef typename boost::range_value<Pieces const>::type piece_type; + piece_type const& piece1 = m_pieces[section1.ring_id.source_index]; + piece_type const& piece2 = m_pieces[section2.ring_id.source_index]; + + if ( piece1.index == piece2.index + || is_adjacent(piece1, piece2) + || is_on_same_convex_ring(piece1, piece2) + || detail::disjoint::disjoint_box_box(section1.bounding_box, + section2.bounding_box) ) { return; } - calculate_turns(piece1, piece2); + + calculate_turns(piece1, piece2, section1, section2); } }; |