1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2012-2020 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // This file was modified by Oracle on 2017-2021.
6 // Modifications copyright (c) 2017-2021 Oracle and/or its affiliates.
7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
8 
9 // Use, modification and distribution is subject to the Boost Software License,
10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
12 
13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_INSERTER_HPP
14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_INSERTER_HPP
15 
16 #include <cstddef>
17 #include <iterator>
18 
19 #include <boost/core/ignore_unused.hpp>
20 #include <boost/numeric/conversion/cast.hpp>
21 #include <boost/range/begin.hpp>
22 #include <boost/range/end.hpp>
23 #include <boost/range/rbegin.hpp>
24 #include <boost/range/rend.hpp>
25 #include <boost/range/size.hpp>
26 #include <boost/range/value_type.hpp>
27 
28 #include <boost/geometry/algorithms/detail/direction_code.hpp>
29 #include <boost/geometry/algorithms/detail/buffer/buffered_piece_collection.hpp>
30 #include <boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp>
31 
32 #include <boost/geometry/algorithms/num_interior_rings.hpp>
33 #include <boost/geometry/algorithms/simplify.hpp>
34 
35 #include <boost/geometry/core/assert.hpp>
36 #include <boost/geometry/core/closure.hpp>
37 #include <boost/geometry/core/exterior_ring.hpp>
38 #include <boost/geometry/core/interior_rings.hpp>
39 
40 #include <boost/geometry/strategies/buffer.hpp>
41 #include <boost/geometry/strategies/side.hpp>
42 
43 #include <boost/geometry/util/condition.hpp>
44 #include <boost/geometry/util/math.hpp>
45 #include <boost/geometry/util/type_traits.hpp>
46 
47 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
48 
49 
50 namespace boost { namespace geometry
51 {
52 
53 #ifndef DOXYGEN_NO_DETAIL
54 namespace detail { namespace buffer
55 {
56 
57 template <typename Range, typename DistanceStrategy, typename Strategies>
simplify_input(Range const & range,DistanceStrategy const & distance,Range & simplified,Strategies const & strategies)58 inline void simplify_input(Range const& range,
59         DistanceStrategy const& distance,
60         Range& simplified,
61         Strategies const& strategies)
62 {
63     // We have to simplify the ring before to avoid very small-scaled
64     // features in the original (convex/concave/convex) being enlarged
65     // in a very large scale and causing issues (IP's within pieces).
66     // This might be reconsidered later. Simplifying with a very small
67     // distance (1%% of the buffer) will never be visible in the result,
68     // if it is using round joins. For miter joins they are even more
69     // sensitive to small scale input features, however the result will
70     // look better.
71     // It also gets rid of duplicate points
72 
73     geometry::detail::simplify::simplify_range<2>::apply(range,
74         simplified, distance.simplify_distance(),
75         detail::simplify::douglas_peucker(),
76         strategies);
77 
78 }
79 
80 
81 template <typename RingOutput>
82 struct buffer_range
83 {
84     typedef typename point_type<RingOutput>::type output_point_type;
85     typedef typename coordinate_type<RingOutput>::type coordinate_type;
86 
87     template
88     <
89         typename Collection,
90         typename Point,
91         typename DistanceStrategy,
92         typename SegmentStrategy,
93         typename JoinStrategy,
94         typename EndStrategy,
95         typename RobustPolicy,
96         typename Strategies
97     >
98     static inline
add_joinboost::geometry::detail::buffer::buffer_range99     void add_join(Collection& collection,
100             Point const& penultimate_input,
101             Point const& previous_input,
102             output_point_type const& prev_perp1,
103             output_point_type const& prev_perp2,
104             Point const& input,
105             output_point_type const& perp1,
106             output_point_type const& perp2,
107             geometry::strategy::buffer::buffer_side_selector side,
108             DistanceStrategy const& distance,
109             SegmentStrategy const& segment_strategy,
110             JoinStrategy const& join_strategy,
111             EndStrategy const& end_strategy,
112             RobustPolicy const& ,
113             Strategies const& strategies)
114     {
115         geometry::strategy::buffer::join_selector const join
116                 = get_join_type(penultimate_input, previous_input, input,
117                                 strategies);
118 
119         switch(join)
120         {
121             case geometry::strategy::buffer::join_continue :
122                 // No join, we get two consecutive sides
123                 break;
124             case geometry::strategy::buffer::join_concave :
125                 {
126                     std::vector<output_point_type> range_out;
127                     range_out.push_back(prev_perp2);
128                     range_out.push_back(previous_input);
129                     collection.add_piece(geometry::strategy::buffer::buffered_concave, previous_input, range_out);
130 
131                     range_out.clear();
132                     range_out.push_back(previous_input);
133                     range_out.push_back(perp1);
134                     collection.add_piece(geometry::strategy::buffer::buffered_concave, previous_input, range_out);
135                 }
136                 break;
137             case geometry::strategy::buffer::join_spike :
138                 {
139                     // For linestrings, only add spike at one side to avoid
140                     // duplicates
141                     std::vector<output_point_type> range_out;
142                     end_strategy.apply(penultimate_input, prev_perp2, previous_input, perp1, side, distance, range_out);
143                     collection.add_endcap(end_strategy, range_out, previous_input);
144                     collection.set_current_ring_concave();
145                 }
146                 break;
147             case geometry::strategy::buffer::join_convex :
148                 {
149                     // The corner is convex, we create a join
150                     // TODO (future) - avoid a separate vector, add the piece directly
151                     output_point_type intersection_point;
152                     if (line_line_intersection::apply(prev_perp1, prev_perp2,
153                                                       perp1, perp2, previous_input,
154                                                       segment_strategy.equidistant(),
155                                                       intersection_point))
156                     {
157                         std::vector<output_point_type> range_out;
158                         if (join_strategy.apply(intersection_point,
159                                     previous_input, prev_perp2, perp1,
160                                     distance.apply(previous_input, input, side),
161                                     range_out))
162                         {
163                             collection.add_piece(geometry::strategy::buffer::buffered_join,
164                                     previous_input, range_out);
165                         }
166                     }
167                 }
168                 break;
169         }
170     }
171 
172     // Returns true if collinear point p2 continues after p0 and p1.
173     // If it turns back (spike), it returns false.
same_directionboost::geometry::detail::buffer::buffer_range174     static inline bool same_direction(output_point_type const& p0,
175             output_point_type const& p1,
176             output_point_type const& p2)
177     {
178         typedef typename cs_tag<output_point_type>::type cs_tag;
179         return direction_code<cs_tag>(p0, p1, p2) == 1;
180     }
181 
182     template <typename Strategies>
get_join_typeboost::geometry::detail::buffer::buffer_range183     static inline geometry::strategy::buffer::join_selector get_join_type(
184             output_point_type const& p0,
185             output_point_type const& p1,
186             output_point_type const& p2,
187             Strategies const& strategies)
188     {
189         int const side = strategies.side().apply(p0, p1, p2);
190         return side == -1 ? geometry::strategy::buffer::join_convex
191             :  side == 1  ? geometry::strategy::buffer::join_concave
192             :  same_direction(p0, p1, p2) ? geometry::strategy::buffer::join_continue
193             : geometry::strategy::buffer::join_spike;
194     }
195 
196     template
197     <
198         typename Collection,
199         typename Iterator,
200         typename DistanceStrategy,
201         typename SegmentStrategy,
202         typename JoinStrategy,
203         typename EndStrategy,
204         typename RobustPolicy,
205         typename Strategies
206     >
iterateboost::geometry::detail::buffer::buffer_range207     static inline geometry::strategy::buffer::result_code iterate(Collection& collection,
208                 Iterator begin, Iterator end,
209                 geometry::strategy::buffer::buffer_side_selector side,
210                 DistanceStrategy const& distance_strategy,
211                 SegmentStrategy const& segment_strategy,
212                 JoinStrategy const& join_strategy,
213                 EndStrategy const& end_strategy,
214                 RobustPolicy const& robust_policy,
215                 Strategies const& strategies,
216                 bool linear,
217                 output_point_type& first_p1,
218                 output_point_type& first_p2,
219                 output_point_type& last_p1,
220                 output_point_type& last_p2)
221     {
222         boost::ignore_unused(segment_strategy);
223 
224         typedef typename std::iterator_traits
225         <
226             Iterator
227         >::value_type point_type;
228 
229         point_type second_point, penultimate_point, ultimate_point; // last two points from begin/end
230 
231         /*
232          * last.p1    last.p2  these are the "previous (last) perpendicular points"
233          * --------------
234          * |            |
235          * *------------*____  <- *prev
236          * pup          |    | p1           "current perpendicular point 1"
237          *              |    |
238          *              |    |       this forms a "side", a side is a piece
239          *              |    |
240          *              *____| p2
241          *
242          *              ^
243          *             *it
244          *
245          * pup: penultimate_point
246          */
247 
248         bool const mark_flat
249             = linear
250                 && end_strategy.get_piece_type() == geometry::strategy::buffer::buffered_flat_end;
251 
252         geometry::strategy::buffer::result_code result = geometry::strategy::buffer::result_no_output;
253         bool first = true;
254 
255         Iterator it = begin;
256 
257         std::vector<output_point_type> generated_side;
258         generated_side.reserve(2);
259 
260         for (Iterator prev = it++; it != end; ++it)
261         {
262             generated_side.clear();
263             geometry::strategy::buffer::result_code error_code
264                 = segment_strategy.apply(*prev, *it, side,
265                                 distance_strategy, generated_side);
266 
267             if (error_code == geometry::strategy::buffer::result_no_output)
268             {
269                 // Because input is simplified, this is improbable,
270                 // but it can happen for degenerate geometries
271                 // Further handling of this side is skipped
272                 continue;
273             }
274             else if (error_code == geometry::strategy::buffer::result_error_numerical)
275             {
276                 return error_code;
277             }
278 
279             BOOST_GEOMETRY_ASSERT(! generated_side.empty());
280 
281             result = geometry::strategy::buffer::result_normal;
282 
283             if (! first)
284             {
285                  add_join(collection,
286                         penultimate_point,
287                         *prev, last_p1, last_p2,
288                         *it, generated_side.front(), generated_side.back(),
289                         side,
290                         distance_strategy, segment_strategy, join_strategy, end_strategy,
291                         robust_policy, strategies);
292             }
293 
294             collection.add_side_piece(*prev, *it, generated_side, first);
295 
296             if (first && mark_flat)
297             {
298                 collection.mark_flat_start(*prev);
299             }
300 
301             penultimate_point = *prev;
302             ultimate_point = *it;
303             last_p1 = generated_side.front();
304             last_p2 = generated_side.back();
305             prev = it;
306             if (first)
307             {
308                 first = false;
309                 second_point = *it;
310                 first_p1 = generated_side.front();
311                 first_p2 = generated_side.back();
312             }
313         }
314 
315         if (mark_flat)
316         {
317             collection.mark_flat_end(ultimate_point);
318         }
319 
320         return result;
321     }
322 };
323 
324 template
325 <
326     typename Multi,
327     typename PolygonOutput,
328     typename Policy
329 >
330 struct buffer_multi
331 {
332     template
333     <
334         typename Collection,
335         typename DistanceStrategy,
336         typename SegmentStrategy,
337         typename JoinStrategy,
338         typename EndStrategy,
339         typename PointStrategy,
340         typename RobustPolicy,
341         typename Strategies
342     >
applyboost::geometry::detail::buffer::buffer_multi343     static inline void apply(Multi const& multi,
344             Collection& collection,
345             DistanceStrategy const& distance_strategy,
346             SegmentStrategy const& segment_strategy,
347             JoinStrategy const& join_strategy,
348             EndStrategy const& end_strategy,
349             PointStrategy const& point_strategy,
350             RobustPolicy const& robust_policy,
351             Strategies const& strategies)
352     {
353         for (typename boost::range_iterator<Multi const>::type
354                 it = boost::begin(multi);
355             it != boost::end(multi);
356             ++it)
357         {
358             Policy::apply(*it, collection,
359                 distance_strategy, segment_strategy,
360                 join_strategy, end_strategy, point_strategy,
361                 robust_policy, strategies);
362         }
363     }
364 };
365 
366 struct visit_pieces_default_policy
367 {
368     template <typename Collection>
applyboost::geometry::detail::buffer::visit_pieces_default_policy369     static inline void apply(Collection const&, int)
370     {}
371 };
372 
373 template
374 <
375     typename OutputPointType,
376     typename Point,
377     typename Collection,
378     typename DistanceStrategy,
379     typename PointStrategy
380 >
buffer_point(Point const & point,Collection & collection,DistanceStrategy const & distance_strategy,PointStrategy const & point_strategy)381 inline void buffer_point(Point const& point, Collection& collection,
382         DistanceStrategy const& distance_strategy,
383         PointStrategy const& point_strategy)
384 {
385     collection.start_new_ring(false);
386     std::vector<OutputPointType> range_out;
387     point_strategy.apply(point, distance_strategy, range_out);
388     collection.add_piece(geometry::strategy::buffer::buffered_point, range_out, false);
389     collection.set_piece_center(point);
390     collection.finish_ring(geometry::strategy::buffer::result_normal);
391 }
392 
393 
394 }} // namespace detail::buffer
395 #endif // DOXYGEN_NO_DETAIL
396 
397 
398 #ifndef DOXYGEN_NO_DISPATCH
399 namespace dispatch
400 {
401 
402 template
403 <
404     typename Tag,
405     typename RingInput,
406     typename RingOutput
407 >
408 struct buffer_inserter
409 {};
410 
411 
412 
413 template
414 <
415     typename Point,
416     typename RingOutput
417 >
418 struct buffer_inserter<point_tag, Point, RingOutput>
419 {
420     template
421     <
422         typename Collection,
423         typename DistanceStrategy,
424         typename SegmentStrategy,
425         typename JoinStrategy,
426         typename EndStrategy,
427         typename PointStrategy,
428         typename RobustPolicy,
429         typename Strategies
430     >
applyboost::geometry::dispatch::buffer_inserter431     static inline void apply(Point const& point, Collection& collection,
432             DistanceStrategy const& distance_strategy,
433             SegmentStrategy const& ,
434             JoinStrategy const& ,
435             EndStrategy const& ,
436             PointStrategy const& point_strategy,
437             RobustPolicy const& ,
438             Strategies const& )
439     {
440         detail::buffer::buffer_point
441         <
442             typename point_type<RingOutput>::type
443         >(point, collection, distance_strategy, point_strategy);
444     }
445 };
446 
447 // Not a specialization, but called from specializations of ring and of polygon.
448 // Calling code starts/finishes ring before/after apply
449 template
450 <
451     typename RingInput,
452     typename RingOutput
453 >
454 struct buffer_inserter_ring
455 {
456     typedef typename point_type<RingOutput>::type output_point_type;
457 
458     template
459     <
460         typename Collection,
461         typename Iterator,
462         typename DistanceStrategy,
463         typename SegmentStrategy,
464         typename JoinStrategy,
465         typename EndStrategy,
466         typename RobustPolicy,
467         typename Strategies
468     >
iterateboost::geometry::dispatch::buffer_inserter_ring469     static inline geometry::strategy::buffer::result_code iterate(Collection& collection,
470                 Iterator begin, Iterator end,
471                 geometry::strategy::buffer::buffer_side_selector side,
472                 DistanceStrategy const& distance_strategy,
473                 SegmentStrategy const& segment_strategy,
474                 JoinStrategy const& join_strategy,
475                 EndStrategy const& end_strategy,
476                 RobustPolicy const& robust_policy,
477                 Strategies const& strategies)
478     {
479         output_point_type first_p1, first_p2, last_p1, last_p2;
480 
481         typedef detail::buffer::buffer_range<RingOutput> buffer_range;
482 
483         geometry::strategy::buffer::result_code result
484             = buffer_range::iterate(collection, begin, end,
485                 side,
486                 distance_strategy, segment_strategy, join_strategy, end_strategy,
487                 robust_policy, strategies,
488                 false, first_p1, first_p2, last_p1, last_p2);
489 
490         // Generate closing join
491         if (result == geometry::strategy::buffer::result_normal)
492         {
493             buffer_range::add_join(collection,
494                 *(end - 2),
495                 *(end - 1), last_p1, last_p2,
496                 *(begin + 1), first_p1, first_p2,
497                 side,
498                 distance_strategy, segment_strategy, join_strategy, end_strategy,
499                 robust_policy, strategies);
500         }
501 
502         // Buffer is closed automatically by last closing corner
503         return result;
504     }
505 
506     template
507     <
508         typename Collection,
509         typename DistanceStrategy,
510         typename SegmentStrategy,
511         typename JoinStrategy,
512         typename EndStrategy,
513         typename PointStrategy,
514         typename RobustPolicy,
515         typename Strategies
516     >
applyboost::geometry::dispatch::buffer_inserter_ring517     static inline geometry::strategy::buffer::result_code apply(RingInput const& ring,
518             Collection& collection,
519             DistanceStrategy const& distance,
520             SegmentStrategy const& segment_strategy,
521             JoinStrategy const& join_strategy,
522             EndStrategy const& end_strategy,
523             PointStrategy const& point_strategy,
524             RobustPolicy const& robust_policy,
525             Strategies const& strategies)
526     {
527         RingInput simplified;
528         detail::buffer::simplify_input(ring, distance, simplified, strategies);
529 
530         geometry::strategy::buffer::result_code code = geometry::strategy::buffer::result_no_output;
531 
532         std::size_t n = boost::size(simplified);
533         std::size_t const min_points = core_detail::closure::minimum_ring_size
534             <
535                 geometry::closure<RingInput>::value
536             >::value;
537 
538         if (n >= min_points)
539         {
540             detail::closed_clockwise_view<RingInput const> view(simplified);
541             if (distance.negative())
542             {
543                 // Walk backwards (rings will be reversed afterwards)
544                 code = iterate(collection, boost::rbegin(view), boost::rend(view),
545                         geometry::strategy::buffer::buffer_side_right,
546                         distance, segment_strategy, join_strategy, end_strategy,
547                         robust_policy, strategies);
548             }
549             else
550             {
551                 code = iterate(collection, boost::begin(view), boost::end(view),
552                         geometry::strategy::buffer::buffer_side_left,
553                         distance, segment_strategy, join_strategy, end_strategy,
554                         robust_policy, strategies);
555             }
556         }
557 
558         if (code == geometry::strategy::buffer::result_no_output && n >= 1)
559         {
560             // Use point_strategy to buffer degenerated ring
561             detail::buffer::buffer_point<output_point_type>
562                 (
563                     geometry::range::front(simplified),
564                     collection, distance, point_strategy
565                 );
566         }
567         return code;
568     }
569 };
570 
571 
572 template
573 <
574     typename RingInput,
575     typename RingOutput
576 >
577 struct buffer_inserter<ring_tag, RingInput, RingOutput>
578 {
579     template
580     <
581         typename Collection,
582         typename DistanceStrategy,
583         typename SegmentStrategy,
584         typename JoinStrategy,
585         typename EndStrategy,
586         typename PointStrategy,
587         typename RobustPolicy,
588         typename Strategies
589     >
applyboost::geometry::dispatch::buffer_inserter590     static inline geometry::strategy::buffer::result_code apply(RingInput const& ring,
591             Collection& collection,
592             DistanceStrategy const& distance,
593             SegmentStrategy const& segment_strategy,
594             JoinStrategy const& join_strategy,
595             EndStrategy const& end_strategy,
596             PointStrategy const& point_strategy,
597             RobustPolicy const& robust_policy,
598             Strategies const& strategies)
599     {
600         collection.start_new_ring(distance.negative());
601         geometry::strategy::buffer::result_code const code
602             = buffer_inserter_ring<RingInput, RingOutput>::apply(ring,
603                 collection, distance,
604                 segment_strategy, join_strategy, end_strategy, point_strategy,
605                 robust_policy, strategies);
606         collection.finish_ring(code, ring, false, false);
607         return code;
608     }
609 };
610 
611 template
612 <
613     typename Linestring,
614     typename Polygon
615 >
616 struct buffer_inserter<linestring_tag, Linestring, Polygon>
617 {
618     typedef typename ring_type<Polygon>::type output_ring_type;
619     typedef typename point_type<output_ring_type>::type output_point_type;
620     typedef typename point_type<Linestring>::type input_point_type;
621 
622     template
623     <
624         typename Collection,
625         typename Iterator,
626         typename DistanceStrategy,
627         typename SegmentStrategy,
628         typename JoinStrategy,
629         typename EndStrategy,
630         typename RobustPolicy,
631         typename Strategies
632     >
iterateboost::geometry::dispatch::buffer_inserter633     static inline geometry::strategy::buffer::result_code iterate(Collection& collection,
634                 Iterator begin, Iterator end,
635                 geometry::strategy::buffer::buffer_side_selector side,
636                 DistanceStrategy const& distance_strategy,
637                 SegmentStrategy const& segment_strategy,
638                 JoinStrategy const& join_strategy,
639                 EndStrategy const& end_strategy,
640                 RobustPolicy const& robust_policy,
641                 Strategies const& strategies,
642                 output_point_type& first_p1)
643     {
644         input_point_type const& ultimate_point = *(end - 1);
645         input_point_type const& penultimate_point = *(end - 2);
646 
647         // For the end-cap, we need to have the last perpendicular point on the
648         // other side of the linestring. If it is the second pass (right),
649         // we have it already from the first phase (left).
650         // But for the first pass, we have to generate it
651         output_point_type reverse_p1;
652         if (side == geometry::strategy::buffer::buffer_side_right)
653         {
654             reverse_p1 = first_p1;
655         }
656         else
657         {
658             std::vector<output_point_type> generated_side;
659             geometry::strategy::buffer::result_code code
660                 = segment_strategy.apply(ultimate_point, penultimate_point,
661                     geometry::strategy::buffer::buffer_side_right,
662                     distance_strategy, generated_side);
663             if (code != geometry::strategy::buffer::result_normal)
664             {
665                 // No output or numerical error
666                 return code;
667             }
668             reverse_p1 = generated_side.front();
669         }
670 
671         output_point_type first_p2, last_p1, last_p2;
672 
673         geometry::strategy::buffer::result_code result
674             = detail::buffer::buffer_range<output_ring_type>::iterate(collection,
675                 begin, end, side,
676                 distance_strategy, segment_strategy, join_strategy, end_strategy,
677                 robust_policy, strategies,
678                 true, first_p1, first_p2, last_p1, last_p2);
679 
680         if (result == geometry::strategy::buffer::result_normal)
681         {
682             std::vector<output_point_type> range_out;
683             end_strategy.apply(penultimate_point, last_p2, ultimate_point, reverse_p1,
684                                side, distance_strategy, range_out);
685             collection.add_endcap(end_strategy, range_out, ultimate_point);
686         }
687         return result;
688     }
689 
690     template
691     <
692         typename Collection,
693         typename DistanceStrategy,
694         typename SegmentStrategy,
695         typename JoinStrategy,
696         typename EndStrategy,
697         typename PointStrategy,
698         typename RobustPolicy,
699         typename Strategies
700     >
applyboost::geometry::dispatch::buffer_inserter701     static inline geometry::strategy::buffer::result_code apply(Linestring const& linestring,
702             Collection& collection,
703             DistanceStrategy const& distance,
704             SegmentStrategy const& segment_strategy,
705             JoinStrategy const& join_strategy,
706             EndStrategy const& end_strategy,
707             PointStrategy const& point_strategy,
708             RobustPolicy const& robust_policy,
709             Strategies const& strategies)
710     {
711         Linestring simplified;
712         detail::buffer::simplify_input(linestring, distance, simplified, strategies);
713 
714         geometry::strategy::buffer::result_code code = geometry::strategy::buffer::result_no_output;
715         std::size_t n = boost::size(simplified);
716         if (n > 1)
717         {
718             collection.start_new_ring(false);
719             output_point_type first_p1;
720             code = iterate(collection,
721                     boost::begin(simplified), boost::end(simplified),
722                     geometry::strategy::buffer::buffer_side_left,
723                     distance, segment_strategy, join_strategy, end_strategy,
724                     robust_policy, strategies,
725                     first_p1);
726 
727             if (code == geometry::strategy::buffer::result_normal)
728             {
729                 code = iterate(collection,
730                         boost::rbegin(simplified), boost::rend(simplified),
731                         geometry::strategy::buffer::buffer_side_right,
732                         distance, segment_strategy, join_strategy, end_strategy,
733                         robust_policy, strategies,
734                         first_p1);
735             }
736             collection.finish_ring(code);
737         }
738         if (code == geometry::strategy::buffer::result_no_output && n >= 1)
739         {
740             // Use point_strategy to buffer degenerated linestring
741             detail::buffer::buffer_point<output_point_type>
742                 (
743                     geometry::range::front(simplified),
744                     collection, distance, point_strategy
745                 );
746         }
747         return code;
748     }
749 };
750 
751 
752 template
753 <
754     typename PolygonInput,
755     typename PolygonOutput
756 >
757 struct buffer_inserter<polygon_tag, PolygonInput, PolygonOutput>
758 {
759 private:
760     typedef typename ring_type<PolygonInput>::type input_ring_type;
761     typedef typename ring_type<PolygonOutput>::type output_ring_type;
762 
763     typedef buffer_inserter_ring<input_ring_type, output_ring_type> policy;
764 
765 
766     template
767     <
768         typename Iterator,
769         typename Collection,
770         typename DistanceStrategy,
771         typename SegmentStrategy,
772         typename JoinStrategy,
773         typename EndStrategy,
774         typename PointStrategy,
775         typename RobustPolicy,
776         typename Strategies
777     >
778     static inline
iterateboost::geometry::dispatch::buffer_inserter779     void iterate(Iterator begin, Iterator end,
780             Collection& collection,
781             DistanceStrategy const& distance,
782             SegmentStrategy const& segment_strategy,
783             JoinStrategy const& join_strategy,
784             EndStrategy const& end_strategy,
785             PointStrategy const& point_strategy,
786             RobustPolicy const& robust_policy,
787             Strategies const& strategies,
788             bool is_interior)
789     {
790         for (Iterator it = begin; it != end; ++it)
791         {
792             // For exterior rings, it deflates if distance is negative.
793             // For interior rings, it is vice versa
794             bool const deflate = is_interior
795                     ? ! distance.negative()
796                     : distance.negative();
797 
798             collection.start_new_ring(deflate);
799             geometry::strategy::buffer::result_code const code
800                     = policy::apply(*it, collection, distance, segment_strategy,
801                     join_strategy, end_strategy, point_strategy,
802                     robust_policy, strategies);
803 
804             collection.finish_ring(code, *it, is_interior, false);
805         }
806     }
807 
808     template
809     <
810         typename InteriorRings,
811         typename Collection,
812         typename DistanceStrategy,
813         typename SegmentStrategy,
814         typename JoinStrategy,
815         typename EndStrategy,
816         typename PointStrategy,
817         typename RobustPolicy,
818         typename Strategies
819     >
820     static inline
apply_interior_ringsboost::geometry::dispatch::buffer_inserter821     void apply_interior_rings(InteriorRings const& interior_rings,
822             Collection& collection,
823             DistanceStrategy const& distance,
824             SegmentStrategy const& segment_strategy,
825             JoinStrategy const& join_strategy,
826             EndStrategy const& end_strategy,
827             PointStrategy const& point_strategy,
828             RobustPolicy const& robust_policy,
829             Strategies const& strategies)
830     {
831         iterate(boost::begin(interior_rings), boost::end(interior_rings),
832             collection, distance, segment_strategy,
833             join_strategy, end_strategy, point_strategy,
834             robust_policy, strategies, true);
835     }
836 
837 public:
838     template
839     <
840         typename Collection,
841         typename DistanceStrategy,
842         typename SegmentStrategy,
843         typename JoinStrategy,
844         typename EndStrategy,
845         typename PointStrategy,
846         typename RobustPolicy,
847         typename Strategies
848     >
applyboost::geometry::dispatch::buffer_inserter849     static inline void apply(PolygonInput const& polygon,
850             Collection& collection,
851             DistanceStrategy const& distance,
852             SegmentStrategy const& segment_strategy,
853             JoinStrategy const& join_strategy,
854             EndStrategy const& end_strategy,
855             PointStrategy const& point_strategy,
856             RobustPolicy const& robust_policy,
857             Strategies const& strategies)
858     {
859         {
860             collection.start_new_ring(distance.negative());
861 
862             geometry::strategy::buffer::result_code const code
863                 = policy::apply(exterior_ring(polygon), collection,
864                     distance, segment_strategy,
865                     join_strategy, end_strategy, point_strategy,
866                     robust_policy, strategies);
867 
868             collection.finish_ring(code, exterior_ring(polygon), false,
869                     geometry::num_interior_rings(polygon) > 0u);
870         }
871 
872         apply_interior_rings(interior_rings(polygon),
873                 collection, distance, segment_strategy,
874                 join_strategy, end_strategy, point_strategy,
875                 robust_policy, strategies);
876     }
877 };
878 
879 
880 template
881 <
882     typename Multi,
883     typename PolygonOutput
884 >
885 struct buffer_inserter<multi_tag, Multi, PolygonOutput>
886     : public detail::buffer::buffer_multi
887              <
888                 Multi,
889                 PolygonOutput,
890                 dispatch::buffer_inserter
891                 <
892                     typename single_tag_of
893                                 <
894                                     typename tag<Multi>::type
895                                 >::type,
896                     typename boost::range_value<Multi const>::type,
897                     typename geometry::ring_type<PolygonOutput>::type
898                 >
899             >
900 {};
901 
902 
903 } // namespace dispatch
904 #endif // DOXYGEN_NO_DISPATCH
905 
906 #ifndef DOXYGEN_NO_DETAIL
907 namespace detail { namespace buffer
908 {
909 
910 template
911 <
912     typename GeometryOutput,
913     typename GeometryInput,
914     typename OutputIterator,
915     typename DistanceStrategy,
916     typename SegmentStrategy,
917     typename JoinStrategy,
918     typename EndStrategy,
919     typename PointStrategy,
920     typename Strategies,
921     typename RobustPolicy,
922     typename VisitPiecesPolicy
923 >
buffer_inserter(GeometryInput const & geometry_input,OutputIterator out,DistanceStrategy const & distance_strategy,SegmentStrategy const & segment_strategy,JoinStrategy const & join_strategy,EndStrategy const & end_strategy,PointStrategy const & point_strategy,Strategies const & strategies,RobustPolicy const & robust_policy,VisitPiecesPolicy & visit_pieces_policy)924 inline void buffer_inserter(GeometryInput const& geometry_input, OutputIterator out,
925         DistanceStrategy const& distance_strategy,
926         SegmentStrategy const& segment_strategy,
927         JoinStrategy const& join_strategy,
928         EndStrategy const& end_strategy,
929         PointStrategy const& point_strategy,
930         Strategies const& strategies,
931         RobustPolicy const& robust_policy,
932         VisitPiecesPolicy& visit_pieces_policy
933     )
934 {
935     boost::ignore_unused(visit_pieces_policy);
936 
937     typedef detail::buffer::buffered_piece_collection
938     <
939         typename geometry::ring_type<GeometryOutput>::type,
940         Strategies,
941         DistanceStrategy,
942         RobustPolicy
943     > collection_type;
944     collection_type collection(strategies, distance_strategy, robust_policy);
945     collection_type const& const_collection = collection;
946 
947     bool const areal = util::is_areal<GeometryInput>::value;
948 
949     dispatch::buffer_inserter
950         <
951             typename tag_cast
952                 <
953                     typename tag<GeometryInput>::type,
954                     multi_tag
955                 >::type,
956             GeometryInput,
957             GeometryOutput
958         >::apply(geometry_input, collection,
959                  distance_strategy, segment_strategy, join_strategy,
960                  end_strategy, point_strategy,
961                  robust_policy, strategies);
962 
963     collection.get_turns();
964     if (BOOST_GEOMETRY_CONDITION(areal))
965     {
966         collection.check_turn_in_original();
967     }
968 
969     collection.verify_turns();
970 
971     // Visit the piece collection. This does nothing (by default), but
972     // optionally a debugging tool can be attached (e.g. console or svg),
973     // or the piece collection can be unit-tested
974     // phase 0: turns (before discarded)
975     visit_pieces_policy.apply(const_collection, 0);
976 
977     collection.discard_rings();
978     collection.block_turns();
979     collection.enrich();
980 
981     // phase 1: turns (after enrichment/clustering)
982     visit_pieces_policy.apply(const_collection, 1);
983 
984     if (BOOST_GEOMETRY_CONDITION(areal))
985     {
986         collection.deflate_check_turns();
987     }
988 
989     collection.traverse();
990 
991     // Reverse all offsetted rings / traversed rings if:
992     // - they were generated on the negative side (deflate) of polygons
993     // - the output is counter clockwise
994     // and avoid reversing twice
995     bool reverse = distance_strategy.negative() && areal;
996     if (BOOST_GEOMETRY_CONDITION(
997             geometry::point_order<GeometryOutput>::value == counterclockwise))
998     {
999         reverse = ! reverse;
1000     }
1001     if (reverse)
1002     {
1003         collection.reverse();
1004     }
1005 
1006     if (BOOST_GEOMETRY_CONDITION(distance_strategy.negative() && areal))
1007     {
1008         collection.discard_nonintersecting_deflated_rings();
1009     }
1010 
1011     collection.template assign<GeometryOutput>(out);
1012 
1013     // Visit collection again
1014     // phase 2: rings (after traversing)
1015     visit_pieces_policy.apply(const_collection, 2);
1016 }
1017 
1018 template
1019 <
1020     typename GeometryOutput,
1021     typename GeometryInput,
1022     typename OutputIterator,
1023     typename DistanceStrategy,
1024     typename SegmentStrategy,
1025     typename JoinStrategy,
1026     typename EndStrategy,
1027     typename PointStrategy,
1028     typename Strategies,
1029     typename RobustPolicy
1030 >
buffer_inserter(GeometryInput const & geometry_input,OutputIterator out,DistanceStrategy const & distance_strategy,SegmentStrategy const & segment_strategy,JoinStrategy const & join_strategy,EndStrategy const & end_strategy,PointStrategy const & point_strategy,Strategies const & strategies,RobustPolicy const & robust_policy)1031 inline void buffer_inserter(GeometryInput const& geometry_input, OutputIterator out,
1032         DistanceStrategy const& distance_strategy,
1033         SegmentStrategy const& segment_strategy,
1034         JoinStrategy const& join_strategy,
1035         EndStrategy const& end_strategy,
1036         PointStrategy const& point_strategy,
1037         Strategies const& strategies,
1038         RobustPolicy const& robust_policy)
1039 {
1040     detail::buffer::visit_pieces_default_policy visitor;
1041     buffer_inserter<GeometryOutput>(geometry_input, out,
1042         distance_strategy, segment_strategy, join_strategy,
1043         end_strategy, point_strategy,
1044         strategies, robust_policy, visitor);
1045 }
1046 #endif // DOXYGEN_NO_DETAIL
1047 
1048 }} // namespace detail::buffer
1049 
1050 }} // namespace boost::geometry
1051 
1052 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_INSERTER_HPP
1053