]> git.proxmox.com Git - ceph.git/blame - ceph/src/boost/boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp
projects / ceph.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
import quincy beta 17.1.0
[ceph.git] / ceph / src / boost / boost / geometry / algorithms / detail / buffer / buffer_inserter.hpp
CommitLineData
7c673cae
FG		 1// Boost.Geometry (aka GGL, Generic Geometry Library)
2
20effc67 3// Copyright (c) 2012-2020 Barend Gehrels, Amsterdam, the Netherlands.
7c673cae 4
20effc67
TL		 5// This file was modified by Oracle on 2017-2020.
6// Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
b32b8144
FG		 7// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
8
7c673cae
FG		 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
7c673cae
FG		 19#include <boost/core/ignore_unused.hpp>
20#include <boost/numeric/conversion/cast.hpp>
20effc67
TL		 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>
7c673cae
FG		 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
7c673cae
FG		 40#include <boost/geometry/strategies/buffer.hpp>
41#include <boost/geometry/strategies/side.hpp>
7c673cae 42
20effc67
TL		 43#include <boost/geometry/util/condition.hpp>
44#include <boost/geometry/util/math.hpp>
45#include <boost/geometry/util/type_traits.hpp>
92f5a8d4 46
7c673cae
FG		 47#include <boost/geometry/views/detail/normalized_view.hpp>
48
7c673cae
FG		 49
50namespace boost { namespace geometry
51{
52
53#ifndef DOXYGEN_NO_DETAIL
54namespace detail { namespace buffer
55{
56
57template <typename Range, typename DistanceStrategy>
58inline 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
7c673cae 71
11fdf7f2
TL		 72 typedef typename geometry::point_type<Range>::type point_type;
73 typedef typename strategy::distance::services::default_strategy
7c673cae 74 <
11fdf7f2
TL		 75 point_tag, segment_tag, point_type
76 >::type ds_strategy_type;
77 typedef strategy::simplify::douglas_peucker
7c673cae 78 <
11fdf7f2
TL		 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());
7c673cae 85
7c673cae
FG		 86}
87
88
89template <typename RingOutput>
90struct 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,
b32b8144 102 typename RobustPolicy,
92f5a8d4 103 typename SideStrategy
7c673cae
FG		 104 >
105 static inline
106 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,
b32b8144 114 geometry::strategy::buffer::buffer_side_selector side,
7c673cae
FG		 115 DistanceStrategy const& distance,
116 JoinStrategy const& join_strategy,
117 EndStrategy const& end_strategy,
b32b8144 118 RobustPolicy const& ,
20effc67 119 SideStrategy const& side_strategy)
7c673cae 120 {
20effc67
TL		 121 geometry::strategy::buffer::join_selector const join
122 = get_join_type(penultimate_input, previous_input, input,
123 side_strategy);
7c673cae
FG		 124
125 switch(join)
126 {
b32b8144 127 case geometry::strategy::buffer::join_continue :
7c673cae
FG		 128 // No join, we get two consecutive sides
129 break;
b32b8144 130 case geometry::strategy::buffer::join_concave :
7c673cae
FG		 131 {
132 std::vector<output_point_type> range_out;
133 range_out.push_back(prev_perp2);
134 range_out.push_back(previous_input);
b32b8144 135 collection.add_piece(geometry::strategy::buffer::buffered_concave, previous_input, range_out);
7c673cae
FG		 136
137 range_out.clear();
138 range_out.push_back(previous_input);
139 range_out.push_back(perp1);
b32b8144 140 collection.add_piece(geometry::strategy::buffer::buffered_concave, previous_input, range_out);
7c673cae
FG		 141 }
142 break;
b32b8144 143 case geometry::strategy::buffer::join_spike :
7c673cae
FG		 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;
b32b8144 153 case geometry::strategy::buffer::join_convex :
7c673cae
FG		 154 {
155 // The corner is convex, we create a join
156 // TODO (future) - avoid a separate vector, add the piece directly
20effc67
TL		 157 output_point_type intersection_point;
158 if (line_line_intersection::apply(perp1, perp2,
159 prev_perp1, prev_perp2, intersection_point))
7c673cae 160 {
20effc67
TL		 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 }
7c673cae
FG		 170 }
171 }
172 break;
173 }
174 }
175
20effc67
TL		 176 // Returns true if collinear point p2 continues after p0 and p1.
177 // If it turns back (spike), it returns false.
178 static inline bool same_direction(output_point_type const& p0,
92f5a8d4
TL		 179 output_point_type const& p1,
180 output_point_type const& p2)
181 {
20effc67
TL		 182 typedef typename cs_tag<output_point_type>::type cs_tag;
183 return direction_code<cs_tag>(p0, p1, p2) == 1;
92f5a8d4
TL		 184 }
185
186 template <typename SideStrategy>
b32b8144 187 static inline geometry::strategy::buffer::join_selector get_join_type(
7c673cae
FG		 188 output_point_type const& p0,
189 output_point_type const& p1,
b32b8144 190 output_point_type const& p2,
92f5a8d4 191 SideStrategy const& side_strategy)
7c673cae 192 {
92f5a8d4 193 int const side = side_strategy.apply(p0, p1, p2);
b32b8144
FG		 194 return side == -1 ? geometry::strategy::buffer::join_convex
195 : side == 1 ? geometry::strategy::buffer::join_concave
20effc67 196 : same_direction(p0, p1, p2) ? geometry::strategy::buffer::join_continue
b32b8144 197 : geometry::strategy::buffer::join_spike;
7c673cae
FG		 198 }
199
200 template
201 <
202 typename Collection,
203 typename Iterator,
204 typename DistanceStrategy,
205 typename SideStrategy,
206 typename JoinStrategy,
207 typename EndStrategy,
b32b8144
FG		 208 typename RobustPolicy,
209 typename Strategy
7c673cae 210 >
b32b8144 211 static inline geometry::strategy::buffer::result_code iterate(Collection& collection,
7c673cae 212 Iterator begin, Iterator end,
b32b8144 213 geometry::strategy::buffer::buffer_side_selector side,
7c673cae
FG		 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,
b32b8144
FG		 219 Strategy const& strategy, // side strategy
220 bool linear,
7c673cae
FG		 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
b32b8144
FG		 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;
7c673cae
FG		 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();
b32b8144 267 geometry::strategy::buffer::result_code error_code
7c673cae
FG		 268 = side_strategy.apply(*prev, *it, side,
269 distance_strategy, generated_side);
270
b32b8144 271 if (error_code == geometry::strategy::buffer::result_no_output)
7c673cae
FG		 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 }
b32b8144 278 else if (error_code == geometry::strategy::buffer::result_error_numerical)
7c673cae
FG		 279 {
280 return error_code;
281 }
282
283 BOOST_GEOMETRY_ASSERT(! generated_side.empty());
284
b32b8144 285 result = geometry::strategy::buffer::result_normal;
7c673cae
FG		 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,
b32b8144 295 robust_policy, strategy);
7c673cae
FG		 296 }
297
298 collection.add_side_piece(*prev, *it, generated_side, first);
299
b32b8144
FG		 300 if (first && mark_flat)
301 {
20effc67 302 collection.mark_flat_start(*prev);
b32b8144
FG		 303 }
304
7c673cae
FG		 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 }
b32b8144
FG		 318
319 if (mark_flat)
320 {
20effc67 321 collection.mark_flat_end(ultimate_point);
b32b8144
FG		 322 }
323
7c673cae
FG		 324 return result;
325 }
326};
327
328template
329<
330 typename Multi,
331 typename PolygonOutput,
332 typename Policy
333>
334struct buffer_multi
335{
336 template
337 <
338 typename Collection,
339 typename DistanceStrategy,
340 typename SideStrategy,
341 typename JoinStrategy,
342 typename EndStrategy,
343 typename PointStrategy,
b32b8144
FG		 344 typename RobustPolicy,
345 typename Strategy
7c673cae
FG		 346 >
347 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,
b32b8144
FG		 354 RobustPolicy const& robust_policy,
355 Strategy const& strategy) // side strategy
7c673cae
FG		 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,
b32b8144 365 robust_policy, strategy);
7c673cae
FG		 366 }
367 }
368};
369
370struct visit_pieces_default_policy
371{
372 template <typename Collection>
373 static inline void apply(Collection const&, int)
374 {}
375};
376
377template
378<
379 typename OutputPointType,
380 typename Point,
381 typename Collection,
382 typename DistanceStrategy,
383 typename PointStrategy
384>
385inline void buffer_point(Point const& point, Collection& collection,
386 DistanceStrategy const& distance_strategy,
387 PointStrategy const& point_strategy)
388{
b32b8144 389 collection.start_new_ring(false);
7c673cae
FG		 390 std::vector<OutputPointType> range_out;
391 point_strategy.apply(point, distance_strategy, range_out);
b32b8144 392 collection.add_piece(geometry::strategy::buffer::buffered_point, range_out, false);
7c673cae 393 collection.set_piece_center(point);
b32b8144 394 collection.finish_ring(geometry::strategy::buffer::result_normal);
7c673cae
FG		 395}
396
397
398}} // namespace detail::buffer
399#endif // DOXYGEN_NO_DETAIL
400
401
402#ifndef DOXYGEN_NO_DISPATCH
403namespace dispatch
404{
405
406template
407<
408 typename Tag,
409 typename RingInput,
410 typename RingOutput
411>
412struct buffer_inserter
413{};
414
415
416
417template
418<
419 typename Point,
420 typename RingOutput
421>
422struct 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,
b32b8144
FG		 432 typename RobustPolicy,
433 typename Strategy
7c673cae
FG		 434 >
435 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,
b32b8144
FG		 441 RobustPolicy const& ,
442 Strategy const& ) // side strategy
7c673cae
FG		 443 {
444 detail::buffer::buffer_point
445 <
446 typename point_type<RingOutput>::type
447 >(point, collection, distance_strategy, point_strategy);
448 }
449};
450
b32b8144
FG		 451// Not a specialization, but called from specializations of ring and of polygon.
452// Calling code starts/finishes ring before/after apply
7c673cae
FG		 453template
454<
455 typename RingInput,
456 typename RingOutput
457>
b32b8144 458struct buffer_inserter_ring
7c673cae
FG		 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,
b32b8144
FG		 470 typename RobustPolicy,
471 typename Strategy
7c673cae 472 >
b32b8144 473 static inline geometry::strategy::buffer::result_code iterate(Collection& collection,
7c673cae 474 Iterator begin, Iterator end,
b32b8144 475 geometry::strategy::buffer::buffer_side_selector side,
7c673cae
FG		 476 DistanceStrategy const& distance_strategy,
477 SideStrategy const& side_strategy,
478 JoinStrategy const& join_strategy,
479 EndStrategy const& end_strategy,
b32b8144
FG		 480 RobustPolicy const& robust_policy,
481 Strategy const& strategy) // side strategy
7c673cae
FG		 482 {
483 output_point_type first_p1, first_p2, last_p1, last_p2;
484
485 typedef detail::buffer::buffer_range<RingOutput> buffer_range;
486
b32b8144 487 geometry::strategy::buffer::result_code result
7c673cae
FG		 488 = buffer_range::iterate(collection, begin, end,
489 side,
b32b8144
FG		 490 distance_strategy, side_strategy, join_strategy, end_strategy,
491 robust_policy, strategy,
492 false, first_p1, first_p2, last_p1, last_p2);
7c673cae
FG		 493
494 // Generate closing join
b32b8144 495 if (result == geometry::strategy::buffer::result_normal)
7c673cae
FG		 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,
b32b8144 503 robust_policy, strategy);
7c673cae
FG		 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,
b32b8144
FG		 518 typename RobustPolicy,
519 typename Strategy
7c673cae 520 >
b32b8144 521 static inline geometry::strategy::buffer::result_code apply(RingInput const& ring,
7c673cae
FG		 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,
b32b8144
FG		 528 RobustPolicy const& robust_policy,
529 Strategy const& strategy) // side strategy
7c673cae
FG		 530 {
531 RingInput simplified;
532 detail::buffer::simplify_input(ring, distance, simplified);
533
b32b8144 534 geometry::strategy::buffer::result_code code = geometry::strategy::buffer::result_no_output;
7c673cae
FG		 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),
b32b8144
FG		 549 geometry::strategy::buffer::buffer_side_right,
550 distance, side_strategy, join_strategy, end_strategy,
551 robust_policy, strategy);
7c673cae
FG		 552 }
553 else
554 {
555 code = iterate(collection, boost::begin(view), boost::end(view),
b32b8144
FG		 556 geometry::strategy::buffer::buffer_side_left,
557 distance, side_strategy, join_strategy, end_strategy,
558 robust_policy, strategy);
7c673cae
FG		 559 }
560 }
561
b32b8144 562 if (code == geometry::strategy::buffer::result_no_output && n >= 1)
7c673cae
FG		 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
b32b8144
FG		 576template
577<
578 typename RingInput,
579 typename RingOutput
580>
581struct 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 >
594 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);
f67539c2 610 collection.finish_ring(code, ring, false, false);
b32b8144
FG		 611 return code;
612 }
613};
614
7c673cae
FG		 615template
616<
617 typename Linestring,
618 typename Polygon
619>
620struct 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,
b32b8144
FG		 634 typename RobustPolicy,
635 typename Strategy
7c673cae 636 >
b32b8144 637 static inline geometry::strategy::buffer::result_code iterate(Collection& collection,
7c673cae 638 Iterator begin, Iterator end,
b32b8144 639 geometry::strategy::buffer::buffer_side_selector side,
7c673cae
FG		 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,
b32b8144 645 Strategy const& strategy, // side strategy
7c673cae
FG		 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;
b32b8144 656 if (side == geometry::strategy::buffer::buffer_side_right)
7c673cae
FG		 657 {
658 reverse_p1 = first_p1;
659 }
660 else
661 {
662 std::vector<output_point_type> generated_side;
b32b8144 663 geometry::strategy::buffer::result_code code
7c673cae 664 = side_strategy.apply(ultimate_point, penultimate_point,
b32b8144 665 geometry::strategy::buffer::buffer_side_right,
7c673cae 666 distance_strategy, generated_side);
b32b8144 667 if (code != geometry::strategy::buffer::result_normal)
7c673cae
FG		 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
b32b8144 677 geometry::strategy::buffer::result_code result
7c673cae
FG		 678 = detail::buffer::buffer_range<output_ring_type>::iterate(collection,
679 begin, end, side,
b32b8144
FG		 680 distance_strategy, side_strategy, join_strategy, end_strategy,
681 robust_policy, strategy,
682 true, first_p1, first_p2, last_p1, last_p2);
7c673cae 683
b32b8144 684 if (result == geometry::strategy::buffer::result_normal)
7c673cae
FG		 685 {
686 std::vector<output_point_type> range_out;
b32b8144
FG		 687 end_strategy.apply(penultimate_point, last_p2, ultimate_point, reverse_p1,
688 side, distance_strategy, range_out);
7c673cae
FG		 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,
b32b8144
FG		 702 typename RobustPolicy,
703 typename Strategy
7c673cae 704 >
b32b8144
FG		 705 static inline geometry::strategy::buffer::result_code apply(Linestring const& linestring,
706 Collection& collection,
7c673cae
FG		 707 DistanceStrategy const& distance,
708 SideStrategy const& side_strategy,
709 JoinStrategy const& join_strategy,
710 EndStrategy const& end_strategy,
711 PointStrategy const& point_strategy,
b32b8144
FG		 712 RobustPolicy const& robust_policy,
713 Strategy const& strategy) // side strategy
7c673cae
FG		 714 {
715 Linestring simplified;
716 detail::buffer::simplify_input(linestring, distance, simplified);
717
b32b8144 718 geometry::strategy::buffer::result_code code = geometry::strategy::buffer::result_no_output;
7c673cae
FG		 719 std::size_t n = boost::size(simplified);
720 if (n > 1)
721 {
b32b8144 722 collection.start_new_ring(false);
7c673cae
FG		 723 output_point_type first_p1;
724 code = iterate(collection,
725 boost::begin(simplified), boost::end(simplified),
b32b8144
FG		 726 geometry::strategy::buffer::buffer_side_left,
727 distance, side_strategy, join_strategy, end_strategy,
728 robust_policy, strategy,
7c673cae
FG		 729 first_p1);
730
b32b8144 731 if (code == geometry::strategy::buffer::result_normal)
7c673cae
FG		 732 {
733 code = iterate(collection,
734 boost::rbegin(simplified), boost::rend(simplified),
b32b8144
FG		 735 geometry::strategy::buffer::buffer_side_right,
736 distance, side_strategy, join_strategy, end_strategy,
737 robust_policy, strategy,
7c673cae
FG		 738 first_p1);
739 }
740 collection.finish_ring(code);
741 }
b32b8144 742 if (code == geometry::strategy::buffer::result_no_output && n >= 1)
7c673cae
FG		 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
756template
757<
758 typename PolygonInput,
759 typename PolygonOutput
760>
761struct buffer_inserter<polygon_tag, PolygonInput, PolygonOutput>
762{
763private:
764 typedef typename ring_type<PolygonInput>::type input_ring_type;
765 typedef typename ring_type<PolygonOutput>::type output_ring_type;
766
b32b8144 767 typedef buffer_inserter_ring<input_ring_type, output_ring_type> policy;
7c673cae
FG		 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,
b32b8144
FG		 779 typename RobustPolicy,
780 typename Strategy
7c673cae
FG		 781 >
782 static inline
783 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,
b32b8144 791 Strategy const& strategy, // side strategy
7c673cae
FG		 792 bool is_interior)
793 {
794 for (Iterator it = begin; it != end; ++it)
795 {
b32b8144
FG		 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
7c673cae
FG		 804 = policy::apply(*it, collection, distance, side_strategy,
805 join_strategy, end_strategy, point_strategy,
b32b8144 806 robust_policy, strategy);
7c673cae 807
f67539c2 808 collection.finish_ring(code, *it, is_interior, false);
7c673cae
FG		 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,
b32b8144
FG		 821 typename RobustPolicy,
822 typename Strategy
7c673cae
FG		 823 >
824 static inline
825 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,
b32b8144
FG		 832 RobustPolicy const& robust_policy,
833 Strategy const& strategy) // side strategy
7c673cae
FG		 834 {
835 iterate(boost::begin(interior_rings), boost::end(interior_rings),
836 collection, distance, side_strategy,
837 join_strategy, end_strategy, point_strategy,
b32b8144 838 robust_policy, strategy, true);
7c673cae
FG		 839 }
840
841public:
842 template
843 <
844 typename Collection,
845 typename DistanceStrategy,
846 typename SideStrategy,
847 typename JoinStrategy,
848 typename EndStrategy,
849 typename PointStrategy,
b32b8144
FG		 850 typename RobustPolicy,
851 typename Strategy
7c673cae
FG		 852 >
853 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,
b32b8144
FG		 860 RobustPolicy const& robust_policy,
861 Strategy const& strategy) // side strategy
7c673cae
FG		 862 {
863 {
b32b8144 864 collection.start_new_ring(distance.negative());
7c673cae 865
b32b8144 866 geometry::strategy::buffer::result_code const code
7c673cae
FG		 867 = policy::apply(exterior_ring(polygon), collection,
868 distance, side_strategy,
869 join_strategy, end_strategy, point_strategy,
b32b8144 870 robust_policy, strategy);
7c673cae 871
f67539c2 872 collection.finish_ring(code, exterior_ring(polygon), false,
7c673cae
FG		 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,
b32b8144 879 robust_policy, strategy);
7c673cae
FG		 880 }
881};
882
883
884template
885<
886 typename Multi,
887 typename PolygonOutput
888>
889struct 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
911namespace detail { namespace buffer
912{
913
914template
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,
b32b8144 924 typename IntersectionStrategy,
7c673cae
FG		 925 typename RobustPolicy,
926 typename VisitPiecesPolicy
927>
928inline 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,
b32b8144 934 IntersectionStrategy const& intersection_strategy,
7c673cae
FG		 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,
b32b8144 944 IntersectionStrategy,
f67539c2 945 DistanceStrategy,
7c673cae
FG		 946 RobustPolicy
947 > collection_type;
f67539c2 948 collection_type collection(intersection_strategy, distance_strategy, robust_policy);
7c673cae
FG		 949 collection_type const& const_collection = collection;
950
20effc67 951 bool const areal = util::is_areal<GeometryInput>::value;
7c673cae
FG		 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,
b32b8144 965 robust_policy, intersection_strategy.get_side_strategy());
7c673cae 966
f67539c2 967 collection.get_turns();
7c673cae
FG		 968 if (BOOST_GEOMETRY_CONDITION(areal))
969 {
20effc67 970 collection.check_turn_in_original();
7c673cae
FG		 971 }
972
20effc67
TL		 973 collection.verify_turns();
974
7c673cae
FG		 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
20effc67
TL		 988 if (BOOST_GEOMETRY_CONDITION(areal))
989 {
990 collection.deflate_check_turns();
991 }
992
7c673cae
FG		 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
1022template
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,
b32b8144 1032 typename IntersectionStrategy,
7c673cae
FG		 1033 typename RobustPolicy
1034>
1035inline 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,
b32b8144 1041 IntersectionStrategy const& intersection_strategy,
7c673cae
FG		 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,
b32b8144 1048 intersection_strategy, robust_policy, visitor);
7c673cae
FG		 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
Ceph