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