1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2015-2016 Barend Gehrels, Amsterdam, the Netherlands.
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)
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP
14 #include <boost/range.hpp>
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/turn_info.hpp>
20 #include <boost/geometry/core/access.hpp>
21 #include <boost/geometry/core/assert.hpp>
23 namespace boost { namespace geometry
26 #ifndef DOXYGEN_NO_DETAIL
27 namespace detail { namespace overlay
30 // Generic function (is this used somewhere else too?)
31 inline ring_identifier ring_id_by_seg_id(segment_identifier const& seg_id)
33 return ring_identifier(seg_id.source_index, seg_id.multi_index, seg_id.ring_index);
40 overlay_type OverlayType,
45 typename RobustPolicy,
48 struct traversal_switch_detector
50 typedef typename boost::range_value<Turns>::type turn_type;
51 typedef typename turn_type::turn_operation_type turn_operation_type;
54 typedef std::set<signed_size_type>::const_iterator set_iterator;
56 inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2,
57 Turns& turns, Clusters& clusters,
58 RobustPolicy const& robust_policy, Visitor& visitor)
59 : m_geometry1(geometry1)
60 , m_geometry2(geometry2)
62 , m_clusters(clusters)
63 , m_robust_policy(robust_policy)
70 static inline bool connects_same_zone(turn_type const& turn)
72 if (turn.cluster_id == -1)
74 // If it is a uu-turn (non clustered), it is never same zone
75 return ! turn.both(operation_union);
78 // It is a cluster, check zones of both operations
79 return turn.operations[0].enriched.zone
80 == turn.operations[1].enriched.zone;
83 inline int get_region_id(turn_operation_type const& op) const
85 std::map<ring_identifier, int>::const_iterator it
86 = m_regions.find(ring_id_by_seg_id(op.seg_id));
87 return it == m_regions.end() ? -1 : it->second;
90 void create_region(ring_identifier const& ring_id, std::set<signed_size_type> const& ring_turn_indices, int region_id = -1)
92 std::map<ring_identifier, int>::const_iterator it = m_regions.find(ring_id);
93 if (it != m_regions.end())
95 // The ring is already gathered in a region, quit
100 region_id = m_region_id++;
103 // Assign this ring to specified region
104 m_regions[ring_id] = region_id;
105 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
106 std::cout << " ADD " << ring_id << " TO REGION " << region_id << std::endl;
109 // Find connecting rings, recursively
110 for (set_iterator sit = ring_turn_indices.begin();
111 sit != ring_turn_indices.end(); ++sit)
113 int const turn_index = *sit;
114 turn_type const& turn = m_turns[turn_index];
115 if (! connects_same_zone(turn))
117 // This is a non clustered uu-turn, or a cluster connecting different 'zones'
121 // This turn connects two rings (interior connected), create the
123 for (int op_index = 0; op_index < 2; op_index++)
125 turn_operation_type const& op = turn.operations[op_index];
126 ring_identifier connected_ring_id = ring_id_by_seg_id(op.seg_id);
127 if (connected_ring_id != ring_id)
129 propagate_region(connected_ring_id, region_id);
135 void propagate_region(ring_identifier const& ring_id, int region_id)
137 std::map<ring_identifier, std::set<signed_size_type> >::const_iterator it = m_turns_per_ring.find(ring_id);
138 if (it != m_turns_per_ring.end())
140 create_region(ring_id, it->second, region_id);
146 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
147 std::cout << "SWITCH BEGIN ITERATION" << std::endl;
150 // Collect turns per ring
151 m_turns_per_ring.clear();
155 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
157 turn_type const& turn = m_turns[turn_index];
159 for (int op_index = 0; op_index < 2; op_index++)
161 turn_operation_type const& op = turn.operations[op_index];
162 m_turns_per_ring[ring_id_by_seg_id(op.seg_id)].insert(turn_index);
166 // All rings having turns are in the map. Now iterate them
167 for (std::map<ring_identifier, std::set<signed_size_type> >::const_iterator it
168 = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
170 create_region(it->first, it->second);
173 // Now that all regions are filled, assign switch_source property
174 // Iterate through all clusters
175 for (typename Clusters::iterator it = m_clusters.begin(); it != m_clusters.end(); ++it)
177 cluster_info& cinfo = it->second;
178 if (cinfo.open_count <= 1)
180 // Not a touching cluster
184 // A touching cluster, gather regions
185 std::set<int> regions;
187 std::set<signed_size_type> const& ids = cinfo.turn_indices;
189 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
190 std::cout << "SWITCH EXAMINE CLUSTER " << it->first << std::endl;
193 for (set_iterator sit = ids.begin(); sit != ids.end(); ++sit)
195 signed_size_type turn_index = *sit;
196 turn_type const& turn = m_turns[turn_index];
197 for (int oi = 0; oi < 2; oi++)
199 int const region = get_region_id(turn.operations[oi]);
200 regions.insert(region);
203 // Switch source if this cluster connects the same region
204 cinfo.switch_source = regions.size() == 1;
207 // Iterate through all uu turns (non-clustered)
208 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
210 turn_type& turn = m_turns[turn_index];
214 || turn.cluster_id >= 0
215 || ! turn.both(operation_union))
217 // Skip discarded, blocked, non-uu and clustered turns
221 if (OverlayType == overlay_buffer)
223 // For deflate, the region approach does not work because many
224 // pieces are outside the real polygons
225 // TODO: implement this in another way for buffer
226 // (because now buffer might output invalid geometries)
230 int const region0 = get_region_id(turn.operations[0]);
231 int const region1 = get_region_id(turn.operations[1]);
233 // Switch sources for same region
234 turn.switch_source = region0 == region1;
238 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
239 std::cout << "SWITCH END ITERATION" << std::endl;
241 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
243 turn_type const& turn = m_turns[turn_index];
245 if (turn.both(operation_union) && turn.cluster_id < 0)
247 std::cout << "UU SWITCH RESULT "
248 << turn_index << " -> "
249 << turn.switch_source << std::endl;
253 for (typename Clusters::const_iterator it = m_clusters.begin(); it != m_clusters.end(); ++it)
255 cluster_info const& cinfo = it->second;
256 if (cinfo.open_count > 1)
258 std::cout << "CL SWITCH RESULT " << it->first
259 << " -> " << cinfo.switch_source << std::endl;
263 std::cout << "CL SWITCH RESULT " << it->first
264 << " is not registered as open" << std::endl;
273 Geometry1 const& m_geometry1;
274 Geometry2 const& m_geometry2;
276 Clusters& m_clusters;
277 RobustPolicy const& m_robust_policy;
280 std::map<ring_identifier, int> m_regions;
281 std::map<ring_identifier, std::set<signed_size_type> > m_turns_per_ring;
286 }} // namespace detail::overlay
287 #endif // DOXYGEN_NO_DETAIL
289 }} // namespace boost::geometry
291 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP