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