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