1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2015-2016 Barend Gehrels, Amsterdam, the Netherlands.
5 // This file was modified by Oracle on 2018-2020.
6 // Modifications copyright (c) 2018-2020 Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP
20 #include <boost/range/value_type.hpp>
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>
31 namespace boost { namespace geometry
34 #ifndef DOXYGEN_NO_DETAIL
35 namespace detail { namespace overlay
42 overlay_type OverlayType,
47 typename RobustPolicy,
50 struct traversal_switch_detector
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
61 isolation_unknown = -1,
64 isolation_multiple = 2
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;
71 // Per ring, first turns are collected (in turn_indices), and later
72 // a region_id is assigned
73 struct merged_ring_properties
75 signed_size_type region_id;
76 set_type turn_indices;
78 merged_ring_properties()
83 struct connection_properties
86 // Contains turn-index OR, if clustered, minus-cluster_id
87 set_type unique_turn_ids;
88 connection_properties()
93 typedef std::map<signed_size_type, connection_properties> connection_map;
95 // Per region, a set of properties is maintained, including its connections
97 struct region_properties
99 signed_size_type region_id;
100 isolation_type isolated;
101 set_type unique_turn_ids;
103 // Maps from connected region_id to their properties
104 connection_map connected_region_counts;
108 , isolated(isolation_unknown)
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;
116 typedef set_type::const_iterator set_iterator;
118 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)
124 , m_clusters(clusters)
125 , m_robust_policy(robust_policy)
130 bool one_connection_to_another_region(region_properties const& region) const
133 // +----------------------+
139 // +----------------------+
141 if (region.connected_region_counts.size() == 1)
143 connection_properties const& cprop = region.connected_region_counts.begin()->second;
144 return cprop.count <= 1;
146 return region.connected_region_counts.empty();
149 // TODO: might be combined with previous
150 bool multiple_connections_to_one_region(region_properties const& region) const
153 // +----------------------+
162 // +----------------------+
164 if (region.connected_region_counts.size() == 1)
166 connection_properties const& cprop = region.connected_region_counts.begin()->second;
167 return cprop.count > 1;
172 bool one_connection_to_multiple_regions(region_properties const& region) const
175 // +----------------------+
181 // +----------------------+
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)
188 connection_properties const& cprop = it->second;
190 if (cprop.count != 1)
194 signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin();
197 first_turn_id = unique_turn_id;
200 else if (first_turn_id != unique_turn_id)
208 bool ii_turn_connects_two_regions(region_properties const& region,
209 region_properties const& connected_region,
210 signed_size_type turn_index) const
212 turn_type const& turn = m_turns[turn_index];
213 if (! turn.both(operation_intersection))
218 signed_size_type const id0 = turn.operations[0].enriched.region_id;
219 signed_size_type const id1 = turn.operations[1].enriched.region_id;
221 return (id0 == region.region_id && id1 == connected_region.region_id)
222 || (id1 == region.region_id && id0 == connected_region.region_id);
226 bool isolated_multiple_connection(region_properties const& region,
227 region_properties const& connected_region) const
229 if (connected_region.isolated != isolation_multiple)
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)
239 turn_ids.erase(*sit);
242 // There should be one connection (turn or cluster) left
243 if (turn_ids.size() != 1)
248 for (set_iterator sit = connected_region.unique_turn_ids.begin();
249 sit != connected_region.unique_turn_ids.end(); ++sit)
251 signed_size_type const id_or_index = *sit;
252 if (id_or_index >= 0)
254 if (! ii_turn_connects_two_regions(region, connected_region, id_or_index))
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())
265 cluster_info const& cinfo = it->second;
266 for (set_iterator cit = cinfo.turn_indices.begin();
267 cit != cinfo.turn_indices.end(); ++cit)
269 if (! ii_turn_connects_two_regions(region, connected_region, *cit))
281 bool has_only_isolated_children(region_properties const& region) const
283 bool first_with_turn = true;
284 signed_size_type first_turn_id = 0;
286 for (typename connection_map::const_iterator it = region.connected_region_counts.begin();
287 it != region.connected_region_counts.end(); ++it)
289 signed_size_type const region_id = it->first;
290 connection_properties const& cprop = it->second;
292 typename region_connection_map::const_iterator mit = m_connected_regions.find(region_id);
293 if (mit == m_connected_regions.end())
299 region_properties const& connected_region = mit->second;
301 if (cprop.count != 1)
303 // If there are more connections, check their isolation
304 if (! isolated_multiple_connection(region, connected_region))
310 if (connected_region.isolated != isolation_yes
311 && connected_region.isolated != isolation_multiple)
313 signed_size_type const unique_turn_id = *cprop.unique_turn_ids.begin();
316 first_turn_id = unique_turn_id;
317 first_with_turn = false;
319 else if (first_turn_id != unique_turn_id)
326 // If there is only one connection (with a 'parent'), and all other
327 // connections are itself isolated, it is isolated
331 void get_isolated_regions()
333 typedef typename region_connection_map::iterator it_type;
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
339 for (it_type it = m_connected_regions.begin();
340 it != m_connected_regions.end(); ++it)
342 region_properties& properties = it->second;
343 if (one_connection_to_another_region(properties))
345 properties.isolated = isolation_yes;
347 else if (multiple_connections_to_one_region(properties))
349 properties.isolated = isolation_multiple;
351 else if (one_connection_to_multiple_regions(properties))
353 properties.isolated = isolation_yes;
357 // Propagate isolation to next level
358 // TODO: should be optimized
359 std::size_t defensive_check = 0;
361 while (changed && defensive_check++ < m_connected_regions.size())
364 for (it_type it = m_connected_regions.begin();
365 it != m_connected_regions.end(); ++it)
367 region_properties& properties = it->second;
369 if (properties.isolated == isolation_unknown
370 && has_only_isolated_children(properties))
372 properties.isolated = isolation_yes;
379 void assign_isolation()
381 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
383 turn_type& turn = m_turns[turn_index];
385 for (int op_index = 0; op_index < 2; op_index++)
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())
391 region_properties const& prop = mit->second;
392 op.enriched.isolated = prop.isolated == isolation_yes;
398 void assign_region_ids()
400 for (typename merge_map::const_iterator it
401 = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
403 ring_identifier const& ring_id = it->first;
404 merged_ring_properties const& properties = it->second;
406 for (set_iterator sit = properties.turn_indices.begin();
407 sit != properties.turn_indices.end(); ++sit)
409 turn_type& turn = m_turns[*sit];
411 if (! acceptable(turn))
413 // No assignment necessary
417 for (int i = 0; i < 2; i++)
419 turn_operation_type& op = turn.operations[i];
420 if (ring_id_by_seg_id(op.seg_id) == ring_id)
422 op.enriched.region_id = properties.region_id;
429 void assign_connected_regions()
431 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
433 turn_type const& turn = m_turns[turn_index];
435 signed_size_type const unique_turn_id
436 = turn.is_clustered() ? -turn.cluster_id : turn_index;
438 turn_operation_type op0 = turn.operations[0];
439 turn_operation_type op1 = turn.operations[1];
441 signed_size_type const& id0 = op0.enriched.region_id;
442 signed_size_type const& id1 = op1.enriched.region_id;
444 // Add region (by assigning) and add involved turns
447 m_connected_regions[id0].region_id = id0;
448 m_connected_regions[id0].unique_turn_ids.insert(unique_turn_id);
450 if (id1 != -1 && id0 != id1)
452 m_connected_regions[id1].region_id = id1;
453 m_connected_regions[id1].unique_turn_ids.insert(unique_turn_id);
456 if (id0 != id1 && id0 != -1 && id1 != -1)
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];
462 // Reference this turn or cluster to later check uniqueness on ring
463 if (prop0.unique_turn_ids.count(unique_turn_id) == 0)
466 prop0.unique_turn_ids.insert(unique_turn_id);
468 if (prop1.unique_turn_ids.count(unique_turn_id) == 0)
471 prop1.unique_turn_ids.insert(unique_turn_id);
477 inline bool acceptable(turn_type const& turn) const
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);
486 inline bool connects_same_region(turn_type const& turn) const
488 if (! acceptable(turn))
493 if (! turn.is_clustered())
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));
499 if (BOOST_GEOMETRY_CONDITION(target_operation == operation_union))
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;
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));
515 inline signed_size_type get_region_id(turn_operation_type const& op) const
517 return op.enriched.region_id;
521 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)
524 if (properties.region_id > 0)
530 // Assign new id if this is a new region
533 region_id = new_region_id++;
536 // Assign this ring to specified region
537 properties.region_id = region_id;
539 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
540 std::cout << " ADD " << ring_id << " TO REGION " << region_id << std::endl;
543 // Find connecting rings, recursively
544 for (set_iterator sit = properties.turn_indices.begin();
545 sit != properties.turn_indices.end(); ++sit)
547 signed_size_type const turn_index = *sit;
548 turn_type const& turn = m_turns[turn_index];
549 if (! connects_same_region(turn))
551 // This is a non clustered uu/ii-turn, or a cluster connecting different 'zones'
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++)
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)
563 propagate_region(new_region_id, connected_ring_id, region_id);
569 void propagate_region(signed_size_type& new_region_id,
570 ring_identifier const& ring_id, signed_size_type region_id)
572 typename merge_map::iterator it = m_turns_per_ring.find(ring_id);
573 if (it != m_turns_per_ring.end())
575 create_region(new_region_id, ring_id, it->second, region_id);
582 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
583 std::cout << "BEGIN ITERATION GETTING REGION_IDS" << std::endl;
586 // Collect turns per ring
587 m_turns_per_ring.clear();
588 m_connected_regions.clear();
590 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
592 turn_type const& turn = m_turns[turn_index];
595 && BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection))
597 // Discarded turn (union currently still needs it to determine regions)
601 for (int op_index = 0; op_index < 2; op_index++)
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);
608 // All rings having turns are in turns/ring map. Process them.
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)
614 create_region(new_region_id, it->first, it->second);
618 assign_connected_regions();
619 get_isolated_regions();
623 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
624 std::cout << "END ITERATION GETTIN REGION_IDS" << std::endl;
626 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
628 turn_type const& turn = m_turns[turn_index];
630 if ((turn.both(operation_union) || turn.both(operation_intersection))
631 && ! turn.is_clustered())
633 std::cout << "UU/II RESULT "
634 << turn_index << " -> "
635 << turn.operations[0].enriched.region_id
636 << " " << turn.operations[1].enriched.region_id
641 for (typename Clusters::const_iterator it = m_clusters.begin(); it != m_clusters.end(); ++it)
643 cluster_info const& cinfo = it->second;
644 std::cout << "CL RESULT " << it->first
645 << " -> " << cinfo.open_count << std::endl;
653 Geometry1 const& m_geometry1;
654 Geometry2 const& m_geometry2;
656 Clusters& m_clusters;
657 merge_map m_turns_per_ring;
658 region_connection_map m_connected_regions;
659 RobustPolicy const& m_robust_policy;
663 }} // namespace detail::overlay
664 #endif // DOXYGEN_NO_DETAIL
666 }} // namespace boost::geometry
668 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP