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