summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp')
-rw-r--r--boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp152
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);
}
};