detail/buffer/buffer_inserter.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2012-2020 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2022-2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2017-2022.
0007 // Modifications copyright (c) 2017-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_BUFFER_INSERTER_HPP
0015 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_INSERTER_HPP
0016
0017 #include <cstddef>
0018 #include <iterator>
0019
0020 #include <boost/core/ignore_unused.hpp>
0021 #include <boost/numeric/conversion/cast.hpp>
0022 #include <boost/range/begin.hpp>
0023 #include <boost/range/end.hpp>
0024 #include <boost/range/rbegin.hpp>
0025 #include <boost/range/rend.hpp>
0026 #include <boost/range/size.hpp>
0027 #include <boost/range/value_type.hpp>
0028
0029 #include <boost/geometry/algorithms/detail/direction_code.hpp>
0030 #include <boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp>
0031 #include <boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp>
0032
0033 #include <boost/geometry/algorithms/num_interior_rings.hpp>
0034 #include <boost/geometry/algorithms/simplify.hpp>
0035
0036 #include <boost/geometry/core/assert.hpp>
0037 #include <boost/geometry/core/closure.hpp>
0038 #include <boost/geometry/core/exterior_ring.hpp>
0039 #include <boost/geometry/core/interior_rings.hpp>
0040
0041 #include <boost/geometry/geometries/linestring.hpp>
0042 #include <boost/geometry/geometries/ring.hpp>
0043
0044 #include <boost/geometry/strategies/buffer.hpp>
0045 #include <boost/geometry/strategies/side.hpp>
0046
0047 #include <boost/geometry/util/constexpr.hpp>
0048 #include <boost/geometry/util/math.hpp>
0049 #include <boost/geometry/util/type_traits.hpp>
0050
0051 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
0052
0053
0054 namespace boost { namespace geometry
0055 {
0056
0057 #ifndef DOXYGEN_NO_DETAIL
0058 namespace detail { namespace buffer
0059 {
0060
0061 template <typename RangeIn, typename DistanceStrategy, typename RangeOut, typename Strategies>
0062 inline void simplify_input(RangeIn const& range,
0063                            DistanceStrategy const& distance,
0064                            RangeOut& simplified,
0065                            Strategies const& strategies)
0066 {
0067     // We have to simplify the ring before to avoid very small-scaled
0068     // features in the original (convex/concave/convex) being enlarged
0069     // in a very large scale and causing issues (IP's within pieces).
0070     // This might be reconsidered later. Simplifying with a very small
0071     // distance (1%% of the buffer) will never be visible in the result,
0072     // if it is using round joins. For miter joins they are even more
0073     // sensitive to small scale input features, however the result will
0074     // look better.
0075     // It also gets rid of duplicate points
0076
0077     geometry::detail::simplify::simplify_range<2>::apply(range,
0078         simplified, distance.simplify_distance(),
0079         detail::simplify::douglas_peucker(),
0080         strategies);
0081
0082 }
0083
0084
0085 template <typename RingOutput>
0086 struct buffer_range
0087 {
0088     typedef typename point_type<RingOutput>::type output_point_type;
0089     typedef typename coordinate_type<RingOutput>::type coordinate_type;
0090
0091     template
0092     <
0093         typename Collection,
0094         typename Point,
0095         typename DistanceStrategy,
0096         typename SegmentStrategy,
0097         typename JoinStrategy,
0098         typename EndStrategy,
0099         typename RobustPolicy,
0100         typename Strategies
0101     >
0102     static inline
0103     void add_join(Collection& collection,
0104             Point const& penultimate_input,
0105             Point const& previous_input,
0106             output_point_type const& prev_perp1,
0107             output_point_type const& prev_perp2,
0108             Point const& input,
0109             output_point_type const& perp1,
0110             output_point_type const& perp2,
0111             geometry::strategy::buffer::buffer_side_selector side,
0112             DistanceStrategy const& distance,
0113             SegmentStrategy const& segment_strategy,
0114             JoinStrategy const& join_strategy,
0115             EndStrategy const& end_strategy,
0116             RobustPolicy const& ,
0117             Strategies const& strategies)
0118     {
0119         geometry::strategy::buffer::join_selector const join
0120                 = get_join_type(penultimate_input, previous_input, input,
0121                                 strategies);
0122
0123         switch(join)
0124         {
0125             case geometry::strategy::buffer::join_continue :
0126                 // No join, we get two consecutive sides
0127                 break;
0128             case geometry::strategy::buffer::join_concave :
0129                 {
0130                     std::vector<output_point_type> range_out;
0131                     range_out.push_back(prev_perp2);
0132                     range_out.push_back(previous_input);
0133                     collection.add_piece(geometry::strategy::buffer::buffered_concave, previous_input, range_out);
0134
0135                     range_out.clear();
0136                     range_out.push_back(previous_input);
0137                     range_out.push_back(perp1);
0138                     collection.add_piece(geometry::strategy::buffer::buffered_concave, previous_input, range_out);
0139                 }
0140                 break;
0141             case geometry::strategy::buffer::join_spike :
0142                 {
0143                     // For linestrings, only add spike at one side to avoid
0144                     // duplicates
0145                     std::vector<output_point_type> range_out;
0146                     end_strategy.apply(penultimate_input, prev_perp2, previous_input, perp1, side, distance, range_out);
0147                     collection.add_endcap(end_strategy, range_out, previous_input);
0148                     collection.set_current_ring_concave();
0149                 }
0150                 break;
0151             case geometry::strategy::buffer::join_convex :
0152                 {
0153                     // The corner is convex, we create a join
0154                     // TODO (future) - avoid a separate vector, add the piece directly
0155                     output_point_type intersection_point;
0156                     if (line_line_intersection::apply(prev_perp1, prev_perp2,
0157                                                       perp1, perp2, previous_input,
0158                                                       segment_strategy.equidistant(),
0159                                                       intersection_point))
0160                     {
0161                         std::vector<output_point_type> range_out;
0162                         if (join_strategy.apply(intersection_point,
0163                                     previous_input, prev_perp2, perp1,
0164                                     distance.apply(previous_input, input, side),
0165                                     range_out))
0166                         {
0167                             collection.add_piece(geometry::strategy::buffer::buffered_join,
0168                                     previous_input, range_out);
0169                         }
0170                     }
0171                 }
0172                 break;
0173         }
0174     }
0175
0176     // Returns true if collinear point p2 continues after p0 and p1.
0177     // If it turns back (spike), it returns false.
0178     static inline bool same_direction(output_point_type const& p0,
0179             output_point_type const& p1,
0180             output_point_type const& p2)
0181     {
0182         typedef typename cs_tag<output_point_type>::type cs_tag;
0183         return direction_code<cs_tag>(p0, p1, p2) == 1;
0184     }
0185
0186     template <typename Strategies>
0187     static inline geometry::strategy::buffer::join_selector get_join_type(
0188             output_point_type const& p0,
0189             output_point_type const& p1,
0190             output_point_type const& p2,
0191             Strategies const& strategies)
0192     {
0193         int const side = strategies.side().apply(p0, p1, p2);
0194         return side == -1 ? geometry::strategy::buffer::join_convex
0195             :  side == 1  ? geometry::strategy::buffer::join_concave
0196             :  same_direction(p0, p1, p2) ? geometry::strategy::buffer::join_continue
0197             : geometry::strategy::buffer::join_spike;
0198     }
0199
0200     template
0201     <
0202         typename Collection,
0203         typename Iterator,
0204         typename DistanceStrategy,
0205         typename SegmentStrategy,
0206         typename JoinStrategy,
0207         typename EndStrategy,
0208         typename RobustPolicy,
0209         typename Strategies
0210     >
0211     static inline geometry::strategy::buffer::result_code iterate(Collection& collection,
0212                 Iterator begin, Iterator end,
0213                 geometry::strategy::buffer::buffer_side_selector side,
0214                 DistanceStrategy const& distance_strategy,
0215                 SegmentStrategy const& segment_strategy,
0216                 JoinStrategy const& join_strategy,
0217                 EndStrategy const& end_strategy,
0218                 RobustPolicy const& robust_policy,
0219                 Strategies const& strategies,
0220                 bool linear,
0221                 output_point_type& first_p1,
0222                 output_point_type& first_p2,
0223                 output_point_type& last_p1,
0224                 output_point_type& last_p2)
0225     {
0226         boost::ignore_unused(segment_strategy);
0227
0228         typedef typename std::iterator_traits
0229         <
0230             Iterator
0231         >::value_type point_type;
0232
0233         point_type second_point, penultimate_point, ultimate_point; // last two points from begin/end
0234
0235         /*
0236          * last.p1    last.p2  these are the "previous (last) perpendicular points"
0237          * --------------
0238          * |            |
0239          * *------------*____  <- *prev
0240          * pup          |    | p1           "current perpendicular point 1"
0241          *              |    |
0242          *              |    |       this forms a "side", a side is a piece
0243          *              |    |
0244          *              *____| p2
0245          *
0246          *              ^
0247          *             *it
0248          *
0249          * pup: penultimate_point
0250          */
0251
0252         bool const mark_flat
0253             = linear
0254                 && end_strategy.get_piece_type() == geometry::strategy::buffer::buffered_flat_end;
0255
0256         geometry::strategy::buffer::result_code result = geometry::strategy::buffer::result_no_output;
0257         bool first = true;
0258
0259         Iterator it = begin;
0260
0261         std::vector<output_point_type> generated_side;
0262         generated_side.reserve(2);
0263
0264         for (Iterator prev = it++; it != end; ++it)
0265         {
0266             generated_side.clear();
0267             geometry::strategy::buffer::result_code error_code
0268                 = segment_strategy.apply(*prev, *it, side,
0269                                 distance_strategy, generated_side);
0270
0271             if (error_code == geometry::strategy::buffer::result_no_output)
0272             {
0273                 // Because input is simplified, this is improbable,
0274                 // but it can happen for degenerate geometries
0275                 // Further handling of this side is skipped
0276                 continue;
0277             }
0278             else if (error_code == geometry::strategy::buffer::result_error_numerical)
0279             {
0280                 return error_code;
0281             }
0282
0283             BOOST_GEOMETRY_ASSERT(! generated_side.empty());
0284
0285             result = geometry::strategy::buffer::result_normal;
0286
0287             if (! first)
0288             {
0289                  add_join(collection,
0290                         penultimate_point,
0291                         *prev, last_p1, last_p2,
0292                         *it, generated_side.front(), generated_side.back(),
0293                         side,
0294                         distance_strategy, segment_strategy, join_strategy, end_strategy,
0295                         robust_policy, strategies);
0296             }
0297
0298             collection.add_side_piece(*prev, *it, generated_side, first, distance_strategy.empty(side));
0299
0300             if (first && mark_flat)
0301             {
0302                 collection.mark_flat_start(*prev);
0303             }
0304
0305             penultimate_point = *prev;
0306             ultimate_point = *it;
0307             last_p1 = generated_side.front();
0308             last_p2 = generated_side.back();
0309             prev = it;
0310             if (first)
0311             {
0312                 first = false;
0313                 second_point = *it;
0314                 first_p1 = generated_side.front();
0315                 first_p2 = generated_side.back();
0316             }
0317         }
0318
0319         if (mark_flat)
0320         {
0321             collection.mark_flat_end(ultimate_point);
0322         }
0323
0324         return result;
0325     }
0326 };
0327
0328 template
0329 <
0330     typename Multi,
0331     typename PolygonOutput,
0332     typename Policy
0333 >
0334 struct buffer_multi
0335 {
0336     template
0337     <
0338         typename Collection,
0339         typename DistanceStrategy,
0340         typename SegmentStrategy,
0341         typename JoinStrategy,
0342         typename EndStrategy,
0343         typename PointStrategy,
0344         typename RobustPolicy,
0345         typename Strategies
0346     >
0347     static inline void apply(Multi const& multi,
0348             Collection& collection,
0349             DistanceStrategy const& distance_strategy,
0350             SegmentStrategy const& segment_strategy,
0351             JoinStrategy const& join_strategy,
0352             EndStrategy const& end_strategy,
0353             PointStrategy const& point_strategy,
0354             RobustPolicy const& robust_policy,
0355             Strategies const& strategies)
0356     {
0357         for (auto it = boost::begin(multi); it != boost::end(multi); ++it)
0358         {
0359             Policy::apply(*it, collection,
0360                 distance_strategy, segment_strategy,
0361                 join_strategy, end_strategy, point_strategy,
0362                 robust_policy, strategies);
0363         }
0364     }
0365 };
0366
0367 struct visit_pieces_default_policy
0368 {
0369     template <typename Collection>
0370     static inline void apply(Collection const&, int)
0371     {}
0372 };
0373
0374 template
0375 <
0376     typename OutputPointType,
0377     typename Point,
0378     typename Collection,
0379     typename DistanceStrategy,
0380     typename PointStrategy
0381 >
0382 inline void buffer_point(Point const& point, Collection& collection,
0383         DistanceStrategy const& distance_strategy,
0384         PointStrategy const& point_strategy)
0385 {
0386     collection.start_new_ring(false);
0387     std::vector<OutputPointType> range_out;
0388     point_strategy.apply(point, distance_strategy, range_out);
0389     collection.add_piece(geometry::strategy::buffer::buffered_point, range_out, false);
0390     collection.set_piece_center(point);
0391     collection.finish_ring(geometry::strategy::buffer::result_normal);
0392 }
0393
0394
0395 }} // namespace detail::buffer
0396 #endif // DOXYGEN_NO_DETAIL
0397
0398
0399 #ifndef DOXYGEN_NO_DISPATCH
0400 namespace dispatch
0401 {
0402
0403 template
0404 <
0405     typename Tag,
0406     typename RingInput,
0407     typename RingOutput
0408 >
0409 struct buffer_inserter
0410 {};
0411
0412
0413
0414 template
0415 <
0416     typename Point,
0417     typename RingOutput
0418 >
0419 struct buffer_inserter<point_tag, Point, RingOutput>
0420 {
0421     template
0422     <
0423         typename Collection,
0424         typename DistanceStrategy,
0425         typename SegmentStrategy,
0426         typename JoinStrategy,
0427         typename EndStrategy,
0428         typename PointStrategy,
0429         typename RobustPolicy,
0430         typename Strategies
0431     >
0432     static inline void apply(Point const& point, Collection& collection,
0433             DistanceStrategy const& distance_strategy,
0434             SegmentStrategy const& ,
0435             JoinStrategy const& ,
0436             EndStrategy const& ,
0437             PointStrategy const& point_strategy,
0438             RobustPolicy const& ,
0439             Strategies const& )
0440     {
0441         detail::buffer::buffer_point
0442         <
0443             typename point_type<RingOutput>::type
0444         >(point, collection, distance_strategy, point_strategy);
0445     }
0446 };
0447
0448 // Not a specialization, but called from specializations of ring and of polygon.
0449 // Calling code starts/finishes ring before/after apply
0450 template
0451 <
0452     typename RingInput,
0453     typename RingOutput
0454 >
0455 struct buffer_inserter_ring
0456 {
0457     using output_point_type = typename point_type<RingOutput>::type;
0458
0459     template
0460     <
0461         typename Collection,
0462         typename Iterator,
0463         typename DistanceStrategy,
0464         typename SegmentStrategy,
0465         typename JoinStrategy,
0466         typename EndStrategy,
0467         typename RobustPolicy,
0468         typename Strategies
0469     >
0470     static inline geometry::strategy::buffer::result_code iterate(Collection& collection,
0471                 Iterator begin, Iterator end,
0472                 geometry::strategy::buffer::buffer_side_selector side,
0473                 DistanceStrategy const& distance_strategy,
0474                 SegmentStrategy const& segment_strategy,
0475                 JoinStrategy const& join_strategy,
0476                 EndStrategy const& end_strategy,
0477                 RobustPolicy const& robust_policy,
0478                 Strategies const& strategies)
0479     {
0480         output_point_type first_p1, first_p2, last_p1, last_p2;
0481
0482         typedef detail::buffer::buffer_range<RingOutput> buffer_range;
0483
0484         geometry::strategy::buffer::result_code result
0485             = buffer_range::iterate(collection, begin, end,
0486                 side,
0487                 distance_strategy, segment_strategy, join_strategy, end_strategy,
0488                 robust_policy, strategies,
0489                 false, first_p1, first_p2, last_p1, last_p2);
0490
0491         // Generate closing join
0492         if (result == geometry::strategy::buffer::result_normal)
0493         {
0494             buffer_range::add_join(collection,
0495                 *(end - 2),
0496                 *(end - 1), last_p1, last_p2,
0497                 *(begin + 1), first_p1, first_p2,
0498                 side,
0499                 distance_strategy, segment_strategy, join_strategy, end_strategy,
0500                 robust_policy, strategies);
0501         }
0502
0503         // Buffer is closed automatically by last closing corner
0504         return result;
0505     }
0506
0507     template
0508     <
0509         typename Collection,
0510         typename DistanceStrategy,
0511         typename SegmentStrategy,
0512         typename JoinStrategy,
0513         typename EndStrategy,
0514         typename PointStrategy,
0515         typename RobustPolicy,
0516         typename Strategies
0517     >
0518     static inline geometry::strategy::buffer::result_code apply(RingInput const& ring,
0519             Collection& collection,
0520             DistanceStrategy const& distance,
0521             SegmentStrategy const& segment_strategy,
0522             JoinStrategy const& join_strategy,
0523             EndStrategy const& end_strategy,
0524             PointStrategy const& point_strategy,
0525             RobustPolicy const& robust_policy,
0526             Strategies const& strategies)
0527     {
0528         // Use helper geometry to support non-mutable input Rings
0529         using simplified_ring_t = model::ring
0530             <
0531                 output_point_type,
0532                 point_order<RingInput>::value != counterclockwise,
0533                 closure<RingInput>::value != open
0534             >;
0535         simplified_ring_t simplified;
0536         detail::buffer::simplify_input(ring, distance, simplified, strategies);
0537
0538         geometry::strategy::buffer::result_code code = geometry::strategy::buffer::result_no_output;
0539
0540         std::size_t n = boost::size(simplified);
0541         std::size_t const min_points = core_detail::closure::minimum_ring_size
0542             <
0543                 geometry::closure<simplified_ring_t>::value
0544             >::value;
0545
0546         if (n >= min_points)
0547         {
0548             detail::closed_clockwise_view<simplified_ring_t const> view(simplified);
0549             if (distance.negative())
0550             {
0551                 // Walk backwards (rings will be reversed afterwards)
0552                 code = iterate(collection, boost::rbegin(view), boost::rend(view),
0553                         geometry::strategy::buffer::buffer_side_right,
0554                         distance, segment_strategy, join_strategy, end_strategy,
0555                         robust_policy, strategies);
0556             }
0557             else
0558             {
0559                 code = iterate(collection, boost::begin(view), boost::end(view),
0560                         geometry::strategy::buffer::buffer_side_left,
0561                         distance, segment_strategy, join_strategy, end_strategy,
0562                         robust_policy, strategies);
0563             }
0564         }
0565
0566         if (code == geometry::strategy::buffer::result_no_output && n >= 1)
0567         {
0568             // Use point_strategy to buffer degenerated ring
0569             detail::buffer::buffer_point<output_point_type>
0570                 (
0571                     geometry::range::front(simplified),
0572                     collection, distance, point_strategy
0573                 );
0574         }
0575         return code;
0576     }
0577 };
0578
0579
0580 template
0581 <
0582     typename RingInput,
0583     typename RingOutput
0584 >
0585 struct buffer_inserter<ring_tag, RingInput, RingOutput>
0586 {
0587     template
0588     <
0589         typename Collection,
0590         typename DistanceStrategy,
0591         typename SegmentStrategy,
0592         typename JoinStrategy,
0593         typename EndStrategy,
0594         typename PointStrategy,
0595         typename RobustPolicy,
0596         typename Strategies
0597     >
0598     static inline geometry::strategy::buffer::result_code apply(RingInput const& ring,
0599             Collection& collection,
0600             DistanceStrategy const& distance,
0601             SegmentStrategy const& segment_strategy,
0602             JoinStrategy const& join_strategy,
0603             EndStrategy const& end_strategy,
0604             PointStrategy const& point_strategy,
0605             RobustPolicy const& robust_policy,
0606             Strategies const& strategies)
0607     {
0608         collection.start_new_ring(distance.negative());
0609         geometry::strategy::buffer::result_code const code
0610             = buffer_inserter_ring<RingInput, RingOutput>::apply(ring,
0611                 collection, distance,
0612                 segment_strategy, join_strategy, end_strategy, point_strategy,
0613                 robust_policy, strategies);
0614         collection.finish_ring(code, ring, false, false);
0615         return code;
0616     }
0617 };
0618
0619 template
0620 <
0621     typename Linestring,
0622     typename Polygon
0623 >
0624 struct buffer_inserter<linestring_tag, Linestring, Polygon>
0625 {
0626     using output_ring_type = typename ring_type<Polygon>::type;
0627     using output_point_type = typename point_type<output_ring_type>::type;
0628
0629     template
0630     <
0631         typename Collection,
0632         typename Iterator,
0633         typename DistanceStrategy,
0634         typename SegmentStrategy,
0635         typename JoinStrategy,
0636         typename EndStrategy,
0637         typename RobustPolicy,
0638         typename Strategies
0639     >
0640     static inline geometry::strategy::buffer::result_code iterate(Collection& collection,
0641                 Iterator begin, Iterator end,
0642                 geometry::strategy::buffer::buffer_side_selector side,
0643                 DistanceStrategy const& distance_strategy,
0644                 SegmentStrategy const& segment_strategy,
0645                 JoinStrategy const& join_strategy,
0646                 EndStrategy const& end_strategy,
0647                 RobustPolicy const& robust_policy,
0648                 Strategies const& strategies,
0649                 output_point_type& first_p1)
0650     {
0651         output_point_type const& ultimate_point = *(end - 1);
0652         output_point_type const& penultimate_point = *(end - 2);
0653
0654         // For the end-cap, we need to have the last perpendicular point on the
0655         // other side of the linestring. If it is the second pass (right),
0656         // we have it already from the first phase (left).
0657         // But for the first pass, we have to generate it
0658         output_point_type reverse_p1;
0659         if (side == geometry::strategy::buffer::buffer_side_right)
0660         {
0661             reverse_p1 = first_p1;
0662         }
0663         else
0664         {
0665             std::vector<output_point_type> generated_side;
0666             geometry::strategy::buffer::result_code code
0667                 = segment_strategy.apply(ultimate_point, penultimate_point,
0668                     geometry::strategy::buffer::buffer_side_right,
0669                     distance_strategy, generated_side);
0670             if (code != geometry::strategy::buffer::result_normal)
0671             {
0672                 // No output or numerical error
0673                 return code;
0674             }
0675             reverse_p1 = generated_side.front();
0676         }
0677
0678         output_point_type first_p2, last_p1, last_p2;
0679
0680         geometry::strategy::buffer::result_code result
0681             = detail::buffer::buffer_range<output_ring_type>::iterate(collection,
0682                 begin, end, side,
0683                 distance_strategy, segment_strategy, join_strategy, end_strategy,
0684                 robust_policy, strategies,
0685                 true, first_p1, first_p2, last_p1, last_p2);
0686
0687         if (result == geometry::strategy::buffer::result_normal)
0688         {
0689             std::vector<output_point_type> range_out;
0690             end_strategy.apply(penultimate_point, last_p2, ultimate_point, reverse_p1,
0691                                side, distance_strategy, range_out);
0692             collection.add_endcap(end_strategy, range_out, ultimate_point);
0693         }
0694         return result;
0695     }
0696
0697     template
0698     <
0699         typename Collection,
0700         typename DistanceStrategy,
0701         typename SegmentStrategy,
0702         typename JoinStrategy,
0703         typename EndStrategy,
0704         typename PointStrategy,
0705         typename RobustPolicy,
0706         typename Strategies
0707     >
0708     static inline geometry::strategy::buffer::result_code apply(Linestring const& linestring,
0709             Collection& collection,
0710             DistanceStrategy const& distance,
0711             SegmentStrategy const& segment_strategy,
0712             JoinStrategy const& join_strategy,
0713             EndStrategy const& end_strategy,
0714             PointStrategy const& point_strategy,
0715             RobustPolicy const& robust_policy,
0716             Strategies const& strategies)
0717     {
0718         // Use helper geometry to support non-mutable input Linestrings
0719         model::linestring<output_point_type> simplified;
0720         detail::buffer::simplify_input(linestring, distance, simplified, strategies);
0721
0722         geometry::strategy::buffer::result_code code = geometry::strategy::buffer::result_no_output;
0723         std::size_t n = boost::size(simplified);
0724         if (n > 1)
0725         {
0726             collection.start_new_ring(false);
0727             output_point_type first_p1;
0728             code = iterate(collection,
0729                     boost::begin(simplified), boost::end(simplified),
0730                     geometry::strategy::buffer::buffer_side_left,
0731                     distance, segment_strategy, join_strategy, end_strategy,
0732                     robust_policy, strategies,
0733                     first_p1);
0734
0735             if (code == geometry::strategy::buffer::result_normal)
0736             {
0737                 code = iterate(collection,
0738                         boost::rbegin(simplified), boost::rend(simplified),
0739                         geometry::strategy::buffer::buffer_side_right,
0740                         distance, segment_strategy, join_strategy, end_strategy,
0741                         robust_policy, strategies,
0742                         first_p1);
0743             }
0744             collection.finish_ring(code);
0745         }
0746         if (code == geometry::strategy::buffer::result_no_output && n >= 1)
0747         {
0748             // Use point_strategy to buffer degenerated linestring
0749             detail::buffer::buffer_point<output_point_type>
0750                 (
0751                     geometry::range::front(simplified),
0752                     collection, distance, point_strategy
0753                 );
0754         }
0755         return code;
0756     }
0757 };
0758
0759
0760 template
0761 <
0762     typename PolygonInput,
0763     typename PolygonOutput
0764 >
0765 struct buffer_inserter<polygon_tag, PolygonInput, PolygonOutput>
0766 {
0767 private:
0768     typedef typename ring_type<PolygonInput>::type input_ring_type;
0769     typedef typename ring_type<PolygonOutput>::type output_ring_type;
0770
0771     typedef buffer_inserter_ring<input_ring_type, output_ring_type> policy;
0772
0773
0774     template
0775     <
0776         typename Iterator,
0777         typename Collection,
0778         typename DistanceStrategy,
0779         typename SegmentStrategy,
0780         typename JoinStrategy,
0781         typename EndStrategy,
0782         typename PointStrategy,
0783         typename RobustPolicy,
0784         typename Strategies
0785     >
0786     static inline
0787     void iterate(Iterator begin, Iterator end,
0788             Collection& collection,
0789             DistanceStrategy const& distance,
0790             SegmentStrategy const& segment_strategy,
0791             JoinStrategy const& join_strategy,
0792             EndStrategy const& end_strategy,
0793             PointStrategy const& point_strategy,
0794             RobustPolicy const& robust_policy,
0795             Strategies const& strategies,
0796             bool is_interior)
0797     {
0798         for (Iterator it = begin; it != end; ++it)
0799         {
0800             // For exterior rings, it deflates if distance is negative.
0801             // For interior rings, it is vice versa
0802             bool const deflate = is_interior
0803                     ? ! distance.negative()
0804                     : distance.negative();
0805
0806             collection.start_new_ring(deflate);
0807             geometry::strategy::buffer::result_code const code
0808                     = policy::apply(*it, collection, distance, segment_strategy,
0809                     join_strategy, end_strategy, point_strategy,
0810                     robust_policy, strategies);
0811
0812             collection.finish_ring(code, *it, is_interior, false);
0813         }
0814     }
0815
0816     template
0817     <
0818         typename InteriorRings,
0819         typename Collection,
0820         typename DistanceStrategy,
0821         typename SegmentStrategy,
0822         typename JoinStrategy,
0823         typename EndStrategy,
0824         typename PointStrategy,
0825         typename RobustPolicy,
0826         typename Strategies
0827     >
0828     static inline
0829     void apply_interior_rings(InteriorRings const& interior_rings,
0830             Collection& collection,
0831             DistanceStrategy const& distance,
0832             SegmentStrategy const& segment_strategy,
0833             JoinStrategy const& join_strategy,
0834             EndStrategy const& end_strategy,
0835             PointStrategy const& point_strategy,
0836             RobustPolicy const& robust_policy,
0837             Strategies const& strategies)
0838     {
0839         iterate(boost::begin(interior_rings), boost::end(interior_rings),
0840             collection, distance, segment_strategy,
0841             join_strategy, end_strategy, point_strategy,
0842             robust_policy, strategies, true);
0843     }
0844
0845 public:
0846     template
0847     <
0848         typename Collection,
0849         typename DistanceStrategy,
0850         typename SegmentStrategy,
0851         typename JoinStrategy,
0852         typename EndStrategy,
0853         typename PointStrategy,
0854         typename RobustPolicy,
0855         typename Strategies
0856     >
0857     static inline void apply(PolygonInput const& polygon,
0858             Collection& collection,
0859             DistanceStrategy const& distance,
0860             SegmentStrategy const& segment_strategy,
0861             JoinStrategy const& join_strategy,
0862             EndStrategy const& end_strategy,
0863             PointStrategy const& point_strategy,
0864             RobustPolicy const& robust_policy,
0865             Strategies const& strategies)
0866     {
0867         {
0868             collection.start_new_ring(distance.negative());
0869
0870             geometry::strategy::buffer::result_code const code
0871                 = policy::apply(exterior_ring(polygon), collection,
0872                     distance, segment_strategy,
0873                     join_strategy, end_strategy, point_strategy,
0874                     robust_policy, strategies);
0875
0876             collection.finish_ring(code, exterior_ring(polygon), false,
0877                     geometry::num_interior_rings(polygon) > 0u);
0878         }
0879
0880         apply_interior_rings(interior_rings(polygon),
0881                 collection, distance, segment_strategy,
0882                 join_strategy, end_strategy, point_strategy,
0883                 robust_policy, strategies);
0884     }
0885 };
0886
0887
0888 template
0889 <
0890     typename Multi,
0891     typename PolygonOutput
0892 >
0893 struct buffer_inserter<multi_tag, Multi, PolygonOutput>
0894     : public detail::buffer::buffer_multi
0895              <
0896                 Multi,
0897                 PolygonOutput,
0898                 dispatch::buffer_inserter
0899                 <
0900                     typename single_tag_of
0901                                 <
0902                                     typename tag<Multi>::type
0903                                 >::type,
0904                     typename boost::range_value<Multi const>::type,
0905                     typename geometry::ring_type<PolygonOutput>::type
0906                 >
0907             >
0908 {};
0909
0910
0911 } // namespace dispatch
0912 #endif // DOXYGEN_NO_DISPATCH
0913
0914 #ifndef DOXYGEN_NO_DETAIL
0915 namespace detail { namespace buffer
0916 {
0917
0918 template
0919 <
0920     typename GeometryOutput,
0921     typename GeometryInput,
0922     typename OutputIterator,
0923     typename DistanceStrategy,
0924     typename SegmentStrategy,
0925     typename JoinStrategy,
0926     typename EndStrategy,
0927     typename PointStrategy,
0928     typename Strategies,
0929     typename RobustPolicy,
0930     typename VisitPiecesPolicy
0931 >
0932 inline void buffer_inserter(GeometryInput const& geometry_input, OutputIterator out,
0933         DistanceStrategy const& distance_strategy,
0934         SegmentStrategy const& segment_strategy,
0935         JoinStrategy const& join_strategy,
0936         EndStrategy const& end_strategy,
0937         PointStrategy const& point_strategy,
0938         Strategies const& strategies,
0939         RobustPolicy const& robust_policy,
0940         VisitPiecesPolicy& visit_pieces_policy
0941     )
0942 {
0943     boost::ignore_unused(visit_pieces_policy);
0944
0945     using collection_type = detail::buffer::buffered_piece_collection
0946         <
0947             typename geometry::ring_type<GeometryOutput>::type,
0948             Strategies,
0949             DistanceStrategy,
0950             RobustPolicy
0951         >;
0952     collection_type collection(strategies, distance_strategy, robust_policy);
0953     collection_type const& const_collection = collection;
0954
0955     static constexpr bool areal = util::is_areal<GeometryInput>::value;
0956
0957     dispatch::buffer_inserter
0958         <
0959             typename tag_cast
0960                 <
0961                     typename tag<GeometryInput>::type,
0962                     multi_tag
0963                 >::type,
0964             GeometryInput,
0965             GeometryOutput
0966         >::apply(geometry_input, collection,
0967                  distance_strategy, segment_strategy, join_strategy,
0968                  end_strategy, point_strategy,
0969                  robust_policy, strategies);
0970
0971     collection.get_turns();
0972     if BOOST_GEOMETRY_CONSTEXPR (areal)
0973     {
0974         collection.check_turn_in_original();
0975     }
0976
0977     collection.verify_turns();
0978
0979     // Visit the piece collection. This does nothing (by default), but
0980     // optionally a debugging tool can be attached (e.g. console or svg),
0981     // or the piece collection can be unit-tested
0982     // phase 0: turns (before discarded)
0983     visit_pieces_policy.apply(const_collection, 0);
0984
0985     collection.discard_rings();
0986     collection.block_turns();
0987     collection.enrich();
0988
0989     // phase 1: turns (after enrichment/clustering)
0990     visit_pieces_policy.apply(const_collection, 1);
0991
0992     if BOOST_GEOMETRY_CONSTEXPR (areal)
0993     {
0994         collection.deflate_check_turns();
0995     }
0996
0997     collection.traverse();
0998
0999     // Reverse all offsetted rings / traversed rings if:
1000     // - they were generated on the negative side (deflate) of polygons
1001     // - the output is counter clockwise
1002     // and avoid reversing twice
1003     bool reverse = distance_strategy.negative() && areal;
1004     if BOOST_GEOMETRY_CONSTEXPR (geometry::point_order<GeometryOutput>::value == counterclockwise)
1005     {
1006         reverse = ! reverse;
1007     }
1008     if (reverse)
1009     {
1010         collection.reverse();
1011     }
1012
1013     if BOOST_GEOMETRY_CONSTEXPR (areal)
1014     {
1015         if (distance_strategy.negative())
1016         {
1017             collection.discard_nonintersecting_deflated_rings();
1018         }
1019     }
1020
1021     collection.template assign<GeometryOutput>(out);
1022
1023     // Visit collection again
1024     // phase 2: rings (after traversing)
1025     visit_pieces_policy.apply(const_collection, 2);
1026 }
1027
1028 template
1029 <
1030     typename GeometryOutput,
1031     typename GeometryInput,
1032     typename OutputIterator,
1033     typename DistanceStrategy,
1034     typename SegmentStrategy,
1035     typename JoinStrategy,
1036     typename EndStrategy,
1037     typename PointStrategy,
1038     typename Strategies,
1039     typename RobustPolicy
1040 >
1041 inline void buffer_inserter(GeometryInput const& geometry_input, OutputIterator out,
1042         DistanceStrategy const& distance_strategy,
1043         SegmentStrategy const& segment_strategy,
1044         JoinStrategy const& join_strategy,
1045         EndStrategy const& end_strategy,
1046         PointStrategy const& point_strategy,
1047         Strategies const& strategies,
1048         RobustPolicy const& robust_policy)
1049 {
1050     detail::buffer::visit_pieces_default_policy visitor;
1051     buffer_inserter<GeometryOutput>(geometry_input, out,
1052         distance_strategy, segment_strategy, join_strategy,
1053         end_strategy, point_strategy,
1054         strategies, robust_policy, visitor);
1055 }
1056 #endif // DOXYGEN_NO_DETAIL
1057
1058 }} // namespace detail::buffer
1059
1060 }} // namespace boost::geometry
1061
1062 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_INSERTER_HPP