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