diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/sort_by_side.hpp')
-rw-r--r-- | boost/geometry/algorithms/detail/overlay/sort_by_side.hpp | 111 |
1 files changed, 72 insertions, 39 deletions
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()) + ; + } }; |