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