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