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?)
ring_id_by_seg_id(segment_identifier const & seg_id)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 { isolation_unknown = -1, isolation_no = 0, isolation_yes = 1 };
52
53 typedef typename boost::range_value<Turns>::type turn_type;
54 typedef typename turn_type::turn_operation_type turn_operation_type;
55
56 // Per ring, first turns are collected (in turn_indices), and later
57 // a region_id is assigned
58 struct merged_ring_properties
59 {
60 signed_size_type region_id;
61 std::set<signed_size_type> turn_indices;
62
merged_ring_propertiesboost::geometry::detail::overlay::traversal_switch_detector::merged_ring_properties63 merged_ring_properties()
64 : region_id(-1)
65 {}
66 };
67
68 struct connection_properties
69 {
70 std::size_t count;
71 std::set<signed_size_type> cluster_indices;
connection_propertiesboost::geometry::detail::overlay::traversal_switch_detector::connection_properties72 connection_properties()
73 : count(0)
74 {}
75 };
76
77 typedef std::map<signed_size_type, connection_properties> connection_map;
78
79 // Per region, a set of properties is maintained, including its connections
80 // to other regions
81 struct region_properties
82 {
83 signed_size_type region_id;
84 isolation_type isolated;
85
86 // Maps from connected region_id to their properties
87 connection_map connected_region_counts;
88
region_propertiesboost::geometry::detail::overlay::traversal_switch_detector::region_properties89 region_properties()
90 : region_id(-1)
91 , isolated(isolation_unknown)
92 {}
93 };
94
95 // Keeps turn indices per ring
96 typedef std::map<ring_identifier, merged_ring_properties > merge_map;
97 typedef std::map<signed_size_type, region_properties> region_connection_map;
98
99 typedef std::set<signed_size_type>::const_iterator set_iterator;
100
traversal_switch_detectorboost::geometry::detail::overlay::traversal_switch_detector101 inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2,
102 Turns& turns, Clusters& clusters,
103 RobustPolicy const& robust_policy, Visitor& visitor)
104 : m_geometry1(geometry1)
105 , m_geometry2(geometry2)
106 , m_turns(turns)
107 , m_clusters(clusters)
108 , m_robust_policy(robust_policy)
109 , m_visitor(visitor)
110 {
111 }
112
get_isolationboost::geometry::detail::overlay::traversal_switch_detector113 isolation_type get_isolation(region_properties const& properties,
114 signed_size_type parent_region_id,
115 const std::set<signed_size_type>& visited)
116 {
117 if (properties.isolated != isolation_unknown)
118 {
119 return properties.isolated;
120 }
121
122 bool all_colocated = true;
123 int unique_cluster_id = -1;
124 for (typename connection_map::const_iterator it = properties.connected_region_counts.begin();
125 all_colocated && it != properties.connected_region_counts.end(); ++it)
126 {
127 connection_properties const& cprop = it->second;
128 if (cprop.cluster_indices.size() != 1)
129 {
130 // Either no cluster (non colocated point), or more clusters
131 all_colocated = false;
132 }
133 int const cluster_id = *cprop.cluster_indices.begin();
134 if (cluster_id == -1)
135 {
136 all_colocated = false;
137 }
138 else if (unique_cluster_id == -1)
139 {
140 unique_cluster_id = cluster_id;
141 }
142 else if (unique_cluster_id != cluster_id)
143 {
144 all_colocated = false;
145 }
146 }
147 if (all_colocated)
148 {
149 return isolation_yes;
150 }
151
152
153 // It is isolated if there is only one connection, or if there are more connections but all
154 // of them are isolated themselves, or if there are more connections
155 // but they are all colocated
156 std::size_t non_isolation_count = 0;
157 bool child_not_isolated = false;
158 for (typename connection_map::const_iterator it = properties.connected_region_counts.begin();
159 it != properties.connected_region_counts.end(); ++it)
160 {
161 signed_size_type const region_id = it->first;
162 connection_properties const& cprop = it->second;
163
164 if (region_id == parent_region_id)
165 {
166 // Normal situation, skip its direct parent
167 continue;
168 }
169 if (visited.count(region_id) > 0)
170 {
171 // Find one of its ancestors again, this is a ring. Not isolated.
172 return isolation_no;
173 }
174 if (cprop.count > 1)
175 {
176 return isolation_no;
177 }
178
179 typename region_connection_map::iterator mit = m_connected_regions.find(region_id);
180 if (mit == m_connected_regions.end())
181 {
182 // Should not occur
183 continue;
184 }
185
186 std::set<signed_size_type> vis = visited;
187 vis.insert(parent_region_id);
188
189 region_properties& prop = mit->second;
190 if (prop.isolated == isolation_unknown)
191 {
192 isolation_type const iso = get_isolation(prop, properties.region_id, vis);
193 prop.isolated = iso;
194 if (iso == isolation_no)
195 {
196 child_not_isolated = true;
197 }
198 }
199 if (prop.isolated == isolation_no)
200 {
201 non_isolation_count++;
202 }
203 }
204
205 return child_not_isolated || non_isolation_count > 1 ? isolation_no : isolation_yes;
206 }
207
get_isolated_regionsboost::geometry::detail::overlay::traversal_switch_detector208 void get_isolated_regions()
209 {
210 for (typename region_connection_map::iterator it = m_connected_regions.begin();
211 it != m_connected_regions.end(); ++it)
212 {
213 region_properties& properties = it->second;
214 if (properties.isolated == isolation_unknown)
215 {
216 std::set<signed_size_type> visited;
217 properties.isolated = get_isolation(properties, properties.region_id, visited);
218 }
219 }
220 }
221
assign_isolationboost::geometry::detail::overlay::traversal_switch_detector222 void assign_isolation()
223 {
224 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
225 {
226 turn_type& turn = m_turns[turn_index];
227
228 for (int op_index = 0; op_index < 2; op_index++)
229 {
230 turn_operation_type& op = turn.operations[op_index];
231 typename region_connection_map::const_iterator mit = m_connected_regions.find(op.enriched.region_id);
232 if (mit != m_connected_regions.end())
233 {
234 region_properties const& prop = mit->second;
235 op.enriched.isolated = prop.isolated == isolation_yes;
236 }
237 }
238 }
239 }
240
assign_regionsboost::geometry::detail::overlay::traversal_switch_detector241 void assign_regions()
242 {
243 for (typename merge_map::const_iterator it
244 = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
245 {
246 ring_identifier const& ring_id = it->first;
247 merged_ring_properties const& properties = it->second;
248
249 for (set_iterator sit = properties.turn_indices.begin();
250 sit != properties.turn_indices.end(); ++sit)
251 {
252 turn_type& turn = m_turns[*sit];
253
254 for (int i = 0; i < 2; i++)
255 {
256 turn_operation_type& op = turn.operations[i];
257 if (ring_id_by_seg_id(op.seg_id) == ring_id)
258 {
259 op.enriched.region_id = properties.region_id;
260 }
261 }
262 signed_size_type const& id0 = turn.operations[0].enriched.region_id;
263 signed_size_type const& id1 = turn.operations[1].enriched.region_id;
264 if (id0 != id1 && id0 != -1 && id1 != -1)
265 {
266 // Force insertion
267 m_connected_regions[id0].region_id = id0;
268 m_connected_regions[id1].region_id = id1;
269
270 connection_properties& prop0 = m_connected_regions[id0].connected_region_counts[id1];
271 connection_properties& prop1 = m_connected_regions[id1].connected_region_counts[id0];
272
273 if (turn.cluster_id < 0)
274 {
275 // Turn is not colocated, add reference to connection
276 prop0.count++;
277 prop1.count++;
278 }
279 else
280 {
281 // Turn is colocated, only add region reference if it was not yet registered
282 if (prop0.cluster_indices.count(turn.cluster_id) == 0)
283 {
284 prop0.count++;
285 }
286 if (prop1.cluster_indices.count(turn.cluster_id) == 0)
287 {
288 prop1.count++;
289 }
290 }
291 // Insert cluster-id (also -1 is inserted - reinsertion of
292 // same cluster id is OK)
293 prop0.cluster_indices.insert(turn.cluster_id);
294 prop1.cluster_indices.insert(turn.cluster_id);
295 }
296 }
297 }
298 }
299
connects_same_regionboost::geometry::detail::overlay::traversal_switch_detector300 inline bool connects_same_region(turn_type const& turn) const
301 {
302 if (turn.discarded)
303 {
304 // Discarded turns don't connect same region (otherwise discarded colocated uu turn
305 // could make a connection)
306 return false;
307 }
308
309 if (turn.cluster_id == -1)
310 {
311 // If it is a uu/ii-turn (non clustered), it is never same region
312 return ! (turn.both(operation_union) || turn.both(operation_intersection));
313 }
314
315 if (operation_from_overlay<OverlayType>::value == operation_union)
316 {
317 // It is a cluster, check zones
318 // (assigned by sort_by_side/handle colocations) of both operations
319 return turn.operations[0].enriched.zone
320 == turn.operations[1].enriched.zone;
321 }
322
323 // If a cluster contains an ii/cc it is not same region (for intersection)
324 typename Clusters::const_iterator it = m_clusters.find(turn.cluster_id);
325 if (it == m_clusters.end())
326 {
327 // Should not occur
328 return true;
329 }
330
331 cluster_info const& cinfo = it->second;
332 for (set_iterator sit = cinfo.turn_indices.begin();
333 sit != cinfo.turn_indices.end(); ++sit)
334 {
335 turn_type const& cluster_turn = m_turns[*sit];
336 if (cluster_turn.both(operation_union)
337 || cluster_turn.both(operation_intersection))
338 {
339 return false;
340 }
341 }
342
343 // It is the same region
344 return false;
345 }
346
347
get_region_idboost::geometry::detail::overlay::traversal_switch_detector348 inline int get_region_id(turn_operation_type const& op) const
349 {
350 return op.enriched.region_id;
351 }
352
353
create_regionboost::geometry::detail::overlay::traversal_switch_detector354 void create_region(signed_size_type& new_region_id, ring_identifier const& ring_id,
355 merged_ring_properties& properties, int region_id = -1)
356 {
357 if (properties.region_id > 0)
358 {
359 // Already handled
360 return;
361 }
362
363 // Assign new id if this is a new region
364 if (region_id == -1)
365 {
366 region_id = new_region_id++;
367 }
368
369 // Assign this ring to specified region
370 properties.region_id = region_id;
371
372 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
373 std::cout << " ADD " << ring_id << " TO REGION " << region_id << std::endl;
374 #endif
375
376 // Find connecting rings, recursively
377 for (set_iterator sit = properties.turn_indices.begin();
378 sit != properties.turn_indices.end(); ++sit)
379 {
380 signed_size_type const turn_index = *sit;
381 turn_type const& turn = m_turns[turn_index];
382 if (! connects_same_region(turn))
383 {
384 // This is a non clustered uu/ii-turn, or a cluster connecting different 'zones'
385 continue;
386 }
387
388 // Union: This turn connects two rings (interior connected), create the region
389 // Intersection: This turn connects two rings, set same regions for these two rings
390 for (int op_index = 0; op_index < 2; op_index++)
391 {
392 turn_operation_type const& op = turn.operations[op_index];
393 ring_identifier connected_ring_id = ring_id_by_seg_id(op.seg_id);
394 if (connected_ring_id != ring_id)
395 {
396 propagate_region(new_region_id, connected_ring_id, region_id);
397 }
398 }
399 }
400 }
401
propagate_regionboost::geometry::detail::overlay::traversal_switch_detector402 void propagate_region(signed_size_type& new_region_id,
403 ring_identifier const& ring_id, int region_id)
404 {
405 typename merge_map::iterator it = m_turns_per_ring.find(ring_id);
406 if (it != m_turns_per_ring.end())
407 {
408 create_region(new_region_id, ring_id, it->second, region_id);
409 }
410 }
411
412
iterateboost::geometry::detail::overlay::traversal_switch_detector413 void iterate()
414 {
415 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
416 std::cout << "SWITCH BEGIN ITERATION" << std::endl;
417 #endif
418
419 // Collect turns per ring
420 m_turns_per_ring.clear();
421 m_connected_regions.clear();
422
423 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
424 {
425 turn_type const& turn = m_turns[turn_index];
426
427 if (turn.discarded
428 && operation_from_overlay<OverlayType>::value == operation_intersection)
429 {
430 // Discarded turn (union currently still needs it to determine regions)
431 continue;
432 }
433
434 for (int op_index = 0; op_index < 2; op_index++)
435 {
436 turn_operation_type const& op = turn.operations[op_index];
437 m_turns_per_ring[ring_id_by_seg_id(op.seg_id)].turn_indices.insert(turn_index);
438 }
439 }
440
441 // All rings having turns are in the map. Now iterate them
442 {
443 signed_size_type new_region_id = 1;
444 for (typename merge_map::iterator it
445 = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
446 {
447 create_region(new_region_id, it->first, it->second);
448 }
449
450 assign_regions();
451 get_isolated_regions();
452 assign_isolation();
453 }
454
455 // Now that all regions are filled, assign switch_source property
456 // Iterate through all clusters
457 for (typename Clusters::iterator it = m_clusters.begin(); it != m_clusters.end(); ++it)
458 {
459 cluster_info& cinfo = it->second;
460 if (cinfo.open_count <= 1)
461 {
462 // Not a touching cluster
463 continue;
464 }
465
466 // A touching cluster, gather regions
467 std::set<int> regions;
468
469 std::set<signed_size_type> const& ids = cinfo.turn_indices;
470
471 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
472 std::cout << "SWITCH EXAMINE CLUSTER " << it->first << std::endl;
473 #endif
474
475 for (set_iterator sit = ids.begin(); sit != ids.end(); ++sit)
476 {
477 signed_size_type turn_index = *sit;
478 turn_type const& turn = m_turns[turn_index];
479 if (turn.colocated_ii && ! turn.colocated_uu)
480 {
481 continue;
482 }
483 for (int oi = 0; oi < 2; oi++)
484 {
485 int const region = get_region_id(turn.operations[oi]);
486 regions.insert(region);
487 }
488 }
489 // Switch source if this cluster connects the same region
490 cinfo.switch_source = regions.size() <= 1;
491 }
492
493 // Iterate through all uu/ii turns (non-clustered)
494 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
495 {
496 turn_type& turn = m_turns[turn_index];
497
498 if (turn.discarded
499 || turn.blocked()
500 || turn.cluster_id >= 0
501 || ! (turn.both(operation_union) || turn.both(operation_intersection)))
502 {
503 // Skip discarded, blocked, non-uu/ii and clustered turns
504 continue;
505 }
506
507 if (OverlayType == overlay_buffer)
508 {
509 // For deflate, the region approach does not work because many
510 // pieces are outside the real polygons
511 // TODO: implement this in another way for buffer
512 // (because now buffer might output invalid geometries)
513 continue;
514 }
515
516 int const region0 = get_region_id(turn.operations[0]);
517 int const region1 = get_region_id(turn.operations[1]);
518
519 // Switch sources for same region
520 turn.switch_source = region0 == region1;
521 }
522
523
524 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
525 std::cout << "SWITCH END ITERATION" << std::endl;
526
527 for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
528 {
529 turn_type const& turn = m_turns[turn_index];
530
531 if ((turn.both(operation_union) || turn.both(operation_intersection))
532 && turn.cluster_id < 0)
533 {
534 std::cout << "UU/II SWITCH RESULT "
535 << turn_index << " -> "
536 << turn.switch_source << std::endl;
537 }
538 }
539
540 for (typename Clusters::const_iterator it = m_clusters.begin(); it != m_clusters.end(); ++it)
541 {
542 cluster_info const& cinfo = it->second;
543 if (cinfo.open_count > 1)
544 {
545 std::cout << "CL SWITCH RESULT " << it->first
546 << " -> " << cinfo.switch_source << std::endl;
547 }
548 else
549 {
550 std::cout << "CL SWITCH RESULT " << it->first
551 << " is not registered as open" << std::endl;
552 }
553 }
554 #endif
555
556 }
557
558 private:
559
560 Geometry1 const& m_geometry1;
561 Geometry2 const& m_geometry2;
562 Turns& m_turns;
563 Clusters& m_clusters;
564 merge_map m_turns_per_ring;
565 region_connection_map m_connected_regions;
566 RobustPolicy const& m_robust_policy;
567 Visitor& m_visitor;
568 };
569
570 }} // namespace detail::overlay
571 #endif // DOXYGEN_NO_DETAIL
572
573 }} // namespace boost::geometry
574
575 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP
576