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