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.
6 // Modifications copyright (c) 2017 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
19 #include <boost/range.hpp>
20
21 #include <boost/geometry/algorithms/detail/overlay/aggregate_operations.hpp>
22 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
23 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
24 #include <boost/geometry/algorithms/detail/overlay/traversal_intersection_patterns.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
26 #include <boost/geometry/core/access.hpp>
27 #include <boost/geometry/core/assert.hpp>
28
29 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
30 || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
31 || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
32 # include <string>
33 # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
34 # include <boost/geometry/io/wkt/wkt.hpp>
35 #endif
36
37 namespace boost { namespace geometry
38 {
39
40 #ifndef DOXYGEN_NO_DETAIL
41 namespace detail { namespace overlay
42 {
43
44 template <typename Turn, typename Operation>
45 #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
debug_traverse(Turn const & turn,Operation op,std::string const & header,bool condition=true)46 inline void debug_traverse(Turn const& turn, Operation op,
47 std::string const& header, bool condition = true)
48 {
49 if (! condition)
50 {
51 return;
52 }
53 std::cout << " " << header
54 << " at " << op.seg_id
55 << " meth: " << method_char(turn.method)
56 << " op: " << operation_char(op.operation)
57 << " vis: " << visited_char(op.visited)
58 << " of: " << operation_char(turn.operations[0].operation)
59 << operation_char(turn.operations[1].operation)
60 << " " << geometry::wkt(turn.point)
61 << std::endl;
62
63 if (boost::contains(header, "Finished"))
64 {
65 std::cout << std::endl;
66 }
67 }
68 #else
69 inline void debug_traverse(Turn const& , Operation, const char*, bool = true)
70 {
71 }
72 #endif
73
74
75 //! Metafunction to define side_order (clockwise, ccw) by operation_type
76 template <operation_type OpType>
77 struct side_compare {};
78
79 template <>
80 struct side_compare<operation_union>
81 {
82 typedef std::greater<int> type;
83 };
84
85 template <>
86 struct side_compare<operation_intersection>
87 {
88 typedef std::less<int> type;
89 };
90
91
92 template
93 <
94 bool Reverse1,
95 bool Reverse2,
96 overlay_type OverlayType,
97 typename Geometry1,
98 typename Geometry2,
99 typename Turns,
100 typename Clusters,
101 typename RobustPolicy,
102 typename SideStrategy,
103 typename Visitor
104 >
105 struct traversal
106 {
107 static const operation_type target_operation = operation_from_overlay<OverlayType>::value;
108
109 typedef typename side_compare<target_operation>::type side_compare_type;
110 typedef typename boost::range_value<Turns>::type turn_type;
111 typedef typename turn_type::turn_operation_type turn_operation_type;
112
113 typedef typename geometry::point_type<Geometry1>::type point_type;
114 typedef sort_by_side::side_sorter
115 <
116 Reverse1, Reverse2, OverlayType,
117 point_type, SideStrategy, side_compare_type
118 > sbs_type;
119
traversalboost::geometry::detail::overlay::traversal120 inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2,
121 Turns& turns, Clusters const& clusters,
122 RobustPolicy const& robust_policy, SideStrategy const& strategy,
123 Visitor& visitor)
124 : m_geometry1(geometry1)
125 , m_geometry2(geometry2)
126 , m_turns(turns)
127 , m_clusters(clusters)
128 , m_robust_policy(robust_policy)
129 , m_strategy(strategy)
130 , m_visitor(visitor)
131 {
132 }
133
finalize_visit_infoboost::geometry::detail::overlay::traversal134 inline void finalize_visit_info()
135 {
136 for (typename boost::range_iterator<Turns>::type
137 it = boost::begin(m_turns);
138 it != boost::end(m_turns);
139 ++it)
140 {
141 turn_type& turn = *it;
142 for (int i = 0; i < 2; i++)
143 {
144 turn_operation_type& op = turn.operations[i];
145 op.visited.finalize();
146 }
147 }
148 }
149
150 //! Sets visited for ALL turns traveling to the same turn
set_visited_in_clusterboost::geometry::detail::overlay::traversal151 inline void set_visited_in_cluster(signed_size_type cluster_id,
152 signed_size_type rank)
153 {
154 typename Clusters::const_iterator mit = m_clusters.find(cluster_id);
155 BOOST_ASSERT(mit != m_clusters.end());
156
157 cluster_info const& cinfo = mit->second;
158 std::set<signed_size_type> const& ids = cinfo.turn_indices;
159
160 for (typename std::set<signed_size_type>::const_iterator it = ids.begin();
161 it != ids.end(); ++it)
162 {
163 signed_size_type const turn_index = *it;
164 turn_type& turn = m_turns[turn_index];
165
166 for (int i = 0; i < 2; i++)
167 {
168 turn_operation_type& op = turn.operations[i];
169 if (op.visited.none()
170 && op.enriched.rank == rank)
171 {
172 op.visited.set_visited();
173 }
174 }
175 }
176 }
set_visitedboost::geometry::detail::overlay::traversal177 inline void set_visited(turn_type& turn, turn_operation_type& op)
178 {
179 if (op.operation == detail::overlay::operation_continue)
180 {
181 // On "continue", all go in same direction so set "visited" for ALL
182 for (int i = 0; i < 2; i++)
183 {
184 turn_operation_type& turn_op = turn.operations[i];
185 if (turn_op.visited.none())
186 {
187 turn_op.visited.set_visited();
188 }
189 }
190 }
191 else
192 {
193 op.visited.set_visited();
194 }
195 if (turn.cluster_id >= 0)
196 {
197 set_visited_in_cluster(turn.cluster_id, op.enriched.rank);
198 }
199 }
200
is_visitedboost::geometry::detail::overlay::traversal201 inline bool is_visited(turn_type const& , turn_operation_type const& op,
202 signed_size_type , int) const
203 {
204 return op.visited.visited();
205 }
206
select_sourceboost::geometry::detail::overlay::traversal207 inline bool select_source(signed_size_type turn_index,
208 segment_identifier const& candidate_seg_id,
209 segment_identifier const& previous_seg_id) const
210 {
211 // For uu/ii, only switch sources if indicated
212 turn_type const& turn = m_turns[turn_index];
213
214 if (OverlayType == overlay_buffer)
215 {
216 // Buffer does not use source_index (always 0)
217 return turn.switch_source
218 ? candidate_seg_id.multi_index != previous_seg_id.multi_index
219 : candidate_seg_id.multi_index == previous_seg_id.multi_index;
220 }
221
222 if (is_self_turn<OverlayType>(turn))
223 {
224 // Also, if it is a self-turn, stay on same ring (multi/ring)
225 return turn.switch_source
226 ? candidate_seg_id.multi_index != previous_seg_id.multi_index
227 : candidate_seg_id.multi_index == previous_seg_id.multi_index;
228 }
229
230 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
231 if (turn.switch_source)
232 {
233 std::cout << "Switch source at " << turn_index << std::endl;
234 }
235 else
236 {
237 std::cout << "DON'T SWITCH SOURCES at " << turn_index << std::endl;
238 }
239 #endif
240 return turn.switch_source
241 ? candidate_seg_id.source_index != previous_seg_id.source_index
242 : candidate_seg_id.source_index == previous_seg_id.source_index;
243 }
244
traverse_possibleboost::geometry::detail::overlay::traversal245 inline bool traverse_possible(signed_size_type turn_index) const
246 {
247 if (turn_index == -1)
248 {
249 return false;
250 }
251
252 turn_type const& turn = m_turns[turn_index];
253
254 // It is not a dead end if there is an operation to continue, or of
255 // there is a cluster (assuming for now we can get out of the cluster)
256 return turn.cluster_id >= 0
257 || turn.has(target_operation)
258 || turn.has(operation_continue);
259 }
260
261 inline
select_cc_operationboost::geometry::detail::overlay::traversal262 bool select_cc_operation(turn_type const& turn,
263 signed_size_type start_turn_index,
264 int& selected_op_index) const
265 {
266 // For "cc", take either one, but if there is a starting one,
267 // take that one. If next is dead end, skip that one.
268 // If both are valid candidates, take the one with minimal remaining
269 // distance (important for #mysql_23023665 in buffer).
270
271 // Initialize with 0, automatically assigned on first result
272 typename turn_operation_type::comparable_distance_type
273 min_remaining_distance = 0;
274
275 bool result = false;
276
277 for (int i = 0; i < 2; i++)
278 {
279 turn_operation_type const& op = turn.operations[i];
280
281 signed_size_type const next_turn_index = op.enriched.get_next_turn_index();
282
283 if (! traverse_possible(next_turn_index))
284 {
285 continue;
286 }
287
288 if (! result
289 || next_turn_index == start_turn_index
290 || op.remaining_distance < min_remaining_distance)
291 {
292 debug_traverse(turn, op, "First candidate cc", ! result);
293 debug_traverse(turn, op, "Candidate cc override (start)",
294 result && next_turn_index == start_turn_index);
295 debug_traverse(turn, op, "Candidate cc override (remaining)",
296 result && op.remaining_distance < min_remaining_distance);
297
298 selected_op_index = i;
299 min_remaining_distance = op.remaining_distance;
300 result = true;
301 }
302 }
303
304 return result;
305 }
306
307 inline
select_noncc_operationboost::geometry::detail::overlay::traversal308 bool select_noncc_operation(turn_type const& turn,
309 signed_size_type turn_index,
310 segment_identifier const& previous_seg_id,
311 int& selected_op_index) const
312 {
313 bool result = false;
314
315 for (int i = 0; i < 2; i++)
316 {
317 turn_operation_type const& op = turn.operations[i];
318
319 if (op.operation == target_operation
320 && ! op.visited.finished()
321 && (! result || select_source(turn_index, op.seg_id, previous_seg_id)))
322 {
323 selected_op_index = i;
324 debug_traverse(turn, op, "Candidate");
325 result = true;
326 }
327 }
328
329 return result;
330 }
331
332 inline
select_operationboost::geometry::detail::overlay::traversal333 bool select_operation(const turn_type& turn,
334 signed_size_type turn_index,
335 signed_size_type start_turn_index,
336 segment_identifier const& previous_seg_id,
337 int& selected_op_index) const
338 {
339 bool result = false;
340 selected_op_index = -1;
341 if (turn.both(operation_continue))
342 {
343 result = select_cc_operation(turn, start_turn_index,
344 selected_op_index);
345 }
346 else
347 {
348 result = select_noncc_operation(turn, turn_index,
349 previous_seg_id, selected_op_index);
350 }
351 if (result)
352 {
353 debug_traverse(turn, turn.operations[selected_op_index], "Accepted");
354 }
355
356 return result;
357 }
358
starting_operation_indexboost::geometry::detail::overlay::traversal359 inline int starting_operation_index(const turn_type& turn) const
360 {
361 for (int i = 0; i < 2; i++)
362 {
363 if (turn.operations[i].visited.started())
364 {
365 return i;
366 }
367 }
368 return -1;
369 }
370
both_finishedboost::geometry::detail::overlay::traversal371 inline bool both_finished(const turn_type& turn) const
372 {
373 for (int i = 0; i < 2; i++)
374 {
375 if (! turn.operations[i].visited.finished())
376 {
377 return false;
378 }
379 }
380 return true;
381 }
382
select_from_cluster_unionboost::geometry::detail::overlay::traversal383 inline bool select_from_cluster_union(signed_size_type& turn_index,
384 int& op_index, sbs_type& sbs) const
385 {
386 std::vector<sort_by_side::rank_with_rings> aggregation;
387 sort_by_side::aggregate_operations(sbs, aggregation, m_turns, operation_union);
388
389
390 sort_by_side::rank_with_rings const& incoming = aggregation.front();
391
392 // Take the first one outgoing for the incoming region
393 std::size_t selected_rank = 0;
394 for (std::size_t i = 1; i < aggregation.size(); i++)
395 {
396 sort_by_side::rank_with_rings const& rwr = aggregation[i];
397 if (rwr.all_to()
398 && rwr.region_id() == incoming.region_id())
399 {
400 selected_rank = rwr.rank;
401 break;
402 }
403 }
404
405 for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++)
406 {
407 typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
408 if (ranked_point.rank == selected_rank
409 && ranked_point.direction == sort_by_side::dir_to)
410 {
411 turn_index = ranked_point.turn_index;
412 op_index = ranked_point.operation_index;
413
414 turn_type const& turn = m_turns[turn_index];
415 turn_operation_type const& op = turn.operations[op_index];
416
417 if (op.enriched.count_left == 0
418 && op.enriched.count_right > 0
419 && ! op.visited.finalized())
420 {
421 // In some cases interior rings might be generated with polygons
422 // on both sides
423
424 // TODO: this should be finetuned such that checking
425 // finalized is not necessary
426 return true;
427 }
428 }
429 }
430 return false;
431 }
432
433
all_operations_of_typeboost::geometry::detail::overlay::traversal434 inline bool all_operations_of_type(sort_by_side::rank_with_rings const& rwr,
435 operation_type op_type,
436 sort_by_side::direction_type dir) const
437 {
438 typedef std::set<sort_by_side::ring_with_direction>::const_iterator sit_type;
439 for (sit_type it = rwr.rings.begin(); it != rwr.rings.end(); ++it)
440 {
441 sort_by_side::ring_with_direction const& rwd = *it;
442 if (rwd.direction != dir)
443 {
444 return false;
445 }
446 turn_type const& turn = m_turns[rwd.turn_index];
447 if (! turn.both(op_type))
448 {
449 return false;
450 }
451
452 // Check if this is not yet taken
453 turn_operation_type const& op = turn.operations[rwd.operation_index];
454 if (op.visited.finalized())
455 {
456 return false;
457 }
458
459 }
460 return true;
461 }
462
analyze_cluster_intersectionboost::geometry::detail::overlay::traversal463 inline bool analyze_cluster_intersection(signed_size_type& turn_index,
464 int& op_index, sbs_type const& sbs) const
465 {
466 std::vector<sort_by_side::rank_with_rings> aggregation;
467 sort_by_side::aggregate_operations(sbs, aggregation, m_turns, operation_intersection);
468
469 std::size_t selected_rank = 0;
470
471
472 // Detect specific pattern(s)
473 bool const detected
474 = intersection_pattern_common_interior1(selected_rank, aggregation)
475 || intersection_pattern_common_interior2(selected_rank, aggregation)
476 || intersection_pattern_common_interior3(selected_rank, aggregation)
477 || intersection_pattern_common_interior4(selected_rank, aggregation)
478 ;
479
480 if (! detected)
481 {
482 int incoming_region_id = 0;
483 std::set<int> outgoing_region_ids;
484
485 for (std::size_t i = 0; i < aggregation.size(); i++)
486 {
487 sort_by_side::rank_with_rings const& rwr = aggregation[i];
488
489 if (rwr.all_to()
490 && rwr.traversable(m_turns)
491 && selected_rank == 0)
492 {
493 // Take the first (= right) where segments leave,
494 // having the polygon on the right side
495 selected_rank = rwr.rank;
496 }
497
498 if (rwr.all_from()
499 && selected_rank > 0
500 && outgoing_region_ids.empty())
501 {
502 // Incoming
503 break;
504 }
505
506 if (incoming_region_id == 0)
507 {
508 sort_by_side::ring_with_direction const& rwd = *rwr.rings.begin();
509 turn_type const& turn = m_turns[rwd.turn_index];
510 incoming_region_id = turn.operations[rwd.operation_index].enriched.region_id;
511 }
512 else
513 {
514 if (rwr.rings.size() == 1)
515 {
516 sort_by_side::ring_with_direction const& rwd = *rwr.rings.begin();
517 turn_type const& turn = m_turns[rwd.turn_index];
518 if (rwd.direction == sort_by_side::dir_to
519 && turn.both(operation_intersection))
520 {
521
522 turn_operation_type const& op = turn.operations[rwd.operation_index];
523 if (op.enriched.region_id != incoming_region_id
524 && op.enriched.isolated)
525 {
526 outgoing_region_ids.insert(op.enriched.region_id);
527 }
528 }
529 else if (! outgoing_region_ids.empty())
530 {
531 for (int i = 0; i < 2; i++)
532 {
533 int const region_id = turn.operations[i].enriched.region_id;
534 if (outgoing_region_ids.count(region_id) == 1)
535 {
536 selected_rank = 0;
537 outgoing_region_ids.erase(region_id);
538 }
539 }
540 }
541 }
542 }
543 }
544 }
545
546 if (selected_rank > 0)
547 {
548 std::size_t selected_index = sbs.m_ranked_points.size();
549 for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
550 {
551 typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
552
553 if (ranked_point.rank == selected_rank)
554 {
555 turn_type const& ranked_turn = m_turns[ranked_point.turn_index];
556 turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.operation_index];
557
558 if (ranked_op.visited.finalized())
559 {
560 // This direction is already traveled before, the same
561 // cannot be traveled again
562 continue;
563 }
564
565 // Take the last turn from this rank
566 selected_index = i;
567 }
568 }
569
570 if (selected_index < sbs.m_ranked_points.size())
571 {
572 typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[selected_index];
573 turn_index = ranked_point.turn_index;
574 op_index = ranked_point.operation_index;
575 return true;
576 }
577 }
578
579 return false;
580 }
581
select_turn_from_clusterboost::geometry::detail::overlay::traversal582 inline bool select_turn_from_cluster(signed_size_type& turn_index,
583 int& op_index,
584 signed_size_type start_turn_index,
585 segment_identifier const& previous_seg_id) const
586 {
587 bool const is_union = target_operation == operation_union;
588
589 turn_type const& turn = m_turns[turn_index];
590 BOOST_ASSERT(turn.cluster_id >= 0);
591
592 typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id);
593 BOOST_ASSERT(mit != m_clusters.end());
594
595 cluster_info const& cinfo = mit->second;
596 std::set<signed_size_type> const& ids = cinfo.turn_indices;
597
598 sbs_type sbs(m_strategy);
599
600 for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
601 sit != ids.end(); ++sit)
602 {
603 signed_size_type cluster_turn_index = *sit;
604 turn_type const& cluster_turn = m_turns[cluster_turn_index];
605 bool const departure_turn = cluster_turn_index == turn_index;
606 if (cluster_turn.discarded)
607 {
608 // Defensive check, discarded turns should not be in cluster
609 continue;
610 }
611
612 for (int i = 0; i < 2; i++)
613 {
614 sbs.add(cluster_turn.operations[i],
615 cluster_turn_index, i, previous_seg_id,
616 m_geometry1, m_geometry2,
617 departure_turn);
618 }
619 }
620
621 if (! sbs.has_origin())
622 {
623 return false;
624 }
625 sbs.apply(turn.point);
626
627 bool result = false;
628
629 if (is_union)
630 {
631 result = select_from_cluster_union(turn_index, op_index, sbs);
632 }
633 else
634 {
635 result = analyze_cluster_intersection(turn_index, op_index, sbs);
636 }
637 return result;
638 }
639
analyze_ii_intersectionboost::geometry::detail::overlay::traversal640 inline bool analyze_ii_intersection(signed_size_type& turn_index, int& op_index,
641 turn_type const& current_turn,
642 segment_identifier const& previous_seg_id)
643 {
644 sbs_type sbs(m_strategy);
645
646 // Add this turn to the sort-by-side sorter
647 for (int i = 0; i < 2; i++)
648 {
649 sbs.add(current_turn.operations[i],
650 turn_index, i, previous_seg_id,
651 m_geometry1, m_geometry2,
652 true);
653 }
654
655 if (! sbs.has_origin())
656 {
657 return false;
658 }
659
660 sbs.apply(current_turn.point);
661
662 bool result = analyze_cluster_intersection(turn_index, op_index, sbs);
663
664 return result;
665 }
666
change_index_for_self_turnboost::geometry::detail::overlay::traversal667 inline void change_index_for_self_turn(signed_size_type& to_vertex_index,
668 turn_type const& start_turn,
669 turn_operation_type const& start_op,
670 int start_op_index) const
671 {
672 if (OverlayType != overlay_buffer)
673 {
674 return;
675 }
676
677 // It travels to itself, can happen. If this is a buffer, it can
678 // sometimes travel to itself in the following configuration:
679 //
680 // +---->--+
681 // | |
682 // | +---*----+ *: one turn, with segment index 2/7
683 // | | | |
684 // | +---C | C: closing point (start/end)
685 // | |
686 // +------------+
687 //
688 // If it starts on segment 2 and travels to itself on segment 2, that
689 // should be corrected to 7 because that is the shortest path
690 //
691 // Also a uu turn (touching with another buffered ring) might have this
692 // apparent configuration, but there it should
693 // always travel the whole ring
694
695 turn_operation_type const& other_op
696 = start_turn.operations[1 - start_op_index];
697
698 bool const correct
699 = ! start_turn.both(operation_union)
700 && start_op.seg_id.segment_index == to_vertex_index;
701
702 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
703 std::cout << " WARNING: self-buffer "
704 << " correct=" << correct
705 << " turn=" << operation_char(start_turn.operations[0].operation)
706 << operation_char(start_turn.operations[1].operation)
707 << " start=" << start_op.seg_id.segment_index
708 << " from=" << to_vertex_index
709 << " to=" << other_op.enriched.travels_to_vertex_index
710 << std::endl;
711 #endif
712
713 if (correct)
714 {
715 to_vertex_index = other_op.enriched.travels_to_vertex_index;
716 }
717 }
718
select_turn_from_enrichedboost::geometry::detail::overlay::traversal719 bool select_turn_from_enriched(signed_size_type& turn_index,
720 segment_identifier& previous_seg_id,
721 signed_size_type& to_vertex_index,
722 signed_size_type start_turn_index,
723 int start_op_index,
724 turn_type const& previous_turn,
725 turn_operation_type const& previous_op,
726 bool is_start) const
727 {
728 to_vertex_index = -1;
729
730 if (previous_op.enriched.next_ip_index < 0)
731 {
732 // There is no next IP on this segment
733 if (previous_op.enriched.travels_to_vertex_index < 0
734 || previous_op.enriched.travels_to_ip_index < 0)
735 {
736 return false;
737 }
738
739 to_vertex_index = previous_op.enriched.travels_to_vertex_index;
740
741 if (is_start &&
742 previous_op.enriched.travels_to_ip_index == start_turn_index)
743 {
744 change_index_for_self_turn(to_vertex_index, previous_turn,
745 previous_op, start_op_index);
746 }
747
748 turn_index = previous_op.enriched.travels_to_ip_index;
749 previous_seg_id = previous_op.seg_id;
750 }
751 else
752 {
753 // Take the next IP on this segment
754 turn_index = previous_op.enriched.next_ip_index;
755 previous_seg_id = previous_op.seg_id;
756 }
757 return true;
758 }
759
select_turnboost::geometry::detail::overlay::traversal760 bool select_turn(signed_size_type start_turn_index, int start_op_index,
761 signed_size_type& turn_index,
762 int& op_index,
763 int previous_op_index,
764 signed_size_type previous_turn_index,
765 segment_identifier const& previous_seg_id,
766 bool is_start)
767 {
768 turn_type const& current_turn = m_turns[turn_index];
769
770 if (target_operation == operation_intersection)
771 {
772 bool const back_at_start_cluster
773 = current_turn.cluster_id >= 0
774 && m_turns[start_turn_index].cluster_id == current_turn.cluster_id;
775
776 if (turn_index == start_turn_index || back_at_start_cluster)
777 {
778 // Intersection can always be finished if returning
779 turn_index = start_turn_index;
780 op_index = start_op_index;
781 return true;
782 }
783
784 if (current_turn.cluster_id < 0
785 && current_turn.both(operation_intersection))
786 {
787 if (analyze_ii_intersection(turn_index, op_index,
788 current_turn, previous_seg_id))
789 {
790 return true;
791 }
792 }
793 }
794
795 if (current_turn.cluster_id >= 0)
796 {
797 if (! select_turn_from_cluster(turn_index, op_index,
798 start_turn_index, previous_seg_id))
799 {
800 return false;
801 }
802
803 if (is_start && turn_index == previous_turn_index)
804 {
805 op_index = previous_op_index;
806 }
807 }
808 else
809 {
810 op_index = starting_operation_index(current_turn);
811 if (op_index == -1)
812 {
813 if (both_finished(current_turn))
814 {
815 return false;
816 }
817
818 if (! select_operation(current_turn, turn_index,
819 start_turn_index,
820 previous_seg_id,
821 op_index))
822 {
823 return false;
824 }
825 }
826 }
827 return true;
828 }
829
830 private :
831 Geometry1 const& m_geometry1;
832 Geometry2 const& m_geometry2;
833 Turns& m_turns;
834 Clusters const& m_clusters;
835 RobustPolicy const& m_robust_policy;
836 SideStrategy m_strategy;
837 Visitor& m_visitor;
838 };
839
840
841
842 }} // namespace detail::overlay
843 #endif // DOXYGEN_NO_DETAIL
844
845 }} // namespace boost::geometry
846
847 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
848