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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2016-2019.
   7 // Modifications copyright (c) 2016-2019 Oracle and/or its affiliates.
   8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   9
  10 // Use, modification and distribution is subject to the Boost Software License,
  11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  12 // http://www.boost.org/LICENSE_1_0.txt)
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP
  16
  17 #include <algorithm>
  18 #include <cstddef>
  19 #include <set>
  20
  21 #include <boost/core/ignore_unused.hpp>
  22 #include <boost/range.hpp>
  23
  24 #include <boost/geometry/core/assert.hpp>
  25 #include <boost/geometry/core/coordinate_type.hpp>
  26 #include <boost/geometry/core/point_type.hpp>
  27
  28 #include <boost/geometry/algorithms/comparable_distance.hpp>
  29 #include <boost/geometry/algorithms/covered_by.hpp>
  30 #include <boost/geometry/algorithms/envelope.hpp>
  31 #include <boost/geometry/algorithms/is_convex.hpp>
  32
  33 #include <boost/geometry/strategies/buffer.hpp>
  34
  35 #include <boost/geometry/geometries/ring.hpp>
  36
  37 #include <boost/geometry/algorithms/detail/buffer/buffered_ring.hpp>
  38 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
  39 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
  40 #include <boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp>
  41 #include <boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp>
  42 #include <boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp>
  43
  44 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
  45 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
  46 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
  47 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
  48 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
  49 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
  50 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
  51 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
  52 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
  53 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  54 #include <boost/geometry/algorithms/detail/occupation_info.hpp>
  55 #include <boost/geometry/algorithms/detail/partition.hpp>
  56 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
  57 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
  58
  59 #include <boost/geometry/util/range.hpp>
  60
  61
  62 namespace boost { namespace geometry
  63 {
  64
  65
  66 #ifndef DOXYGEN_NO_DETAIL
  67 namespace detail { namespace buffer
  68 {
  69
  70 enum segment_relation_code
  71 {
  72     segment_relation_on_left,
  73     segment_relation_on_right,
  74     segment_relation_within,
  75     segment_relation_disjoint
  76 };
  77
  78 /*
  79  *  Terminology
  80  *
  81  *  Suppose we make a buffer (using blocked corners) of this rectangle:
  82  *
  83  *         +-------+
  84  *         |       |
  85  *         |  rect |
  86  *         |       |
  87  *         +-------+
  88  *
  89  * For the sides we get these four buffered side-pieces (marked with s)
  90  * and four buffered corner pieces (marked with c)
  91  *
  92  *     c---+---s---+---c
  93  *     |   | piece |   |     <- see below for details of the middle top-side-piece
  94  *     +---+-------+---+
  95  *     |   |       |   |
  96  *     s   |  rect |   s     <- two side pieces left/right of rect
  97  *     |   |       |   |
  98  *     +---+-------+---+
  99  *     |   | piece |   |     <- one side-piece below, and two corner pieces
 100  *     c---+---s---+---c
 101  *
 102  *  The outer part of the picture above, using all pieces,
 103  *    form together the offsetted ring (marked with o below)
 104  *  The 8 pieces are part of the piece collection and use for inside-checks
 105  *  The inner parts form (using 1 or 2 points per piece, often co-located)
 106  *    form together the robust_polygons (marked with r below)
 107  *  The remaining piece-segments are helper-segments (marked with h)
 108  *
 109  *     ooooooooooooooooo
 110  *     o   h       h   o
 111  *     ohhhrrrrrrrrrhhho
 112  *     o   r       r   o
 113  *     o   r       r   o
 114  *     o   r       r   o
 115  *     ohhhrrrrrrrrrhhho
 116  *     o   h       h   o
 117  *     ooooooooooooooooo
 118  *
 119  */
 120
 121
 122 template <typename Ring, typename IntersectionStrategy, typename RobustPolicy>
 123 struct buffered_piece_collection
 124 {
 125     typedef buffered_piece_collection
 126         <
 127             Ring, IntersectionStrategy, RobustPolicy
 128         > this_type;
 129
 130     typedef typename geometry::point_type<Ring>::type point_type;
 131     typedef typename geometry::coordinate_type<Ring>::type coordinate_type;
 132     typedef typename geometry::robust_point_type
 133     <
 134         point_type,
 135         RobustPolicy
 136     >::type robust_point_type;
 137
 138     // Robust ring/polygon type, always clockwise
 139     typedef geometry::model::ring<robust_point_type> robust_ring_type;
 140     typedef geometry::model::box<robust_point_type> robust_box_type;
 141
 142     typedef typename default_comparable_distance_result
 143         <
 144             robust_point_type
 145         >::type robust_comparable_radius_type;
 146
 147     typedef typename IntersectionStrategy::side_strategy_type side_strategy_type;
 148     typedef typename IntersectionStrategy::envelope_strategy_type envelope_strategy_type;
 149     typedef typename IntersectionStrategy::expand_strategy_type expand_strategy_type;
 150
 151     typedef typename IntersectionStrategy::template area_strategy
 152         <
 153             point_type
 154         >::type area_strategy_type;
 155
 156     typedef typename IntersectionStrategy::template area_strategy
 157         <
 158             robust_point_type
 159         >::type robust_area_strategy_type;
 160
 161     typedef typename area_strategy_type::template result_type
 162         <
 163             point_type
 164         >::type area_result_type;
 165     typedef typename robust_area_strategy_type::template result_type
 166         <
 167             robust_point_type
 168         >::type robust_area_result_type;
 169
 170     typedef typename IntersectionStrategy::template point_in_geometry_strategy
 171         <
 172             robust_point_type,
 173             robust_ring_type
 174         >::type point_in_geometry_strategy_type;
 175
 176     typedef typename geometry::rescale_policy_type
 177         <
 178             typename geometry::point_type<Ring>::type,
 179             typename IntersectionStrategy::cs_tag
 180         >::type rescale_policy_type;
 181
 182     typedef geometry::segment_ratio
 183     <
 184         typename geometry::coordinate_type<robust_point_type>::type
 185     > ratio_type;
 186
 187     typedef buffer_turn_info
 188     <
 189         point_type,
 190         robust_point_type,
 191         ratio_type
 192     > buffer_turn_info_type;
 193
 194     typedef buffer_turn_operation
 195     <
 196         point_type,
 197         ratio_type
 198     > buffer_turn_operation_type;
 199
 200     typedef std::vector<buffer_turn_info_type> turn_vector_type;
 201
 202     struct robust_turn
 203     {
 204         std::size_t turn_index;
 205         int operation_index;
 206         robust_point_type point;
 207         segment_identifier seg_id;
 208         ratio_type fraction;
 209     };
 210
 211     struct piece
 212     {
 213         typedef robust_ring_type piece_robust_ring_type;
 214         typedef geometry::section<robust_box_type, 1> section_type;
 215
 216         strategy::buffer::piece_type type;
 217         signed_size_type index;
 218
 219         signed_size_type left_index; // points to previous piece of same ring
 220         signed_size_type right_index; // points to next piece of same ring
 221
 222         // The next two members (1, 2) form together a complete clockwise ring
 223         // for each piece (with one dupped point)
 224         // The complete clockwise ring is also included as a robust ring (3)
 225
 226         // 1: half, part of offsetted_rings
 227         segment_identifier first_seg_id;
 228         signed_size_type last_segment_index; // no segment-identifier - it is the same as first_seg_id
 229         signed_size_type offsetted_count; // part in robust_ring which is part of offsetted ring
 230
 231 #if defined(BOOST_GEOMETRY_BUFFER_USE_HELPER_POINTS)
 232         // 2: half, not part of offsetted rings - part of robust ring
 233         std::vector<point_type> helper_points; // 4 points for side, 3 points for join - 0 points for flat-end
 234 #endif
 235         bool is_flat_start;
 236         bool is_flat_end;
 237
 238         bool is_deflated;
 239         bool is_convex;
 240         bool is_monotonic_increasing[2]; // 0=x, 1=y
 241         bool is_monotonic_decreasing[2]; // 0=x, 1=y
 242
 243         // Monotonic sections of pieces around points
 244         std::vector<section_type> sections;
 245
 246         // Robust representations
 247         // 3: complete ring
 248         robust_ring_type robust_ring;
 249
 250         robust_box_type robust_envelope;
 251         robust_box_type robust_offsetted_envelope;
 252
 253         std::vector<robust_turn> robust_turns; // Used only in insert_rescaled_piece_turns - we might use a map instead
 254
 255         robust_point_type robust_center;
 256         robust_comparable_radius_type robust_min_comparable_radius;
 257         robust_comparable_radius_type robust_max_comparable_radius;
 258
 259         piece()
 260             : type(strategy::buffer::piece_type_unknown)
 261             , index(-1)
 262             , left_index(-1)
 263             , right_index(-1)
 264             , last_segment_index(-1)
 265             , offsetted_count(-1)
 266             , is_flat_start(false)
 267             , is_flat_end(false)
 268             , is_deflated(false)
 269             , is_convex(false)
 270             , robust_min_comparable_radius(0)
 271             , robust_max_comparable_radius(0)
 272         {
 273             is_monotonic_increasing[0] = false;
 274             is_monotonic_increasing[1] = false;
 275             is_monotonic_decreasing[0] = false;
 276             is_monotonic_decreasing[1] = false;
 277         }
 278     };
 279
 280     struct robust_original
 281     {
 282         typedef robust_ring_type original_robust_ring_type;
 283         typedef geometry::sections<robust_box_type, 1> sections_type;
 284
 285         inline robust_original()
 286             : m_is_interior(false)
 287             , m_has_interiors(true)
 288         {}
 289
 290         inline robust_original(robust_ring_type const& ring,
 291                 bool is_interior, bool has_interiors,
 292                 envelope_strategy_type const& envelope_strategy,
 293                 expand_strategy_type const& expand_strategy)
 294             : m_ring(ring)
 295             , m_is_interior(is_interior)
 296             , m_has_interiors(has_interiors)
 297         {
 298             geometry::envelope(m_ring, m_box, envelope_strategy);
 299
 300             // create monotonic sections in x-dimension
 301             // The dimension is critical because the direction is later used
 302             // in the optimization for within checks using winding strategy
 303             // and this strategy is scanning in x direction.
 304             typedef boost::mpl::vector_c<std::size_t, 0> dimensions;
 305             geometry::sectionalize<false, dimensions>(m_ring,
 306                     detail::no_rescale_policy(), m_sections,
 307                     envelope_strategy, expand_strategy);
 308         }
 309
 310         robust_ring_type m_ring;
 311         robust_box_type m_box;
 312         sections_type m_sections;
 313
 314         bool m_is_interior;
 315         bool m_has_interiors;
 316     };
 317
 318     typedef std::vector<piece> piece_vector_type;
 319
 320     piece_vector_type m_pieces;
 321     turn_vector_type m_turns;
 322     signed_size_type m_first_piece_index;
 323     bool m_deflate;
 324     bool m_has_deflated;
 325
 326     buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; // indexed by multi_index
 327     std::vector<robust_original> robust_originals; // robust representation of the original(s)
 328     robust_ring_type current_robust_ring;
 329     buffered_ring_collection<Ring> traversed_rings;
 330     segment_identifier current_segment_id;
 331
 332     // Specificly for offsetted rings around points
 333     // but also for large joins with many points
 334     typedef geometry::sections<robust_box_type, 2> sections_type;
 335     sections_type monotonic_sections;
 336
 337     // Define the clusters, mapping cluster_id -> turns
 338     typedef std::map
 339         <
 340             signed_size_type,
 341             detail::overlay::cluster_info
 342         > cluster_type;
 343
 344     cluster_type m_clusters;
 345
 346     IntersectionStrategy m_intersection_strategy;
 347     side_strategy_type m_side_strategy;
 348     area_strategy_type m_area_strategy;
 349     envelope_strategy_type m_envelope_strategy;
 350     expand_strategy_type m_expand_strategy;
 351     point_in_geometry_strategy_type m_point_in_geometry_strategy;
 352
 353     robust_area_strategy_type m_robust_area_strategy;
 354     RobustPolicy const& m_robust_policy;
 355
 356     struct redundant_turn
 357     {
 358         inline bool operator()(buffer_turn_info_type const& turn) const
 359         {
 360             return turn.remove_on_multi;
 361         }
 362     };
 363
 364     buffered_piece_collection(IntersectionStrategy const& intersection_strategy,
 365                               RobustPolicy const& robust_policy)
 366         : m_first_piece_index(-1)
 367         , m_deflate(false)
 368         , m_has_deflated(false)
 369         , m_intersection_strategy(intersection_strategy)
 370         , m_side_strategy(intersection_strategy.get_side_strategy())
 371         , m_area_strategy(intersection_strategy
 372             .template get_area_strategy<point_type>())
 373         , m_envelope_strategy(intersection_strategy.get_envelope_strategy())
 374         , m_expand_strategy(intersection_strategy.get_expand_strategy())
 375         , m_point_in_geometry_strategy(intersection_strategy
 376             .template get_point_in_geometry_strategy<robust_point_type,
 377                         robust_ring_type>())
 378         , m_robust_area_strategy(intersection_strategy
 379             .template get_area_strategy<robust_point_type>())
 380         , m_robust_policy(robust_policy)
 381     {}
 382
 383
 384 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
 385     // Will (most probably) be removed later
 386     template <typename OccupationMap>
 387     inline void adapt_mapped_robust_point(OccupationMap const& map,
 388             buffer_turn_info_type& turn, int distance) const
 389     {
 390         for (int x = -distance; x <= distance; x++)
 391         {
 392             for (int y = -distance; y <= distance; y++)
 393             {
 394                 robust_point_type rp = turn.robust_point;
 395                 geometry::set<0>(rp, geometry::get<0>(rp) + x);
 396                 geometry::set<1>(rp, geometry::get<1>(rp) + y);
 397                 if (map.find(rp) != map.end())
 398                 {
 399                     turn.mapped_robust_point = rp;
 400                     return;
 401                 }
 402             }
 403         }
 404     }
 405 #endif
 406
 407     inline void get_occupation(
 408 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
 409         int distance = 0
 410 #endif
 411     )
 412     {
 413         typedef occupation_info<angle_info<robust_point_type, coordinate_type> >
 414                 buffer_occupation_info;
 415
 416         typedef std::map
 417         <
 418             robust_point_type,
 419             buffer_occupation_info,
 420             geometry::less<robust_point_type>
 421         > occupation_map_type;
 422
 423         occupation_map_type occupation_map;
 424
 425         // 1: Add all intersection points to occupation map
 426         typedef typename boost::range_iterator<turn_vector_type>::type
 427             iterator_type;
 428
 429         for (iterator_type it = boost::begin(m_turns);
 430             it != boost::end(m_turns);
 431             ++it)
 432         {
 433             if (it->location == location_ok)
 434             {
 435 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
 436                 if (distance > 0 && ! occupation_map.empty())
 437                 {
 438                     adapt_mapped_robust_point(occupation_map, *it, distance);
 439                 }
 440 #endif
 441                 occupation_map[it->get_robust_point()].count++;
 442             }
 443         }
 444
 445         // Remove all points with one or more u/u points from the map
 446         // (Alternatively, we could NOT do this here and change all u/u
 447         // behaviour in overlay. Currently nothing is done: each polygon is
 448         // just followed there. We could also always switch polygons there. For
 449         // buffer behaviour, where 3 pieces might meet of which 2 (or more) form
 450         // a u/u turn, this last option would have been better, probably).
 451         for (iterator_type it = boost::begin(m_turns);
 452             it != boost::end(m_turns);
 453             ++it)
 454         {
 455             if (it->both(detail::overlay::operation_union))
 456             {
 457                 typename occupation_map_type::iterator mit =
 458                             occupation_map.find(it->get_robust_point());
 459
 460                 if (mit != occupation_map.end())
 461                 {
 462                     occupation_map.erase(mit);
 463                 }
 464             }
 465         }
 466
 467         // 2: Remove all points from map which has only one
 468         typename occupation_map_type::iterator it = occupation_map.begin();
 469         while (it != occupation_map.end())
 470         {
 471             if (it->second.count <= 1)
 472             {
 473                 typename occupation_map_type::iterator to_erase = it;
 474                 ++it;
 475                 occupation_map.erase(to_erase);
 476             }
 477             else
 478             {
 479                 ++it;
 480             }
 481         }
 482
 483         if (occupation_map.empty())
 484         {
 485             return;
 486         }
 487
 488         // 3: Add vectors (incoming->intersection-point,
 489         //                 intersection-point -> outgoing)
 490         //    for all (co-located) points still present in the map
 491
 492         for (iterator_type tit = boost::begin(m_turns);
 493             tit != boost::end(m_turns);
 494             ++tit)
 495         {
 496             typename occupation_map_type::iterator mit =
 497                         occupation_map.find(tit->get_robust_point());
 498
 499             if (mit != occupation_map.end())
 500             {
 501                 buffer_occupation_info& info = mit->second;
 502                 for (int i = 0; i < 2; i++)
 503                 {
 504                     add_incoming_and_outgoing_angles(tit->get_robust_point(), *tit,
 505                                 m_pieces,
 506                                 i, tit->operations[i].seg_id,
 507                                 info);
 508                 }
 509
 510                 tit->count_on_multi++;
 511             }
 512         }
 513
 514 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
 515         // X: Check rounding issues
 516         if (distance == 0)
 517         {
 518             for (typename occupation_map_type::const_iterator it = occupation_map.begin();
 519                 it != occupation_map.end(); ++it)
 520             {
 521                 if (it->second.has_rounding_issues(it->first))
 522                 {
 523                     if(distance == 0)
 524                     {
 525                         get_occupation(distance + 1);
 526                         return;
 527                     }
 528                 }
 529             }
 530         }
 531 #endif
 532
 533         // Get left turns from all clusters
 534         for (typename occupation_map_type::iterator mit = occupation_map.begin();
 535             mit != occupation_map.end(); ++mit)
 536         {
 537             mit->second.get_left_turns(mit->first, m_turns, m_side_strategy);
 538         }
 539     }
 540
 541     inline void classify_turns()
 542     {
 543         for (typename boost::range_iterator<turn_vector_type>::type it =
 544             boost::begin(m_turns); it != boost::end(m_turns); ++it)
 545         {
 546             if (it->count_within > 0)
 547             {
 548                 it->location = inside_buffer;
 549             }
 550             if (it->count_within_near_offsetted > 0)
 551             {
 552                 // Within can have in rare cases a rounding issue. We don't discard this
 553                 // point, so it can be used to continue started rings in traversal. But
 554                 // will never start a new ring from this type of points.
 555                 it->operations[0].enriched.startable = false;
 556                 it->operations[1].enriched.startable = false;
 557             }
 558         }
 559     }
 560
 561     struct deflate_properties
 562     {
 563         bool has_inflated;
 564         std::size_t count;
 565
 566         inline deflate_properties()
 567             : has_inflated(false)
 568             , count(0u)
 569         {}
 570     };
 571
 572     inline void discard_turns_for_deflate()
 573     {
 574         // Deflate cases should have at least 3 points PER deflated original
 575         // to form a correct triangle
 576
 577         // But if there are intersections between a deflated ring and another
 578         // ring, it is all accepted
 579
 580         // In deflate most turns are i/u by nature, but u/u is also possible
 581
 582         std::map<signed_size_type, deflate_properties> properties;
 583
 584         for (typename boost::range_iterator<turn_vector_type const>::type it =
 585             boost::begin(m_turns); it != boost::end(m_turns); ++it)
 586         {
 587             const buffer_turn_info_type& turn = *it;
 588             if (turn.location == location_ok)
 589             {
 590                 const buffer_turn_operation_type& op0 = turn.operations[0];
 591                 const buffer_turn_operation_type& op1 = turn.operations[1];
 592
 593                 if (! m_pieces[op0.seg_id.piece_index].is_deflated
 594                  || ! m_pieces[op1.seg_id.piece_index].is_deflated)
 595                 {
 596                     properties[op0.seg_id.multi_index].has_inflated = true;
 597                     properties[op1.seg_id.multi_index].has_inflated = true;
 598                     continue;
 599                 }
 600
 601                 // It is deflated, update counts
 602                 for (int i = 0; i < 2; i++)
 603                 {
 604                     const buffer_turn_operation_type& op = turn.operations[i];
 605                     if (op.operation == detail::overlay::operation_union
 606                         || op.operation == detail::overlay::operation_continue)
 607                     {
 608                         properties[op.seg_id.multi_index].count++;
 609                     }
 610                 }
 611             }
 612         }
 613
 614         for (typename boost::range_iterator<turn_vector_type>::type it =
 615             boost::begin(m_turns); it != boost::end(m_turns); ++it)
 616         {
 617             buffer_turn_info_type& turn = *it;
 618
 619             if (turn.location == location_ok)
 620             {
 621                 const buffer_turn_operation_type& op0 = turn.operations[0];
 622                 const buffer_turn_operation_type& op1 = turn.operations[1];
 623                 signed_size_type const multi0 = op0.seg_id.multi_index;
 624                 signed_size_type const multi1 = op1.seg_id.multi_index;
 625
 626                 if (multi0 == multi1)
 627                 {
 628                     const deflate_properties& prop =  properties[multi0];
 629
 630                     // NOTE: Keep brackets around prop.count
 631                     // avoid gcc-bug "parse error in template argument list"
 632                     // GCC versions 5.4 and 5.5 (and probably more)
 633                     if (! prop.has_inflated && (prop.count) < 3)
 634                     {
 635                         // Property is not inflated
 636                         // Not enough points, this might be caused by <float> where
 637                         // detection turn-in-original failed because of numeric errors
 638                         turn.location = location_discard;
 639                     }
 640                 }
 641                 else
 642                 {
 643                     // Two different (possibly deflated) rings
 644                 }
 645             }
 646         }
 647     }
 648
 649     template <typename DistanceStrategy>
 650     inline void check_remaining_points(DistanceStrategy const& distance_strategy)
 651     {
 652         // Check if a turn is inside any of the originals
 653
 654         typedef turn_in_original_ovelaps_box
 655             <
 656                 typename IntersectionStrategy::disjoint_point_box_strategy_type
 657             > turn_in_original_ovelaps_box_type;
 658         typedef original_ovelaps_box
 659             <
 660                 typename IntersectionStrategy::disjoint_box_box_strategy_type
 661             > original_ovelaps_box_type;
 662
 663         turn_in_original_visitor
 664             <
 665                 turn_vector_type,
 666                 point_in_geometry_strategy_type
 667             > visitor(m_turns, m_point_in_geometry_strategy);
 668
 669         geometry::partition
 670             <
 671                 robust_box_type,
 672                 include_turn_policy,
 673                 detail::partition::include_all_policy
 674             >::apply(m_turns, robust_originals, visitor,
 675                      turn_get_box(), turn_in_original_ovelaps_box_type(),
 676                      original_get_box(), original_ovelaps_box_type());
 677
 678         bool const deflate = distance_strategy.negative();
 679
 680         for (typename boost::range_iterator<turn_vector_type>::type it =
 681             boost::begin(m_turns); it != boost::end(m_turns); ++it)
 682         {
 683             buffer_turn_info_type& turn = *it;
 684             if (turn.location == location_ok)
 685             {
 686                 if (deflate && turn.count_in_original <= 0)
 687                 {
 688                     // For deflate/negative buffers: it is not in original, discard
 689                     turn.location = location_discard;
 690                 }
 691                 else if (! deflate && turn.count_in_original > 0)
 692                 {
 693                     // For inflate: it is in original, discard
 694                     turn.location = location_discard;
 695                 }
 696             }
 697         }
 698
 699         if (m_has_deflated)
 700         {
 701             // Either strategy was negative, or there were interior rings
 702             discard_turns_for_deflate();
 703         }
 704     }
 705
 706     inline bool assert_indices_in_robust_rings() const
 707     {
 708         geometry::equal_to<robust_point_type> comparator;
 709         for (typename boost::range_iterator<turn_vector_type const>::type it =
 710             boost::begin(m_turns); it != boost::end(m_turns); ++it)
 711         {
 712             for (int i = 0; i < 2; i++)
 713             {
 714                 robust_point_type const &p1
 715                     = m_pieces[it->operations[i].piece_index].robust_ring
 716                               [it->operations[i].index_in_robust_ring];
 717                 robust_point_type const &p2 = it->robust_point;
 718                 if (! comparator(p1, p2))
 719                 {
 720                     return false;
 721                 }
 722             }
 723         }
 724         return true;
 725     }
 726
 727     inline void insert_rescaled_piece_turns()
 728     {
 729         // Add rescaled turn points to corresponding pieces
 730         // (after this, each turn occurs twice)
 731         std::size_t index = 0;
 732         for (typename boost::range_iterator<turn_vector_type>::type it =
 733             boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index)
 734         {
 735             geometry::recalculate(it->robust_point, it->point, m_robust_policy);
 736 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS)
 737             it->mapped_robust_point = it->robust_point;
 738 #endif
 739
 740             robust_turn turn;
 741             it->turn_index = index;
 742             turn.turn_index = index;
 743             turn.point = it->robust_point;
 744             for (int i = 0; i < 2; i++)
 745             {
 746                 turn.operation_index = i;
 747                 turn.seg_id = it->operations[i].seg_id;
 748                 turn.fraction = it->operations[i].fraction;
 749
 750                 piece& pc = m_pieces[it->operations[i].piece_index];
 751                 pc.robust_turns.push_back(turn);
 752
 753                 // Take into account for the box (intersection points should fall inside,
 754                 // but in theory they can be one off because of rounding
 755                 geometry::expand(pc.robust_envelope, it->robust_point);
 756                 geometry::expand(pc.robust_offsetted_envelope, it->robust_point);
 757             }
 758         }
 759
 760         if (! use_side_of_intersection<typename geometry::cs_tag<point_type>::type>::value)
 761         {
 762             // Insert all rescaled turn-points into these rings, to form a
 763             // reliable integer-based ring. All turns can be compared (inside) to this
 764             // rings to see if they are inside.
 765
 766             for (typename boost::range_iterator<piece_vector_type>::type
 767                     it = boost::begin(m_pieces); it != boost::end(m_pieces); ++it)
 768             {
 769                 piece& pc = *it;
 770                 signed_size_type piece_segment_index = pc.first_seg_id.segment_index;
 771                 if (! pc.robust_turns.empty())
 772                 {
 773                     if (pc.robust_turns.size() > 1u)
 774                     {
 775                         std::sort(pc.robust_turns.begin(), pc.robust_turns.end(), buffer_operation_less());
 776                     }
 777                     // Walk through them, in reverse to insert at right index
 778                     signed_size_type index_offset = static_cast<signed_size_type>(pc.robust_turns.size()) - 1;
 779                     for (typename boost::range_reverse_iterator<const std::vector<robust_turn> >::type
 780                             rit = boost::const_rbegin(pc.robust_turns);
 781                         rit != boost::const_rend(pc.robust_turns);
 782                         ++rit, --index_offset)
 783                     {
 784                         signed_size_type const index_in_vector = 1 + rit->seg_id.segment_index - piece_segment_index;
 785                         BOOST_GEOMETRY_ASSERT
 786                         (
 787                             index_in_vector > 0
 788                             && index_in_vector < pc.offsetted_count
 789                         );
 790
 791                         pc.robust_ring.insert(boost::begin(pc.robust_ring) + index_in_vector, rit->point);
 792                         pc.offsetted_count++;
 793
 794                         m_turns[rit->turn_index].operations[rit->operation_index].index_in_robust_ring = index_in_vector + index_offset;
 795                     }
 796                 }
 797             }
 798
 799             BOOST_GEOMETRY_ASSERT(assert_indices_in_robust_rings());
 800         }
 801     }
 802
 803     template <std::size_t Dimension>
 804     static inline void determine_monotonicity(piece& pc,
 805             robust_point_type const& current,
 806             robust_point_type const& next)
 807     {
 808         if (geometry::get<Dimension>(current) >= geometry::get<Dimension>(next))
 809         {
 810             pc.is_monotonic_increasing[Dimension] = false;
 811         }
 812         if (geometry::get<Dimension>(current) <= geometry::get<Dimension>(next))
 813         {
 814             pc.is_monotonic_decreasing[Dimension] = false;
 815         }
 816     }
 817
 818     inline void determine_properties(piece& pc) const
 819     {
 820         pc.is_monotonic_increasing[0] = true;
 821         pc.is_monotonic_increasing[1] = true;
 822         pc.is_monotonic_decreasing[0] = true;
 823         pc.is_monotonic_decreasing[1] = true;
 824
 825         pc.is_convex = geometry::is_convex(pc.robust_ring, m_side_strategy);
 826
 827         if (pc.offsetted_count < 2)
 828         {
 829             return;
 830         }
 831
 832         typename robust_ring_type::const_iterator current = pc.robust_ring.begin();
 833         typename robust_ring_type::const_iterator next = current + 1;
 834
 835         for (signed_size_type i = 1; i < pc.offsetted_count; i++)
 836         {
 837             determine_monotonicity<0>(pc, *current, *next);
 838             determine_monotonicity<1>(pc, *current, *next);
 839             current = next;
 840             ++next;
 841         }
 842     }
 843
 844     void determine_properties()
 845     {
 846         for (typename piece_vector_type::iterator it = boost::begin(m_pieces);
 847             it != boost::end(m_pieces);
 848             ++it)
 849         {
 850             determine_properties(*it);
 851         }
 852     }
 853
 854     inline void reverse_negative_robust_rings()
 855     {
 856         for (typename piece_vector_type::iterator it = boost::begin(m_pieces);
 857             it != boost::end(m_pieces);
 858             ++it)
 859         {
 860             piece& pc = *it;
 861             if (geometry::area(pc.robust_ring, m_robust_area_strategy) < 0)
 862             {
 863                 // Rings can be ccw:
 864                 // - in a concave piece
 865                 // - in a line-buffer with a negative buffer-distance
 866                 std::reverse(pc.robust_ring.begin(), pc.robust_ring.end());
 867             }
 868         }
 869     }
 870
 871     inline void prepare_buffered_point_piece(piece& pc)
 872     {
 873         // create monotonic sections in y-dimension
 874         typedef boost::mpl::vector_c<std::size_t, 1> dimensions;
 875         geometry::sectionalize<false, dimensions>(pc.robust_ring,
 876                 detail::no_rescale_policy(), pc.sections,
 877                 m_envelope_strategy, m_expand_strategy);
 878
 879         // Determine min/max radius
 880         typedef geometry::model::referring_segment<robust_point_type const>
 881             robust_segment_type;
 882
 883         typename robust_ring_type::const_iterator current = pc.robust_ring.begin();
 884         typename robust_ring_type::const_iterator next = current + 1;
 885
 886         for (signed_size_type i = 1; i < pc.offsetted_count; i++)
 887         {
 888             robust_segment_type s(*current, *next);
 889             robust_comparable_radius_type const d
 890                 = geometry::comparable_distance(pc.robust_center, s);
 891
 892             if (i == 1 || d < pc.robust_min_comparable_radius)
 893             {
 894                 pc.robust_min_comparable_radius = d;
 895             }
 896             if (i == 1 || d > pc.robust_max_comparable_radius)
 897             {
 898                 pc.robust_max_comparable_radius = d;
 899             }
 900
 901             current = next;
 902             ++next;
 903         }
 904     }
 905
 906     inline void prepare_buffered_point_pieces()
 907     {
 908         for (typename piece_vector_type::iterator it = boost::begin(m_pieces);
 909             it != boost::end(m_pieces);
 910             ++it)
 911         {
 912             if (it->type == geometry::strategy::buffer::buffered_point)
 913             {
 914                 prepare_buffered_point_piece(*it);
 915             }
 916         }
 917     }
 918
 919     template <typename DistanceStrategy>
 920     inline void get_turns(DistanceStrategy const& distance_strategy)
 921     {
 922         for(typename boost::range_iterator<sections_type>::type it
 923                 = boost::begin(monotonic_sections);
 924             it != boost::end(monotonic_sections);
 925             ++it)
 926         {
 927             enlarge_box(it->bounding_box, 1);
 928         }
 929
 930         {
 931             // Calculate the turns
 932             piece_turn_visitor
 933                 <
 934                     piece_vector_type,
 935                     buffered_ring_collection<buffered_ring<Ring> >,
 936                     turn_vector_type,
 937                     IntersectionStrategy,
 938                     RobustPolicy
 939                 > visitor(m_pieces, offsetted_rings, m_turns,
 940                           m_intersection_strategy, m_robust_policy);
 941
 942             typedef detail::section::get_section_box
 943                 <
 944                     typename IntersectionStrategy::expand_box_strategy_type
 945                 > get_section_box_type;
 946             typedef detail::section::overlaps_section_box
 947                 <
 948                     typename IntersectionStrategy::disjoint_box_box_strategy_type
 949                 > overlaps_section_box_type;
 950
 951             geometry::partition
 952                 <
 953                     robust_box_type
 954                 >::apply(monotonic_sections, visitor,
 955                          get_section_box_type(),
 956                          overlaps_section_box_type());
 957         }
 958
 959         insert_rescaled_piece_turns();
 960
 961         reverse_negative_robust_rings();
 962
 963         determine_properties();
 964
 965         prepare_buffered_point_pieces();
 966
 967         {
 968             // Check if it is inside any of the pieces
 969             turn_in_piece_visitor
 970                 <
 971                     typename geometry::cs_tag<point_type>::type,
 972                     turn_vector_type, piece_vector_type,
 973                     DistanceStrategy,
 974                     point_in_geometry_strategy_type,
 975                     side_strategy_type
 976                 > visitor(m_turns, m_pieces,
 977                           distance_strategy,
 978                           m_point_in_geometry_strategy,
 979                           m_side_strategy);
 980
 981             typedef turn_ovelaps_box
 982                 <
 983                     typename IntersectionStrategy::disjoint_point_box_strategy_type
 984                 > turn_ovelaps_box_type;
 985             typedef piece_ovelaps_box
 986                 <
 987                     typename IntersectionStrategy::disjoint_box_box_strategy_type
 988                 > piece_ovelaps_box_type;
 989
 990             geometry::partition
 991                 <
 992                     robust_box_type
 993                 >::apply(m_turns, m_pieces, visitor,
 994                          turn_get_box(), turn_ovelaps_box_type(),
 995                          piece_get_box(), piece_ovelaps_box_type());
 996
 997         }
 998     }
 999
1000     inline void start_new_ring(bool deflate)
1001     {
1002         signed_size_type const n = static_cast<signed_size_type>(offsetted_rings.size());
1003         current_segment_id.source_index = 0;
1004         current_segment_id.multi_index = n;
1005         current_segment_id.ring_index = -1;
1006         current_segment_id.segment_index = 0;
1007
1008         offsetted_rings.resize(n + 1);
1009         current_robust_ring.clear();
1010
1011         m_first_piece_index = static_cast<signed_size_type>(boost::size(m_pieces));
1012         m_deflate = deflate;
1013         if (deflate)
1014         {
1015             // Pieces contain either deflated exterior rings, or inflated
1016             // interior rings which are effectively deflated too
1017             m_has_deflated = true;
1018         }
1019     }
1020
1021     inline void abort_ring()
1022     {
1023         // Remove all created pieces for this ring, sections, last offsetted
1024         while (! m_pieces.empty()
1025                && m_pieces.back().first_seg_id.multi_index
1026                == current_segment_id.multi_index)
1027         {
1028             m_pieces.erase(m_pieces.end() - 1);
1029         }
1030
1031         while (! monotonic_sections.empty()
1032                && monotonic_sections.back().ring_id.multi_index
1033                == current_segment_id.multi_index)
1034         {
1035             monotonic_sections.erase(monotonic_sections.end() - 1);
1036         }
1037
1038         offsetted_rings.erase(offsetted_rings.end() - 1);
1039         current_robust_ring.clear();
1040
1041         m_first_piece_index = -1;
1042     }
1043
1044     inline void update_closing_point()
1045     {
1046         BOOST_GEOMETRY_ASSERT(! offsetted_rings.empty());
1047         buffered_ring<Ring>& added = offsetted_rings.back();
1048         if (! boost::empty(added))
1049         {
1050             range::back(added) = range::front(added);
1051         }
1052     }
1053
1054     inline void update_last_point(point_type const& p,
1055             buffered_ring<Ring>& ring)
1056     {
1057         // For the first point of a new piece, and there were already
1058         // points in the offsetted ring, for some piece types the first point
1059         // is a duplicate of the last point of the previous piece.
1060
1061         // TODO: disable that, that point should not be added
1062
1063         // For now, it is made equal because due to numerical instability,
1064         // it can be a tiny bit off, possibly causing a self-intersection
1065
1066         BOOST_GEOMETRY_ASSERT(boost::size(m_pieces) > 0);
1067         if (! ring.empty()
1068             && current_segment_id.segment_index
1069                 == m_pieces.back().first_seg_id.segment_index)
1070         {
1071             ring.back() = p;
1072         }
1073     }
1074
1075     inline void set_piece_center(point_type const& center)
1076     {
1077         BOOST_GEOMETRY_ASSERT(! m_pieces.empty());
1078         geometry::recalculate(m_pieces.back().robust_center, center,
1079                 m_robust_policy);
1080     }
1081
1082     inline void finish_ring(strategy::buffer::result_code code,
1083                             bool is_interior = false, bool has_interiors = false)
1084     {
1085         if (code == strategy::buffer::result_error_numerical)
1086         {
1087             abort_ring();
1088             return;
1089         }
1090
1091         if (m_first_piece_index == -1)
1092         {
1093             return;
1094         }
1095
1096         if (m_first_piece_index < static_cast<signed_size_type>(boost::size(m_pieces)))
1097         {
1098             // If piece was added
1099             // Reassign left-of-first and right-of-last
1100             geometry::range::at(m_pieces, m_first_piece_index).left_index
1101                     = static_cast<signed_size_type>(boost::size(m_pieces)) - 1;
1102             geometry::range::back(m_pieces).right_index = m_first_piece_index;
1103         }
1104         m_first_piece_index = -1;
1105
1106         update_closing_point();
1107
1108         if (! current_robust_ring.empty())
1109         {
1110             BOOST_GEOMETRY_ASSERT
1111             (
1112                 geometry::equals(current_robust_ring.front(),
1113                     current_robust_ring.back())
1114             );
1115
1116             robust_originals.push_back(
1117                 robust_original(current_robust_ring,
1118                     is_interior, has_interiors, m_envelope_strategy, m_expand_strategy));
1119         }
1120     }
1121
1122     inline void set_current_ring_concave()
1123     {
1124         BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0);
1125         offsetted_rings.back().has_concave = true;
1126     }
1127
1128     inline signed_size_type add_point(point_type const& p)
1129     {
1130         BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0);
1131
1132         buffered_ring<Ring>& current_ring = offsetted_rings.back();
1133         update_last_point(p, current_ring);
1134
1135         current_segment_id.segment_index++;
1136         current_ring.push_back(p);
1137         return static_cast<signed_size_type>(current_ring.size());
1138     }
1139
1140     //-------------------------------------------------------------------------
1141
1142     inline piece& create_piece(strategy::buffer::piece_type type,
1143             bool decrease_segment_index_by_one)
1144     {
1145         if (type == strategy::buffer::buffered_concave)
1146         {
1147             offsetted_rings.back().has_concave = true;
1148         }
1149
1150         piece pc;
1151         pc.type = type;
1152         pc.index = static_cast<signed_size_type>(boost::size(m_pieces));
1153         pc.is_deflated = m_deflate;
1154
1155         current_segment_id.piece_index = pc.index;
1156
1157         pc.first_seg_id = current_segment_id;
1158
1159         // Assign left/right (for first/last piece per ring they will be re-assigned later)
1160         pc.left_index = pc.index - 1;
1161         pc.right_index = pc.index + 1;
1162
1163         std::size_t const n = boost::size(offsetted_rings.back());
1164         pc.first_seg_id.segment_index = decrease_segment_index_by_one ? n - 1 : n;
1165         pc.last_segment_index = pc.first_seg_id.segment_index;
1166
1167         m_pieces.push_back(pc);
1168         return m_pieces.back();
1169     }
1170
1171     inline void init_rescale_piece(piece& pc, std::size_t helper_points_size)
1172     {
1173         if (pc.first_seg_id.segment_index < 0)
1174         {
1175             // This indicates an error situation: an earlier piece was empty
1176             // It currently does not happen
1177             // std::cout << "EMPTY " << pc.type << " " << pc.index << " " << pc.first_seg_id.multi_index << std::endl;
1178             pc.offsetted_count = 0;
1179             return;
1180         }
1181
1182         BOOST_GEOMETRY_ASSERT(pc.first_seg_id.multi_index >= 0);
1183         BOOST_GEOMETRY_ASSERT(pc.last_segment_index >= 0);
1184
1185         pc.offsetted_count = pc.last_segment_index - pc.first_seg_id.segment_index;
1186         BOOST_GEOMETRY_ASSERT(pc.offsetted_count >= 0);
1187
1188         pc.robust_ring.reserve(pc.offsetted_count + helper_points_size);
1189
1190         // Add rescaled offsetted segments
1191         {
1192             buffered_ring<Ring> const& ring = offsetted_rings[pc.first_seg_id.multi_index];
1193
1194             typedef typename boost::range_iterator<const buffered_ring<Ring> >::type it_type;
1195             for (it_type it = boost::begin(ring) + pc.first_seg_id.segment_index;
1196                 it != boost::begin(ring) + pc.last_segment_index;
1197                 ++it)
1198             {
1199                 robust_point_type point;
1200                 geometry::recalculate(point, *it, m_robust_policy);
1201                 pc.robust_ring.push_back(point);
1202             }
1203         }
1204     }
1205
1206     inline robust_point_type add_helper_point(piece& pc, const point_type& point)
1207     {
1208 #if defined(BOOST_GEOMETRY_BUFFER_USE_HELPER_POINTS)
1209         pc.helper_points.push_back(point);
1210 #endif
1211
1212         robust_point_type rob_point;
1213         geometry::recalculate(rob_point, point, m_robust_policy);
1214         pc.robust_ring.push_back(rob_point);
1215         return rob_point;
1216     }
1217
1218     // TODO: this is shared with sectionalize, move to somewhere else (assign?)
1219     template <typename Box, typename Value>
1220     inline void enlarge_box(Box& box, Value value)
1221     {
1222         geometry::set<0, 0>(box, geometry::get<0, 0>(box) - value);
1223         geometry::set<0, 1>(box, geometry::get<0, 1>(box) - value);
1224         geometry::set<1, 0>(box, geometry::get<1, 0>(box) + value);
1225         geometry::set<1, 1>(box, geometry::get<1, 1>(box) + value);
1226     }
1227
1228     inline void calculate_robust_envelope(piece& pc)
1229     {
1230         if (pc.offsetted_count == 0)
1231         {
1232             return;
1233         }
1234
1235         geometry::envelope(pc.robust_ring, pc.robust_envelope, m_envelope_strategy);
1236
1237         geometry::assign_inverse(pc.robust_offsetted_envelope);
1238         for (signed_size_type i = 0; i < pc.offsetted_count; i++)
1239         {
1240             geometry::expand(pc.robust_offsetted_envelope, pc.robust_ring[i]);
1241         }
1242
1243         // Take roundings into account, enlarge boxes with 1 integer
1244         enlarge_box(pc.robust_envelope, 1);
1245         enlarge_box(pc.robust_offsetted_envelope, 1);
1246     }
1247
1248     inline void sectionalize(piece& pc)
1249     {
1250
1251         buffered_ring<Ring> const& ring = offsetted_rings.back();
1252
1253         typedef geometry::detail::sectionalize::sectionalize_part
1254         <
1255             point_type,
1256             boost::mpl::vector_c<std::size_t, 0, 1> // x,y dimension
1257         > sectionalizer;
1258
1259         // Create a ring-identifier. The source-index is the piece index
1260         // The multi_index is as in this collection (the ring), but not used here
1261         // The ring_index is not used
1262         ring_identifier ring_id(pc.index, pc.first_seg_id.multi_index, -1);
1263
1264         sectionalizer::apply(monotonic_sections,
1265             boost::begin(ring) + pc.first_seg_id.segment_index,
1266             boost::begin(ring) + pc.last_segment_index,
1267             m_robust_policy,
1268             ring_id, 10);
1269     }
1270
1271     inline void finish_piece(piece& pc)
1272     {
1273         init_rescale_piece(pc, 0u);
1274         calculate_robust_envelope(pc);
1275         sectionalize(pc);
1276     }
1277
1278     inline void finish_piece(piece& pc,
1279                     const point_type& point1,
1280                     const point_type& point2,
1281                     const point_type& point3)
1282     {
1283         init_rescale_piece(pc, 3u);
1284         if (pc.offsetted_count == 0)
1285         {
1286             return;
1287         }
1288
1289         add_helper_point(pc, point1);
1290         robust_point_type mid_point = add_helper_point(pc, point2);
1291         add_helper_point(pc, point3);
1292         calculate_robust_envelope(pc);
1293         sectionalize(pc);
1294
1295         current_robust_ring.push_back(mid_point);
1296     }
1297
1298     inline void finish_piece(piece& pc,
1299                     const point_type& point1,
1300                     const point_type& point2,
1301                     const point_type& point3,
1302                     const point_type& point4)
1303     {
1304         init_rescale_piece(pc, 4u);
1305         add_helper_point(pc, point1);
1306         robust_point_type mid_point2 = add_helper_point(pc, point2);
1307         robust_point_type mid_point1 = add_helper_point(pc, point3);
1308         add_helper_point(pc, point4);
1309         sectionalize(pc);
1310         calculate_robust_envelope(pc);
1311
1312         // Add mid-points in other order to current helper_ring
1313         current_robust_ring.push_back(mid_point1);
1314         current_robust_ring.push_back(mid_point2);
1315     }
1316
1317     inline void add_piece(strategy::buffer::piece_type type, point_type const& p,
1318             point_type const& b1, point_type const& b2)
1319     {
1320         piece& pc = create_piece(type, false);
1321         add_point(b1);
1322         pc.last_segment_index = add_point(b2);
1323         finish_piece(pc, b2, p, b1);
1324     }
1325
1326     template <typename Range>
1327     inline void add_range_to_piece(piece& pc, Range const& range, bool add_front)
1328     {
1329         BOOST_GEOMETRY_ASSERT(boost::size(range) != 0u);
1330
1331         typename Range::const_iterator it = boost::begin(range);
1332
1333         // If it follows a non-join (so basically the same piece-type) point b1 should be added.
1334         // There should be two intersections later and it should be discarded.
1335         // But for now we need it to calculate intersections
1336         if (add_front)
1337         {
1338             add_point(*it);
1339         }
1340
1341         for (++it; it != boost::end(range); ++it)
1342         {
1343             pc.last_segment_index = add_point(*it);
1344         }
1345     }
1346
1347
1348     template <typename Range>
1349     inline void add_piece(strategy::buffer::piece_type type, Range const& range,
1350             bool decrease_segment_index_by_one)
1351     {
1352         piece& pc = create_piece(type, decrease_segment_index_by_one);
1353
1354         if (boost::size(range) > 0u)
1355         {
1356             add_range_to_piece(pc, range, offsetted_rings.back().empty());
1357         }
1358         finish_piece(pc);
1359     }
1360
1361     template <typename Range>
1362     inline void add_side_piece(point_type const& p1, point_type const& p2,
1363             Range const& range, bool first)
1364     {
1365         BOOST_GEOMETRY_ASSERT(boost::size(range) >= 2u);
1366
1367         piece& pc = create_piece(strategy::buffer::buffered_segment, ! first);
1368         add_range_to_piece(pc, range, first);
1369         finish_piece(pc, range.back(), p2, p1, range.front());
1370     }
1371
1372     template <typename Range>
1373     inline void add_piece(strategy::buffer::piece_type type,
1374             point_type const& p, Range const& range)
1375     {
1376         piece& pc = create_piece(type, true);
1377
1378         if (boost::size(range) > 0u)
1379         {
1380             add_range_to_piece(pc, range, offsetted_rings.back().empty());
1381             finish_piece(pc, range.back(), p, range.front());
1382         }
1383         else
1384         {
1385             finish_piece(pc);
1386         }
1387     }
1388
1389     template <typename EndcapStrategy, typename Range>
1390     inline void add_endcap(EndcapStrategy const& strategy, Range const& range,
1391             point_type const& end_point)
1392     {
1393         boost::ignore_unused(strategy);
1394
1395         if (range.empty())
1396         {
1397             return;
1398         }
1399         strategy::buffer::piece_type pt = strategy.get_piece_type();
1400         if (pt == strategy::buffer::buffered_flat_end)
1401         {
1402             // It is flat, should just be added, without helper segments
1403             add_piece(pt, range, true);
1404         }
1405         else
1406         {
1407             // Normal case, it has an "inside", helper segments should be added
1408             add_piece(pt, end_point, range);
1409         }
1410     }
1411
1412     inline void mark_flat_start()
1413     {
1414         if (! m_pieces.empty())
1415         {
1416             piece& back = m_pieces.back();
1417             back.is_flat_start = true;
1418         }
1419     }
1420
1421     inline void mark_flat_end()
1422     {
1423         if (! m_pieces.empty())
1424         {
1425             piece& back = m_pieces.back();
1426             back.is_flat_end = true;
1427         }
1428     }
1429
1430     //-------------------------------------------------------------------------
1431
1432     inline void enrich()
1433     {
1434         enrich_intersection_points<false, false, overlay_buffer>(m_turns,
1435             m_clusters, offsetted_rings, offsetted_rings,
1436             m_robust_policy,
1437             m_intersection_strategy);
1438     }
1439
1440     // Discards all rings which do have not-OK intersection points only.
1441     // Those can never be traversed and should not be part of the output.
1442     inline void discard_rings()
1443     {
1444         for (typename boost::range_iterator<turn_vector_type const>::type it =
1445             boost::begin(m_turns); it != boost::end(m_turns); ++it)
1446         {
1447             if (it->location != location_ok)
1448             {
1449                 offsetted_rings[it->operations[0].seg_id.multi_index].has_discarded_intersections = true;
1450                 offsetted_rings[it->operations[1].seg_id.multi_index].has_discarded_intersections = true;
1451             }
1452             else
1453             {
1454                 offsetted_rings[it->operations[0].seg_id.multi_index].has_accepted_intersections = true;
1455                 offsetted_rings[it->operations[1].seg_id.multi_index].has_accepted_intersections = true;
1456             }
1457         }
1458     }
1459
1460     inline bool point_coveredby_original(point_type const& point)
1461     {
1462         typedef typename IntersectionStrategy::disjoint_point_box_strategy_type d_pb_strategy_type;
1463
1464         robust_point_type any_point;
1465         geometry::recalculate(any_point, point, m_robust_policy);
1466
1467         signed_size_type count_in_original = 0;
1468
1469         // Check of the robust point of this outputted ring is in
1470         // any of the robust original rings
1471         // This can go quadratic if the input has many rings, and there
1472         // are many untouched deflated rings around
1473         for (typename std::vector<robust_original>::const_iterator it
1474             = robust_originals.begin();
1475             it != robust_originals.end();
1476             ++it)
1477         {
1478             robust_original const& original = *it;
1479             if (detail::disjoint::disjoint_point_box(any_point,
1480                                                      original.m_box,
1481                                                      d_pb_strategy_type()))
1482             {
1483                 continue;
1484             }
1485
1486             int const geometry_code
1487                 = detail::within::point_in_geometry(any_point,
1488                     original.m_ring, m_point_in_geometry_strategy);
1489
1490             if (geometry_code == -1)
1491             {
1492                 // Outside, continue
1493                 continue;
1494             }
1495
1496             // Apply for possibly nested interior rings
1497             if (original.m_is_interior)
1498             {
1499                 count_in_original--;
1500             }
1501             else if (original.m_has_interiors)
1502             {
1503                 count_in_original++;
1504             }
1505             else
1506             {
1507                 // Exterior ring without interior rings
1508                 return true;
1509             }
1510         }
1511         return count_in_original > 0;
1512     }
1513
1514     // For a deflate, all rings around inner rings which are untouched
1515     // (no intersections/turns) and which are OUTSIDE the original should
1516     // be discarded
1517     inline void discard_nonintersecting_deflated_rings()
1518     {
1519         for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it
1520             = boost::begin(offsetted_rings);
1521             it != boost::end(offsetted_rings);
1522             ++it)
1523         {
1524             buffered_ring<Ring>& ring = *it;
1525             if (! ring.has_intersections()
1526                 && boost::size(ring) > 0u
1527                 && geometry::area(ring, m_area_strategy) < 0)
1528             {
1529                 if (! point_coveredby_original(geometry::range::front(ring)))
1530                 {
1531                     ring.is_untouched_outside_original = true;
1532                 }
1533             }
1534         }
1535     }
1536
1537     inline void block_turns()
1538     {
1539         // To fix left-turn issues like #rt_u13
1540         // But currently it causes more other issues than it fixes
1541 //        m_turns.erase
1542 //            (
1543 //                std::remove_if(boost::begin(m_turns), boost::end(m_turns),
1544 //                                redundant_turn()),
1545 //                boost::end(m_turns)
1546 //            );
1547
1548         for (typename boost::range_iterator<turn_vector_type>::type it =
1549             boost::begin(m_turns); it != boost::end(m_turns); ++it)
1550         {
1551             buffer_turn_info_type& turn = *it;
1552             if (turn.location != location_ok)
1553             {
1554                 // Discard this turn (don't set it to blocked to avoid colocated
1555                 // clusters being discarded afterwards
1556                 turn.discarded = true;
1557             }
1558         }
1559     }
1560
1561     inline void traverse()
1562     {
1563         typedef detail::overlay::traverse
1564             <
1565                 false, false,
1566                 buffered_ring_collection<buffered_ring<Ring> >,
1567                 buffered_ring_collection<buffered_ring<Ring > >,
1568                 overlay_buffer,
1569                 backtrack_for_buffer
1570             > traverser;
1571         std::map<ring_identifier, overlay::ring_turn_info> turn_info_per_ring;
1572
1573         traversed_rings.clear();
1574         buffer_overlay_visitor visitor;
1575         traverser::apply(offsetted_rings, offsetted_rings,
1576                         m_intersection_strategy, m_robust_policy,
1577                         m_turns, traversed_rings,
1578                         turn_info_per_ring,
1579                         m_clusters, visitor);
1580     }
1581
1582     inline void reverse()
1583     {
1584         for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it = boost::begin(offsetted_rings);
1585             it != boost::end(offsetted_rings);
1586             ++it)
1587         {
1588             if (! it->has_intersections())
1589             {
1590                 std::reverse(it->begin(), it->end());
1591             }
1592         }
1593         for (typename boost::range_iterator<buffered_ring_collection<Ring> >::type
1594                 it = boost::begin(traversed_rings);
1595                 it != boost::end(traversed_rings);
1596                 ++it)
1597         {
1598             std::reverse(it->begin(), it->end());
1599         }
1600
1601     }
1602
1603     template <typename GeometryOutput, typename OutputIterator>
1604     inline OutputIterator assign(OutputIterator out) const
1605     {
1606         typedef detail::overlay::ring_properties<point_type, area_result_type> properties;
1607
1608         std::map<ring_identifier, properties> selected;
1609
1610         // Select all rings which do not have any self-intersection
1611         // Inner rings, for deflate, which do not have intersections, and
1612         // which are outside originals, are skipped
1613         // (other ones should be traversed)
1614         signed_size_type index = 0;
1615         for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings);
1616             it != boost::end(offsetted_rings);
1617             ++it, ++index)
1618         {
1619             if (! it->has_intersections()
1620                 && ! it->is_untouched_outside_original)
1621             {
1622                 properties p = properties(*it, m_area_strategy);
1623                 if (p.valid)
1624                 {
1625                     ring_identifier id(0, index, -1);
1626                     selected[id] = p;
1627                 }
1628             }
1629         }
1630
1631         // Select all created rings
1632         index = 0;
1633         for (typename boost::range_iterator<buffered_ring_collection<Ring> const>::type
1634                 it = boost::begin(traversed_rings);
1635                 it != boost::end(traversed_rings);
1636                 ++it, ++index)
1637         {
1638             properties p = properties(*it, m_area_strategy);
1639             if (p.valid)
1640             {
1641                 ring_identifier id(2, index, -1);
1642                 selected[id] = p;
1643             }
1644         }
1645
1646         detail::overlay::assign_parents<overlay_buffer>(offsetted_rings, traversed_rings,
1647                 selected, m_intersection_strategy);
1648         return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out,
1649                                                           m_area_strategy);
1650     }
1651
1652 };
1653
1654
1655 }} // namespace detail::buffer
1656 #endif // DOXYGEN_NO_DETAIL
1657
1658
1659 }} // namespace boost::geometry
1660
1661 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP