boost/geometry/algorithms/detail/buffer/buffer_inserter.hpp

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