diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp')
-rw-r--r-- | boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp | 409 |
1 files changed, 262 insertions, 147 deletions
diff --git a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp index 0b4f393ef4..72f9c4f12a 100644 --- a/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp +++ b/boost/geometry/algorithms/detail/overlay/traversal_switch_detector.hpp @@ -48,17 +48,24 @@ template > struct traversal_switch_detector { - enum isolation_type { isolation_unknown = -1, isolation_no = 0, isolation_yes = 1 }; + enum isolation_type + { + isolation_unknown = -1, + isolation_no = 0, + isolation_yes = 1, + isolation_multiple = 2 + }; typedef typename boost::range_value<Turns>::type turn_type; typedef typename turn_type::turn_operation_type turn_operation_type; + typedef std::set<signed_size_type> set_type; // Per ring, first turns are collected (in turn_indices), and later // a region_id is assigned struct merged_ring_properties { signed_size_type region_id; - std::set<signed_size_type> turn_indices; + set_type turn_indices; merged_ring_properties() : region_id(-1) @@ -68,7 +75,8 @@ struct traversal_switch_detector struct connection_properties { std::size_t count; - std::set<signed_size_type> cluster_indices; + // Contains turn-index OR, if clustered, minus-cluster_id + set_type unique_turn_ids; connection_properties() : count(0) {} @@ -82,6 +90,7 @@ struct traversal_switch_detector { signed_size_type region_id; isolation_type isolated; + set_type unique_turn_ids; // Maps from connected region_id to their properties connection_map connected_region_counts; @@ -96,7 +105,7 @@ struct traversal_switch_detector typedef std::map<ring_identifier, merged_ring_properties > merge_map; typedef std::map<signed_size_type, region_properties> region_connection_map; - typedef std::set<signed_size_type>::const_iterator set_iterator; + typedef set_type::const_iterator set_iterator; inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2, Turns& turns, Clusters& clusters, @@ -110,111 +119,232 @@ struct traversal_switch_detector { } - isolation_type get_isolation(region_properties const& properties, - signed_size_type parent_region_id, - const std::set<signed_size_type>& visited) + bool inspect_difference(set_type& turn_id_difference, + set_type const& turn_ids, + set_type const& other_turn_ids) const { - if (properties.isolated != isolation_unknown) + // TODO: consider if std::set_difference can be used in the final version + int const turn_count = turn_ids.size(); + int const other_turn_count = other_turn_ids.size(); + + // First quick check on size (TODO: implement multiple-multiple connections) + if (turn_count - other_turn_count > 1) { - return properties.isolated; + return false; } - bool all_colocated = true; - int unique_cluster_id = -1; - for (typename connection_map::const_iterator it = properties.connected_region_counts.begin(); - all_colocated && it != properties.connected_region_counts.end(); ++it) + // Check if all turns are also present in the connection. + // The difference is returned + for (set_iterator it = turn_ids.begin(); it != turn_ids.end(); ++it) { - connection_properties const& cprop = it->second; - if (cprop.cluster_indices.size() != 1) - { - // Either no cluster (non colocated point), or more clusters - all_colocated = false; - } - int const cluster_id = *cprop.cluster_indices.begin(); - if (cluster_id == -1) + signed_size_type const& id = *it; + if (other_turn_ids.count(id) == 0) { - all_colocated = false; - } - else if (unique_cluster_id == -1) - { - unique_cluster_id = cluster_id; - } - else if (unique_cluster_id != cluster_id) - { - all_colocated = false; + turn_id_difference.insert(id); } } - if (all_colocated) + return true; + } + + bool one_connection_to_another_region(region_properties const& region) const + { + // For example: + // +----------------------+ + // | __ | + // | / \| + // | | x + // | \__/| + // | | + // +----------------------+ + + if (region.connected_region_counts.size() == 1) { - return isolation_yes; + connection_properties const& cprop = region.connected_region_counts.begin()->second; + return cprop.count <= 1; } + return region.connected_region_counts.empty(); + } + // TODO: might be combined with previous + bool multiple_connections_to_one_region(region_properties const& region) const + { + // For example: + // +----------------------+ + // | __ | + // | / \| + // | | x + // | \ /| + // | / \| + // | | x + // | \__/| + // | | + // +----------------------+ + + if (region.connected_region_counts.size() == 1) + { + connection_properties const& cprop = region.connected_region_counts.begin()->second; + return cprop.count > 1; + } + return false; + } - // It is isolated if there is only one connection, or if there are more connections but all - // of them are isolated themselves, or if there are more connections - // but they are all colocated - std::size_t non_isolation_count = 0; - bool child_not_isolated = false; - for (typename connection_map::const_iterator it = properties.connected_region_counts.begin(); - it != properties.connected_region_counts.end(); ++it) + bool one_connection_to_multiple_regions(region_properties const& region) const + { + // For example: + // +----------------------+ + // | __ | __ + // | / \|/ | + // | | x | + // | \__/|\__| + // | | + // +----------------------+ + + bool first = true; + signed_size_type first_turn_id = 0; + for (typename connection_map::const_iterator it = region.connected_region_counts.begin(); + it != region.connected_region_counts.end(); ++it) { - signed_size_type const region_id = it->first; connection_properties const& cprop = it->second; - if (region_id == parent_region_id) + if (cprop.count != 1) { - // Normal situation, skip its direct parent - continue; + return false; } - if (visited.count(region_id) > 0) + signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin(); + if (first) { - // Find one of its ancestors again, this is a ring. Not isolated. - return isolation_no; + first_turn_id = unique_turn_id; + first = false; } - if (cprop.count > 1) + else if (first_turn_id != unique_turn_id) { - return isolation_no; + return false; } + } + return true; + } - typename region_connection_map::iterator mit = m_connected_regions.find(region_id); + bool has_only_isolated_children(region_properties const& region) const + { + bool first_with_turn = true; + bool first_with_multiple = true; + signed_size_type first_turn_id = 0; + signed_size_type first_multiple_region_id = 0; + + for (typename connection_map::const_iterator it = region.connected_region_counts.begin(); + it != region.connected_region_counts.end(); ++it) + { + signed_size_type const region_id = it->first; + connection_properties const& cprop = it->second; + + typename region_connection_map::const_iterator mit = m_connected_regions.find(region_id); if (mit == m_connected_regions.end()) { // Should not occur - continue; + return false; } - std::set<signed_size_type> vis = visited; - vis.insert(parent_region_id); + region_properties const& connected_region = mit->second; + + bool const multiple = connected_region.isolated == isolation_multiple; - region_properties& prop = mit->second; - if (prop.isolated == isolation_unknown) + if (cprop.count != 1) { - isolation_type const iso = get_isolation(prop, properties.region_id, vis); - prop.isolated = iso; - if (iso == isolation_no) + if (! multiple) + { + return false; + } + + // It connects multiple times to an isolated region. + // This is allowed as long as it happens only once + if (first_with_multiple) + { + first_multiple_region_id = connected_region.region_id; + first_with_multiple = false; + } + else if (first_multiple_region_id != connected_region.region_id) + { + return false; + } + + // Turns in region should be either present in the connection, + // of form part of the connection with the other region + set_type diff; + if (! inspect_difference(diff, region.unique_turn_ids, + connected_region.unique_turn_ids)) { - child_not_isolated = true; + return false; + } + if (diff.size() > 1) + { + // For now: + return false; } } - if (prop.isolated == isolation_no) + + if (connected_region.isolated != isolation_yes && ! multiple) { - non_isolation_count++; + signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin(); + if (first_with_turn) + { + first_turn_id = unique_turn_id; + first_with_turn = false; + } + else if (first_turn_id != unique_turn_id) + { + return false; + } } } - - return child_not_isolated || non_isolation_count > 1 ? isolation_no : isolation_yes; + // If there is only one connection (with a 'parent'), and all other + // connections are itself isolated, it is isolated + return true; } void get_isolated_regions() { - for (typename region_connection_map::iterator it = m_connected_regions.begin(); + typedef typename region_connection_map::iterator it_type; + + // First time: check regions isolated (one connection only), + // semi-isolated (multiple connections between same region), + // and complex isolated (connection with multiple rings but all + // at same point) + for (it_type it = m_connected_regions.begin(); it != m_connected_regions.end(); ++it) { region_properties& properties = it->second; - if (properties.isolated == isolation_unknown) + if (one_connection_to_another_region(properties)) { - std::set<signed_size_type> visited; - properties.isolated = get_isolation(properties, properties.region_id, visited); + properties.isolated = isolation_yes; + } + else if (multiple_connections_to_one_region(properties)) + { + properties.isolated = isolation_multiple; + } + else if (one_connection_to_multiple_regions(properties)) + { + properties.isolated = isolation_yes; + } + } + + // Propagate isolation to next level + // TODO: should be optimized + std::size_t defensive_check = 0; + bool changed = true; + while (changed && defensive_check++ < m_connected_regions.size()) + { + changed = false; + for (it_type it = m_connected_regions.begin(); + it != m_connected_regions.end(); ++it) + { + region_properties& properties = it->second; + + if (properties.isolated == isolation_unknown + && has_only_isolated_children(properties)) + { + properties.isolated = isolation_yes; + changed = true; + } } } } @@ -238,7 +368,7 @@ struct traversal_switch_detector } } - void assign_regions() + void assign_region_ids() { for (typename merge_map::const_iterator it = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it) @@ -259,39 +389,53 @@ struct traversal_switch_detector op.enriched.region_id = properties.region_id; } } - signed_size_type const& id0 = turn.operations[0].enriched.region_id; - signed_size_type const& id1 = turn.operations[1].enriched.region_id; - if (id0 != id1 && id0 != -1 && id1 != -1) - { - // Force insertion - m_connected_regions[id0].region_id = id0; - m_connected_regions[id1].region_id = id1; + } + } + } - connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1]; - connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0]; + void assign_connected_regions() + { + for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index) + { + turn_type const& turn = m_turns[turn_index]; - if (turn.cluster_id < 0) - { - // Turn is not colocated, add reference to connection - prop0.count++; - prop1.count++; - } - else - { - // Turn is colocated, only add region reference if it was not yet registered - if (prop0.cluster_indices.count(turn.cluster_id) == 0) - { - prop0.count++; - } - if (prop1.cluster_indices.count(turn.cluster_id) == 0) - { - prop1.count++; - } - } - // Insert cluster-id (also -1 is inserted - reinsertion of - // same cluster id is OK) - prop0.cluster_indices.insert(turn.cluster_id); - prop1.cluster_indices.insert(turn.cluster_id); + signed_size_type const unique_turn_id + = turn.is_clustered() ? -turn.cluster_id : turn_index; + + turn_operation_type op0 = turn.operations[0]; + turn_operation_type op1 = turn.operations[1]; + + signed_size_type const& id0 = op0.enriched.region_id; + signed_size_type const& id1 = op1.enriched.region_id; + + // Add region (by assigning) and add involved turns + if (id0 != -1) + { + m_connected_regions[id0].region_id = id0; + m_connected_regions[id0].unique_turn_ids.insert(unique_turn_id); + } + if (id1 != -1 && id0 != id1) + { + m_connected_regions[id1].region_id = id1; + m_connected_regions[id1].unique_turn_ids.insert(unique_turn_id); + } + + if (id0 != id1 && id0 != -1 && id1 != -1) + { + // Assign connections + connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1]; + connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0]; + + // Reference this turn or cluster to later check uniqueness on ring + if (prop0.unique_turn_ids.count(unique_turn_id) == 0) + { + prop0.count++; + prop0.unique_turn_ids.insert(unique_turn_id); + } + if (prop1.unique_turn_ids.count(unique_turn_id) == 0) + { + prop1.count++; + prop1.unique_turn_ids.insert(unique_turn_id); } } } @@ -306,7 +450,7 @@ struct traversal_switch_detector return false; } - if (turn.cluster_id == -1) + if (! turn.is_clustered()) { // If it is a uu/ii-turn (non clustered), it is never same region return ! (turn.both(operation_union) || turn.both(operation_intersection)); @@ -320,39 +464,22 @@ struct traversal_switch_detector == turn.operations[1].enriched.zone; } - // If a cluster contains an ii/cc it is not same region (for intersection) - typename Clusters::const_iterator it = m_clusters.find(turn.cluster_id); - if (it == m_clusters.end()) - { - // Should not occur - return true; - } - - cluster_info const& cinfo = it->second; - for (set_iterator sit = cinfo.turn_indices.begin(); - sit != cinfo.turn_indices.end(); ++sit) - { - turn_type const& cluster_turn = m_turns[*sit]; - if (cluster_turn.both(operation_union) - || cluster_turn.both(operation_intersection)) - { - return false; - } - } - - // It is the same region - return false; + // For an intersection, two regions connect if they are not ii + // (ii-regions are isolated) or, in some cases, not iu (for example + // when a multi-polygon is inside an interior ring and connecting it) + return ! (turn.both(operation_intersection) + || turn.combination(operation_intersection, operation_union)); } - inline int get_region_id(turn_operation_type const& op) const + inline signed_size_type get_region_id(turn_operation_type const& op) const { return op.enriched.region_id; } void create_region(signed_size_type& new_region_id, ring_identifier const& ring_id, - merged_ring_properties& properties, int region_id = -1) + merged_ring_properties& properties, signed_size_type region_id = -1) { if (properties.region_id > 0) { @@ -400,7 +527,7 @@ struct traversal_switch_detector } void propagate_region(signed_size_type& new_region_id, - ring_identifier const& ring_id, int region_id) + ring_identifier const& ring_id, signed_size_type region_id) { typename merge_map::iterator it = m_turns_per_ring.find(ring_id); if (it != m_turns_per_ring.end()) @@ -438,7 +565,7 @@ struct traversal_switch_detector } } - // All rings having turns are in the map. Now iterate them + // All rings having turns are in turns/ring map. Process them. { signed_size_type new_region_id = 1; for (typename merge_map::iterator it @@ -447,7 +574,8 @@ struct traversal_switch_detector create_region(new_region_id, it->first, it->second); } - assign_regions(); + assign_region_ids(); + assign_connected_regions(); get_isolated_regions(); assign_isolation(); } @@ -464,9 +592,8 @@ struct traversal_switch_detector } // A touching cluster, gather regions - std::set<int> regions; - - std::set<signed_size_type> const& ids = cinfo.turn_indices; + set_type regions; + set_type const& ids = cinfo.turn_indices; #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR) std::cout << "SWITCH EXAMINE CLUSTER " << it->first << std::endl; @@ -476,14 +603,10 @@ struct traversal_switch_detector { signed_size_type turn_index = *sit; turn_type const& turn = m_turns[turn_index]; - if (turn.colocated_ii && ! turn.colocated_uu) - { - continue; - } for (int oi = 0; oi < 2; oi++) { - int const region = get_region_id(turn.operations[oi]); - regions.insert(region); + signed_size_type const region_id = get_region_id(turn.operations[oi]); + regions.insert(region_id); } } // Switch source if this cluster connects the same region @@ -497,24 +620,16 @@ struct traversal_switch_detector if (turn.discarded || turn.blocked() - || turn.cluster_id >= 0 + || turn.is_clustered() || ! (turn.both(operation_union) || turn.both(operation_intersection))) { // Skip discarded, blocked, non-uu/ii and clustered turns continue; } - if (OverlayType == overlay_buffer) - { - // For deflate, the region approach does not work because many - // pieces are outside the real polygons - // TODO: implement this in another way for buffer - // (because now buffer might output invalid geometries) - continue; - } - int const region0 = get_region_id(turn.operations[0]); - int const region1 = get_region_id(turn.operations[1]); + signed_size_type const region0 = get_region_id(turn.operations[0]); + signed_size_type const region1 = get_region_id(turn.operations[1]); // Switch sources for same region turn.switch_source = region0 == region1; @@ -529,7 +644,7 @@ struct traversal_switch_detector turn_type const& turn = m_turns[turn_index]; if ((turn.both(operation_union) || turn.both(operation_intersection)) - && turn.cluster_id < 0) + && ! turn.is_clustered()) { std::cout << "UU/II SWITCH RESULT " << turn_index << " -> " |