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