// Boost.Geometry (aka GGL, Generic Geometry Library) // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. // This file was modified by Oracle on 2016-2020. // Modifications copyright (c) 2016-2020 Oracle and/or its affiliates. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle // 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_BUFFER_BUFFERED_PIECE_COLLECTION_HPP #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace boost { namespace geometry { #ifndef DOXYGEN_NO_DETAIL namespace detail { namespace buffer { /* * Terminology * * Suppose we make a buffer (using blocked corners) of this rectangle: * * +-------+ * | | * | rect | * | | * +-------+ * * For the sides we get these four buffered side-pieces (marked with s) * and four buffered corner pieces (marked with c) * * c---+---s---+---c * | | piece | | <- see below for details of the middle top-side-piece * +---+-------+---+ * | | | | * s | rect | s <- two side pieces left/right of rect * | | | | * +---+-------+---+ * | | piece | | <- one side-piece below, and two corner pieces * c---+---s---+---c * * The outer part of the picture above, using all pieces, * 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_polygons (marked with r below) * The remaining piece-segments are helper-segments (marked with h) * * ooooooooooooooooo * o h h o * ohhhrrrrrrrrrhhho * o r r o * o r r o * o r r o * ohhhrrrrrrrrrhhho * o h h o * ooooooooooooooooo * */ template < typename Ring, typename IntersectionStrategy, typename DistanceStrategy, typename RobustPolicy > struct buffered_piece_collection { typedef typename geometry::point_type::type point_type; typedef typename geometry::coordinate_type::type coordinate_type; // Ring/polygon type, always clockwise typedef geometry::model::ring clockwise_ring_type; typedef geometry::model::box box_type; typedef typename IntersectionStrategy::side_strategy_type side_strategy_type; typedef typename IntersectionStrategy::envelope_strategy_type envelope_strategy_type; typedef typename IntersectionStrategy::expand_strategy_type expand_strategy_type; typedef typename IntersectionStrategy::template area_strategy < point_type >::type area_strategy_type; typedef typename area_strategy_type::template result_type < point_type >::type area_result_type; typedef typename IntersectionStrategy::template point_in_geometry_strategy < point_type, clockwise_ring_type >::type point_in_geometry_strategy_type; typedef buffer_turn_info < point_type, typename segment_ratio_type::type > buffer_turn_info_type; typedef buffer_turn_operation < point_type, typename segment_ratio_type::type > buffer_turn_operation_type; typedef std::vector turn_vector_type; typedef piece_border piece_border_type; struct piece { strategy::buffer::piece_type type; signed_size_type index; signed_size_type left_index; // points to previous piece of same ring signed_size_type right_index; // points to next piece of same ring // The next two members (1, 2) form together a complete clockwise ring // for each piece (with one dupped point) // The complete clockwise ring is also included as a robust ring (3) // 1: half, part of offsetted_rings // Segment identifier of this piece, including its start index segment_identifier first_seg_id; // One-beyond index of this piece, to iterate over a ring // from: ring.begin() + pc.first_seg_id.segment_index; // to (not including): ring.begin() + pc.beyond_last_segment_index; // Its ring_id etc are shared with first_seg_id signed_size_type beyond_last_segment_index; // part in offsetted ring which is part of offsetted ring signed_size_type offsetted_count; bool is_flat_start; bool is_flat_end; bool is_deflated; // Ring (parts) of this piece, always clockwise piece_border_type m_piece_border; point_type m_label_point; // For a point buffer point_type m_center; piece() : type(strategy::buffer::piece_type_unknown) , index(-1) , left_index(-1) , right_index(-1) , beyond_last_segment_index(-1) , offsetted_count(-1) , is_flat_start(false) , is_flat_end(false) , is_deflated(false) { } }; struct original_ring { typedef geometry::sections sections_type; // Creates an empty instance inline original_ring() : m_is_interior(false) , m_has_interiors(false) {} inline original_ring(clockwise_ring_type const& ring, bool is_interior, bool has_interiors, envelope_strategy_type const& envelope_strategy, expand_strategy_type const& expand_strategy) : m_ring(ring) , m_is_interior(is_interior) , m_has_interiors(has_interiors) { geometry::envelope(m_ring, m_box, envelope_strategy); // create monotonic sections in x-dimension // The dimension is critical because the direction is later used // in the optimization for within checks using winding strategy // and this strategy is scanning in x direction. typedef std::integer_sequence dimensions; geometry::sectionalize(m_ring, detail::no_rescale_policy(), m_sections, envelope_strategy, expand_strategy); } clockwise_ring_type m_ring; box_type m_box; sections_type m_sections; bool m_is_interior; bool m_has_interiors; }; typedef std::vector piece_vector_type; piece_vector_type m_pieces; turn_vector_type m_turns; signed_size_type m_first_piece_index; bool m_deflate; bool m_has_deflated; // Offsetted rings, and representations of original ring(s) // both indexed by multi_index buffered_ring_collection > offsetted_rings; std::vector original_rings; std::vector m_linear_end_points; buffered_ring_collection traversed_rings; segment_identifier current_segment_id; // Monotonic sections (used for offsetted rings around points) // are still using a robust type, to be comparable with turn calculations, // which is using rescaling. typedef geometry::model::box < typename geometry::robust_point_type::type > robust_box_type; typedef geometry::sections robust_sections_type; robust_sections_type monotonic_sections; // Define the clusters, mapping cluster_id -> turns typedef std::map < signed_size_type, detail::overlay::cluster_info > cluster_type; cluster_type m_clusters; IntersectionStrategy m_intersection_strategy; DistanceStrategy m_distance_strategy; side_strategy_type m_side_strategy; area_strategy_type m_area_strategy; envelope_strategy_type m_envelope_strategy; expand_strategy_type m_expand_strategy; point_in_geometry_strategy_type m_point_in_geometry_strategy; RobustPolicy const& m_robust_policy; buffered_piece_collection(IntersectionStrategy const& intersection_strategy, DistanceStrategy const& distance_strategy, RobustPolicy const& robust_policy) : m_first_piece_index(-1) , m_deflate(false) , m_has_deflated(false) , m_intersection_strategy(intersection_strategy) , m_distance_strategy(distance_strategy) , m_side_strategy(intersection_strategy.get_side_strategy()) , m_area_strategy(intersection_strategy .template get_area_strategy()) , m_envelope_strategy(intersection_strategy.get_envelope_strategy()) , m_expand_strategy(intersection_strategy.get_expand_strategy()) , m_point_in_geometry_strategy(intersection_strategy .template get_point_in_geometry_strategy()) , m_robust_policy(robust_policy) {} inline bool is_following(buffer_turn_info_type const& turn, buffer_turn_operation_type const& op) { return turn.operations[0].seg_id.segment_index == op.seg_id.segment_index || turn.operations[1].seg_id.segment_index == op.seg_id.segment_index; } // Verify if turns which are classified as OK (outside or on border of // offsetted ring) do not traverse through other turns which are classified // as WITHIN (inside a piece). This can happen if turns are nearly colocated // and due to floating point precision just classified as within, while // they should not be within. // In those cases the turns are fine to travel through (and should), // but they are not made startable. template inline void pretraverse(Vector const& indexed_operations) { // Verify if the turns which are OK don't skip segments typedef typename boost::range_value::type indexed_type; buffer_turn_operation_type last_traversable_operation; buffer_turn_info_type last_traversable_turn; bool first = true; for (std::size_t i = 0; i < indexed_operations.size(); i++) { indexed_type const & itop = indexed_operations[i]; buffer_turn_info_type const& turn = m_turns[itop.turn_index]; if (turn.is_turn_traversable && ! first) { // Check previous and next turns. The first is handled BOOST_GEOMETRY_ASSERT(i > 0); indexed_type const& previous_itop = indexed_operations[i - 1]; std::size_t const next_index = i + 1 < indexed_operations.size() ? i + 1 : 0; indexed_type const& next_itop = indexed_operations[next_index]; buffer_turn_info_type& previous_turn = m_turns[previous_itop.turn_index]; buffer_turn_info_type& next_turn = m_turns[next_itop.turn_index]; if (previous_turn.close_to_offset && is_following(previous_turn, last_traversable_operation)) { previous_turn.is_turn_traversable = true; } else if (next_turn.close_to_offset && is_following(next_turn, last_traversable_operation)) { next_turn.is_turn_traversable = true; } } if (turn.is_turn_traversable) { first = false; last_traversable_operation = *itop.subject; last_traversable_turn = turn; } } } inline void check_linear_endpoints(buffer_turn_info_type& turn) const { // TODO this is quadratic. But the #endpoints, expected, is low, // and only applicable for linear features // (in a multi linestring with many short lines, the #endpoints can be // much higher) for (typename boost::range_iterator const>::type it = boost::begin(m_linear_end_points); it != boost::end(m_linear_end_points); ++it) { if (detail::equals::equals_point_point(turn.point, *it, m_intersection_strategy.get_equals_point_point_strategy())) { turn.is_linear_end_point = true; } } } inline void verify_turns() { typedef detail::overlay::indexed_turn_operation < buffer_turn_operation_type > indexed_turn_operation; typedef std::map < ring_identifier, std::vector > mapped_vector_type; mapped_vector_type mapped_vector; detail::overlay::create_map(m_turns, mapped_vector, enriched_map_buffer_include_policy()); // Sort turns over offsetted ring(s) for (typename mapped_vector_type::iterator mit = mapped_vector.begin(); mit != mapped_vector.end(); ++mit) { std::sort(mit->second.begin(), mit->second.end(), buffer_less()); } for (typename mapped_vector_type::iterator mit = mapped_vector.begin(); mit != mapped_vector.end(); ++mit) { pretraverse(mit->second); } } inline void deflate_check_turns() { if (! m_has_deflated) { return; } // Deflated rings may not travel to themselves, there should at least // be three turns (which cannot be checked here - TODO: add to traverse) for (typename boost::range_iterator::type it = boost::begin(m_turns); it != boost::end(m_turns); ++it) { buffer_turn_info_type& turn = *it; if (! turn.is_turn_traversable) { continue; } for (int i = 0; i < 2; i++) { buffer_turn_operation_type& op = turn.operations[i]; if (op.enriched.get_next_turn_index() == static_cast(turn.turn_index) && m_pieces[op.seg_id.piece_index].is_deflated) { // Keep traversable, but don't start here op.enriched.startable = false; } } } } // Check if a turn is inside any of the originals inline void check_turn_in_original() { typedef turn_in_original_overlaps_box < typename IntersectionStrategy::disjoint_point_box_strategy_type > turn_in_original_overlaps_box_type; typedef original_overlaps_box < typename IntersectionStrategy::disjoint_box_box_strategy_type > original_overlaps_box_type; turn_in_original_visitor < turn_vector_type, point_in_geometry_strategy_type > visitor(m_turns, m_point_in_geometry_strategy); geometry::partition < box_type, include_turn_policy, detail::partition::include_all_policy >::apply(m_turns, original_rings, visitor, turn_get_box(), turn_in_original_overlaps_box_type(), original_get_box(), original_overlaps_box_type()); bool const deflate = m_distance_strategy.negative(); for (typename boost::range_iterator::type it = boost::begin(m_turns); it != boost::end(m_turns); ++it) { buffer_turn_info_type& turn = *it; if (turn.is_turn_traversable) { if (deflate && turn.count_in_original <= 0) { // For deflate/negative buffers: // it is not in the original, so don't use it turn.is_turn_traversable = false; } else if (! deflate && turn.count_in_original > 0) { // For inflate: it is in original, so don't use it turn.is_turn_traversable = false; } } } } inline void update_turn_administration() { std::size_t index = 0; for (typename boost::range_iterator::type it = boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index) { buffer_turn_info_type& turn = *it; // Update member used turn.turn_index = index; // Verify if a turn is a linear endpoint if (! turn.is_linear_end_point) { check_linear_endpoints(turn); } } } // Calculate properties of piece borders which are not influenced // by turns themselves: // - envelopes (essential for partitioning during calc turns) // - convexity // - monotonicity // - min/max radius of point buffers // - (if pieces are reversed) inline void update_piece_administration() { for (typename piece_vector_type::iterator it = boost::begin(m_pieces); it != boost::end(m_pieces); ++it) { piece& pc = *it; piece_border_type& border = pc.m_piece_border; buffered_ring const& ring = offsetted_rings[pc.first_seg_id.multi_index]; if (pc.offsetted_count > 0) { if (pc.type != strategy::buffer::buffered_concave) { border.set_offsetted(ring, pc.first_seg_id.segment_index, pc.beyond_last_segment_index); } // Calculate envelopes for piece borders border.get_properties_of_border(pc.type == geometry::strategy::buffer::buffered_point, pc.m_center); if (! pc.is_flat_end && ! pc.is_flat_start) { border.get_properties_of_offsetted_ring_part(m_side_strategy); } } } } inline void get_turns() { update_piece_administration(); { // Calculate the turns piece_turn_visitor < piece_vector_type, buffered_ring_collection >, turn_vector_type, IntersectionStrategy, RobustPolicy > visitor(m_pieces, offsetted_rings, m_turns, m_intersection_strategy, m_robust_policy); typedef detail::section::get_section_box < typename IntersectionStrategy::expand_box_strategy_type > get_section_box_type; typedef detail::section::overlaps_section_box < typename IntersectionStrategy::disjoint_box_box_strategy_type > overlaps_section_box_type; detail::sectionalize::enlarge_sections(monotonic_sections, m_envelope_strategy); geometry::partition < robust_box_type >::apply(monotonic_sections, visitor, get_section_box_type(), overlaps_section_box_type()); } update_turn_administration(); { // Check if turns are inside pieces turn_in_piece_visitor < typename geometry::cs_tag::type, turn_vector_type, piece_vector_type, DistanceStrategy > visitor(m_turns, m_pieces, m_distance_strategy); typedef turn_overlaps_box < typename IntersectionStrategy::disjoint_point_box_strategy_type > turn_overlaps_box_type; typedef piece_overlaps_box < typename IntersectionStrategy::disjoint_box_box_strategy_type > piece_overlaps_box_type; geometry::partition < box_type >::apply(m_turns, m_pieces, visitor, turn_get_box(), turn_overlaps_box_type(), piece_get_box(), piece_overlaps_box_type()); } } inline void start_new_ring(bool deflate) { std::size_t const n = offsetted_rings.size(); current_segment_id.source_index = 0; current_segment_id.multi_index = static_cast(n); current_segment_id.ring_index = -1; current_segment_id.segment_index = 0; offsetted_rings.resize(n + 1); original_rings.resize(n + 1); m_first_piece_index = static_cast(boost::size(m_pieces)); m_deflate = deflate; if (deflate) { // Pieces contain either deflated exterior rings, or inflated // interior rings which are effectively deflated too m_has_deflated = true; } } inline void abort_ring() { // Remove all created pieces for this ring, sections, last offsetted while (! m_pieces.empty() && m_pieces.back().first_seg_id.multi_index == current_segment_id.multi_index) { m_pieces.pop_back(); } offsetted_rings.pop_back(); original_rings.pop_back(); m_first_piece_index = -1; } inline void update_last_point(point_type const& p, buffered_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_GEOMETRY_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 set_piece_center(point_type const& center) { BOOST_GEOMETRY_ASSERT(! m_pieces.empty()); m_pieces.back().m_center = center; } inline bool finish_ring(strategy::buffer::result_code code) { if (code == strategy::buffer::result_error_numerical) { abort_ring(); return false; } if (m_first_piece_index == -1) { return false; } // Casted version std::size_t const first_piece_index = static_cast(m_first_piece_index); signed_size_type const last_piece_index = static_cast(boost::size(m_pieces)) - 1; if (first_piece_index < boost::size(m_pieces)) { // If pieces were added, // reassign left-of-first and right-of-last geometry::range::at(m_pieces, first_piece_index).left_index = last_piece_index; geometry::range::back(m_pieces).right_index = m_first_piece_index; } buffered_ring& added = offsetted_rings.back(); if (! boost::empty(added)) { // Make sure the closing point is identical (they are calculated // separately by different pieces) range::back(added) = range::front(added); } for (std::size_t i = first_piece_index; i < boost::size(m_pieces); i++) { sectionalize(m_pieces[i], added); } m_first_piece_index = -1; return true; } template inline void finish_ring(strategy::buffer::result_code code, InputRing const& input_ring, bool is_interior, bool has_interiors) { if (! finish_ring(code)) { return; } if (! input_ring.empty()) { // Assign the ring to the original_ring collection // For rescaling, it is recalculated. Without rescaling, it // is just assigning (note that this Ring type is the // GeometryOut type, which might differ from the input ring type) clockwise_ring_type clockwise_ring; typedef detail::normalized_view view_type; view_type const view(input_ring); for (typename boost::range_iterator::type it = boost::begin(view); it != boost::end(view); ++it) { clockwise_ring.push_back(*it); } original_rings.back() = original_ring(clockwise_ring, is_interior, has_interiors, m_envelope_strategy, m_expand_strategy); } } inline void set_current_ring_concave() { BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0); offsetted_rings.back().has_concave = true; } inline signed_size_type add_point(point_type const& p) { BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0); buffered_ring& current_ring = offsetted_rings.back(); update_last_point(p, current_ring); current_segment_id.segment_index++; current_ring.push_back(p); return static_cast(current_ring.size()); } //------------------------------------------------------------------------- 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 = static_cast(boost::size(m_pieces)); pc.is_deflated = m_deflate; current_segment_id.piece_index = pc.index; pc.first_seg_id = current_segment_id; // Assign left/right (for first/last piece per ring they will be re-assigned later) pc.left_index = pc.index - 1; pc.right_index = pc.index + 1; 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.beyond_last_segment_index = pc.first_seg_id.segment_index; m_pieces.push_back(pc); return m_pieces.back(); } inline void init_rescale_piece(piece& pc) { if (pc.first_seg_id.segment_index < 0) { // This indicates an error situation: an earlier piece was empty // It currently does not happen pc.offsetted_count = 0; return; } BOOST_GEOMETRY_ASSERT(pc.first_seg_id.multi_index >= 0); BOOST_GEOMETRY_ASSERT(pc.beyond_last_segment_index >= 0); pc.offsetted_count = pc.beyond_last_segment_index - pc.first_seg_id.segment_index; BOOST_GEOMETRY_ASSERT(pc.offsetted_count >= 0); } inline void add_piece_point(piece& pc, const point_type& point, bool add_to_original) { if (add_to_original && pc.type != strategy::buffer::buffered_concave) { pc.m_piece_border.add_original_point(point); } else { pc.m_label_point = point; } } inline void sectionalize(piece const& pc, buffered_ring const& ring) { typedef geometry::detail::sectionalize::sectionalize_part < point_type, std::integer_sequence // 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 const 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.beyond_last_segment_index, m_robust_policy, ring_id, 10); } inline void finish_piece(piece& pc) { init_rescale_piece(pc); } inline void finish_piece(piece& pc, point_type const& point1, point_type const& point2, point_type const& point3) { init_rescale_piece(pc); if (pc.offsetted_count == 0) { return; } add_piece_point(pc, point1, false); add_piece_point(pc, point2, true); add_piece_point(pc, point3, false); } inline void finish_piece(piece& pc, point_type const& point1, point_type const& point2, point_type const& point3, point_type const& point4) { init_rescale_piece(pc); // Add the four points. Note that points 2 and 3 are the originals, // and that they are already passed in reverse order // (because the offsetted ring is in clockwise order) add_piece_point(pc, point1, false); add_piece_point(pc, point2, true); add_piece_point(pc, point3, true); add_piece_point(pc, point4, false); } template inline void add_range_to_piece(piece& pc, Range const& range, bool add_front) { BOOST_GEOMETRY_ASSERT(boost::size(range) != 0u); typename Range::const_iterator it = boost::begin(range); // If it follows a non-join (so basically the same piece-type) point b1 should be added. // There should be two intersections later and it should be discarded. // But for now we need it to calculate intersections if (add_front) { add_point(*it); } for (++it; it != boost::end(range); ++it) { pc.beyond_last_segment_index = add_point(*it); } } inline void add_piece(strategy::buffer::piece_type type, point_type const& p, point_type const& b1, point_type const& b2) { piece& pc = create_piece(type, false); add_point(b1); pc.beyond_last_segment_index = add_point(b2); finish_piece(pc, b2, p, b1); } template 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); if (boost::size(range) > 0u) { add_range_to_piece(pc, range, offsetted_rings.back().empty()); } finish_piece(pc); } template inline void add_piece(strategy::buffer::piece_type type, point_type const& p, Range const& range) { piece& pc = create_piece(type, true); if (boost::size(range) > 0u) { add_range_to_piece(pc, range, offsetted_rings.back().empty()); finish_piece(pc, range.back(), p, range.front()); } else { finish_piece(pc); } } template inline void add_side_piece(point_type const& original_point1, point_type const& original_point2, Range const& range, bool first) { BOOST_GEOMETRY_ASSERT(boost::size(range) >= 2u); piece& pc = create_piece(strategy::buffer::buffered_segment, ! first); add_range_to_piece(pc, range, first); // Add the four points of the side, starting with the last point of the // range, and reversing the order of the originals to keep it clockwise finish_piece(pc, range.back(), original_point2, original_point1, range.front()); } template inline void add_endcap(EndcapStrategy const& strategy, Range const& range, point_type const& end_point) { boost::ignore_unused(strategy); if (range.empty()) { return; } strategy::buffer::piece_type pt = strategy.get_piece_type(); if (pt == strategy::buffer::buffered_flat_end) { // It is flat, should just be added, without helper segments add_piece(pt, range, true); } else { // Normal case, it has an "inside", helper segments should be added add_piece(pt, end_point, range); } } inline void mark_flat_start(point_type const& point) { if (! m_pieces.empty()) { piece& back = m_pieces.back(); back.is_flat_start = true; // This happens to linear buffers, and it will be the very // first or last point. If that coincides with a turn, // and the turn was marked as ON_BORDER // the turn should NOT be within (even though it can be marked // as such) m_linear_end_points.push_back(point); } } inline void mark_flat_end(point_type const& point) { if (! m_pieces.empty()) { piece& back = m_pieces.back(); back.is_flat_end = true; m_linear_end_points.push_back(point); } } //------------------------------------------------------------------------- inline void enrich() { enrich_intersection_points(m_turns, m_clusters, offsetted_rings, offsetted_rings, m_robust_policy, m_intersection_strategy); } // Discards all rings which do have not-OK intersection points only. // Those can never be traversed and should not be part of the output. inline void discard_rings() { for (typename boost::range_iterator::type it = boost::begin(m_turns); it != boost::end(m_turns); ++it) { if (it->is_turn_traversable) { offsetted_rings[it->operations[0].seg_id.multi_index].has_accepted_intersections = true; offsetted_rings[it->operations[1].seg_id.multi_index].has_accepted_intersections = true; } else { offsetted_rings[it->operations[0].seg_id.multi_index].has_discarded_intersections = true; offsetted_rings[it->operations[1].seg_id.multi_index].has_discarded_intersections = true; } } } inline bool point_coveredby_original(point_type const& point) { typedef typename IntersectionStrategy::disjoint_point_box_strategy_type d_pb_strategy_type; signed_size_type 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::const_iterator it = original_rings.begin(); it != original_rings.end(); ++it) { original_ring const& original = *it; if (original.m_ring.empty()) { continue; } if (detail::disjoint::disjoint_point_box(point, original.m_box, d_pb_strategy_type())) { continue; } int const geometry_code = detail::within::point_in_geometry(point, original.m_ring, m_point_in_geometry_strategy); 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 >::iterator it = boost::begin(offsetted_rings); it != boost::end(offsetted_rings); ++it) { buffered_ring& ring = *it; if (! ring.has_intersections() && boost::size(ring) > 0u && geometry::area(ring, m_area_strategy) < 0) { if (! point_coveredby_original(geometry::range::front(ring))) { ring.is_untouched_outside_original = true; } } } } inline void block_turns() { for (typename boost::range_iterator::type it = boost::begin(m_turns); it != boost::end(m_turns); ++it) { buffer_turn_info_type& turn = *it; if (! turn.is_turn_traversable) { // Discard this turn (don't set it to blocked to avoid colocated // clusters being discarded afterwards turn.discarded = true; } } } inline void traverse() { typedef detail::overlay::traverse < false, false, buffered_ring_collection >, buffered_ring_collection >, overlay_buffer, backtrack_for_buffer > traverser; std::map turn_info_per_ring; traversed_rings.clear(); buffer_overlay_visitor visitor; traverser::apply(offsetted_rings, offsetted_rings, m_intersection_strategy, m_robust_policy, m_turns, traversed_rings, turn_info_per_ring, m_clusters, visitor); } inline void reverse() { for(typename buffered_ring_collection >::iterator it = boost::begin(offsetted_rings); it != boost::end(offsetted_rings); ++it) { if (! it->has_intersections()) { std::reverse(it->begin(), it->end()); } } for (typename boost::range_iterator >::type it = boost::begin(traversed_rings); it != boost::end(traversed_rings); ++it) { std::reverse(it->begin(), it->end()); } } template inline OutputIterator assign(OutputIterator out) const { typedef detail::overlay::ring_properties properties; std::map selected; // 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) signed_size_type index = 0; for(typename buffered_ring_collection >::const_iterator it = boost::begin(offsetted_rings); it != boost::end(offsetted_rings); ++it, ++index) { if (! it->has_intersections() && ! it->is_untouched_outside_original) { properties p = properties(*it, m_area_strategy); if (p.valid) { ring_identifier id(0, index, -1); selected[id] = p; } } } // Select all created rings index = 0; for (typename boost::range_iterator const>::type it = boost::begin(traversed_rings); it != boost::end(traversed_rings); ++it, ++index) { properties p = properties(*it, m_area_strategy); if (p.valid) { ring_identifier id(2, index, -1); selected[id] = p; } } detail::overlay::assign_parents(offsetted_rings, traversed_rings, selected, m_intersection_strategy); return detail::overlay::add_rings(selected, offsetted_rings, traversed_rings, out, m_area_strategy); } }; }} // namespace detail::buffer #endif // DOXYGEN_NO_DETAIL }} // namespace boost::geometry #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP