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