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