ceph/src/boost/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp

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