1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. 4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. 5 6 // This file was modified by Oracle on 2016-2019. 7 // Modifications copyright (c) 2016-2019 Oracle and/or its affiliates. 8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 9 10 // Use, modification and distribution is subject to the Boost Software License, 11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 12 // http://www.boost.org/LICENSE_1_0.txt) 13 14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP 15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP 16 17 #include <algorithm> 18 #include <cstddef> 19 #include <set> 20 21 #include <boost/core/ignore_unused.hpp> 22 #include <boost/range.hpp> 23 24 #include <boost/geometry/core/assert.hpp> 25 #include <boost/geometry/core/coordinate_type.hpp> 26 #include <boost/geometry/core/point_type.hpp> 27 28 #include <boost/geometry/algorithms/covered_by.hpp> 29 #include <boost/geometry/algorithms/envelope.hpp> 30 31 #include <boost/geometry/strategies/buffer.hpp> 32 33 #include <boost/geometry/geometries/ring.hpp> 34 35 #include <boost/geometry/algorithms/detail/buffer/buffered_ring.hpp> 36 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp> 37 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> 38 #include <boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp> 39 #include <boost/geometry/algorithms/detail/buffer/piece_border.hpp> 40 #include <boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp> 41 #include <boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp> 42 43 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> 44 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp> 45 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp> 46 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp> 47 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp> 48 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp> 49 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp> 50 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp> 51 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp> 52 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> 53 #include <boost/geometry/algorithms/detail/partition.hpp> 54 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp> 55 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp> 56 57 #include <boost/geometry/views/detail/normalized_view.hpp> 58 #include <boost/geometry/util/range.hpp> 59 60 // TODO remove this 61 #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> 62 63 namespace boost { namespace geometry 64 { 65 66 67 #ifndef DOXYGEN_NO_DETAIL 68 namespace detail { namespace buffer 69 { 70 71 72 /* 73 * Terminology 74 * 75 * Suppose we make a buffer (using blocked corners) of this rectangle: 76 * 77 * +-------+ 78 * | | 79 * | rect | 80 * | | 81 * +-------+ 82 * 83 * For the sides we get these four buffered side-pieces (marked with s) 84 * and four buffered corner pieces (marked with c) 85 * 86 * c---+---s---+---c 87 * | | piece | | <- see below for details of the middle top-side-piece 88 * +---+-------+---+ 89 * | | | | 90 * s | rect | s <- two side pieces left/right of rect 91 * | | | | 92 * +---+-------+---+ 93 * | | piece | | <- one side-piece below, and two corner pieces 94 * c---+---s---+---c 95 * 96 * The outer part of the picture above, using all pieces, 97 * form together the offsetted ring (marked with o below) 98 * The 8 pieces are part of the piece collection and use for inside-checks 99 * The inner parts form (using 1 or 2 points per piece, often co-located) 100 * form together the robust_polygons (marked with r below) 101 * The remaining piece-segments are helper-segments (marked with h) 102 * 103 * ooooooooooooooooo 104 * o h h o 105 * ohhhrrrrrrrrrhhho 106 * o r r o 107 * o r r o 108 * o r r o 109 * ohhhrrrrrrrrrhhho 110 * o h h o 111 * ooooooooooooooooo 112 * 113 */ 114 115 template 116 < 117 typename Ring, 118 typename IntersectionStrategy, 119 typename DistanceStrategy, 120 typename RobustPolicy 121 > 122 struct buffered_piece_collection 123 { 124 typedef typename geometry::point_type<Ring>::type point_type; 125 typedef typename geometry::coordinate_type<Ring>::type coordinate_type; 126 127 // Robust ring/polygon type, always clockwise 128 typedef geometry::model::ring<point_type> clockwise_ring_type; 129 130 typedef geometry::model::box<point_type> box_type; 131 132 typedef typename IntersectionStrategy::side_strategy_type side_strategy_type; 133 typedef typename IntersectionStrategy::envelope_strategy_type envelope_strategy_type; 134 typedef typename IntersectionStrategy::expand_strategy_type expand_strategy_type; 135 136 typedef typename IntersectionStrategy::template area_strategy 137 < 138 point_type 139 >::type area_strategy_type; 140 141 typedef typename area_strategy_type::template result_type 142 < 143 point_type 144 >::type area_result_type; 145 146 typedef typename IntersectionStrategy::template point_in_geometry_strategy 147 < 148 point_type, 149 clockwise_ring_type 150 >::type point_in_geometry_strategy_type; 151 152 153 typedef buffer_turn_info 154 < 155 point_type, 156 typename segment_ratio_type<point_type, RobustPolicy>::type 157 > buffer_turn_info_type; 158 159 typedef buffer_turn_operation 160 < 161 point_type, 162 typename segment_ratio_type<point_type, RobustPolicy>::type 163 > buffer_turn_operation_type; 164 165 typedef std::vector<buffer_turn_info_type> turn_vector_type; 166 167 typedef piece_border<Ring, point_type> piece_border_type; 168 169 struct piece 170 { 171 strategy::buffer::piece_type type; 172 signed_size_type index; 173 174 signed_size_type left_index; // points to previous piece of same ring 175 signed_size_type right_index; // points to next piece of same ring 176 177 // The next two members (1, 2) form together a complete clockwise ring 178 // for each piece (with one dupped point) 179 // The complete clockwise ring is also included as a robust ring (3) 180 181 // 1: half, part of offsetted_rings 182 183 // Segment identifier of this piece, including its start index 184 segment_identifier first_seg_id; 185 186 // One-beyond index of this piece, to iterate over a ring 187 // from: ring.begin() + pc.first_seg_id.segment_index; 188 // to (not including): ring.begin() + pc.beyond_last_segment_index; 189 // Its ring_id etc are shared with first_seg_id 190 signed_size_type beyond_last_segment_index; 191 192 // part in offsetted ring which is part of offsetted ring 193 signed_size_type offsetted_count; 194 195 bool is_flat_start; 196 bool is_flat_end; 197 198 bool is_deflated; 199 200 // Ring (parts) of this piece, always clockwise 201 piece_border_type m_piece_border; 202 203 point_type m_label_point; 204 205 // For a point buffer 206 point_type m_center; 207 pieceboost::geometry::detail::buffer::buffered_piece_collection::piece208 piece() 209 : type(strategy::buffer::piece_type_unknown) 210 , index(-1) 211 , left_index(-1) 212 , right_index(-1) 213 , beyond_last_segment_index(-1) 214 , offsetted_count(-1) 215 , is_flat_start(false) 216 , is_flat_end(false) 217 , is_deflated(false) 218 { 219 } 220 }; 221 222 struct original_ring 223 { 224 typedef geometry::sections<box_type, 1> sections_type; 225 226 // Creates an empty instance original_ringboost::geometry::detail::buffer::buffered_piece_collection::original_ring227 inline original_ring() 228 : m_is_interior(false) 229 , m_has_interiors(false) 230 {} 231 original_ringboost::geometry::detail::buffer::buffered_piece_collection::original_ring232 inline original_ring(clockwise_ring_type const& ring, 233 bool is_interior, bool has_interiors, 234 envelope_strategy_type const& envelope_strategy, 235 expand_strategy_type const& expand_strategy) 236 : m_ring(ring) 237 , m_is_interior(is_interior) 238 , m_has_interiors(has_interiors) 239 { 240 geometry::envelope(m_ring, m_box, envelope_strategy); 241 242 // create monotonic sections in x-dimension 243 // The dimension is critical because the direction is later used 244 // in the optimization for within checks using winding strategy 245 // and this strategy is scanning in x direction. 246 typedef boost::mpl::vector_c<std::size_t, 0> dimensions; 247 geometry::sectionalize<false, dimensions>(m_ring, 248 detail::no_rescale_policy(), m_sections, 249 envelope_strategy, expand_strategy); 250 } 251 252 clockwise_ring_type m_ring; 253 box_type m_box; 254 sections_type m_sections; 255 256 bool m_is_interior; 257 bool m_has_interiors; 258 }; 259 260 typedef std::vector<piece> piece_vector_type; 261 262 piece_vector_type m_pieces; 263 turn_vector_type m_turns; 264 signed_size_type m_first_piece_index; 265 bool m_deflate; 266 bool m_has_deflated; 267 268 // Offsetted rings, and representations of original ring(s) 269 // both indexed by multi_index 270 buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; 271 std::vector<original_ring> original_rings; 272 std::vector<point_type> m_linear_end_points; 273 274 buffered_ring_collection<Ring> traversed_rings; 275 segment_identifier current_segment_id; 276 277 // Specificly for offsetted rings around points 278 // but also for large joins with many points 279 typedef geometry::sections<box_type, 2> sections_type; 280 sections_type monotonic_sections; 281 282 // Define the clusters, mapping cluster_id -> turns 283 typedef std::map 284 < 285 signed_size_type, 286 detail::overlay::cluster_info 287 > cluster_type; 288 289 cluster_type m_clusters; 290 291 IntersectionStrategy m_intersection_strategy; 292 DistanceStrategy m_distance_strategy; 293 side_strategy_type m_side_strategy; 294 area_strategy_type m_area_strategy; 295 envelope_strategy_type m_envelope_strategy; 296 expand_strategy_type m_expand_strategy; 297 point_in_geometry_strategy_type m_point_in_geometry_strategy; 298 299 RobustPolicy const& m_robust_policy; 300 buffered_piece_collectionboost::geometry::detail::buffer::buffered_piece_collection301 buffered_piece_collection(IntersectionStrategy const& intersection_strategy, 302 DistanceStrategy const& distance_strategy, 303 RobustPolicy const& robust_policy) 304 : m_first_piece_index(-1) 305 , m_deflate(false) 306 , m_has_deflated(false) 307 , m_intersection_strategy(intersection_strategy) 308 , m_distance_strategy(distance_strategy) 309 , m_side_strategy(intersection_strategy.get_side_strategy()) 310 , m_area_strategy(intersection_strategy 311 .template get_area_strategy<point_type>()) 312 , m_envelope_strategy(intersection_strategy.get_envelope_strategy()) 313 , m_expand_strategy(intersection_strategy.get_expand_strategy()) 314 , m_point_in_geometry_strategy(intersection_strategy 315 .template get_point_in_geometry_strategy<point_type, clockwise_ring_type>()) 316 , m_robust_policy(robust_policy) 317 {} 318 is_followingboost::geometry::detail::buffer::buffered_piece_collection319 inline bool is_following(buffer_turn_info_type const& turn, 320 buffer_turn_operation_type const& op) 321 { 322 return turn.operations[0].seg_id.segment_index == op.seg_id.segment_index 323 || turn.operations[1].seg_id.segment_index == op.seg_id.segment_index; 324 } 325 326 // Verify if turns which are classified as OK (outside or on border of 327 // offsetted ring) do not traverse through other turns which are classified 328 // as WITHIN (inside a piece). This can happen if turns are nearly colocated 329 // and due to floating point precision just classified as within, while 330 // they should not be within. 331 // In those cases the turns are fine to travel through (and should), 332 // but they are not made startable. 333 template <typename Vector> pretraverseboost::geometry::detail::buffer::buffered_piece_collection334 inline void pretraverse(Vector const& indexed_operations) 335 { 336 // Verify if the turns which are OK don't skip segments 337 typedef typename boost::range_value<Vector>::type indexed_type; 338 buffer_turn_operation_type last_traversable_operation; 339 buffer_turn_info_type last_traversable_turn; 340 bool first = true; 341 for (std::size_t i = 0; i < indexed_operations.size(); i++) 342 { 343 indexed_type const & itop = indexed_operations[i]; 344 buffer_turn_info_type const& turn = m_turns[itop.turn_index]; 345 346 if (turn.is_turn_traversable && ! first) 347 { 348 // Check previous and next turns. The first is handled 349 BOOST_GEOMETRY_ASSERT(i > 0); 350 indexed_type const& previous_itop = indexed_operations[i - 1]; 351 std::size_t const next_index = i + 1 < indexed_operations.size() ? i + 1 : 0; 352 indexed_type const& next_itop = indexed_operations[next_index]; 353 354 buffer_turn_info_type& previous_turn = m_turns[previous_itop.turn_index]; 355 buffer_turn_info_type& next_turn = m_turns[next_itop.turn_index]; 356 357 if (previous_turn.close_to_offset 358 && is_following(previous_turn, last_traversable_operation)) 359 { 360 previous_turn.is_turn_traversable = true; 361 } 362 else if (next_turn.close_to_offset 363 && is_following(next_turn, last_traversable_operation)) 364 { 365 next_turn.is_turn_traversable = true; 366 } 367 } 368 369 if (turn.is_turn_traversable) 370 { 371 first = false; 372 last_traversable_operation = *itop.subject; 373 last_traversable_turn = turn; 374 } 375 } 376 } 377 check_linear_endpointsboost::geometry::detail::buffer::buffered_piece_collection378 inline void check_linear_endpoints(buffer_turn_info_type& turn) const 379 { 380 // TODO this is quadratic. But the #endpoints, expected, is low, 381 // and only applicable for linear features 382 // (in a multi linestring with many short lines, the #endpoints can be 383 // much higher) 384 for (typename boost::range_iterator<std::vector<point_type> const>::type it 385 = boost::begin(m_linear_end_points); 386 it != boost::end(m_linear_end_points); 387 ++it) 388 { 389 if (detail::equals::equals_point_point(turn.point, *it, 390 m_intersection_strategy.get_equals_point_point_strategy())) 391 { 392 turn.is_linear_end_point = true; 393 } 394 } 395 } 396 verify_turnsboost::geometry::detail::buffer::buffered_piece_collection397 inline void verify_turns() 398 { 399 typedef detail::overlay::indexed_turn_operation 400 < 401 buffer_turn_operation_type 402 > indexed_turn_operation; 403 typedef std::map 404 < 405 ring_identifier, 406 std::vector<indexed_turn_operation> 407 > mapped_vector_type; 408 mapped_vector_type mapped_vector; 409 410 detail::overlay::create_map(m_turns, mapped_vector, 411 enriched_map_buffer_include_policy()); 412 413 // Sort turns over offsetted ring(s) 414 for (typename mapped_vector_type::iterator mit 415 = mapped_vector.begin(); 416 mit != mapped_vector.end(); 417 ++mit) 418 { 419 std::sort(mit->second.begin(), mit->second.end(), buffer_less()); 420 } 421 422 for (typename mapped_vector_type::iterator mit 423 = mapped_vector.begin(); 424 mit != mapped_vector.end(); 425 ++mit) 426 { 427 pretraverse(mit->second); 428 } 429 } 430 deflate_check_turnsboost::geometry::detail::buffer::buffered_piece_collection431 inline void deflate_check_turns() 432 { 433 if (! m_has_deflated) 434 { 435 return; 436 } 437 438 // Deflated rings may not travel to themselves, there should at least 439 // be three turns (which cannot be checked here - TODO: add to traverse) 440 for (typename boost::range_iterator<turn_vector_type>::type it = 441 boost::begin(m_turns); it != boost::end(m_turns); ++it) 442 { 443 buffer_turn_info_type& turn = *it; 444 if (! turn.is_turn_traversable) 445 { 446 continue; 447 } 448 for (int i = 0; i < 2; i++) 449 { 450 buffer_turn_operation_type& op = turn.operations[i]; 451 if (op.enriched.get_next_turn_index() == static_cast<signed_size_type>(turn.turn_index) 452 && m_pieces[op.seg_id.piece_index].is_deflated) 453 { 454 // Keep traversable, but don't start here 455 op.enriched.startable = false; 456 } 457 } 458 } 459 } 460 461 // Check if a turn is inside any of the originals check_turn_in_originalboost::geometry::detail::buffer::buffered_piece_collection462 inline void check_turn_in_original() 463 { 464 typedef turn_in_original_ovelaps_box 465 < 466 typename IntersectionStrategy::disjoint_point_box_strategy_type 467 > turn_in_original_ovelaps_box_type; 468 typedef original_ovelaps_box 469 < 470 typename IntersectionStrategy::disjoint_box_box_strategy_type 471 > original_ovelaps_box_type; 472 473 turn_in_original_visitor 474 < 475 turn_vector_type, 476 point_in_geometry_strategy_type 477 > visitor(m_turns, m_point_in_geometry_strategy); 478 479 geometry::partition 480 < 481 box_type, 482 include_turn_policy, 483 detail::partition::include_all_policy 484 >::apply(m_turns, original_rings, visitor, 485 turn_get_box(), turn_in_original_ovelaps_box_type(), 486 original_get_box(), original_ovelaps_box_type()); 487 488 bool const deflate = m_distance_strategy.negative(); 489 490 for (typename boost::range_iterator<turn_vector_type>::type it = 491 boost::begin(m_turns); it != boost::end(m_turns); ++it) 492 { 493 buffer_turn_info_type& turn = *it; 494 if (turn.is_turn_traversable) 495 { 496 if (deflate && turn.count_in_original <= 0) 497 { 498 // For deflate/negative buffers: 499 // it is not in the original, so don't use it 500 turn.is_turn_traversable = false; 501 } 502 else if (! deflate && turn.count_in_original > 0) 503 { 504 // For inflate: it is in original, so don't use it 505 turn.is_turn_traversable = false; 506 } 507 } 508 } 509 } 510 update_turn_administrationboost::geometry::detail::buffer::buffered_piece_collection511 inline void update_turn_administration() 512 { 513 std::size_t index = 0; 514 for (typename boost::range_iterator<turn_vector_type>::type it = 515 boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index) 516 { 517 buffer_turn_info_type& turn = *it; 518 519 // Update member used 520 turn.turn_index = index; 521 522 // Verify if a turn is a linear endpoint 523 if (! turn.is_linear_end_point) 524 { 525 check_linear_endpoints(turn); 526 } 527 } 528 } 529 530 // Calculate properties of piece borders which are not influenced 531 // by turns themselves: 532 // - envelopes (essential for partitioning during calc turns) 533 // - convexity 534 // - monotonicity 535 // - min/max radius of point buffers 536 // - (if pieces are reversed) update_piece_administrationboost::geometry::detail::buffer::buffered_piece_collection537 inline void update_piece_administration() 538 { 539 for (typename piece_vector_type::iterator it = boost::begin(m_pieces); 540 it != boost::end(m_pieces); 541 ++it) 542 { 543 piece& pc = *it; 544 piece_border_type& border = pc.m_piece_border; 545 buffered_ring<Ring> const& ring = offsetted_rings[pc.first_seg_id.multi_index]; 546 547 if (pc.offsetted_count > 0) 548 { 549 if (pc.type != strategy::buffer::buffered_concave) 550 { 551 border.set_offsetted(ring, pc.first_seg_id.segment_index, 552 pc.beyond_last_segment_index); 553 } 554 555 // Calculate envelopes for piece borders 556 border.get_properties_of_border(pc.type == geometry::strategy::buffer::buffered_point, pc.m_center); 557 if (! pc.is_flat_end && ! pc.is_flat_start) 558 { 559 border.get_properties_of_offsetted_ring_part(m_side_strategy); 560 } 561 } 562 } 563 } 564 get_turnsboost::geometry::detail::buffer::buffered_piece_collection565 inline void get_turns() 566 { 567 update_piece_administration(); 568 569 { 570 // Calculate the turns 571 piece_turn_visitor 572 < 573 piece_vector_type, 574 buffered_ring_collection<buffered_ring<Ring> >, 575 turn_vector_type, 576 IntersectionStrategy, 577 RobustPolicy 578 > visitor(m_pieces, offsetted_rings, m_turns, 579 m_intersection_strategy, m_robust_policy); 580 581 typedef detail::section::get_section_box 582 < 583 typename IntersectionStrategy::expand_box_strategy_type 584 > get_section_box_type; 585 typedef detail::section::overlaps_section_box 586 < 587 typename IntersectionStrategy::disjoint_box_box_strategy_type 588 > overlaps_section_box_type; 589 590 detail::sectionalize::enlarge_sections(monotonic_sections, 591 m_envelope_strategy); 592 geometry::partition 593 < 594 box_type 595 >::apply(monotonic_sections, visitor, 596 get_section_box_type(), 597 overlaps_section_box_type()); 598 } 599 600 update_turn_administration(); 601 602 { 603 // Check if turns are inside pieces 604 turn_in_piece_visitor 605 < 606 typename geometry::cs_tag<point_type>::type, 607 turn_vector_type, piece_vector_type, DistanceStrategy 608 > visitor(m_turns, m_pieces, m_distance_strategy); 609 610 typedef turn_ovelaps_box 611 < 612 typename IntersectionStrategy::disjoint_point_box_strategy_type 613 > turn_ovelaps_box_type; 614 typedef piece_ovelaps_box 615 < 616 typename IntersectionStrategy::disjoint_box_box_strategy_type 617 > piece_ovelaps_box_type; 618 619 geometry::partition 620 < 621 box_type 622 >::apply(m_turns, m_pieces, visitor, 623 turn_get_box(), turn_ovelaps_box_type(), 624 piece_get_box(), piece_ovelaps_box_type()); 625 } 626 } 627 start_new_ringboost::geometry::detail::buffer::buffered_piece_collection628 inline void start_new_ring(bool deflate) 629 { 630 std::size_t const n = offsetted_rings.size(); 631 current_segment_id.source_index = 0; 632 current_segment_id.multi_index = static_cast<signed_size_type>(n); 633 current_segment_id.ring_index = -1; 634 current_segment_id.segment_index = 0; 635 636 offsetted_rings.resize(n + 1); 637 original_rings.resize(n + 1); 638 639 m_first_piece_index = static_cast<signed_size_type>(boost::size(m_pieces)); 640 m_deflate = deflate; 641 if (deflate) 642 { 643 // Pieces contain either deflated exterior rings, or inflated 644 // interior rings which are effectively deflated too 645 m_has_deflated = true; 646 } 647 } 648 abort_ringboost::geometry::detail::buffer::buffered_piece_collection649 inline void abort_ring() 650 { 651 // Remove all created pieces for this ring, sections, last offsetted 652 while (! m_pieces.empty() 653 && m_pieces.back().first_seg_id.multi_index 654 == current_segment_id.multi_index) 655 { 656 m_pieces.pop_back(); 657 } 658 659 offsetted_rings.pop_back(); 660 original_rings.pop_back(); 661 662 m_first_piece_index = -1; 663 } 664 update_last_pointboost::geometry::detail::buffer::buffered_piece_collection665 inline void update_last_point(point_type const& p, 666 buffered_ring<Ring>& ring) 667 { 668 // For the first point of a new piece, and there were already 669 // points in the offsetted ring, for some piece types the first point 670 // is a duplicate of the last point of the previous piece. 671 672 // TODO: disable that, that point should not be added 673 674 // For now, it is made equal because due to numerical instability, 675 // it can be a tiny bit off, possibly causing a self-intersection 676 677 BOOST_GEOMETRY_ASSERT(boost::size(m_pieces) > 0); 678 if (! ring.empty() 679 && current_segment_id.segment_index 680 == m_pieces.back().first_seg_id.segment_index) 681 { 682 ring.back() = p; 683 } 684 } 685 set_piece_centerboost::geometry::detail::buffer::buffered_piece_collection686 inline void set_piece_center(point_type const& center) 687 { 688 BOOST_GEOMETRY_ASSERT(! m_pieces.empty()); 689 m_pieces.back().m_center = center; 690 } 691 finish_ringboost::geometry::detail::buffer::buffered_piece_collection692 inline bool finish_ring(strategy::buffer::result_code code) 693 { 694 if (code == strategy::buffer::result_error_numerical) 695 { 696 abort_ring(); 697 return false; 698 } 699 700 if (m_first_piece_index == -1) 701 { 702 return false; 703 } 704 705 // Casted version 706 std::size_t const first_piece_index 707 = static_cast<std::size_t>(m_first_piece_index); 708 signed_size_type const last_piece_index 709 = static_cast<signed_size_type>(boost::size(m_pieces)) - 1; 710 711 if (first_piece_index < boost::size(m_pieces)) 712 { 713 // If pieces were added, 714 // reassign left-of-first and right-of-last 715 geometry::range::at(m_pieces, first_piece_index).left_index 716 = last_piece_index; 717 geometry::range::back(m_pieces).right_index = m_first_piece_index; 718 } 719 720 buffered_ring<Ring>& added = offsetted_rings.back(); 721 if (! boost::empty(added)) 722 { 723 // Make sure the closing point is identical (they are calculated 724 // separately by different pieces) 725 range::back(added) = range::front(added); 726 } 727 728 for (std::size_t i = first_piece_index; i < boost::size(m_pieces); i++) 729 { 730 sectionalize(m_pieces[i], added); 731 } 732 733 m_first_piece_index = -1; 734 return true; 735 } 736 737 template <typename InputRing> finish_ringboost::geometry::detail::buffer::buffered_piece_collection738 inline void finish_ring(strategy::buffer::result_code code, 739 InputRing const& input_ring, 740 bool is_interior, bool has_interiors) 741 { 742 if (! finish_ring(code)) 743 { 744 return; 745 } 746 747 if (! input_ring.empty()) 748 { 749 // Assign the ring to the original_ring collection 750 // For rescaling, it is recalculated. Without rescaling, it 751 // is just assigning (note that this Ring type is the 752 // GeometryOut type, which might differ from the input ring type) 753 clockwise_ring_type clockwise_ring; 754 755 typedef detail::normalized_view<InputRing const> view_type; 756 view_type const view(input_ring); 757 758 for (typename boost::range_iterator<view_type const>::type it = 759 boost::begin(view); it != boost::end(view); ++it) 760 { 761 clockwise_ring.push_back(*it); 762 } 763 764 original_rings.back() 765 = original_ring(clockwise_ring, 766 is_interior, has_interiors, 767 m_envelope_strategy, m_expand_strategy); 768 } 769 } 770 set_current_ring_concaveboost::geometry::detail::buffer::buffered_piece_collection771 inline void set_current_ring_concave() 772 { 773 BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0); 774 offsetted_rings.back().has_concave = true; 775 } 776 add_pointboost::geometry::detail::buffer::buffered_piece_collection777 inline signed_size_type add_point(point_type const& p) 778 { 779 BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0); 780 781 buffered_ring<Ring>& current_ring = offsetted_rings.back(); 782 update_last_point(p, current_ring); 783 784 current_segment_id.segment_index++; 785 current_ring.push_back(p); 786 return static_cast<signed_size_type>(current_ring.size()); 787 } 788 789 //------------------------------------------------------------------------- 790 create_pieceboost::geometry::detail::buffer::buffered_piece_collection791 inline piece& create_piece(strategy::buffer::piece_type type, 792 bool decrease_segment_index_by_one) 793 { 794 if (type == strategy::buffer::buffered_concave) 795 { 796 offsetted_rings.back().has_concave = true; 797 } 798 799 piece pc; 800 pc.type = type; 801 pc.index = static_cast<signed_size_type>(boost::size(m_pieces)); 802 pc.is_deflated = m_deflate; 803 804 current_segment_id.piece_index = pc.index; 805 806 pc.first_seg_id = current_segment_id; 807 808 // Assign left/right (for first/last piece per ring they will be re-assigned later) 809 pc.left_index = pc.index - 1; 810 pc.right_index = pc.index + 1; 811 812 std::size_t const n = boost::size(offsetted_rings.back()); 813 pc.first_seg_id.segment_index = decrease_segment_index_by_one ? n - 1 : n; 814 pc.beyond_last_segment_index = pc.first_seg_id.segment_index; 815 816 m_pieces.push_back(pc); 817 return m_pieces.back(); 818 } 819 init_rescale_pieceboost::geometry::detail::buffer::buffered_piece_collection820 inline void init_rescale_piece(piece& pc) 821 { 822 if (pc.first_seg_id.segment_index < 0) 823 { 824 // This indicates an error situation: an earlier piece was empty 825 // It currently does not happen 826 pc.offsetted_count = 0; 827 return; 828 } 829 830 BOOST_GEOMETRY_ASSERT(pc.first_seg_id.multi_index >= 0); 831 BOOST_GEOMETRY_ASSERT(pc.beyond_last_segment_index >= 0); 832 833 pc.offsetted_count = pc.beyond_last_segment_index - pc.first_seg_id.segment_index; 834 BOOST_GEOMETRY_ASSERT(pc.offsetted_count >= 0); 835 } 836 add_piece_pointboost::geometry::detail::buffer::buffered_piece_collection837 inline void add_piece_point(piece& pc, const point_type& point, bool add_to_original) 838 { 839 if (add_to_original && pc.type != strategy::buffer::buffered_concave) 840 { 841 pc.m_piece_border.add_original_point(point); 842 } 843 else 844 { 845 pc.m_label_point = point; 846 } 847 } 848 sectionalizeboost::geometry::detail::buffer::buffered_piece_collection849 inline void sectionalize(piece const& pc, buffered_ring<Ring> const& ring) 850 { 851 typedef geometry::detail::sectionalize::sectionalize_part 852 < 853 point_type, 854 boost::mpl::vector_c<std::size_t, 0, 1> // x,y dimension 855 > sectionalizer; 856 857 // Create a ring-identifier. The source-index is the piece index 858 // The multi_index is as in this collection (the ring), but not used here 859 // The ring_index is not used 860 ring_identifier const ring_id(pc.index, pc.first_seg_id.multi_index, -1); 861 862 sectionalizer::apply(monotonic_sections, 863 boost::begin(ring) + pc.first_seg_id.segment_index, 864 boost::begin(ring) + pc.beyond_last_segment_index, 865 m_robust_policy, 866 ring_id, 10); 867 } 868 finish_pieceboost::geometry::detail::buffer::buffered_piece_collection869 inline void finish_piece(piece& pc) 870 { 871 init_rescale_piece(pc); 872 } 873 finish_pieceboost::geometry::detail::buffer::buffered_piece_collection874 inline void finish_piece(piece& pc, 875 point_type const& point1, 876 point_type const& point2, 877 point_type const& point3) 878 { 879 init_rescale_piece(pc); 880 if (pc.offsetted_count == 0) 881 { 882 return; 883 } 884 885 add_piece_point(pc, point1, false); 886 add_piece_point(pc, point2, true); 887 add_piece_point(pc, point3, false); 888 } 889 finish_pieceboost::geometry::detail::buffer::buffered_piece_collection890 inline void finish_piece(piece& pc, 891 point_type const& point1, 892 point_type const& point2, 893 point_type const& point3, 894 point_type const& point4) 895 { 896 init_rescale_piece(pc); 897 898 // Add the four points. Note that points 2 and 3 are the originals, 899 // and that they are already passed in reverse order 900 // (because the offsetted ring is in clockwise order) 901 add_piece_point(pc, point1, false); 902 add_piece_point(pc, point2, true); 903 add_piece_point(pc, point3, true); 904 add_piece_point(pc, point4, false); 905 } 906 907 template <typename Range> add_range_to_pieceboost::geometry::detail::buffer::buffered_piece_collection908 inline void add_range_to_piece(piece& pc, Range const& range, bool add_front) 909 { 910 BOOST_GEOMETRY_ASSERT(boost::size(range) != 0u); 911 912 typename Range::const_iterator it = boost::begin(range); 913 914 // If it follows a non-join (so basically the same piece-type) point b1 should be added. 915 // There should be two intersections later and it should be discarded. 916 // But for now we need it to calculate intersections 917 if (add_front) 918 { 919 add_point(*it); 920 } 921 922 for (++it; it != boost::end(range); ++it) 923 { 924 pc.beyond_last_segment_index = add_point(*it); 925 } 926 } 927 add_pieceboost::geometry::detail::buffer::buffered_piece_collection928 inline void add_piece(strategy::buffer::piece_type type, point_type const& p, 929 point_type const& b1, point_type const& b2) 930 { 931 piece& pc = create_piece(type, false); 932 add_point(b1); 933 pc.beyond_last_segment_index = add_point(b2); 934 finish_piece(pc, b2, p, b1); 935 } 936 937 template <typename Range> add_pieceboost::geometry::detail::buffer::buffered_piece_collection938 inline void add_piece(strategy::buffer::piece_type type, Range const& range, 939 bool decrease_segment_index_by_one) 940 { 941 piece& pc = create_piece(type, decrease_segment_index_by_one); 942 943 if (boost::size(range) > 0u) 944 { 945 add_range_to_piece(pc, range, offsetted_rings.back().empty()); 946 } 947 finish_piece(pc); 948 } 949 950 template <typename Range> add_pieceboost::geometry::detail::buffer::buffered_piece_collection951 inline void add_piece(strategy::buffer::piece_type type, 952 point_type const& p, Range const& range) 953 { 954 piece& pc = create_piece(type, true); 955 956 if (boost::size(range) > 0u) 957 { 958 add_range_to_piece(pc, range, offsetted_rings.back().empty()); 959 finish_piece(pc, range.back(), p, range.front()); 960 } 961 else 962 { 963 finish_piece(pc); 964 } 965 } 966 967 template <typename Range> add_side_pieceboost::geometry::detail::buffer::buffered_piece_collection968 inline void add_side_piece(point_type const& original_point1, 969 point_type const& original_point2, 970 Range const& range, bool first) 971 { 972 BOOST_GEOMETRY_ASSERT(boost::size(range) >= 2u); 973 974 piece& pc = create_piece(strategy::buffer::buffered_segment, ! first); 975 add_range_to_piece(pc, range, first); 976 977 // Add the four points of the side, starting with the last point of the 978 // range, and reversing the order of the originals to keep it clockwise 979 finish_piece(pc, range.back(), original_point2, original_point1, range.front()); 980 } 981 982 template <typename EndcapStrategy, typename Range> add_endcapboost::geometry::detail::buffer::buffered_piece_collection983 inline void add_endcap(EndcapStrategy const& strategy, Range const& range, 984 point_type const& end_point) 985 { 986 boost::ignore_unused(strategy); 987 988 if (range.empty()) 989 { 990 return; 991 } 992 strategy::buffer::piece_type pt = strategy.get_piece_type(); 993 if (pt == strategy::buffer::buffered_flat_end) 994 { 995 // It is flat, should just be added, without helper segments 996 add_piece(pt, range, true); 997 } 998 else 999 { 1000 // Normal case, it has an "inside", helper segments should be added 1001 add_piece(pt, end_point, range); 1002 } 1003 } 1004 mark_flat_startboost::geometry::detail::buffer::buffered_piece_collection1005 inline void mark_flat_start(point_type const& point) 1006 { 1007 if (! m_pieces.empty()) 1008 { 1009 piece& back = m_pieces.back(); 1010 back.is_flat_start = true; 1011 1012 // This happens to linear buffers, and it will be the very 1013 // first or last point. If that coincides with a turn, 1014 // and the turn was marked as ON_BORDER 1015 // the turn should NOT be within (even though it can be marked 1016 // as such) 1017 m_linear_end_points.push_back(point); 1018 } 1019 } 1020 mark_flat_endboost::geometry::detail::buffer::buffered_piece_collection1021 inline void mark_flat_end(point_type const& point) 1022 { 1023 if (! m_pieces.empty()) 1024 { 1025 piece& back = m_pieces.back(); 1026 back.is_flat_end = true; 1027 m_linear_end_points.push_back(point); 1028 } 1029 } 1030 1031 //------------------------------------------------------------------------- 1032 enrichboost::geometry::detail::buffer::buffered_piece_collection1033 inline void enrich() 1034 { 1035 enrich_intersection_points<false, false, overlay_buffer>(m_turns, 1036 m_clusters, offsetted_rings, offsetted_rings, 1037 m_robust_policy, 1038 m_intersection_strategy); 1039 } 1040 1041 // Discards all rings which do have not-OK intersection points only. 1042 // Those can never be traversed and should not be part of the output. discard_ringsboost::geometry::detail::buffer::buffered_piece_collection1043 inline void discard_rings() 1044 { 1045 for (typename boost::range_iterator<turn_vector_type const>::type it = 1046 boost::begin(m_turns); it != boost::end(m_turns); ++it) 1047 { 1048 if (it->is_turn_traversable) 1049 { 1050 offsetted_rings[it->operations[0].seg_id.multi_index].has_accepted_intersections = true; 1051 offsetted_rings[it->operations[1].seg_id.multi_index].has_accepted_intersections = true; 1052 } 1053 else 1054 { 1055 offsetted_rings[it->operations[0].seg_id.multi_index].has_discarded_intersections = true; 1056 offsetted_rings[it->operations[1].seg_id.multi_index].has_discarded_intersections = true; 1057 } 1058 } 1059 } 1060 point_coveredby_originalboost::geometry::detail::buffer::buffered_piece_collection1061 inline bool point_coveredby_original(point_type const& point) 1062 { 1063 typedef typename IntersectionStrategy::disjoint_point_box_strategy_type d_pb_strategy_type; 1064 1065 signed_size_type count_in_original = 0; 1066 1067 // Check of the robust point of this outputted ring is in 1068 // any of the robust original rings 1069 // This can go quadratic if the input has many rings, and there 1070 // are many untouched deflated rings around 1071 for (typename std::vector<original_ring>::const_iterator it 1072 = original_rings.begin(); 1073 it != original_rings.end(); 1074 ++it) 1075 { 1076 original_ring const& original = *it; 1077 if (original.m_ring.empty()) 1078 { 1079 continue; 1080 } 1081 if (detail::disjoint::disjoint_point_box(point, 1082 original.m_box, 1083 d_pb_strategy_type())) 1084 { 1085 continue; 1086 } 1087 1088 int const geometry_code 1089 = detail::within::point_in_geometry(point, 1090 original.m_ring, m_point_in_geometry_strategy); 1091 1092 if (geometry_code == -1) 1093 { 1094 // Outside, continue 1095 continue; 1096 } 1097 1098 // Apply for possibly nested interior rings 1099 if (original.m_is_interior) 1100 { 1101 count_in_original--; 1102 } 1103 else if (original.m_has_interiors) 1104 { 1105 count_in_original++; 1106 } 1107 else 1108 { 1109 // Exterior ring without interior rings 1110 return true; 1111 } 1112 } 1113 return count_in_original > 0; 1114 } 1115 1116 // For a deflate, all rings around inner rings which are untouched 1117 // (no intersections/turns) and which are OUTSIDE the original should 1118 // be discarded discard_nonintersecting_deflated_ringsboost::geometry::detail::buffer::buffered_piece_collection1119 inline void discard_nonintersecting_deflated_rings() 1120 { 1121 for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it 1122 = boost::begin(offsetted_rings); 1123 it != boost::end(offsetted_rings); 1124 ++it) 1125 { 1126 buffered_ring<Ring>& ring = *it; 1127 if (! ring.has_intersections() 1128 && boost::size(ring) > 0u 1129 && geometry::area(ring, m_area_strategy) < 0) 1130 { 1131 if (! point_coveredby_original(geometry::range::front(ring))) 1132 { 1133 ring.is_untouched_outside_original = true; 1134 } 1135 } 1136 } 1137 } 1138 block_turnsboost::geometry::detail::buffer::buffered_piece_collection1139 inline void block_turns() 1140 { 1141 for (typename boost::range_iterator<turn_vector_type>::type it = 1142 boost::begin(m_turns); it != boost::end(m_turns); ++it) 1143 { 1144 buffer_turn_info_type& turn = *it; 1145 if (! turn.is_turn_traversable) 1146 { 1147 // Discard this turn (don't set it to blocked to avoid colocated 1148 // clusters being discarded afterwards 1149 turn.discarded = true; 1150 } 1151 } 1152 } 1153 traverseboost::geometry::detail::buffer::buffered_piece_collection1154 inline void traverse() 1155 { 1156 typedef detail::overlay::traverse 1157 < 1158 false, false, 1159 buffered_ring_collection<buffered_ring<Ring> >, 1160 buffered_ring_collection<buffered_ring<Ring > >, 1161 overlay_buffer, 1162 backtrack_for_buffer 1163 > traverser; 1164 std::map<ring_identifier, overlay::ring_turn_info> turn_info_per_ring; 1165 1166 traversed_rings.clear(); 1167 buffer_overlay_visitor visitor; 1168 traverser::apply(offsetted_rings, offsetted_rings, 1169 m_intersection_strategy, m_robust_policy, 1170 m_turns, traversed_rings, 1171 turn_info_per_ring, 1172 m_clusters, visitor); 1173 } 1174 reverseboost::geometry::detail::buffer::buffered_piece_collection1175 inline void reverse() 1176 { 1177 for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it = boost::begin(offsetted_rings); 1178 it != boost::end(offsetted_rings); 1179 ++it) 1180 { 1181 if (! it->has_intersections()) 1182 { 1183 std::reverse(it->begin(), it->end()); 1184 } 1185 } 1186 for (typename boost::range_iterator<buffered_ring_collection<Ring> >::type 1187 it = boost::begin(traversed_rings); 1188 it != boost::end(traversed_rings); 1189 ++it) 1190 { 1191 std::reverse(it->begin(), it->end()); 1192 } 1193 } 1194 1195 template <typename GeometryOutput, typename OutputIterator> assignboost::geometry::detail::buffer::buffered_piece_collection1196 inline OutputIterator assign(OutputIterator out) const 1197 { 1198 typedef detail::overlay::ring_properties<point_type, area_result_type> properties; 1199 1200 std::map<ring_identifier, properties> selected; 1201 1202 // Select all rings which do not have any self-intersection 1203 // Inner rings, for deflate, which do not have intersections, and 1204 // which are outside originals, are skipped 1205 // (other ones should be traversed) 1206 signed_size_type index = 0; 1207 for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings); 1208 it != boost::end(offsetted_rings); 1209 ++it, ++index) 1210 { 1211 if (! it->has_intersections() 1212 && ! it->is_untouched_outside_original) 1213 { 1214 properties p = properties(*it, m_area_strategy); 1215 if (p.valid) 1216 { 1217 ring_identifier id(0, index, -1); 1218 selected[id] = p; 1219 } 1220 } 1221 } 1222 1223 // Select all created rings 1224 index = 0; 1225 for (typename boost::range_iterator<buffered_ring_collection<Ring> const>::type 1226 it = boost::begin(traversed_rings); 1227 it != boost::end(traversed_rings); 1228 ++it, ++index) 1229 { 1230 properties p = properties(*it, m_area_strategy); 1231 if (p.valid) 1232 { 1233 ring_identifier id(2, index, -1); 1234 selected[id] = p; 1235 } 1236 } 1237 1238 detail::overlay::assign_parents<overlay_buffer>(offsetted_rings, traversed_rings, 1239 selected, m_intersection_strategy); 1240 return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out, 1241 m_area_strategy); 1242 } 1243 1244 }; 1245 1246 1247 }} // namespace detail::buffer 1248 #endif // DOXYGEN_NO_DETAIL 1249 1250 1251 }} // namespace boost::geometry 1252 1253 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP 1254