1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2015-2016 Barend Gehrels, Amsterdam, the Netherlands. 4 5 // This file was modified by Oracle on 2018. 6 // Modifications copyright (c) 2018 Oracle and/or its affiliates. 7 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_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP 15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP 16 17 #include <cstddef> 18 #include <map> 19 20 #include <boost/range.hpp> 21 22 #include <boost/geometry/algorithms/detail/ring_identifier.hpp> 23 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp> 24 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> 25 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> 26 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> 27 #include <boost/geometry/core/access.hpp> 28 #include <boost/geometry/core/assert.hpp> 29 #include <boost/geometry/util/condition.hpp> 30 31 namespace boost { namespace geometry 32 { 33 34 #ifndef DOXYGEN_NO_DETAIL 35 namespace detail { namespace overlay 36 { 37 38 template 39 < 40 bool Reverse1, 41 bool Reverse2, 42 overlay_type OverlayType, 43 typename Geometry1, 44 typename Geometry2, 45 typename Turns, 46 typename Clusters, 47 typename RobustPolicy, 48 typename Visitor 49 > 50 struct traversal_switch_detector 51 { 52 static const operation_type target_operation 53 = operation_from_overlay<OverlayType>::value; 54 static const operation_type opposite_operation 55 = target_operation == operation_union 56 ? operation_intersection 57 : operation_union; 58 59 enum isolation_type 60 { 61 isolation_unknown = -1, 62 isolation_no = 0, 63 isolation_yes = 1, 64 isolation_multiple = 2 65 }; 66 67 typedef typename boost::range_value<Turns>::type turn_type; 68 typedef typename turn_type::turn_operation_type turn_operation_type; 69 typedef std::set<signed_size_type> set_type; 70 71 // Per ring, first turns are collected (in turn_indices), and later 72 // a region_id is assigned 73 struct merged_ring_properties 74 { 75 signed_size_type region_id; 76 set_type turn_indices; 77 merged_ring_propertiesboost::geometry::detail::overlay::traversal_switch_detector::merged_ring_properties78 merged_ring_properties() 79 : region_id(-1) 80 {} 81 }; 82 83 struct connection_properties 84 { 85 std::size_t count; 86 // Contains turn-index OR, if clustered, minus-cluster_id 87 set_type unique_turn_ids; connection_propertiesboost::geometry::detail::overlay::traversal_switch_detector::connection_properties88 connection_properties() 89 : count(0) 90 {} 91 }; 92 93 typedef std::map<signed_size_type, connection_properties> connection_map; 94 95 // Per region, a set of properties is maintained, including its connections 96 // to other regions 97 struct region_properties 98 { 99 signed_size_type region_id; 100 isolation_type isolated; 101 set_type unique_turn_ids; 102 103 // Maps from connected region_id to their properties 104 connection_map connected_region_counts; 105 region_propertiesboost::geometry::detail::overlay::traversal_switch_detector::region_properties106 region_properties() 107 : region_id(-1) 108 , isolated(isolation_unknown) 109 {} 110 }; 111 112 // Keeps turn indices per ring 113 typedef std::map<ring_identifier, merged_ring_properties > merge_map; 114 typedef std::map<signed_size_type, region_properties> region_connection_map; 115 116 typedef set_type::const_iterator set_iterator; 117 traversal_switch_detectorboost::geometry::detail::overlay::traversal_switch_detector118 inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2, 119 Turns& turns, Clusters& clusters, 120 RobustPolicy const& robust_policy, Visitor& visitor) 121 : m_geometry1(geometry1) 122 , m_geometry2(geometry2) 123 , m_turns(turns) 124 , m_clusters(clusters) 125 , m_robust_policy(robust_policy) 126 , m_visitor(visitor) 127 { 128 } 129 one_connection_to_another_regionboost::geometry::detail::overlay::traversal_switch_detector130 bool one_connection_to_another_region(region_properties const& region) const 131 { 132 // For example: 133 // +----------------------+ 134 // | __ | 135 // | / \| 136 // | | x 137 // | \__/| 138 // | | 139 // +----------------------+ 140 141 if (region.connected_region_counts.size() == 1) 142 { 143 connection_properties const& cprop = region.connected_region_counts.begin()->second; 144 return cprop.count <= 1; 145 } 146 return region.connected_region_counts.empty(); 147 } 148 149 // TODO: might be combined with previous multiple_connections_to_one_regionboost::geometry::detail::overlay::traversal_switch_detector150 bool multiple_connections_to_one_region(region_properties const& region) const 151 { 152 // For example: 153 // +----------------------+ 154 // | __ | 155 // | / \| 156 // | | x 157 // | \ /| 158 // | / \| 159 // | | x 160 // | \__/| 161 // | | 162 // +----------------------+ 163 164 if (region.connected_region_counts.size() == 1) 165 { 166 connection_properties const& cprop = region.connected_region_counts.begin()->second; 167 return cprop.count > 1; 168 } 169 return false; 170 } 171 one_connection_to_multiple_regionsboost::geometry::detail::overlay::traversal_switch_detector172 bool one_connection_to_multiple_regions(region_properties const& region) const 173 { 174 // For example: 175 // +----------------------+ 176 // | __ | __ 177 // | / \|/ | 178 // | | x | 179 // | \__/|\__| 180 // | | 181 // +----------------------+ 182 183 bool first = true; 184 signed_size_type first_turn_id = 0; 185 for (typename connection_map::const_iterator it = region.connected_region_counts.begin(); 186 it != region.connected_region_counts.end(); ++it) 187 { 188 connection_properties const& cprop = it->second; 189 190 if (cprop.count != 1) 191 { 192 return false; 193 } 194 signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin(); 195 if (first) 196 { 197 first_turn_id = unique_turn_id; 198 first = false; 199 } 200 else if (first_turn_id != unique_turn_id) 201 { 202 return false; 203 } 204 } 205 return true; 206 } 207 ii_turn_connects_two_regionsboost::geometry::detail::overlay::traversal_switch_detector208 bool ii_turn_connects_two_regions(region_properties const& region, 209 region_properties const& connected_region, 210 signed_size_type turn_index) const 211 { 212 turn_type const& turn = m_turns[turn_index]; 213 if (! turn.both(operation_intersection)) 214 { 215 return false; 216 } 217 218 signed_size_type const id0 = turn.operations[0].enriched.region_id; 219 signed_size_type const id1 = turn.operations[1].enriched.region_id; 220 221 return (id0 == region.region_id && id1 == connected_region.region_id) 222 || (id1 == region.region_id && id0 == connected_region.region_id); 223 } 224 225 isolated_multiple_connectionboost::geometry::detail::overlay::traversal_switch_detector226 bool isolated_multiple_connection(region_properties const& region, 227 region_properties const& connected_region) const 228 { 229 if (connected_region.isolated != isolation_multiple) 230 { 231 return false; 232 } 233 234 // First step: compare turns of regions with turns of connected region 235 set_type turn_ids = region.unique_turn_ids; 236 for (set_iterator sit = connected_region.unique_turn_ids.begin(); 237 sit != connected_region.unique_turn_ids.end(); ++sit) 238 { 239 turn_ids.erase(*sit); 240 } 241 242 // There should be one connection (turn or cluster) left 243 if (turn_ids.size() != 1) 244 { 245 return false; 246 } 247 248 for (set_iterator sit = connected_region.unique_turn_ids.begin(); 249 sit != connected_region.unique_turn_ids.end(); ++sit) 250 { 251 signed_size_type const id_or_index = *sit; 252 if (id_or_index >= 0) 253 { 254 if (! ii_turn_connects_two_regions(region, connected_region, id_or_index)) 255 { 256 return false; 257 } 258 } 259 else 260 { 261 signed_size_type const cluster_id = -id_or_index; 262 typename Clusters::const_iterator it = m_clusters.find(cluster_id); 263 if (it != m_clusters.end()) 264 { 265 cluster_info const& cinfo = it->second; 266 for (set_iterator cit = cinfo.turn_indices.begin(); 267 cit != cinfo.turn_indices.end(); ++cit) 268 { 269 if (! ii_turn_connects_two_regions(region, connected_region, *cit)) 270 { 271 return false; 272 } 273 } 274 } 275 } 276 } 277 278 return true; 279 } 280 has_only_isolated_childrenboost::geometry::detail::overlay::traversal_switch_detector281 bool has_only_isolated_children(region_properties const& region) const 282 { 283 bool first_with_turn = true; 284 signed_size_type first_turn_id = 0; 285 286 for (typename connection_map::const_iterator it = region.connected_region_counts.begin(); 287 it != region.connected_region_counts.end(); ++it) 288 { 289 signed_size_type const region_id = it->first; 290 connection_properties const& cprop = it->second; 291 292 typename region_connection_map::const_iterator mit = m_connected_regions.find(region_id); 293 if (mit == m_connected_regions.end()) 294 { 295 // Should not occur 296 return false; 297 } 298 299 region_properties const& connected_region = mit->second; 300 301 if (cprop.count != 1) 302 { 303 // If there are more connections, check their isolation 304 if (! isolated_multiple_connection(region, connected_region)) 305 { 306 return false; 307 } 308 } 309 310 if (connected_region.isolated != isolation_yes 311 && connected_region.isolated != isolation_multiple) 312 { 313 signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin(); 314 if (first_with_turn) 315 { 316 first_turn_id = unique_turn_id; 317 first_with_turn = false; 318 } 319 else if (first_turn_id != unique_turn_id) 320 { 321 return false; 322 } 323 } 324 } 325 326 // If there is only one connection (with a 'parent'), and all other 327 // connections are itself isolated, it is isolated 328 return true; 329 } 330 get_isolated_regionsboost::geometry::detail::overlay::traversal_switch_detector331 void get_isolated_regions() 332 { 333 typedef typename region_connection_map::iterator it_type; 334 335 // First time: check regions isolated (one connection only), 336 // semi-isolated (multiple connections between same region), 337 // and complex isolated (connection with multiple rings but all 338 // at same point) 339 for (it_type it = m_connected_regions.begin(); 340 it != m_connected_regions.end(); ++it) 341 { 342 region_properties& properties = it->second; 343 if (one_connection_to_another_region(properties)) 344 { 345 properties.isolated = isolation_yes; 346 } 347 else if (multiple_connections_to_one_region(properties)) 348 { 349 properties.isolated = isolation_multiple; 350 } 351 else if (one_connection_to_multiple_regions(properties)) 352 { 353 properties.isolated = isolation_yes; 354 } 355 } 356 357 // Propagate isolation to next level 358 // TODO: should be optimized 359 std::size_t defensive_check = 0; 360 bool changed = true; 361 while (changed && defensive_check++ < m_connected_regions.size()) 362 { 363 changed = false; 364 for (it_type it = m_connected_regions.begin(); 365 it != m_connected_regions.end(); ++it) 366 { 367 region_properties& properties = it->second; 368 369 if (properties.isolated == isolation_unknown 370 && has_only_isolated_children(properties)) 371 { 372 properties.isolated = isolation_yes; 373 changed = true; 374 } 375 } 376 } 377 } 378 assign_isolationboost::geometry::detail::overlay::traversal_switch_detector379 void assign_isolation() 380 { 381 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) 382 { 383 turn_type& turn = m_turns[turn_index]; 384 385 for (int op_index = 0; op_index < 2; op_index++) 386 { 387 turn_operation_type& op = turn.operations[op_index]; 388 typename region_connection_map::const_iterator mit = m_connected_regions.find(op.enriched.region_id); 389 if (mit != m_connected_regions.end()) 390 { 391 region_properties const& prop = mit->second; 392 op.enriched.isolated = prop.isolated == isolation_yes; 393 } 394 } 395 } 396 } 397 assign_region_idsboost::geometry::detail::overlay::traversal_switch_detector398 void assign_region_ids() 399 { 400 for (typename merge_map::const_iterator it 401 = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it) 402 { 403 ring_identifier const& ring_id = it->first; 404 merged_ring_properties const& properties = it->second; 405 406 for (set_iterator sit = properties.turn_indices.begin(); 407 sit != properties.turn_indices.end(); ++sit) 408 { 409 turn_type& turn = m_turns[*sit]; 410 411 if (! acceptable(turn)) 412 { 413 // No assignment necessary 414 continue; 415 } 416 417 for (int i = 0; i < 2; i++) 418 { 419 turn_operation_type& op = turn.operations[i]; 420 if (ring_id_by_seg_id(op.seg_id) == ring_id) 421 { 422 op.enriched.region_id = properties.region_id; 423 } 424 } 425 } 426 } 427 } 428 assign_connected_regionsboost::geometry::detail::overlay::traversal_switch_detector429 void assign_connected_regions() 430 { 431 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) 432 { 433 turn_type const& turn = m_turns[turn_index]; 434 435 signed_size_type const unique_turn_id 436 = turn.is_clustered() ? -turn.cluster_id : turn_index; 437 438 turn_operation_type op0 = turn.operations[0]; 439 turn_operation_type op1 = turn.operations[1]; 440 441 signed_size_type const& id0 = op0.enriched.region_id; 442 signed_size_type const& id1 = op1.enriched.region_id; 443 444 // Add region (by assigning) and add involved turns 445 if (id0 != -1) 446 { 447 m_connected_regions[id0].region_id = id0; 448 m_connected_regions[id0].unique_turn_ids.insert(unique_turn_id); 449 } 450 if (id1 != -1 && id0 != id1) 451 { 452 m_connected_regions[id1].region_id = id1; 453 m_connected_regions[id1].unique_turn_ids.insert(unique_turn_id); 454 } 455 456 if (id0 != id1 && id0 != -1 && id1 != -1) 457 { 458 // Assign connections 459 connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1]; 460 connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0]; 461 462 // Reference this turn or cluster to later check uniqueness on ring 463 if (prop0.unique_turn_ids.count(unique_turn_id) == 0) 464 { 465 prop0.count++; 466 prop0.unique_turn_ids.insert(unique_turn_id); 467 } 468 if (prop1.unique_turn_ids.count(unique_turn_id) == 0) 469 { 470 prop1.count++; 471 prop1.unique_turn_ids.insert(unique_turn_id); 472 } 473 } 474 } 475 } 476 acceptableboost::geometry::detail::overlay::traversal_switch_detector477 inline bool acceptable(turn_type const& turn) const 478 { 479 // Discarded turns don't connect rings to the same region 480 // Also xx are not relevant 481 // (otherwise discarded colocated uu turn could make a connection) 482 return ! turn.discarded 483 && ! turn.both(operation_blocked); 484 } 485 connects_same_regionboost::geometry::detail::overlay::traversal_switch_detector486 inline bool connects_same_region(turn_type const& turn) const 487 { 488 if (! acceptable(turn)) 489 { 490 return false; 491 } 492 493 if (! turn.is_clustered()) 494 { 495 // If it is a uu/ii-turn (non clustered), it is never same region 496 return ! (turn.both(operation_union) || turn.both(operation_intersection)); 497 } 498 499 if (BOOST_GEOMETRY_CONDITION(target_operation == operation_union)) 500 { 501 // It is a cluster, check zones 502 // (assigned by sort_by_side/handle colocations) of both operations 503 return turn.operations[0].enriched.zone 504 == turn.operations[1].enriched.zone; 505 } 506 507 // For an intersection, two regions connect if they are not ii 508 // (ii-regions are isolated) or, in some cases, not iu (for example 509 // when a multi-polygon is inside an interior ring and connecting it) 510 return ! (turn.both(operation_intersection) 511 || turn.combination(operation_intersection, operation_union)); 512 } 513 514 get_region_idboost::geometry::detail::overlay::traversal_switch_detector515 inline signed_size_type get_region_id(turn_operation_type const& op) const 516 { 517 return op.enriched.region_id; 518 } 519 520 create_regionboost::geometry::detail::overlay::traversal_switch_detector521 void create_region(signed_size_type& new_region_id, ring_identifier const& ring_id, 522 merged_ring_properties& properties, signed_size_type region_id = -1) 523 { 524 if (properties.region_id > 0) 525 { 526 // Already handled 527 return; 528 } 529 530 // Assign new id if this is a new region 531 if (region_id == -1) 532 { 533 region_id = new_region_id++; 534 } 535 536 // Assign this ring to specified region 537 properties.region_id = region_id; 538 539 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) 540 std::cout << " ADD " << ring_id << " TO REGION " << region_id << std::endl; 541 #endif 542 543 // Find connecting rings, recursively 544 for (set_iterator sit = properties.turn_indices.begin(); 545 sit != properties.turn_indices.end(); ++sit) 546 { 547 signed_size_type const turn_index = *sit; 548 turn_type const& turn = m_turns[turn_index]; 549 if (! connects_same_region(turn)) 550 { 551 // This is a non clustered uu/ii-turn, or a cluster connecting different 'zones' 552 continue; 553 } 554 555 // Union: This turn connects two rings (interior connected), create the region 556 // Intersection: This turn connects two rings, set same regions for these two rings 557 for (int op_index = 0; op_index < 2; op_index++) 558 { 559 turn_operation_type const& op = turn.operations[op_index]; 560 ring_identifier connected_ring_id = ring_id_by_seg_id(op.seg_id); 561 if (connected_ring_id != ring_id) 562 { 563 propagate_region(new_region_id, connected_ring_id, region_id); 564 } 565 } 566 } 567 } 568 propagate_regionboost::geometry::detail::overlay::traversal_switch_detector569 void propagate_region(signed_size_type& new_region_id, 570 ring_identifier const& ring_id, signed_size_type region_id) 571 { 572 typename merge_map::iterator it = m_turns_per_ring.find(ring_id); 573 if (it != m_turns_per_ring.end()) 574 { 575 create_region(new_region_id, ring_id, it->second, region_id); 576 } 577 } 578 579 iterateboost::geometry::detail::overlay::traversal_switch_detector580 void iterate() 581 { 582 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) 583 std::cout << "BEGIN ITERATION GETTING REGION_IDS" << std::endl; 584 #endif 585 586 // Collect turns per ring 587 m_turns_per_ring.clear(); 588 m_connected_regions.clear(); 589 590 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) 591 { 592 turn_type const& turn = m_turns[turn_index]; 593 594 if (turn.discarded 595 && BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection)) 596 { 597 // Discarded turn (union currently still needs it to determine regions) 598 continue; 599 } 600 601 for (int op_index = 0; op_index < 2; op_index++) 602 { 603 turn_operation_type const& op = turn.operations[op_index]; 604 m_turns_per_ring[ring_id_by_seg_id(op.seg_id)].turn_indices.insert(turn_index); 605 } 606 } 607 608 // All rings having turns are in turns/ring map. Process them. 609 { 610 signed_size_type new_region_id = 1; 611 for (typename merge_map::iterator it 612 = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it) 613 { 614 create_region(new_region_id, it->first, it->second); 615 } 616 617 assign_region_ids(); 618 assign_connected_regions(); 619 get_isolated_regions(); 620 assign_isolation(); 621 } 622 623 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) 624 std::cout << "END ITERATION GETTIN REGION_IDS" << std::endl; 625 626 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) 627 { 628 turn_type const& turn = m_turns[turn_index]; 629 630 if ((turn.both(operation_union) || turn.both(operation_intersection)) 631 && ! turn.is_clustered()) 632 { 633 std::cout << "UU/II RESULT " 634 << turn_index << " -> " 635 << turn.operations[0].enriched.region_id 636 << " " << turn.operations[1].enriched.region_id 637 << std::endl; 638 } 639 } 640 641 for (typename Clusters::const_iterator it = m_clusters.begin(); it != m_clusters.end(); ++it) 642 { 643 cluster_info const& cinfo = it->second; 644 std::cout << "CL RESULT " << it->first 645 << " -> " << cinfo.open_count << std::endl; 646 } 647 #endif 648 649 } 650 651 private: 652 653 Geometry1 const& m_geometry1; 654 Geometry2 const& m_geometry2; 655 Turns& m_turns; 656 Clusters& m_clusters; 657 merge_map m_turns_per_ring; 658 region_connection_map m_connected_regions; 659 RobustPolicy const& m_robust_policy; 660 Visitor& m_visitor; 661 }; 662 663 }} // namespace detail::overlay 664 #endif // DOXYGEN_NO_DETAIL 665 666 }} // namespace boost::geometry 667 668 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP 669