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