1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4
5 // This file was modified by Oracle on 2017, 2018.
6 // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates.
7
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9
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)
13
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
16
17 #include <cstddef>
18 #include <set>
19
20 #include <boost/range.hpp>
21
22 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
23 #include <boost/geometry/algorithms/detail/overlay/cluster_exits.hpp>
24 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.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>
30
31 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
32 || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
33 || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
34 # include <string>
35 # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
36 # include <boost/geometry/io/wkt/wkt.hpp>
37 #endif
38
39 namespace boost { namespace geometry
40 {
41
42 #ifndef DOXYGEN_NO_DETAIL
43 namespace detail { namespace overlay
44 {
45
46 template <typename Turn, typename Operation>
47 #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
debug_traverse(Turn const & turn,Operation op,std::string const & header,bool condition=true)48 inline void debug_traverse(Turn const& turn, Operation op,
49 std::string const& header, bool condition = true)
50 {
51 if (! condition)
52 {
53 return;
54 }
55 std::cout << " " << header
56 << " at " << op.seg_id
57 << " meth: " << method_char(turn.method)
58 << " op: " << operation_char(op.operation)
59 << " vis: " << visited_char(op.visited)
60 << " of: " << operation_char(turn.operations[0].operation)
61 << operation_char(turn.operations[1].operation)
62 << " " << geometry::wkt(turn.point)
63 << std::endl;
64
65 if (boost::contains(header, "Finished"))
66 {
67 std::cout << std::endl;
68 }
69 }
70 #else
71 inline void debug_traverse(Turn const& , Operation, const char*, bool = true)
72 {
73 }
74 #endif
75
76 template
77 <
78 bool Reverse1,
79 bool Reverse2,
80 overlay_type OverlayType,
81 typename Geometry1,
82 typename Geometry2,
83 typename Turns,
84 typename Clusters,
85 typename RobustPolicy,
86 typename SideStrategy,
87 typename Visitor
88 >
89 struct traversal
90 {
91 private :
92
93 static const operation_type target_operation = operation_from_overlay<OverlayType>::value;
94
95 typedef typename sort_by_side::side_compare<target_operation>::type side_compare_type;
96 typedef typename boost::range_value<Turns>::type turn_type;
97 typedef typename turn_type::turn_operation_type turn_operation_type;
98
99 typedef typename geometry::point_type<Geometry1>::type point_type;
100 typedef sort_by_side::side_sorter
101 <
102 Reverse1, Reverse2, OverlayType,
103 point_type, SideStrategy, side_compare_type
104 > sbs_type;
105
106 public :
traversalboost::geometry::detail::overlay::traversal107 inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2,
108 Turns& turns, Clusters const& clusters,
109 RobustPolicy const& robust_policy, SideStrategy const& strategy,
110 Visitor& visitor)
111 : m_geometry1(geometry1)
112 , m_geometry2(geometry2)
113 , m_turns(turns)
114 , m_clusters(clusters)
115 , m_robust_policy(robust_policy)
116 , m_strategy(strategy)
117 , m_visitor(visitor)
118 {
119 }
120
121 template <typename TurnInfoMap>
finalize_visit_infoboost::geometry::detail::overlay::traversal122 inline void finalize_visit_info(TurnInfoMap& turn_info_map)
123 {
124 for (typename boost::range_iterator<Turns>::type
125 it = boost::begin(m_turns);
126 it != boost::end(m_turns);
127 ++it)
128 {
129 turn_type& turn = *it;
130 for (int i = 0; i < 2; i++)
131 {
132 turn_operation_type& op = turn.operations[i];
133 if (op.visited.visited()
134 || op.visited.started()
135 || op.visited.finished() )
136 {
137 ring_identifier const ring_id = ring_id_by_seg_id(op.seg_id);
138 turn_info_map[ring_id].has_traversed_turn = true;
139
140 if (op.operation == operation_continue)
141 {
142 // Continue operations should mark the other operation
143 // as traversed too
144 turn_operation_type& other_op = turn.operations[1 - i];
145 ring_identifier const other_ring_id
146 = ring_id_by_seg_id(other_op.seg_id);
147 turn_info_map[other_ring_id].has_traversed_turn = true;
148 }
149 }
150 op.visited.finalize();
151 }
152 }
153 }
154
155 //! Sets visited for ALL turns traveling to the same turn
set_visited_in_clusterboost::geometry::detail::overlay::traversal156 inline void set_visited_in_cluster(signed_size_type cluster_id,
157 signed_size_type rank)
158 {
159 typename Clusters::const_iterator mit = m_clusters.find(cluster_id);
160 BOOST_ASSERT(mit != m_clusters.end());
161
162 cluster_info const& cinfo = mit->second;
163 std::set<signed_size_type> const& ids = cinfo.turn_indices;
164
165 for (typename std::set<signed_size_type>::const_iterator it = ids.begin();
166 it != ids.end(); ++it)
167 {
168 signed_size_type const turn_index = *it;
169 turn_type& turn = m_turns[turn_index];
170
171 for (int i = 0; i < 2; i++)
172 {
173 turn_operation_type& op = turn.operations[i];
174 if (op.visited.none()
175 && op.enriched.rank == rank)
176 {
177 op.visited.set_visited();
178 }
179 }
180 }
181 }
set_visitedboost::geometry::detail::overlay::traversal182 inline void set_visited(turn_type& turn, turn_operation_type& op)
183 {
184 if (op.operation == detail::overlay::operation_continue)
185 {
186 // On "continue", all go in same direction so set "visited" for ALL
187 for (int i = 0; i < 2; i++)
188 {
189 turn_operation_type& turn_op = turn.operations[i];
190 if (turn_op.visited.none())
191 {
192 turn_op.visited.set_visited();
193 }
194 }
195 }
196 else
197 {
198 op.visited.set_visited();
199 }
200 if (turn.is_clustered())
201 {
202 set_visited_in_cluster(turn.cluster_id, op.enriched.rank);
203 }
204 }
205
is_visitedboost::geometry::detail::overlay::traversal206 inline bool is_visited(turn_type const& , turn_operation_type const& op,
207 signed_size_type , int) const
208 {
209 return op.visited.visited();
210 }
211
212 template <signed_size_type segment_identifier::*Member>
select_source_genericboost::geometry::detail::overlay::traversal213 inline bool select_source_generic(turn_type const& turn,
214 segment_identifier const& current,
215 segment_identifier const& previous) const
216 {
217 turn_operation_type const& op0 = turn.operations[0];
218 turn_operation_type const& op1 = turn.operations[1];
219
220 bool const switch_source = op0.enriched.region_id != -1
221 && op0.enriched.region_id == op1.enriched.region_id;
222
223 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
224 if (switch_source)
225 {
226 std::cout << "Switch source at " << &turn << std::endl;
227 }
228 else
229 {
230 std::cout << "DON'T SWITCH SOURCES at " << &turn << std::endl;
231 }
232 #endif
233 return switch_source
234 ? current.*Member != previous.*Member
235 : current.*Member == previous.*Member;
236 }
237
select_sourceboost::geometry::detail::overlay::traversal238 inline bool select_source(turn_type const& turn,
239 segment_identifier const& candidate_seg_id,
240 segment_identifier const& previous_seg_id) const
241 {
242 // For uu/ii, only switch sources if indicated
243
244 if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_buffer))
245 {
246 // Buffer does not use source_index (always 0).
247 return select_source_generic<&segment_identifier::multi_index>(
248 turn, candidate_seg_id, previous_seg_id);
249 }
250
251 if (is_self_turn<OverlayType>(turn))
252 {
253 // Also, if it is a self-turn, stay on same ring (multi/ring)
254 return select_source_generic<&segment_identifier::multi_index>(
255 turn, candidate_seg_id, previous_seg_id);
256 }
257
258 // Use source_index
259 return select_source_generic<&segment_identifier::source_index>(
260 turn, candidate_seg_id, previous_seg_id);
261 }
262
traverse_possibleboost::geometry::detail::overlay::traversal263 inline bool traverse_possible(signed_size_type turn_index) const
264 {
265 if (turn_index == -1)
266 {
267 return false;
268 }
269
270 turn_type const& turn = m_turns[turn_index];
271
272 // It is not a dead end if there is an operation to continue, or of
273 // there is a cluster (assuming for now we can get out of the cluster)
274 return turn.is_clustered()
275 || turn.has(target_operation)
276 || turn.has(operation_continue);
277 }
278
get_shortcut_levelboost::geometry::detail::overlay::traversal279 inline std::size_t get_shortcut_level(turn_operation_type const& op,
280 signed_size_type start_turn_index,
281 signed_size_type origin_turn_index,
282 std::size_t level = 1) const
283 {
284 signed_size_type next_turn_index = op.enriched.get_next_turn_index();
285 if (next_turn_index == -1)
286 {
287 return 0;
288 }
289 if (next_turn_index == start_turn_index)
290 {
291 // This operation finishes the ring
292 return 0;
293 }
294 if (next_turn_index == origin_turn_index)
295 {
296 // This operation travels to itself
297 return level;
298 }
299 if (level > 10)
300 {
301 // Avoid infinite recursion
302 return 0;
303 }
304
305 turn_type const& next_turn = m_turns[next_turn_index];
306 for (int i = 0; i < 2; i++)
307 {
308 turn_operation_type const& next_op = next_turn.operations[i];
309 if (next_op.operation == target_operation
310 && ! next_op.visited.finished()
311 && ! next_op.visited.visited())
312 {
313 // Recursively continue verifying
314 if (get_shortcut_level(next_op, start_turn_index,
315 origin_turn_index, level + 1))
316 {
317 return level + 1;
318 }
319 }
320 }
321 return 0;
322 }
323
324 inline
select_cc_operationboost::geometry::detail::overlay::traversal325 bool select_cc_operation(turn_type const& turn,
326 signed_size_type start_turn_index,
327 int& selected_op_index) const
328 {
329 // For "cc", take either one, but if there is a starting one,
330 // take that one. If next is dead end, skip that one.
331 // If both are valid candidates, take the one with minimal remaining
332 // distance (important for #mysql_23023665 in buffer).
333
334 signed_size_type next[2] = {0};
335 bool possible[2] = {0};
336 bool close[2] = {0};
337
338 for (int i = 0; i < 2; i++)
339 {
340 next[i] = turn.operations[i].enriched.get_next_turn_index();
341 possible[i] = traverse_possible(next[i]);
342 close[i] = possible[i] && next[i] == start_turn_index;
343 }
344
345 if (close[0] != close[1])
346 {
347 // One of the operations will finish the ring. Take that one.
348 selected_op_index = close[0] ? 0 : 1;
349 debug_traverse(turn, turn.operations[selected_op_index], "Candidate cc closing");
350 return true;
351 }
352
353 if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_buffer)
354 && possible[0] && possible[1])
355 {
356 // Buffers sometimes have multiple overlapping pieces, where remaining
357 // distance could lead to the wrong choice. Take the matching operation.
358
359 bool is_target[2] = {0};
360 for (int i = 0; i < 2; i++)
361 {
362 turn_operation_type const& next_op = m_turns[next[i]].operations[i];
363 is_target[i] = next_op.operation == target_operation;
364 }
365
366 if (is_target[0] != is_target[1])
367 {
368 // Take the matching operation
369 selected_op_index = is_target[0] ? 0 : 1;
370 debug_traverse(turn, turn.operations[selected_op_index], "Candidate cc target");
371 return true;
372 }
373 }
374
375 static bool const is_union = target_operation == operation_union;
376
377 typename turn_operation_type::comparable_distance_type
378 best_remaining_distance = 0;
379
380 bool result = false;
381
382 for (int i = 0; i < 2; i++)
383 {
384 if (!possible[i])
385 {
386 continue;
387 }
388
389 turn_operation_type const& op = turn.operations[i];
390
391 if (! result
392 || (is_union && op.remaining_distance > best_remaining_distance)
393 || (!is_union && op.remaining_distance < best_remaining_distance))
394 {
395 debug_traverse(turn, op, "First candidate cc", ! result);
396 debug_traverse(turn, op, "Candidate cc override (remaining)",
397 result && op.remaining_distance < best_remaining_distance);
398
399 selected_op_index = i;
400 best_remaining_distance = op.remaining_distance;
401 result = true;
402 }
403 }
404
405 return result;
406 }
407
408 inline
select_noncc_operationboost::geometry::detail::overlay::traversal409 bool select_noncc_operation(turn_type const& turn,
410 segment_identifier const& previous_seg_id,
411 int& selected_op_index) const
412 {
413 bool result = false;
414
415 for (int i = 0; i < 2; i++)
416 {
417 turn_operation_type const& op = turn.operations[i];
418
419 if (op.operation == target_operation
420 && ! op.visited.finished()
421 && ! op.visited.visited()
422 && (! result || select_source(turn, op.seg_id, previous_seg_id)))
423 {
424 selected_op_index = i;
425 debug_traverse(turn, op, "Candidate");
426 result = true;
427 }
428 }
429
430 return result;
431 }
432
433 inline
select_preferred_operationboost::geometry::detail::overlay::traversal434 bool select_preferred_operation(turn_type const& turn,
435 signed_size_type turn_index,
436 signed_size_type start_turn_index,
437 int& selected_op_index) const
438 {
439 bool option[2] = {0};
440 bool finishing[2] = {0};
441 bool preferred[2] = {0};
442 std::size_t shortcut_level[2] = {0};
443 for (int i = 0; i < 2; i++)
444 {
445 turn_operation_type const& op = turn.operations[i];
446
447 if (op.operation == target_operation
448 && ! op.visited.finished()
449 && ! op.visited.visited())
450 {
451 option[i] = true;
452 if (op.enriched.get_next_turn_index() == start_turn_index)
453 {
454 finishing[i] = true;
455 }
456 else
457 {
458 shortcut_level[i] = get_shortcut_level(op, start_turn_index,
459 turn_index);
460 }
461
462 if (op.enriched.prefer_start)
463 {
464 preferred[i] = true;
465 }
466 }
467 }
468
469 if (option[0] != option[1])
470 {
471 // Only one operation is acceptable, take that one
472 selected_op_index = option[0] ? 0 : 1;
473 return true;
474 }
475
476 if (option[0] && option[1])
477 {
478 // Both operations are acceptable
479 if (finishing[0] != finishing[1])
480 {
481 // Prefer operation finishing the ring
482 selected_op_index = finishing[0] ? 0 : 1;
483 return true;
484 }
485
486 if (shortcut_level[0] != shortcut_level[1])
487 {
488 // If a turn can travel to itself again (without closing the
489 // ring), take the shortest one
490 selected_op_index = shortcut_level[0] < shortcut_level[1] ? 0 : 1;
491 return true;
492 }
493
494 if (preferred[0] != preferred[1])
495 {
496 // Only one operation is preferred (== was not intersection)
497 selected_op_index = preferred[0] ? 0 : 1;
498 return true;
499 }
500 }
501
502 for (int i = 0; i < 2; i++)
503 {
504 if (option[i])
505 {
506 selected_op_index = 0;
507 return true;
508 }
509 }
510
511 return false;
512 }
513
514 inline
select_operationboost::geometry::detail::overlay::traversal515 bool select_operation(const turn_type& turn,
516 signed_size_type turn_index,
517 signed_size_type start_turn_index,
518 segment_identifier const& previous_seg_id,
519 int& selected_op_index) const
520 {
521 bool result = false;
522 selected_op_index = -1;
523 if (turn.both(operation_continue))
524 {
525 result = select_cc_operation(turn, start_turn_index,
526 selected_op_index);
527 }
528 else if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_dissolve))
529 {
530 result = select_preferred_operation(turn, turn_index,
531 start_turn_index, selected_op_index);
532 }
533 else
534 {
535 result = select_noncc_operation(turn, previous_seg_id,
536 selected_op_index);
537 }
538 if (result)
539 {
540 debug_traverse(turn, turn.operations[selected_op_index], "Accepted");
541 }
542
543 return result;
544 }
545
starting_operation_indexboost::geometry::detail::overlay::traversal546 inline int starting_operation_index(const turn_type& turn) const
547 {
548 for (int i = 0; i < 2; i++)
549 {
550 if (turn.operations[i].visited.started())
551 {
552 return i;
553 }
554 }
555 return -1;
556 }
557
both_finishedboost::geometry::detail::overlay::traversal558 inline bool both_finished(const turn_type& turn) const
559 {
560 for (int i = 0; i < 2; i++)
561 {
562 if (! turn.operations[i].visited.finished())
563 {
564 return false;
565 }
566 }
567 return true;
568 }
569
570
571 template <typename RankedPoint>
operation_from_rankboost::geometry::detail::overlay::traversal572 inline turn_operation_type const& operation_from_rank(RankedPoint const& rp) const
573 {
574 return m_turns[rp.turn_index].operations[rp.operation_index];
575 }
576
select_turn_in_cluster_unionboost::geometry::detail::overlay::traversal577 inline int select_turn_in_cluster_union(sort_by_side::rank_type selected_rank,
578 typename sbs_type::rp const& ranked_point,
579 signed_size_type start_turn_index, int start_op_index) const
580 {
581 // Returns 0 if it not OK
582 // Returns 1 if it OK
583 // Returns 2 if it OK and start turn matches
584 // Returns 3 if it OK and start turn and start op both match
585 if (ranked_point.rank != selected_rank
586 || ranked_point.direction != sort_by_side::dir_to)
587 {
588 return 0;
589 }
590
591 turn_operation_type const& op = operation_from_rank(ranked_point);
592
593 // Check finalized: TODO: this should be finetuned, it is not necessary
594 if (op.visited.finalized())
595 {
596 return 0;
597 }
598
599 if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_dissolve)
600 && (op.enriched.count_left != 0 || op.enriched.count_right == 0))
601 {
602 // Check counts: in some cases interior rings might be generated with
603 // polygons on both sides. For dissolve it can be anything.
604 return 0;
605 }
606
607 return ranked_point.turn_index == start_turn_index
608 && ranked_point.operation_index == start_op_index ? 3
609 : ranked_point.turn_index == start_turn_index ? 2
610 : 1
611 ;
612 }
613
select_rankboost::geometry::detail::overlay::traversal614 inline sort_by_side::rank_type select_rank(sbs_type const& sbs,
615 bool skip_isolated) const
616 {
617 // Take the first outgoing rank corresponding to incoming region,
618 // or take another region if it is not isolated
619 turn_operation_type const& incoming_op
620 = operation_from_rank(sbs.m_ranked_points.front());
621
622 for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
623 {
624 typename sbs_type::rp const& rp = sbs.m_ranked_points[i];
625 if (rp.rank == 0 || rp.direction == sort_by_side::dir_from)
626 {
627 continue;
628 }
629 turn_operation_type const& op = operation_from_rank(rp);
630
631 if (op.operation != target_operation
632 && op.operation != operation_continue)
633 {
634 continue;
635 }
636
637 if (op.enriched.region_id == incoming_op.enriched.region_id
638 || (skip_isolated && ! op.enriched.isolated))
639 {
640 // Region corresponds to incoming region, or (for intersection)
641 // there is a non-isolated other region which should be taken
642 return rp.rank;
643 }
644 }
645 return -1;
646 }
647
select_from_cluster_unionboost::geometry::detail::overlay::traversal648 inline bool select_from_cluster_union(signed_size_type& turn_index,
649 int& op_index, sbs_type const& sbs,
650 signed_size_type start_turn_index, int start_op_index) const
651 {
652 sort_by_side::rank_type const selected_rank = select_rank(sbs, false);
653
654 int best_code = 0;
655 bool result = false;
656 for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++)
657 {
658 typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
659
660 if (ranked_point.rank > selected_rank)
661 {
662 // Sorted on rank, so it makes no sense to continue
663 break;
664 }
665
666 int const code
667 = select_turn_in_cluster_union(selected_rank, ranked_point,
668 start_turn_index, start_op_index);
669
670 if (code > best_code)
671 {
672 // It is 1 or higher and matching better than previous
673 best_code = code;
674 turn_index = ranked_point.turn_index;
675 op_index = ranked_point.operation_index;
676 result = true;
677 }
678 }
679 return result;
680 }
681
analyze_cluster_intersectionboost::geometry::detail::overlay::traversal682 inline bool analyze_cluster_intersection(signed_size_type& turn_index,
683 int& op_index, sbs_type const& sbs) const
684 {
685 sort_by_side::rank_type const selected_rank = select_rank(sbs, true);
686
687 if (selected_rank > 0)
688 {
689 typename turn_operation_type::comparable_distance_type
690 min_remaining_distance = 0;
691
692 std::size_t selected_index = sbs.m_ranked_points.size();
693 for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
694 {
695 typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
696
697 if (ranked_point.rank == selected_rank)
698 {
699 turn_operation_type const& op = operation_from_rank(ranked_point);
700
701 if (op.visited.finalized())
702 {
703 // This direction is already traveled before, the same
704 // cannot be traveled again
705 continue;
706 }
707
708 // Take turn with the smallest remaining distance
709 if (selected_index == sbs.m_ranked_points.size()
710 || op.remaining_distance < min_remaining_distance)
711 {
712 selected_index = i;
713 min_remaining_distance = op.remaining_distance;
714 }
715 }
716 }
717
718 if (selected_index < sbs.m_ranked_points.size())
719 {
720 typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[selected_index];
721 turn_index = ranked_point.turn_index;
722 op_index = ranked_point.operation_index;
723 return true;
724 }
725 }
726
727 return false;
728 }
729
fill_sbsboost::geometry::detail::overlay::traversal730 inline bool fill_sbs(sbs_type& sbs,
731 signed_size_type turn_index,
732 std::set<signed_size_type> const& ids,
733 segment_identifier const& previous_seg_id) const
734 {
735 for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
736 sit != ids.end(); ++sit)
737 {
738 signed_size_type cluster_turn_index = *sit;
739 turn_type const& cluster_turn = m_turns[cluster_turn_index];
740 bool const departure_turn = cluster_turn_index == turn_index;
741 if (cluster_turn.discarded)
742 {
743 // Defensive check, discarded turns should not be in cluster
744 continue;
745 }
746
747 for (int i = 0; i < 2; i++)
748 {
749 sbs.add(cluster_turn.operations[i],
750 cluster_turn_index, i, previous_seg_id,
751 m_geometry1, m_geometry2,
752 departure_turn);
753 }
754 }
755
756 if (! sbs.has_origin())
757 {
758 return false;
759 }
760 turn_type const& turn = m_turns[turn_index];
761 sbs.apply(turn.point);
762 return true;
763 }
764
765
select_turn_from_clusterboost::geometry::detail::overlay::traversal766 inline bool select_turn_from_cluster(signed_size_type& turn_index,
767 int& op_index,
768 signed_size_type start_turn_index, int start_op_index,
769 segment_identifier const& previous_seg_id) const
770 {
771 bool const is_union = target_operation == operation_union;
772
773 turn_type const& turn = m_turns[turn_index];
774 BOOST_ASSERT(turn.is_clustered());
775
776 typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id);
777 BOOST_ASSERT(mit != m_clusters.end());
778
779 cluster_info const& cinfo = mit->second;
780 std::set<signed_size_type> const& ids = cinfo.turn_indices;
781
782 sbs_type sbs(m_strategy);
783
784 if (! fill_sbs(sbs, turn_index, ids, previous_seg_id))
785 {
786 return false;
787 }
788
789 cluster_exits<OverlayType, Turns, sbs_type> exits(m_turns, ids, sbs);
790
791 if (exits.apply(turn_index, op_index))
792 {
793 return true;
794 }
795
796 bool result = false;
797
798 if (is_union)
799 {
800 result = select_from_cluster_union(turn_index, op_index, sbs,
801 start_turn_index, start_op_index);
802 if (! result)
803 {
804 // There no way out found, try second pass in collected cluster exits
805 result = exits.apply(turn_index, op_index, false);
806 }
807 }
808 else
809 {
810 result = analyze_cluster_intersection(turn_index, op_index, sbs);
811 }
812 return result;
813 }
814
analyze_ii_intersectionboost::geometry::detail::overlay::traversal815 inline bool analyze_ii_intersection(signed_size_type& turn_index, int& op_index,
816 turn_type const& current_turn,
817 segment_identifier const& previous_seg_id)
818 {
819 sbs_type sbs(m_strategy);
820
821 // Add this turn to the sort-by-side sorter
822 for (int i = 0; i < 2; i++)
823 {
824 sbs.add(current_turn.operations[i],
825 turn_index, i, previous_seg_id,
826 m_geometry1, m_geometry2,
827 true);
828 }
829
830 if (! sbs.has_origin())
831 {
832 return false;
833 }
834
835 sbs.apply(current_turn.point);
836
837 bool result = analyze_cluster_intersection(turn_index, op_index, sbs);
838
839 return result;
840 }
841
change_index_for_self_turnboost::geometry::detail::overlay::traversal842 inline void change_index_for_self_turn(signed_size_type& to_vertex_index,
843 turn_type const& start_turn,
844 turn_operation_type const& start_op,
845 int start_op_index) const
846 {
847 if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_buffer
848 && OverlayType != overlay_dissolve))
849 {
850 return;
851 }
852
853 const bool allow_uu = OverlayType != overlay_buffer;
854
855 // It travels to itself, can happen. If this is a buffer, it can
856 // sometimes travel to itself in the following configuration:
857 //
858 // +---->--+
859 // | |
860 // | +---*----+ *: one turn, with segment index 2/7
861 // | | | |
862 // | +---C | C: closing point (start/end)
863 // | |
864 // +------------+
865 //
866 // If it starts on segment 2 and travels to itself on segment 2, that
867 // should be corrected to 7 because that is the shortest path
868 //
869 // Also a uu turn (touching with another buffered ring) might have this
870 // apparent configuration, but there it should
871 // always travel the whole ring
872
873 turn_operation_type const& other_op
874 = start_turn.operations[1 - start_op_index];
875
876 bool const correct
877 = (allow_uu || ! start_turn.both(operation_union))
878 && start_op.seg_id.source_index == other_op.seg_id.source_index
879 && start_op.seg_id.multi_index == other_op.seg_id.multi_index
880 && start_op.seg_id.ring_index == other_op.seg_id.ring_index
881 && start_op.seg_id.segment_index == to_vertex_index;
882
883 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
884 std::cout << " WARNING: self-buffer "
885 << " correct=" << correct
886 << " turn=" << operation_char(start_turn.operations[0].operation)
887 << operation_char(start_turn.operations[1].operation)
888 << " start=" << start_op.seg_id.segment_index
889 << " from=" << to_vertex_index
890 << " to=" << other_op.enriched.travels_to_vertex_index
891 << std::endl;
892 #endif
893
894 if (correct)
895 {
896 to_vertex_index = other_op.enriched.travels_to_vertex_index;
897 }
898 }
899
select_turn_from_enrichedboost::geometry::detail::overlay::traversal900 bool select_turn_from_enriched(signed_size_type& turn_index,
901 segment_identifier& previous_seg_id,
902 signed_size_type& to_vertex_index,
903 signed_size_type start_turn_index,
904 int start_op_index,
905 turn_type const& previous_turn,
906 turn_operation_type const& previous_op,
907 bool is_start) const
908 {
909 to_vertex_index = -1;
910
911 if (previous_op.enriched.next_ip_index < 0)
912 {
913 // There is no next IP on this segment
914 if (previous_op.enriched.travels_to_vertex_index < 0
915 || previous_op.enriched.travels_to_ip_index < 0)
916 {
917 return false;
918 }
919
920 to_vertex_index = previous_op.enriched.travels_to_vertex_index;
921
922 if (is_start &&
923 previous_op.enriched.travels_to_ip_index == start_turn_index)
924 {
925 change_index_for_self_turn(to_vertex_index, previous_turn,
926 previous_op, start_op_index);
927 }
928
929 turn_index = previous_op.enriched.travels_to_ip_index;
930 previous_seg_id = previous_op.seg_id;
931 }
932 else
933 {
934 // Take the next IP on this segment
935 turn_index = previous_op.enriched.next_ip_index;
936 previous_seg_id = previous_op.seg_id;
937 }
938 return true;
939 }
940
select_turnboost::geometry::detail::overlay::traversal941 bool select_turn(signed_size_type start_turn_index, int start_op_index,
942 signed_size_type& turn_index,
943 int& op_index,
944 int previous_op_index,
945 signed_size_type previous_turn_index,
946 segment_identifier const& previous_seg_id,
947 bool is_start, bool has_points)
948 {
949 turn_type const& current_turn = m_turns[turn_index];
950
951 if (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection))
952 {
953 if (has_points)
954 {
955 bool const back_at_start_cluster
956 = current_turn.is_clustered()
957 && m_turns[start_turn_index].cluster_id == current_turn.cluster_id;
958
959 if (turn_index == start_turn_index || back_at_start_cluster)
960 {
961 // Intersection can always be finished if returning
962 turn_index = start_turn_index;
963 op_index = start_op_index;
964 return true;
965 }
966 }
967
968 if (! current_turn.is_clustered()
969 && current_turn.both(operation_intersection))
970 {
971 if (analyze_ii_intersection(turn_index, op_index,
972 current_turn, previous_seg_id))
973 {
974 return true;
975 }
976 }
977 }
978
979 if (current_turn.is_clustered())
980 {
981 if (! select_turn_from_cluster(turn_index, op_index,
982 start_turn_index, start_op_index, previous_seg_id))
983 {
984 return false;
985 }
986
987 if (is_start && turn_index == previous_turn_index)
988 {
989 op_index = previous_op_index;
990 }
991 }
992 else
993 {
994 op_index = starting_operation_index(current_turn);
995 if (op_index == -1)
996 {
997 if (both_finished(current_turn))
998 {
999 return false;
1000 }
1001
1002 if (! select_operation(current_turn, turn_index,
1003 start_turn_index,
1004 previous_seg_id,
1005 op_index))
1006 {
1007 return false;
1008 }
1009 }
1010 }
1011 return true;
1012 }
1013
1014 private :
1015 Geometry1 const& m_geometry1;
1016 Geometry2 const& m_geometry2;
1017 Turns& m_turns;
1018 Clusters const& m_clusters;
1019 RobustPolicy const& m_robust_policy;
1020 SideStrategy m_strategy;
1021 Visitor& m_visitor;
1022 };
1023
1024
1025
1026 }} // namespace detail::overlay
1027 #endif // DOXYGEN_NO_DETAIL
1028
1029 }} // namespace boost::geometry
1030
1031 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
1032