detail/buffer/buffered_piece_collection.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2017-2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2016-2022.
0007 // Modifications copyright (c) 2016-2022 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
0016
0017 #include <algorithm>
0018 #include <cstddef>
0019 #include <set>
0020
0021 #include <boost/core/ignore_unused.hpp>
0022 #include <boost/range/begin.hpp>
0023 #include <boost/range/empty.hpp>
0024 #include <boost/range/end.hpp>
0025 #include <boost/range/size.hpp>
0026 #include <boost/range/value_type.hpp>
0027
0028 #include <boost/geometry/core/assert.hpp>
0029 #include <boost/geometry/core/coordinate_type.hpp>
0030 #include <boost/geometry/core/point_type.hpp>
0031
0032 #include <boost/geometry/algorithms/covered_by.hpp>
0033 #include <boost/geometry/algorithms/envelope.hpp>
0034
0035 #include <boost/geometry/strategies/buffer.hpp>
0036
0037 #include <boost/geometry/geometries/ring.hpp>
0038
0039 #include <boost/geometry/algorithms/detail/buffer/buffered_ring.hpp>
0040 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
0041 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
0042 #include <boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp>
0043 #include <boost/geometry/algorithms/detail/buffer/piece_border.hpp>
0044 #include <boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp>
0045 #include <boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp>
0046
0047 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
0048 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
0049 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
0050 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
0051 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
0052 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
0053 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
0054 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
0055 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
0056 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
0057 #include <boost/geometry/algorithms/detail/partition.hpp>
0058 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
0059 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
0060
0061 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
0062 #include <boost/geometry/util/for_each_with_index.hpp>
0063 #include <boost/geometry/util/range.hpp>
0064
0065
0066 namespace boost { namespace geometry
0067 {
0068
0069
0070 #ifndef DOXYGEN_NO_DETAIL
0071 namespace detail { namespace buffer
0072 {
0073
0074
0075 /*
0076  *  Terminology
0077  *
0078  *  Suppose we make a buffer (using blocked corners) of this rectangle:
0079  *
0080  *         +-------+
0081  *         |       |
0082  *         |  rect |
0083  *         |       |
0084  *         +-------+
0085  *
0086  * For the sides we get these four buffered side-pieces (marked with s)
0087  * and four buffered corner pieces (marked with c)
0088  *
0089  *     c---+---s---+---c
0090  *     |   | piece |   |     <- see below for details of the middle top-side-piece
0091  *     +---+-------+---+
0092  *     |   |       |   |
0093  *     s   |  rect |   s     <- two side pieces left/right of rect
0094  *     |   |       |   |
0095  *     +---+-------+---+
0096  *     |   | piece |   |     <- one side-piece below, and two corner pieces
0097  *     c---+---s---+---c
0098  *
0099  *  The outer part of the picture above, using all pieces,
0100  *    form together the offsetted ring (marked with o below)
0101  *  The 8 pieces are part of the piece collection and use for inside-checks
0102  *  The inner parts form (using 1 or 2 points per piece, often co-located)
0103  *    form together the robust_polygons (marked with r below)
0104  *  The remaining piece-segments are helper-segments (marked with h)
0105  *
0106  *     ooooooooooooooooo
0107  *     o   h       h   o
0108  *     ohhhrrrrrrrrrhhho
0109  *     o   r       r   o
0110  *     o   r       r   o
0111  *     o   r       r   o
0112  *     ohhhrrrrrrrrrhhho
0113  *     o   h       h   o
0114  *     ooooooooooooooooo
0115  *
0116  */
0117
0118 template
0119 <
0120     typename Ring,
0121     typename Strategy,
0122     typename DistanceStrategy,
0123     typename RobustPolicy
0124 >
0125 struct buffered_piece_collection
0126 {
0127     typedef typename geometry::point_type<Ring>::type point_type;
0128     typedef typename geometry::coordinate_type<Ring>::type coordinate_type;
0129
0130     // Ring/polygon type, always clockwise
0131     typedef geometry::model::ring<point_type> clockwise_ring_type;
0132
0133     typedef geometry::model::box<point_type> box_type;
0134
0135     typedef buffer_turn_info
0136     <
0137         point_type,
0138         typename segment_ratio_type<point_type, RobustPolicy>::type
0139     > buffer_turn_info_type;
0140
0141     typedef buffer_turn_operation
0142     <
0143         point_type,
0144         typename segment_ratio_type<point_type, RobustPolicy>::type
0145     > buffer_turn_operation_type;
0146
0147     typedef std::vector<buffer_turn_info_type> turn_vector_type;
0148
0149     typedef piece_border<Ring, point_type> piece_border_type;
0150
0151     struct piece
0152     {
0153         strategy::buffer::piece_type type;
0154         signed_size_type index;
0155
0156         signed_size_type left_index; // points to previous piece of same ring
0157         signed_size_type right_index; // points to next piece of same ring
0158
0159         // The next two members (1, 2) form together a complete clockwise ring
0160         // for each piece (with one dupped point)
0161         // The complete clockwise ring is also included as a robust ring (3)
0162
0163         // 1: half, part of offsetted_rings
0164
0165         // Segment identifier of this piece, including its start index
0166         segment_identifier first_seg_id;
0167
0168         // One-beyond index of this piece, to iterate over a ring
0169         // from:                ring.begin() + pc.first_seg_id.segment_index;
0170         // to (not including):  ring.begin() + pc.beyond_last_segment_index;
0171         // Its ring_id etc are shared with first_seg_id
0172         signed_size_type beyond_last_segment_index;
0173
0174         // part in offsetted ring which is part of offsetted ring
0175         signed_size_type offsetted_count;
0176
0177         bool is_flat_start;
0178         bool is_flat_end;
0179
0180         bool is_deflated;
0181
0182         // Ring (parts) of this piece, always clockwise
0183         piece_border_type m_piece_border;
0184
0185         point_type m_label_point;
0186
0187         // For a point buffer
0188         point_type m_center;
0189
0190         piece()
0191             : type(strategy::buffer::piece_type_unknown)
0192             , index(-1)
0193             , left_index(-1)
0194             , right_index(-1)
0195             , beyond_last_segment_index(-1)
0196             , offsetted_count(-1)
0197             , is_flat_start(false)
0198             , is_flat_end(false)
0199             , is_deflated(false)
0200         {
0201         }
0202     };
0203
0204     struct original_ring
0205     {
0206         typedef geometry::sections<box_type, 1> sections_type;
0207
0208         // Creates an empty instance
0209         inline original_ring()
0210             : m_is_interior(false)
0211             , m_has_interiors(false)
0212         {}
0213
0214         inline original_ring(clockwise_ring_type const& ring,
0215                              bool is_interior, bool has_interiors,
0216                              Strategy const& strategy)
0217             : m_ring(ring)
0218             , m_is_interior(is_interior)
0219             , m_has_interiors(has_interiors)
0220         {
0221             geometry::envelope(m_ring, m_box, strategy);
0222
0223             // create monotonic sections in x-dimension
0224             // The dimension is critical because the direction is later used
0225             // in the optimization for within checks using winding strategy
0226             // and this strategy is scanning in x direction.
0227             typedef std::integer_sequence<std::size_t, 0> dimensions;
0228             geometry::sectionalize
0229                 <
0230                     false, dimensions
0231                 >(m_ring, detail::no_rescale_policy(), m_sections, strategy);
0232         }
0233
0234         clockwise_ring_type m_ring;
0235         box_type m_box;
0236         sections_type m_sections;
0237
0238         bool m_is_interior;
0239         bool m_has_interiors;
0240     };
0241
0242     typedef std::vector<piece> piece_vector_type;
0243
0244     piece_vector_type m_pieces;
0245     turn_vector_type m_turns;
0246     signed_size_type m_first_piece_index;
0247     bool m_deflate;
0248     bool m_has_deflated;
0249
0250     // Offsetted rings, and representations of original ring(s)
0251     // both indexed by multi_index
0252     using ring_collection_t = buffered_ring_collection<buffered_ring<Ring>>;
0253     ring_collection_t offsetted_rings;
0254     std::vector<original_ring> original_rings;
0255     std::vector<point_type> m_linear_end_points;
0256
0257     buffered_ring_collection<Ring> traversed_rings;
0258     segment_identifier current_segment_id;
0259
0260     // Monotonic sections (used for offsetted rings around points)
0261     // are still using a robust type, to be comparable with turn calculations,
0262     // which is using rescaling.
0263     typedef geometry::model::box
0264     <
0265         typename geometry::robust_point_type<point_type, RobustPolicy>::type
0266     > robust_box_type;
0267     typedef geometry::sections <robust_box_type, 2> robust_sections_type;
0268     robust_sections_type monotonic_sections;
0269
0270     // Define the clusters, mapping cluster_id -> turns
0271     typedef std::map
0272         <
0273             signed_size_type,
0274             detail::overlay::cluster_info
0275         > cluster_type;
0276
0277     cluster_type m_clusters;
0278
0279     Strategy m_strategy;
0280     DistanceStrategy m_distance_strategy;
0281     RobustPolicy const& m_robust_policy;
0282
0283     buffered_piece_collection(Strategy const& strategy,
0284                               DistanceStrategy const& distance_strategy,
0285                               RobustPolicy const& robust_policy)
0286         : m_first_piece_index(-1)
0287         , m_deflate(false)
0288         , m_has_deflated(false)
0289         , m_strategy(strategy)
0290         , m_distance_strategy(distance_strategy)
0291         , m_robust_policy(robust_policy)
0292     {}
0293
0294     inline void check_linear_endpoints(buffer_turn_info_type& turn) const
0295     {
0296         // TODO this is quadratic. But the #endpoints, expected, is low,
0297         // and only applicable for linear features
0298         // (in a multi linestring with many short lines, the #endpoints can be
0299         // much higher)
0300         for (auto const& p : m_linear_end_points)
0301         {
0302             if (detail::equals::equals_point_point(turn.point, p, m_strategy))
0303             {
0304                 turn.is_linear_end_point = true;
0305             }
0306         }
0307     }
0308
0309     inline void deflate_check_turns()
0310     {
0311         if (! m_has_deflated)
0312         {
0313             return;
0314         }
0315
0316         // Deflated rings may not travel to themselves, there should at least
0317         // be three turns (which cannot be checked here - TODO: add to traverse)
0318         for (auto& turn : m_turns)
0319         {
0320             if (! turn.is_turn_traversable)
0321             {
0322                 continue;
0323             }
0324             for (auto& op : turn.operations)
0325             {
0326                 if (op.enriched.get_next_turn_index() == static_cast<signed_size_type>(turn.turn_index)
0327                     && m_pieces[op.seg_id.piece_index].is_deflated)
0328                 {
0329                     // Keep traversable, but don't start here
0330                     op.enriched.startable = false;
0331                 }
0332             }
0333         }
0334     }
0335
0336     // Check if a turn is inside any of the originals
0337     inline void check_turn_in_original()
0338     {
0339         turn_in_original_visitor
0340             <
0341                 turn_vector_type,
0342                 Strategy
0343             > visitor(m_turns, m_strategy);
0344
0345         geometry::partition
0346             <
0347                 box_type,
0348                 include_turn_policy,
0349                 detail::partition::include_all_policy
0350             >::apply(m_turns, original_rings, visitor,
0351                      turn_get_box<Strategy>(m_strategy),
0352                      turn_in_original_overlaps_box<Strategy>(m_strategy),
0353                      original_get_box<Strategy>(m_strategy),
0354                      original_overlaps_box<Strategy>(m_strategy));
0355
0356         bool const deflate = m_distance_strategy.negative();
0357
0358         for (auto& turn : m_turns)
0359         {
0360             if (turn.is_turn_traversable)
0361             {
0362                 if (deflate && turn.count_in_original <= 0)
0363                 {
0364                     // For deflate/negative buffers:
0365                     // it is not in the original, so don't use it
0366                     turn.is_turn_traversable = false;
0367                 }
0368                 else if (! deflate && turn.count_in_original > 0)
0369                 {
0370                     // For inflate: it is in original, so don't use it
0371                     turn.is_turn_traversable = false;
0372                 }
0373             }
0374         }
0375     }
0376
0377     inline void update_turn_administration()
0378     {
0379         for_each_with_index(m_turns, [this](std::size_t index, auto& turn)
0380         {
0381             turn.turn_index = index;
0382
0383             // Verify if a turn is a linear endpoint
0384             if (! turn.is_linear_end_point)
0385             {
0386                 this->check_linear_endpoints(turn);
0387             }
0388         });
0389     }
0390
0391     // Calculate properties of piece borders which are not influenced
0392     // by turns themselves:
0393     // - envelopes (essential for partitioning during calc turns)
0394     // - convexity
0395     // - monotonicity
0396     // - min/max radius of point buffers
0397     // - (if pieces are reversed)
0398     inline void update_piece_administration()
0399     {
0400         for (auto& pc : m_pieces)
0401         {
0402             piece_border_type& border = pc.m_piece_border;
0403             buffered_ring<Ring> const& ring = offsetted_rings[pc.first_seg_id.multi_index];
0404
0405             if (pc.offsetted_count > 0)
0406             {
0407                 if (pc.type != strategy::buffer::buffered_concave)
0408                 {
0409                     border.set_offsetted(ring, pc.first_seg_id.segment_index,
0410                                        pc.beyond_last_segment_index);
0411                 }
0412
0413                 // Calculate envelopes for piece borders
0414                 border.get_properties_of_border(pc.type == geometry::strategy::buffer::buffered_point,
0415                                                 pc.m_center, m_strategy);
0416                 if (! pc.is_flat_end && ! pc.is_flat_start)
0417                 {
0418                     border.get_properties_of_offsetted_ring_part(m_strategy);
0419                 }
0420             }
0421         }
0422     }
0423
0424     inline void get_turns()
0425     {
0426         update_piece_administration();
0427
0428         {
0429             // Calculate the turns
0430             piece_turn_visitor
0431                 <
0432                     piece_vector_type,
0433                     buffered_ring_collection<buffered_ring<Ring> >,
0434                     turn_vector_type,
0435                     Strategy,
0436                     RobustPolicy
0437                 > visitor(m_pieces, offsetted_rings, m_turns,
0438                           m_strategy, m_robust_policy);
0439
0440             detail::sectionalize::enlarge_sections(monotonic_sections, m_strategy);
0441
0442             geometry::partition
0443                 <
0444                     robust_box_type
0445                 >::apply(monotonic_sections, visitor,
0446                          detail::section::get_section_box<Strategy>(m_strategy),
0447                          detail::section::overlaps_section_box<Strategy>(m_strategy));
0448         }
0449
0450         update_turn_administration();
0451     }
0452
0453     inline void check_turn_in_pieces()
0454     {
0455         // Check if turns are inside pieces
0456         turn_in_piece_visitor
0457             <
0458                 typename geometry::cs_tag<point_type>::type,
0459                 turn_vector_type, piece_vector_type, DistanceStrategy, Strategy
0460             > visitor(m_turns, m_pieces, m_distance_strategy, m_strategy);
0461
0462         geometry::partition
0463             <
0464                 box_type
0465             >::apply(m_turns, m_pieces, visitor,
0466                         turn_get_box<Strategy>(m_strategy),
0467                         turn_overlaps_box<Strategy>(m_strategy),
0468                         piece_get_box<Strategy>(m_strategy),
0469                         piece_overlaps_box<Strategy>(m_strategy));
0470     }
0471
0472     inline void start_new_ring(bool deflate)
0473     {
0474         std::size_t const n = offsetted_rings.size();
0475         current_segment_id.source_index = 0;
0476         current_segment_id.multi_index = static_cast<signed_size_type>(n);
0477         current_segment_id.ring_index = -1;
0478         current_segment_id.segment_index = 0;
0479
0480         offsetted_rings.resize(n + 1);
0481         original_rings.resize(n + 1);
0482
0483         m_first_piece_index = static_cast<signed_size_type>(boost::size(m_pieces));
0484         m_deflate = deflate;
0485         if (deflate)
0486         {
0487             // Pieces contain either deflated exterior rings, or inflated
0488             // interior rings which are effectively deflated too
0489             m_has_deflated = true;
0490         }
0491     }
0492
0493     inline void abort_ring()
0494     {
0495         // Remove all created pieces for this ring, sections, last offsetted
0496         while (! m_pieces.empty()
0497                && m_pieces.back().first_seg_id.multi_index
0498                == current_segment_id.multi_index)
0499         {
0500             m_pieces.pop_back();
0501         }
0502
0503         offsetted_rings.pop_back();
0504         original_rings.pop_back();
0505
0506         m_first_piece_index = -1;
0507     }
0508
0509     inline void update_last_point(point_type const& p,
0510             buffered_ring<Ring>& ring)
0511     {
0512         // For the first point of a new piece, and there were already
0513         // points in the offsetted ring, for some piece types the first point
0514         // is a duplicate of the last point of the previous piece.
0515
0516         // TODO: disable that, that point should not be added
0517
0518         // For now, it is made equal because due to numerical instability,
0519         // it can be a tiny bit off, possibly causing a self-intersection
0520
0521         BOOST_GEOMETRY_ASSERT(boost::size(m_pieces) > 0);
0522         if (! ring.empty()
0523             && current_segment_id.segment_index
0524                 == m_pieces.back().first_seg_id.segment_index)
0525         {
0526             ring.back() = p;
0527         }
0528     }
0529
0530     inline void set_piece_center(point_type const& center)
0531     {
0532         BOOST_GEOMETRY_ASSERT(! m_pieces.empty());
0533         m_pieces.back().m_center = center;
0534     }
0535
0536     inline bool finish_ring(strategy::buffer::result_code code)
0537     {
0538         if (code == strategy::buffer::result_error_numerical)
0539         {
0540             abort_ring();
0541             return false;
0542         }
0543
0544         if (m_first_piece_index == -1)
0545         {
0546             return false;
0547         }
0548
0549         // Casted version
0550         std::size_t const first_piece_index
0551                 = static_cast<std::size_t>(m_first_piece_index);
0552         signed_size_type const last_piece_index
0553                 = static_cast<signed_size_type>(boost::size(m_pieces)) - 1;
0554
0555         if (first_piece_index < boost::size(m_pieces))
0556         {
0557             // If pieces were added,
0558             // reassign left-of-first and right-of-last
0559             geometry::range::at(m_pieces, first_piece_index).left_index
0560                     = last_piece_index;
0561             geometry::range::back(m_pieces).right_index = m_first_piece_index;
0562         }
0563
0564         buffered_ring<Ring>& added = offsetted_rings.back();
0565         if (! boost::empty(added))
0566         {
0567             // Make sure the closing point is identical (they are calculated
0568             // separately by different pieces)
0569             range::back(added) = range::front(added);
0570         }
0571
0572         for (std::size_t i = first_piece_index; i < boost::size(m_pieces); i++)
0573         {
0574             sectionalize(m_pieces[i], added);
0575         }
0576
0577         m_first_piece_index = -1;
0578         return true;
0579     }
0580
0581     template <typename InputRing>
0582     inline void finish_ring(strategy::buffer::result_code code,
0583                             InputRing const& input_ring,
0584                             bool is_interior, bool has_interiors)
0585     {
0586         if (! finish_ring(code))
0587         {
0588             return;
0589         }
0590
0591         if (! boost::empty(input_ring))
0592         {
0593             // Assign the ring to the original_ring collection
0594             // For rescaling, it is recalculated. Without rescaling, it
0595             // is just assigning (note that this Ring type is the
0596             // GeometryOut type, which might differ from the input ring type)
0597             clockwise_ring_type clockwise_ring;
0598
0599             using view_type = detail::closed_clockwise_view<InputRing const>;
0600             view_type const view(input_ring);
0601
0602             for (auto it = boost::begin(view); it != boost::end(view); ++it)
0603             {
0604                 clockwise_ring.push_back(*it);
0605             }
0606
0607             original_rings.back()
0608                 = original_ring(clockwise_ring,
0609                     is_interior, has_interiors,
0610                     m_strategy);
0611         }
0612     }
0613
0614     inline void set_current_ring_concave()
0615     {
0616         BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0);
0617         offsetted_rings.back().has_concave = true;
0618     }
0619
0620     inline signed_size_type add_point(point_type const& p)
0621     {
0622         BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0);
0623
0624         buffered_ring<Ring>& current_ring = offsetted_rings.back();
0625         update_last_point(p, current_ring);
0626
0627         current_segment_id.segment_index++;
0628         current_ring.push_back(p);
0629         return static_cast<signed_size_type>(current_ring.size());
0630     }
0631
0632     //-------------------------------------------------------------------------
0633
0634     inline piece& create_piece(strategy::buffer::piece_type type,
0635             bool decrease_segment_index_by_one)
0636     {
0637         if (type == strategy::buffer::buffered_concave)
0638         {
0639             offsetted_rings.back().has_concave = true;
0640         }
0641
0642         piece pc;
0643         pc.type = type;
0644         pc.index = static_cast<signed_size_type>(boost::size(m_pieces));
0645         pc.is_deflated = m_deflate;
0646
0647         current_segment_id.piece_index = pc.index;
0648
0649         pc.first_seg_id = current_segment_id;
0650
0651         // Assign left/right (for first/last piece per ring they will be re-assigned later)
0652         pc.left_index = pc.index - 1;
0653         pc.right_index = pc.index + 1;
0654
0655         std::size_t const n = boost::size(offsetted_rings.back());
0656         pc.first_seg_id.segment_index = decrease_segment_index_by_one ? n - 1 : n;
0657         pc.beyond_last_segment_index = pc.first_seg_id.segment_index;
0658
0659         m_pieces.push_back(pc);
0660         return m_pieces.back();
0661     }
0662
0663     inline void init_rescale_piece(piece& pc)
0664     {
0665         if (pc.first_seg_id.segment_index < 0)
0666         {
0667             // This indicates an error situation: an earlier piece was empty
0668             // It currently does not happen
0669             pc.offsetted_count = 0;
0670             return;
0671         }
0672
0673         BOOST_GEOMETRY_ASSERT(pc.first_seg_id.multi_index >= 0);
0674         BOOST_GEOMETRY_ASSERT(pc.beyond_last_segment_index >= 0);
0675
0676         pc.offsetted_count = pc.beyond_last_segment_index - pc.first_seg_id.segment_index;
0677         BOOST_GEOMETRY_ASSERT(pc.offsetted_count >= 0);
0678     }
0679
0680     inline void add_piece_point(piece& pc, point_type const& point, bool add_to_original)
0681     {
0682         if (add_to_original && pc.type != strategy::buffer::buffered_concave)
0683         {
0684             pc.m_piece_border.add_original_point(point);
0685         }
0686         else
0687         {
0688             pc.m_label_point = point;
0689         }
0690     }
0691
0692     inline void sectionalize(piece const& pc, buffered_ring<Ring> const& ring)
0693     {
0694         using sectionalizer = geometry::detail::sectionalize::sectionalize_part
0695         <
0696             std::integer_sequence<std::size_t, 0, 1> // x,y dimension
0697         >;
0698
0699         // Create a ring-identifier. The source-index is the piece index
0700         // The multi_index is as in this collection (the ring), but not used here
0701         // The ring_index is not used
0702         ring_identifier const ring_id(pc.index, pc.first_seg_id.multi_index, -1);
0703
0704         sectionalizer::apply(monotonic_sections,
0705             boost::begin(ring) + pc.first_seg_id.segment_index,
0706             boost::begin(ring) + pc.beyond_last_segment_index,
0707             m_robust_policy,
0708             m_strategy,
0709             ring_id, 10);
0710     }
0711
0712     inline void finish_piece(piece& pc)
0713     {
0714         init_rescale_piece(pc);
0715     }
0716
0717     inline void finish_piece(piece& pc,
0718                     point_type const& point1,
0719                     point_type const& point2,
0720                     point_type const& point3)
0721     {
0722         init_rescale_piece(pc);
0723         if (pc.offsetted_count == 0)
0724         {
0725             return;
0726         }
0727
0728         add_piece_point(pc, point1, false);
0729         add_piece_point(pc, point2, true);
0730         add_piece_point(pc, point3, false);
0731     }
0732
0733     inline void finish_piece(piece& pc,
0734                     point_type const& point1,
0735                     point_type const& point2,
0736                     point_type const& point3,
0737                     point_type const& point4)
0738     {
0739         init_rescale_piece(pc);
0740
0741         // Add the four points. Note that points 2 and 3 are the originals,
0742         // and that they are already passed in reverse order
0743         // (because the offsetted ring is in clockwise order)
0744         add_piece_point(pc, point1, false);
0745         add_piece_point(pc, point2, true);
0746         add_piece_point(pc, point3, true);
0747         add_piece_point(pc, point4, false);
0748     }
0749
0750     template <typename Range>
0751     inline void add_range_to_piece(piece& pc, Range const& range, bool add_front)
0752     {
0753         BOOST_GEOMETRY_ASSERT(boost::size(range) != 0u);
0754
0755         auto it = boost::begin(range);
0756
0757         // If it follows a non-join (so basically the same piece-type) point b1 should be added.
0758         // There should be two intersections later and it should be discarded.
0759         // But for now we need it to calculate intersections
0760         if (add_front)
0761         {
0762             add_point(*it);
0763         }
0764
0765         for (++it; it != boost::end(range); ++it)
0766         {
0767             pc.beyond_last_segment_index = add_point(*it);
0768         }
0769     }
0770
0771     inline void add_piece(strategy::buffer::piece_type type, point_type const& p,
0772             point_type const& b1, point_type const& b2)
0773     {
0774         piece& pc = create_piece(type, false);
0775         add_point(b1);
0776         pc.beyond_last_segment_index = add_point(b2);
0777         finish_piece(pc, b2, p, b1);
0778     }
0779
0780     template <typename Range>
0781     inline void add_piece(strategy::buffer::piece_type type, Range const& range,
0782             bool decrease_segment_index_by_one)
0783     {
0784         piece& pc = create_piece(type, decrease_segment_index_by_one);
0785
0786         if (boost::size(range) > 0u)
0787         {
0788             add_range_to_piece(pc, range, offsetted_rings.back().empty());
0789         }
0790         finish_piece(pc);
0791     }
0792
0793     template <typename Range>
0794     inline void add_piece(strategy::buffer::piece_type type,
0795             point_type const& p, Range const& range)
0796     {
0797         piece& pc = create_piece(type, true);
0798
0799         if (boost::size(range) > 0u)
0800         {
0801             add_range_to_piece(pc, range, offsetted_rings.back().empty());
0802             finish_piece(pc, range.back(), p, range.front());
0803         }
0804         else
0805         {
0806             finish_piece(pc);
0807         }
0808     }
0809
0810     template <typename Range>
0811     inline void add_side_piece(point_type const& original_point1,
0812             point_type const& original_point2,
0813             Range const& range, bool is_first, bool is_empty)
0814     {
0815         BOOST_GEOMETRY_ASSERT(boost::size(range) >= 2u);
0816
0817         auto const piece_type = is_empty
0818             ? strategy::buffer::buffered_empty_side
0819             : strategy::buffer::buffered_segment;
0820
0821         piece& pc = create_piece(piece_type, ! is_first);
0822         add_range_to_piece(pc, range, is_first);
0823
0824         // Add the four points of the side, starting with the last point of the
0825         // range, and reversing the order of the originals to keep it clockwise
0826         finish_piece(pc, range.back(), original_point2, original_point1, range.front());
0827     }
0828
0829     template <typename EndcapStrategy, typename Range>
0830     inline void add_endcap(EndcapStrategy const& strategy, Range const& range,
0831             point_type const& end_point)
0832     {
0833         boost::ignore_unused(strategy);
0834
0835         if (range.empty())
0836         {
0837             return;
0838         }
0839         strategy::buffer::piece_type pt = strategy.get_piece_type();
0840         if (pt == strategy::buffer::buffered_flat_end)
0841         {
0842             // It is flat, should just be added, without helper segments
0843             add_piece(pt, range, true);
0844         }
0845         else
0846         {
0847             // Normal case, it has an "inside", helper segments should be added
0848             add_piece(pt, end_point, range);
0849         }
0850     }
0851
0852     inline void mark_flat_start(point_type const& point)
0853     {
0854         if (! m_pieces.empty())
0855         {
0856             piece& back = m_pieces.back();
0857             back.is_flat_start = true;
0858
0859             // This happens to linear buffers, and it will be the very
0860             // first or last point. If that coincides with a turn,
0861             // and the turn was marked as ON_BORDER
0862             // the turn should NOT be within (even though it can be marked
0863             // as such)
0864             m_linear_end_points.push_back(point);
0865         }
0866     }
0867
0868     inline void mark_flat_end(point_type const& point)
0869     {
0870         if (! m_pieces.empty())
0871         {
0872             piece& back = m_pieces.back();
0873             back.is_flat_end = true;
0874             m_linear_end_points.push_back(point);
0875         }
0876     }
0877
0878     //-------------------------------------------------------------------------
0879
0880     inline void handle_colocations()
0881     {
0882         if (! detail::overlay::handle_colocations
0883                 <
0884                     false, false, overlay_buffer,
0885                     ring_collection_t, ring_collection_t
0886                 >(m_turns, m_clusters, m_robust_policy))
0887         {
0888             return;
0889         }
0890
0891         detail::overlay::gather_cluster_properties
0892             <
0893                 false, false, overlay_buffer
0894             >(m_clusters, m_turns, detail::overlay::operation_union,
0895             offsetted_rings, offsetted_rings, m_strategy);
0896
0897         for (auto const& cluster : m_clusters)
0898         {
0899             if (cluster.second.open_count == 0 && cluster.second.spike_count == 0)
0900             {
0901                 // If the cluster is completely closed, mark it as not traversable.
0902                 for (auto const& index : cluster.second.turn_indices)
0903                 {
0904                     m_turns[index].is_turn_traversable = false;
0905                 }
0906             }
0907         }
0908     }
0909
0910     inline void make_traversable_consistent_per_cluster()
0911     {
0912         for (auto const& cluster : m_clusters)
0913         {
0914             bool is_traversable = false;
0915             for (auto const& index : cluster.second.turn_indices)
0916             {
0917                 if (m_turns[index].is_turn_traversable)
0918                 {
0919                     // If there is one turn traversable in the cluster,
0920                     // then all turns should be traversable.
0921                     is_traversable = true;
0922                     break;
0923                 }
0924             }
0925             if (is_traversable)
0926             {
0927                 for (auto const& index : cluster.second.turn_indices)
0928                 {
0929                     m_turns[index].is_turn_traversable = true;
0930                 }
0931             }
0932         }
0933     }
0934
0935     inline void enrich()
0936     {
0937         enrich_intersection_points<false, false, overlay_buffer>(m_turns,
0938             m_clusters, offsetted_rings, offsetted_rings,
0939             m_robust_policy,
0940             m_strategy);
0941     }
0942
0943     // Discards all rings which do have not-OK intersection points only.
0944     // Those can never be traversed and should not be part of the output.
0945     inline void discard_rings()
0946     {
0947         for (auto const& turn : m_turns)
0948         {
0949             if (turn.is_turn_traversable)
0950             {
0951                 offsetted_rings[turn.operations[0].seg_id.multi_index].has_accepted_intersections = true;
0952                 offsetted_rings[turn.operations[1].seg_id.multi_index].has_accepted_intersections = true;
0953             }
0954             else
0955             {
0956                 offsetted_rings[turn.operations[0].seg_id.multi_index].has_discarded_intersections = true;
0957                 offsetted_rings[turn.operations[1].seg_id.multi_index].has_discarded_intersections = true;
0958             }
0959         }
0960     }
0961
0962     inline bool point_coveredby_original(point_type const& point)
0963     {
0964         signed_size_type count_in_original = 0;
0965
0966         // Check of the robust point of this outputted ring is in
0967         // any of the robust original rings
0968         // This can go quadratic if the input has many rings, and there
0969         // are many untouched deflated rings around
0970         for (auto const& original : original_rings)
0971         {
0972             if (original.m_ring.empty())
0973             {
0974                 continue;
0975             }
0976             if (detail::disjoint::disjoint_point_box(point, original.m_box,m_strategy))
0977             {
0978                 continue;
0979             }
0980
0981             int const geometry_code
0982                 = detail::within::point_in_geometry(point, original.m_ring, m_strategy);
0983
0984             if (geometry_code == -1)
0985             {
0986                 // Outside, continue
0987                 continue;
0988             }
0989
0990             // Apply for possibly nested interior rings
0991             if (original.m_is_interior)
0992             {
0993                 count_in_original--;
0994             }
0995             else if (original.m_has_interiors)
0996             {
0997                 count_in_original++;
0998             }
0999             else
1000             {
1001                 // Exterior ring without interior rings
1002                 return true;
1003             }
1004         }
1005         return count_in_original > 0;
1006     }
1007
1008     // For a deflate, all rings around inner rings which are untouched
1009     // (no intersections/turns) and which are OUTSIDE the original should
1010     // be discarded
1011     inline void discard_nonintersecting_deflated_rings()
1012     {
1013         for (auto& ring : offsetted_rings)
1014         {
1015             if (! ring.has_intersections()
1016                 && boost::size(ring) > 0u
1017                 && geometry::area(ring, m_strategy) < 0)
1018             {
1019                 if (! point_coveredby_original(geometry::range::front(ring)))
1020                 {
1021                     ring.is_untouched_outside_original = true;
1022                 }
1023             }
1024         }
1025     }
1026
1027     inline void block_turns()
1028     {
1029         for (auto& turn : m_turns)
1030         {
1031             if (! turn.is_turn_traversable)
1032             {
1033                 // Discard this turn (don't set it to blocked to avoid colocated
1034                 // clusters being discarded afterwards
1035                 turn.discarded = true;
1036             }
1037         }
1038     }
1039
1040     inline void traverse()
1041     {
1042         typedef detail::overlay::traverse
1043             <
1044                 false, false,
1045                 buffered_ring_collection<buffered_ring<Ring> >,
1046                 buffered_ring_collection<buffered_ring<Ring > >,
1047                 overlay_buffer,
1048                 backtrack_for_buffer
1049             > traverser;
1050         std::map<ring_identifier, overlay::ring_turn_info> turn_info_per_ring;
1051
1052         traversed_rings.clear();
1053         buffer_overlay_visitor visitor;
1054         traverser::apply(offsetted_rings, offsetted_rings,
1055                         m_strategy, m_robust_policy,
1056                         m_turns, traversed_rings,
1057                         turn_info_per_ring,
1058                         m_clusters, visitor);
1059     }
1060
1061     inline void reverse()
1062     {
1063         for (auto& ring : offsetted_rings)
1064         {
1065             if (! ring.has_intersections())
1066             {
1067                 std::reverse(ring.begin(), ring.end());
1068             }
1069         }
1070         for (auto& ring : traversed_rings)
1071         {
1072             std::reverse(ring.begin(), ring.end());
1073         }
1074     }
1075
1076     template <typename GeometryOutput, typename OutputIterator>
1077     inline OutputIterator assign(OutputIterator out) const
1078     {
1079         typedef typename geometry::area_result
1080             <
1081                 buffered_ring<Ring>, Strategy
1082             >::type area_result_type;
1083         typedef detail::overlay::ring_properties
1084             <
1085                 point_type, area_result_type
1086             > properties;
1087
1088         std::map<ring_identifier, properties> selected;
1089
1090         // Select all rings which do not have any self-intersection
1091         // Inner rings, for deflate, which do not have intersections, and
1092         // which are outside originals, are skipped
1093         // (other ones should be traversed)
1094         for_each_with_index(offsetted_rings, [&](std::size_t index, auto const& ring)
1095             {
1096                 if (! ring.has_intersections()
1097                     && ! ring.is_untouched_outside_original)
1098                 {
1099                     properties p = properties(ring, m_strategy);
1100                     if (p.valid)
1101                     {
1102                         ring_identifier id(0, index, -1);
1103                         selected[id] = p;
1104                     }
1105                 }
1106             });
1107
1108         // Select all created rings
1109         for_each_with_index(traversed_rings, [&](std::size_t index, auto const& ring)
1110             {
1111                 properties p = properties(ring, m_strategy);
1112                 if (p.valid)
1113                 {
1114                     ring_identifier id(2, index, -1);
1115                     selected[id] = p;
1116                 }
1117             });
1118
1119         detail::overlay::assign_parents<overlay_buffer>(offsetted_rings, traversed_rings,
1120                 selected, m_strategy);
1121         return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out,
1122                                                           m_strategy);
1123     }
1124
1125 };
1126
1127
1128 }} // namespace detail::buffer
1129 #endif // DOXYGEN_NO_DETAIL
1130
1131
1132 }} // namespace boost::geometry
1133
1134 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP