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