diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp | 503 |
1 files changed, 434 insertions, 69 deletions
diff --git a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp index 558a61fcb4..a501e3f197 100644 --- a/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp +++ b/boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp @@ -12,8 +12,9 @@ #include <algorithm> #include <cstddef> #include <set> -#include <boost/range.hpp> +#include <boost/core/ignore_unused.hpp> +#include <boost/range.hpp> #include <boost/geometry/core/coordinate_type.hpp> #include <boost/geometry/core/point_type.hpp> @@ -24,13 +25,14 @@ #include <boost/geometry/strategies/buffer.hpp> #include <boost/geometry/geometries/ring.hpp> -#include <boost/geometry/geometries/polygon.hpp> #include <boost/geometry/algorithms/detail/buffer/buffered_ring.hpp> #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp> #include <boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp> #include <boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp> +#include <boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp> +#include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp> #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp> #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp> @@ -41,6 +43,8 @@ #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> #include <boost/geometry/algorithms/detail/occupation_info.hpp> #include <boost/geometry/algorithms/detail/partition.hpp> +#include <boost/geometry/algorithms/detail/sections/sectionalize.hpp> +#include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp> #include <boost/geometry/util/range.hpp> @@ -89,7 +93,7 @@ enum segment_relation_code * form together the offsetted ring (marked with o below) * The 8 pieces are part of the piece collection and use for inside-checks * The inner parts form (using 1 or 2 points per piece, often co-located) - * form together the robust_ring (marked with r below) + * form together the robust_polygons (marked with r below) * The remaining piece-segments are helper-segments (marked with h) * * ooooooooooooooooo @@ -120,7 +124,7 @@ struct buffered_piece_collection // Robust ring/polygon type, always clockwise typedef geometry::model::ring<robust_point_type> robust_ring_type; - typedef geometry::model::polygon<robust_point_type> robust_polygon_type; + typedef geometry::model::box<robust_point_type> robust_box_type; typedef typename strategy::side::services::default_strategy < @@ -164,6 +168,9 @@ struct buffered_piece_collection struct piece { + typedef robust_ring_type piece_robust_ring_type; + typedef geometry::section<robust_box_type, 1> section_type; + strategy::buffer::piece_type type; int index; @@ -181,18 +188,58 @@ struct buffered_piece_collection #if defined(BOOST_GEOMETRY_BUFFER_USE_HELPER_POINTS) // 2: half, not part of offsetted rings - part of robust ring - std::vector<point_type> helper_points; // 4 points for segment, 3 points for join - 0 points for flat-end + std::vector<point_type> helper_points; // 4 points for side, 3 points for join - 0 points for flat-end #endif + bool is_monotonic_increasing[2]; // 0=x, 1=y + bool is_monotonic_decreasing[2]; // 0=x, 1=y + + // Monotonic sections of pieces around points + std::vector<section_type> sections; + + // Robust representations // 3: complete ring robust_ring_type robust_ring; - geometry::model::box<robust_point_type> robust_envelope; + robust_box_type robust_envelope; + robust_box_type robust_offsetted_envelope; std::vector<robust_turn> robust_turns; // Used only in insert_rescaled_piece_turns - we might use a map instead }; + struct robust_original + { + typedef robust_ring_type original_robust_ring_type; + typedef geometry::sections<robust_box_type, 1> sections_type; + + inline robust_original() + : m_is_interior(false) + , m_has_interiors(true) + {} + + inline robust_original(robust_ring_type const& ring, + bool is_interior, bool has_interiors) + : m_ring(ring) + , m_is_interior(is_interior) + , m_has_interiors(has_interiors) + { + geometry::envelope(m_ring, m_box); + + // create monotonic sections in y-dimension + typedef boost::mpl::vector_c<std::size_t, 1> dimensions; + geometry::sectionalize<false, dimensions>(m_ring, + detail::no_rescale_policy(), m_sections); + } + + robust_ring_type m_ring; + robust_box_type m_box; + sections_type m_sections; + + bool m_is_interior; + bool m_has_interiors; + }; + typedef std::vector<piece> piece_vector_type; piece_vector_type m_pieces; @@ -200,11 +247,17 @@ struct buffered_piece_collection int m_first_piece_index; buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; // indexed by multi_index - buffered_ring_collection<robust_polygon_type> robust_polygons; // robust representation of the original(s) + std::vector<robust_original> robust_originals; // robust representation of the original(s) robust_ring_type current_robust_ring; buffered_ring_collection<Ring> traversed_rings; segment_identifier current_segment_id; + // Specificly for offsetted rings around points + // but also for large joins with many points + typedef geometry::sections<robust_box_type, 2> sections_type; + sections_type monotonic_sections; + + RobustPolicy const& m_robust_policy; struct redundant_turn @@ -378,7 +431,7 @@ struct buffered_piece_collection } } - inline void classify_turns() + inline void classify_turns(bool linear) { for (typename boost::range_iterator<turn_vector_type>::type it = boost::begin(m_turns); it != boost::end(m_turns); ++it) @@ -387,6 +440,10 @@ struct buffered_piece_collection { it->location = inside_buffer; } + if (it->count_on_original_boundary > 0 && ! linear) + { + it->location = inside_buffer; + } if (it->count_within_near_offsetted > 0) { // Within can have in rare cases a rounding issue. We don't discard this @@ -394,31 +451,40 @@ struct buffered_piece_collection // will never start a new ring from this type of points. it->selectable_start = false; } - } } - inline void check_remaining_points(int factor) + template <typename DistanceStrategy> + inline void check_remaining_points(DistanceStrategy const& distance_strategy) { - // TODO: use partition + // Check if a turn is inside any of the originals + + turn_in_original_visitor<turn_vector_type> visitor(m_turns); + geometry::partition + < + robust_box_type, + turn_get_box, turn_in_original_ovelaps_box, + original_get_box, original_ovelaps_box, + include_turn_policy, detail::partition::include_all_policy + >::apply(m_turns, robust_originals, visitor); + + bool const deflate = distance_strategy.negative(); for (typename boost::range_iterator<turn_vector_type>::type it = boost::begin(m_turns); it != boost::end(m_turns); ++it) { - if (it->location == location_ok) + buffer_turn_info_type& turn = *it; + if (turn.location == location_ok) { - int code = -1; - for (std::size_t i = 0; i < robust_polygons.size(); i++) + if (deflate && turn.count_in_original <= 0) { - if (geometry::covered_by(it->robust_point, robust_polygons[i])) - { - code = 1; - break; - } + // For deflate: it is not in original, discard + turn.location = location_discard; } - if (code * factor == 1) + else if (! deflate && turn.count_in_original > 0) { - it->location = inside_original; + // For inflate: it is in original, discard + turn.location = location_discard; } } } @@ -474,6 +540,7 @@ struct buffered_piece_collection // Take into account for the box (intersection points should fall inside, // but in theory they can be one off because of rounding geometry::expand(pc.robust_envelope, it->robust_point); + geometry::expand(pc.robust_offsetted_envelope, it->robust_point); } } @@ -502,9 +569,10 @@ struct buffered_piece_collection { int const index_in_vector = 1 + rit->seg_id.segment_index - piece_segment_index; BOOST_ASSERT - ( - index_in_vector > 0 && index_in_vector < pc.offsetted_count - ); + ( + index_in_vector > 0 + && index_in_vector < pc.offsetted_count + ); pc.robust_ring.insert(boost::begin(pc.robust_ring) + index_in_vector, rit->point); pc.offsetted_count++; @@ -517,25 +585,132 @@ struct buffered_piece_collection BOOST_ASSERT(assert_indices_in_robust_rings()); } + template <std::size_t Dimension> + static inline void determine_monotonicity(piece& pc, + robust_point_type const& current, + robust_point_type const& next) + { + if (geometry::get<Dimension>(current) >= geometry::get<Dimension>(next)) + { + pc.is_monotonic_increasing[Dimension] = false; + } + if (geometry::get<Dimension>(current) <= geometry::get<Dimension>(next)) + { + pc.is_monotonic_decreasing[Dimension] = false; + } + } + + static inline void determine_properties(piece& pc) + { + pc.is_monotonic_increasing[0] = true; + pc.is_monotonic_increasing[1] = true; + pc.is_monotonic_decreasing[0] = true; + pc.is_monotonic_decreasing[1] = true; + + if (pc.offsetted_count < 2) + { + return; + } + + typename robust_ring_type::const_iterator current = pc.robust_ring.begin(); + typename robust_ring_type::const_iterator next = current + 1; + + for (int i = 1; i < pc.offsetted_count; i++) + { + determine_monotonicity<0>(pc, *current, *next); + determine_monotonicity<1>(pc, *current, *next); + current = next; + ++next; + } + + } + + void determine_properties() + { + for (typename piece_vector_type::iterator it = boost::begin(m_pieces); + it != boost::end(m_pieces); + ++it) + { + determine_properties(*it); + } + } + + inline void reverse_negative_robust_rings() + { + for (typename piece_vector_type::iterator it = boost::begin(m_pieces); + it != boost::end(m_pieces); + ++it) + { + piece& pc = *it; + if (geometry::area(pc.robust_ring) < 0) + { + // Rings can be ccw: + // - in a concave piece + // - in a line-buffer with a negative buffer-distance + std::reverse(pc.robust_ring.begin(), pc.robust_ring.end()); + } + } + } + + inline void prepare_buffered_point_piece(piece& pc) + { + // create monotonic sections in y-dimension + typedef boost::mpl::vector_c<std::size_t, 1> dimensions; + geometry::sectionalize<false, dimensions>(pc.robust_ring, + detail::no_rescale_policy(), pc.sections); + + // TODO (next phase) determine min/max radius + } + + inline void prepare_buffered_point_pieces() + { + for (typename piece_vector_type::iterator it = boost::begin(m_pieces); + it != boost::end(m_pieces); + ++it) + { + if (it->type == geometry::strategy::buffer::buffered_point) + { + prepare_buffered_point_piece(*it); + } + } + } + inline void get_turns() { + for(typename boost::range_iterator<sections_type>::type it + = boost::begin(monotonic_sections); + it != boost::end(monotonic_sections); + ++it) + { + enlarge_box(it->bounding_box, 1); + } + { // Calculate the turns piece_turn_visitor < + piece_vector_type, buffered_ring_collection<buffered_ring<Ring> >, turn_vector_type, RobustPolicy - > visitor(offsetted_rings, m_turns, m_robust_policy); + > visitor(m_pieces, offsetted_rings, m_turns, m_robust_policy); geometry::partition < - model::box<robust_point_type>, piece_get_box, piece_ovelaps_box - >::apply(m_pieces, visitor); + robust_box_type, + detail::section::get_section_box, + detail::section::overlaps_section_box + >::apply(monotonic_sections, visitor); } insert_rescaled_piece_turns(); + reverse_negative_robust_rings(); + + determine_properties(); + + prepare_buffered_point_pieces(); + { // Check if it is inside any of the pieces turn_in_piece_visitor @@ -545,16 +720,12 @@ struct buffered_piece_collection geometry::partition < - model::box<robust_point_type>, + robust_box_type, turn_get_box, turn_ovelaps_box, piece_get_box, piece_ovelaps_box >::apply(m_turns, m_pieces, visitor); } - - classify_turns(); - - //get_occupation(); } inline void start_new_ring() @@ -571,7 +742,38 @@ struct buffered_piece_collection m_first_piece_index = boost::size(m_pieces); } - inline void finish_ring(bool is_interior = false) + inline void update_closing_point() + { + BOOST_ASSERT(! offsetted_rings.empty()); + buffered_ring<Ring>& added = offsetted_rings.back(); + if (! boost::empty(added)) + { + range::back(added) = range::front(added); + } + } + + inline void update_last_point(point_type const& p, + buffered_ring<Ring>& ring) + { + // For the first point of a new piece, and there were already + // points in the offsetted ring, for some piece types the first point + // is a duplicate of the last point of the previous piece. + + // TODO: disable that, that point should not be added + + // For now, it is made equal because due to numerical instability, + // it can be a tiny bit off, possibly causing a self-intersection + + BOOST_ASSERT(boost::size(m_pieces) > 0); + if (! ring.empty() + && current_segment_id.segment_index + == m_pieces.back().first_seg_id.segment_index) + { + ring.back() = p; + } + } + + inline void finish_ring(bool is_interior = false, bool has_interiors = false) { if (m_first_piece_index == -1) { @@ -588,41 +790,50 @@ struct buffered_piece_collection } m_first_piece_index = -1; - if (!current_robust_ring.empty()) + update_closing_point(); + + if (! current_robust_ring.empty()) { - BOOST_ASSERT(geometry::equals(current_robust_ring.front(), current_robust_ring.back())); + BOOST_ASSERT + ( + geometry::equals(current_robust_ring.front(), + current_robust_ring.back()) + ); - if (is_interior) - { - if (!robust_polygons.empty()) - { - robust_polygons.back().inners().push_back(current_robust_ring); - } - } - else - { - robust_polygons.resize(robust_polygons.size() + 1); - robust_polygons.back().outer() = current_robust_ring; - } + robust_originals.push_back( + robust_original(current_robust_ring, + is_interior, has_interiors)); } } + inline void set_current_ring_concave() + { + BOOST_ASSERT(boost::size(offsetted_rings) > 0); + offsetted_rings.back().has_concave = true; + } + inline int add_point(point_type const& p) { - BOOST_ASSERT - ( - boost::size(offsetted_rings) > 0 - ); + BOOST_ASSERT(boost::size(offsetted_rings) > 0); + + buffered_ring<Ring>& current_ring = offsetted_rings.back(); + update_last_point(p, current_ring); current_segment_id.segment_index++; - offsetted_rings.back().push_back(p); - return offsetted_rings.back().size(); + current_ring.push_back(p); + return current_ring.size(); } //------------------------------------------------------------------------- - inline piece& create_piece(strategy::buffer::piece_type type, bool decrease_segment_index_by_one) + inline piece& create_piece(strategy::buffer::piece_type type, + bool decrease_segment_index_by_one) { + if (type == strategy::buffer::buffered_concave) + { + offsetted_rings.back().has_concave = true; + } + piece pc; pc.type = type; pc.index = boost::size(m_pieces); @@ -634,6 +845,7 @@ struct buffered_piece_collection std::size_t const n = boost::size(offsetted_rings.back()); pc.first_seg_id.segment_index = decrease_segment_index_by_one ? n - 1 : n; + pc.last_segment_index = pc.first_seg_id.segment_index; m_pieces.push_back(pc); return m_pieces.back(); @@ -641,6 +853,18 @@ struct buffered_piece_collection inline void init_rescale_piece(piece& pc, std::size_t helper_points_size) { + if (pc.first_seg_id.segment_index < 0) + { + // This indicates an error situation: an earlier piece was empty + // It currently does not happen + // std::cout << "EMPTY " << pc.type << " " << pc.index << " " << pc.first_seg_id.multi_index << std::endl; + pc.offsetted_count = 0; + return; + } + + BOOST_ASSERT(pc.first_seg_id.multi_index >= 0); + BOOST_ASSERT(pc.last_segment_index >= 0); + pc.offsetted_count = pc.last_segment_index - pc.first_seg_id.segment_index; BOOST_ASSERT(pc.offsetted_count >= 0); @@ -674,16 +898,65 @@ struct buffered_piece_collection return rob_point; } + // TODO: this is shared with sectionalize, move to somewhere else (assign?) + template <typename Box, typename Value> + inline void enlarge_box(Box& box, Value value) + { + geometry::set<0, 0>(box, geometry::get<0, 0>(box) - value); + geometry::set<0, 1>(box, geometry::get<0, 1>(box) - value); + geometry::set<1, 0>(box, geometry::get<1, 0>(box) + value); + geometry::set<1, 1>(box, geometry::get<1, 1>(box) + value); + } + inline void calculate_robust_envelope(piece& pc) { + if (pc.offsetted_count == 0) + { + return; + } + geometry::detail::envelope::envelope_range::apply(pc.robust_ring, pc.robust_envelope); + + geometry::assign_inverse(pc.robust_offsetted_envelope); + for (int i = 0; i < pc.offsetted_count; i++) + { + geometry::expand(pc.robust_offsetted_envelope, pc.robust_ring[i]); + } + + // Take roundings into account, enlarge boxes with 1 integer + enlarge_box(pc.robust_envelope, 1); + enlarge_box(pc.robust_offsetted_envelope, 1); + } + + inline void sectionalize(piece& pc) + { + + buffered_ring<Ring> const& ring = offsetted_rings.back(); + + typedef geometry::detail::sectionalize::sectionalize_part + < + point_type, + boost::mpl::vector_c<std::size_t, 0, 1> // x,y dimension + > sectionalizer; + + // Create a ring-identifier. The source-index is the piece index + // The multi_index is as in this collection (the ring), but not used here + // The ring_index is not used + ring_identifier ring_id(pc.index, pc.first_seg_id.multi_index, -1); + + sectionalizer::apply(monotonic_sections, + boost::begin(ring) + pc.first_seg_id.segment_index, + boost::begin(ring) + pc.last_segment_index, + m_robust_policy, + ring_id, 10); } inline void finish_piece(piece& pc) { init_rescale_piece(pc, 0u); calculate_robust_envelope(pc); + sectionalize(pc); } inline void finish_piece(piece& pc, @@ -692,10 +965,16 @@ struct buffered_piece_collection const point_type& point3) { init_rescale_piece(pc, 3u); + if (pc.offsetted_count == 0) + { + return; + } + add_helper_point(pc, point1); robust_point_type mid_point = add_helper_point(pc, point2); add_helper_point(pc, point3); calculate_robust_envelope(pc); + sectionalize(pc); current_robust_ring.push_back(mid_point); } @@ -711,6 +990,7 @@ struct buffered_piece_collection robust_point_type mid_point2 = add_helper_point(pc, point2); robust_point_type mid_point1 = add_helper_point(pc, point3); add_helper_point(pc, point4); + sectionalize(pc); calculate_robust_envelope(pc); // Add mid-points in other order to current helper_ring @@ -730,10 +1010,7 @@ struct buffered_piece_collection template <typename Range> inline void add_range_to_piece(piece& pc, Range const& range, bool add_front) { - if (boost::size(range) == 0u) - { - return; - } + BOOST_ASSERT(boost::size(range) != 0u); typename Range::const_iterator it = boost::begin(range); @@ -753,10 +1030,15 @@ struct buffered_piece_collection template <typename Range> - inline void add_piece(strategy::buffer::piece_type type, Range const& range, bool decrease_segment_index_by_one) + inline void add_piece(strategy::buffer::piece_type type, Range const& range, + bool decrease_segment_index_by_one) { piece& pc = create_piece(type, decrease_segment_index_by_one); - add_range_to_piece(pc, range, offsetted_rings.back().empty()); + + if (boost::size(range) > 0u) + { + add_range_to_piece(pc, range, offsetted_rings.back().empty()); + } finish_piece(pc); } @@ -772,13 +1054,14 @@ struct buffered_piece_collection } template <typename Range> - inline void add_piece(strategy::buffer::piece_type type, point_type const& p, Range const& range) + inline void add_piece(strategy::buffer::piece_type type, + point_type const& p, Range const& range) { piece& pc = create_piece(type, true); - add_range_to_piece(pc, range, offsetted_rings.back().empty()); - if (boost::size(range) > 0) + if (boost::size(range) > 0u) { + add_range_to_piece(pc, range, offsetted_rings.back().empty()); finish_piece(pc, range.back(), p, range.front()); } else @@ -788,8 +1071,11 @@ struct buffered_piece_collection } template <typename EndcapStrategy, typename Range> - inline void add_endcap(EndcapStrategy const& strategy, Range const& range, point_type const& end_point) + inline void add_endcap(EndcapStrategy const& strategy, Range const& range, + point_type const& end_point) { + boost::ignore_unused(strategy); + if (range.empty()) { return; @@ -842,6 +1128,80 @@ struct buffered_piece_collection } } + inline bool point_coveredby_original(point_type const& point) + { + robust_point_type any_point; + geometry::recalculate(any_point, point, m_robust_policy); + + int count_in_original = 0; + + // Check of the robust point of this outputted ring is in + // any of the robust original rings + // This can go quadratic if the input has many rings, and there + // are many untouched deflated rings around + for (typename std::vector<robust_original>::const_iterator it + = robust_originals.begin(); + it != robust_originals.end(); + ++it) + { + robust_original const& original = *it; + if (detail::disjoint::disjoint_point_box(any_point, + original.m_box)) + { + continue; + } + + int const geometry_code + = detail::within::point_in_geometry(any_point, + original.m_ring); + + if (geometry_code == -1) + { + // Outside, continue + continue; + } + + // Apply for possibly nested interior rings + if (original.m_is_interior) + { + count_in_original--; + } + else if (original.m_has_interiors) + { + count_in_original++; + } + else + { + // Exterior ring without interior rings + return true; + } + } + return count_in_original > 0; + } + + // For a deflate, all rings around inner rings which are untouched + // (no intersections/turns) and which are OUTSIDE the original should + // be discarded + inline void discard_nonintersecting_deflated_rings() + { + for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it + = boost::begin(offsetted_rings); + it != boost::end(offsetted_rings); + ++it) + { + buffered_ring<Ring>& ring = *it; + if (! ring.has_intersections() + && boost::size(ring) > 0u + && geometry::area(ring) < 0) + { + if (! point_coveredby_original(geometry::range::front(ring))) + { + ring.is_untouched_outside_original = true; + } + } + } + } + inline void block_turns() { // To fix left-turn issues like #rt_u13 @@ -876,7 +1236,8 @@ struct buffered_piece_collection typedef detail::overlay::traverse < false, false, - buffered_ring_collection<buffered_ring<Ring> >, buffered_ring_collection<buffered_ring<Ring > >, + buffered_ring_collection<buffered_ring<Ring> >, + buffered_ring_collection<buffered_ring<Ring > >, backtrack_for_buffer > traverser; @@ -914,16 +1275,20 @@ struct buffered_piece_collection std::map<ring_identifier, properties> selected; - // Select all rings which do not have any self-intersection (other ones should be traversed) + // Select all rings which do not have any self-intersection + // Inner rings, for deflate, which do not have intersections, and + // which are outside originals, are skipped + // (other ones should be traversed) int index = 0; for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings); it != boost::end(offsetted_rings); ++it, ++index) { - if (! it->has_intersections()) + if (! it->has_intersections() + && ! it->is_untouched_outside_original) { ring_identifier id(0, index, -1); - selected[id] = properties(*it, true); + selected[id] = properties(*it); } } @@ -935,7 +1300,7 @@ struct buffered_piece_collection ++it, ++index) { ring_identifier id(2, index, -1); - selected[id] = properties(*it, true); + selected[id] = properties(*it); } detail::overlay::assign_parents(offsetted_rings, traversed_rings, selected, true); |