12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
- // This file was modified by Oracle on 2017, 2018.
- // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates.
- // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
- // Use, modification and distribution is subject to the Boost Software License,
- // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
- #include <cstddef>
- #include <set>
- #include <boost/range.hpp>
- #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
- #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
- #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
- #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
- #include <boost/geometry/core/access.hpp>
- #include <boost/geometry/core/assert.hpp>
- #include <boost/geometry/util/condition.hpp>
- #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
- || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
- || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
- # include <string>
- # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
- # include <boost/geometry/io/wkt/wkt.hpp>
- #endif
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace overlay
- {
- template <typename Turn, typename Operation>
- #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
- inline void debug_traverse(Turn const& turn, Operation op,
- std::string const& header, bool condition = true)
- {
- if (! condition)
- {
- return;
- }
- std::cout << " " << header
- << " at " << op.seg_id
- << " meth: " << method_char(turn.method)
- << " op: " << operation_char(op.operation)
- << " vis: " << visited_char(op.visited)
- << " of: " << operation_char(turn.operations[0].operation)
- << operation_char(turn.operations[1].operation)
- << " " << geometry::wkt(turn.point)
- << std::endl;
- if (boost::contains(header, "Finished"))
- {
- std::cout << std::endl;
- }
- }
- #else
- inline void debug_traverse(Turn const& , Operation, const char*, bool = true)
- {
- }
- #endif
- template
- <
- bool Reverse1,
- bool Reverse2,
- overlay_type OverlayType,
- typename Geometry1,
- typename Geometry2,
- typename Turns,
- typename Clusters,
- typename RobustPolicy,
- typename SideStrategy,
- typename Visitor
- >
- struct traversal
- {
- private :
- struct linked_turn_op_info
- {
- explicit linked_turn_op_info(signed_size_type ti = -1, int oi = -1,
- signed_size_type nti = -1)
- : turn_index(ti)
- , op_index(oi)
- , next_turn_index(nti)
- , rank_index(-1)
- {}
- signed_size_type turn_index;
- int op_index;
- signed_size_type next_turn_index;
- signed_size_type rank_index;
- };
- static const operation_type target_operation = operation_from_overlay<OverlayType>::value;
- typedef typename sort_by_side::side_compare<target_operation>::type side_compare_type;
- typedef typename boost::range_value<Turns>::type turn_type;
- typedef typename turn_type::turn_operation_type turn_operation_type;
- typedef typename geometry::point_type<Geometry1>::type point_type;
- typedef sort_by_side::side_sorter
- <
- Reverse1, Reverse2, OverlayType,
- point_type, SideStrategy, side_compare_type
- > sbs_type;
- public :
- inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2,
- Turns& turns, Clusters const& clusters,
- RobustPolicy const& robust_policy, SideStrategy const& strategy,
- Visitor& visitor)
- : m_geometry1(geometry1)
- , m_geometry2(geometry2)
- , m_turns(turns)
- , m_clusters(clusters)
- , m_robust_policy(robust_policy)
- , m_strategy(strategy)
- , m_visitor(visitor)
- {
- }
- template <typename TurnInfoMap>
- inline void finalize_visit_info(TurnInfoMap& turn_info_map)
- {
- for (typename boost::range_iterator<Turns>::type
- it = boost::begin(m_turns);
- it != boost::end(m_turns);
- ++it)
- {
- turn_type& turn = *it;
- for (int i = 0; i < 2; i++)
- {
- turn_operation_type& op = turn.operations[i];
- if (op.visited.visited()
- || op.visited.started()
- || op.visited.finished() )
- {
- ring_identifier const ring_id
- (
- op.seg_id.source_index,
- op.seg_id.multi_index,
- op.seg_id.ring_index
- );
- turn_info_map[ring_id].has_traversed_turn = true;
- if (op.operation == operation_continue)
- {
- // Continue operations should mark the other operation
- // as traversed too
- turn_operation_type& other_op = turn.operations[1 - i];
- ring_identifier const other_ring_id
- (
- other_op.seg_id.source_index,
- other_op.seg_id.multi_index,
- other_op.seg_id.ring_index
- );
- turn_info_map[other_ring_id].has_traversed_turn = true;
- }
- }
- op.visited.finalize();
- }
- }
- }
- //! Sets visited for ALL turns traveling to the same turn
- inline void set_visited_in_cluster(signed_size_type cluster_id,
- signed_size_type rank)
- {
- typename Clusters::const_iterator mit = m_clusters.find(cluster_id);
- BOOST_ASSERT(mit != m_clusters.end());
- cluster_info const& cinfo = mit->second;
- std::set<signed_size_type> const& ids = cinfo.turn_indices;
- for (typename std::set<signed_size_type>::const_iterator it = ids.begin();
- it != ids.end(); ++it)
- {
- signed_size_type const turn_index = *it;
- turn_type& turn = m_turns[turn_index];
- for (int i = 0; i < 2; i++)
- {
- turn_operation_type& op = turn.operations[i];
- if (op.visited.none()
- && op.enriched.rank == rank)
- {
- op.visited.set_visited();
- }
- }
- }
- }
- inline void set_visited(turn_type& turn, turn_operation_type& op)
- {
- if (op.operation == detail::overlay::operation_continue)
- {
- // On "continue", all go in same direction so set "visited" for ALL
- for (int i = 0; i < 2; i++)
- {
- turn_operation_type& turn_op = turn.operations[i];
- if (turn_op.visited.none())
- {
- turn_op.visited.set_visited();
- }
- }
- }
- else
- {
- op.visited.set_visited();
- }
- if (turn.is_clustered())
- {
- set_visited_in_cluster(turn.cluster_id, op.enriched.rank);
- }
- }
- inline bool is_visited(turn_type const& , turn_operation_type const& op,
- signed_size_type , int) const
- {
- return op.visited.visited();
- }
- template <signed_size_type segment_identifier::*Member>
- inline bool select_source_generic(turn_type const& turn,
- segment_identifier const& current,
- segment_identifier const& previous) const
- {
- turn_operation_type const& op0 = turn.operations[0];
- turn_operation_type const& op1 = turn.operations[1];
- bool const switch_source = op0.enriched.region_id != -1
- && op0.enriched.region_id == op1.enriched.region_id;
- #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
- if (switch_source)
- {
- std::cout << "Switch source at " << &turn << std::endl;
- }
- else
- {
- std::cout << "DON'T SWITCH SOURCES at " << &turn << std::endl;
- }
- #endif
- return switch_source
- ? current.*Member != previous.*Member
- : current.*Member == previous.*Member;
- }
- inline bool select_source(turn_type const& turn,
- segment_identifier const& candidate_seg_id,
- segment_identifier const& previous_seg_id) const
- {
- // For uu/ii, only switch sources if indicated
- if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_buffer))
- {
- // Buffer does not use source_index (always 0).
- return select_source_generic<&segment_identifier::multi_index>(
- turn, candidate_seg_id, previous_seg_id);
- }
- if (is_self_turn<OverlayType>(turn))
- {
- // Also, if it is a self-turn, stay on same ring (multi/ring)
- return select_source_generic<&segment_identifier::multi_index>(
- turn, candidate_seg_id, previous_seg_id);
- }
- // Use source_index
- return select_source_generic<&segment_identifier::source_index>(
- turn, candidate_seg_id, previous_seg_id);
- }
- inline bool traverse_possible(signed_size_type turn_index) const
- {
- if (turn_index == -1)
- {
- return false;
- }
- turn_type const& turn = m_turns[turn_index];
- // It is not a dead end if there is an operation to continue, or of
- // there is a cluster (assuming for now we can get out of the cluster)
- return turn.is_clustered()
- || turn.has(target_operation)
- || turn.has(operation_continue);
- }
- inline std::size_t get_shortcut_level(turn_operation_type const& op,
- signed_size_type start_turn_index,
- signed_size_type origin_turn_index,
- std::size_t level = 1) const
- {
- signed_size_type next_turn_index = op.enriched.get_next_turn_index();
- if (next_turn_index == -1)
- {
- return 0;
- }
- if (next_turn_index == start_turn_index)
- {
- // This operation finishes the ring
- return 0;
- }
- if (next_turn_index == origin_turn_index)
- {
- // This operation travels to itself
- return level;
- }
- if (level > 10)
- {
- // Avoid infinite recursion
- return 0;
- }
- turn_type const& next_turn = m_turns[next_turn_index];
- for (int i = 0; i < 2; i++)
- {
- turn_operation_type const& next_op = next_turn.operations[i];
- if (next_op.operation == target_operation
- && ! next_op.visited.finished()
- && ! next_op.visited.visited())
- {
- // Recursively continue verifying
- if (get_shortcut_level(next_op, start_turn_index,
- origin_turn_index, level + 1))
- {
- return level + 1;
- }
- }
- }
- return 0;
- }
- inline
- bool select_cc_operation(turn_type const& turn,
- signed_size_type start_turn_index,
- int& selected_op_index) const
- {
- // For "cc", take either one, but if there is a starting one,
- // take that one. If next is dead end, skip that one.
- // If both are valid candidates, take the one with minimal remaining
- // distance (important for #mysql_23023665 in buffer).
- signed_size_type next[2] = {0};
- bool possible[2] = {0};
- bool close[2] = {0};
- for (int i = 0; i < 2; i++)
- {
- next[i] = turn.operations[i].enriched.get_next_turn_index();
- possible[i] = traverse_possible(next[i]);
- close[i] = possible[i] && next[i] == start_turn_index;
- }
- if (close[0] != close[1])
- {
- // One of the operations will finish the ring. Take that one.
- selected_op_index = close[0] ? 0 : 1;
- debug_traverse(turn, turn.operations[selected_op_index], "Candidate cc closing");
- return true;
- }
- if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_buffer)
- && possible[0] && possible[1])
- {
- // Buffers sometimes have multiple overlapping pieces, where remaining
- // distance could lead to the wrong choice. Take the matching operation.
- bool is_target[2] = {0};
- for (int i = 0; i < 2; i++)
- {
- turn_operation_type const& next_op = m_turns[next[i]].operations[i];
- is_target[i] = next_op.operation == target_operation;
- }
- if (is_target[0] != is_target[1])
- {
- // Take the matching operation
- selected_op_index = is_target[0] ? 0 : 1;
- debug_traverse(turn, turn.operations[selected_op_index], "Candidate cc target");
- return true;
- }
- }
- static bool const is_union = target_operation == operation_union;
- typename turn_operation_type::comparable_distance_type
- best_remaining_distance = 0;
- bool result = false;
- for (int i = 0; i < 2; i++)
- {
- if (!possible[i])
- {
- continue;
- }
- turn_operation_type const& op = turn.operations[i];
- if (! result
- || (is_union && op.remaining_distance > best_remaining_distance)
- || (!is_union && op.remaining_distance < best_remaining_distance))
- {
- debug_traverse(turn, op, "First candidate cc", ! result);
- debug_traverse(turn, op, "Candidate cc override (remaining)",
- result && op.remaining_distance < best_remaining_distance);
- selected_op_index = i;
- best_remaining_distance = op.remaining_distance;
- result = true;
- }
- }
- return result;
- }
- inline
- bool select_noncc_operation(turn_type const& turn,
- segment_identifier const& previous_seg_id,
- int& selected_op_index) const
- {
- bool result = false;
- for (int i = 0; i < 2; i++)
- {
- turn_operation_type const& op = turn.operations[i];
- if (op.operation == target_operation
- && ! op.visited.finished()
- && ! op.visited.visited()
- && (! result || select_source(turn, op.seg_id, previous_seg_id)))
- {
- selected_op_index = i;
- debug_traverse(turn, op, "Candidate");
- result = true;
- }
- }
- return result;
- }
- inline
- bool select_preferred_operation(turn_type const& turn,
- signed_size_type turn_index,
- signed_size_type start_turn_index,
- int& selected_op_index) const
- {
- bool option[2] = {0};
- bool finishing[2] = {0};
- bool preferred[2] = {0};
- std::size_t shortcut_level[2] = {0};
- for (int i = 0; i < 2; i++)
- {
- turn_operation_type const& op = turn.operations[i];
- if (op.operation == target_operation
- && ! op.visited.finished()
- && ! op.visited.visited())
- {
- option[i] = true;
- if (op.enriched.get_next_turn_index() == start_turn_index)
- {
- finishing[i] = true;
- }
- else
- {
- shortcut_level[i] = get_shortcut_level(op, start_turn_index,
- turn_index);
- }
- if (op.enriched.prefer_start)
- {
- preferred[i] = true;
- }
- }
- }
- if (option[0] != option[1])
- {
- // Only one operation is acceptable, take that one
- selected_op_index = option[0] ? 0 : 1;
- return true;
- }
- if (option[0] && option[1])
- {
- // Both operations are acceptable
- if (finishing[0] != finishing[1])
- {
- // Prefer operation finishing the ring
- selected_op_index = finishing[0] ? 0 : 1;
- return true;
- }
- if (shortcut_level[0] != shortcut_level[1])
- {
- // If a turn can travel to itself again (without closing the
- // ring), take the shortest one
- selected_op_index = shortcut_level[0] < shortcut_level[1] ? 0 : 1;
- return true;
- }
- if (preferred[0] != preferred[1])
- {
- // Only one operation is preferred (== was not intersection)
- selected_op_index = preferred[0] ? 0 : 1;
- return true;
- }
- }
- for (int i = 0; i < 2; i++)
- {
- if (option[i])
- {
- selected_op_index = 0;
- return true;
- }
- }
- return false;
- }
- inline
- bool select_operation(const turn_type& turn,
- signed_size_type turn_index,
- signed_size_type start_turn_index,
- segment_identifier const& previous_seg_id,
- int& selected_op_index) const
- {
- bool result = false;
- selected_op_index = -1;
- if (turn.both(operation_continue))
- {
- result = select_cc_operation(turn, start_turn_index,
- selected_op_index);
- }
- else if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_dissolve))
- {
- result = select_preferred_operation(turn, turn_index,
- start_turn_index, selected_op_index);
- }
- else
- {
- result = select_noncc_operation(turn, previous_seg_id,
- selected_op_index);
- }
- if (result)
- {
- debug_traverse(turn, turn.operations[selected_op_index], "Accepted");
- }
- return result;
- }
- inline int starting_operation_index(const turn_type& turn) const
- {
- for (int i = 0; i < 2; i++)
- {
- if (turn.operations[i].visited.started())
- {
- return i;
- }
- }
- return -1;
- }
- inline bool both_finished(const turn_type& turn) const
- {
- for (int i = 0; i < 2; i++)
- {
- if (! turn.operations[i].visited.finished())
- {
- return false;
- }
- }
- return true;
- }
- template <typename RankedPoint>
- inline turn_operation_type const& operation_from_rank(RankedPoint const& rp) const
- {
- return m_turns[rp.turn_index].operations[rp.operation_index];
- }
- inline int select_turn_in_cluster_union(sort_by_side::rank_type selected_rank,
- typename sbs_type::rp const& ranked_point,
- signed_size_type start_turn_index, int start_op_index) const
- {
- // Returns 0 if it not OK
- // Returns 1 if it OK
- // Returns 2 if it OK and start turn matches
- // Returns 3 if it OK and start turn and start op both match
- if (ranked_point.rank != selected_rank
- || ranked_point.direction != sort_by_side::dir_to)
- {
- return 0;
- }
- turn_operation_type const& op = operation_from_rank(ranked_point);
- // Check finalized: TODO: this should be finetuned, it is not necessary
- if (op.visited.finalized())
- {
- return 0;
- }
- if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_dissolve)
- && (op.enriched.count_left != 0 || op.enriched.count_right == 0))
- {
- // Check counts: in some cases interior rings might be generated with
- // polygons on both sides. For dissolve it can be anything.
- return 0;
- }
- return ranked_point.turn_index == start_turn_index
- && ranked_point.operation_index == start_op_index ? 3
- : ranked_point.turn_index == start_turn_index ? 2
- : 1
- ;
- }
- inline sort_by_side::rank_type select_rank(sbs_type const& sbs,
- bool skip_isolated) const
- {
- // Take the first outgoing rank corresponding to incoming region,
- // or take another region if it is not isolated
- turn_operation_type const& incoming_op
- = operation_from_rank(sbs.m_ranked_points.front());
- for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
- {
- typename sbs_type::rp const& rp = sbs.m_ranked_points[i];
- if (rp.rank == 0 || rp.direction == sort_by_side::dir_from)
- {
- continue;
- }
- turn_operation_type const& op = operation_from_rank(rp);
- if (op.operation != target_operation
- && op.operation != operation_continue)
- {
- continue;
- }
- if (op.enriched.region_id == incoming_op.enriched.region_id
- || (skip_isolated && ! op.enriched.isolated))
- {
- // Region corresponds to incoming region, or (for intersection)
- // there is a non-isolated other region which should be taken
- return rp.rank;
- }
- }
- return -1;
- }
- inline bool select_from_cluster_union(signed_size_type& turn_index,
- int& op_index, sbs_type const& sbs,
- signed_size_type start_turn_index, int start_op_index) const
- {
- sort_by_side::rank_type const selected_rank = select_rank(sbs, false);
- int best_code = 0;
- bool result = false;
- for (std::size_t i = 1; i < sbs.m_ranked_points.size(); i++)
- {
- typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
- if (ranked_point.rank > selected_rank)
- {
- // Sorted on rank, so it makes no sense to continue
- break;
- }
- int const code
- = select_turn_in_cluster_union(selected_rank, ranked_point,
- start_turn_index, start_op_index);
- if (code > best_code)
- {
- // It is 1 or higher and matching better than previous
- best_code = code;
- turn_index = ranked_point.turn_index;
- op_index = ranked_point.operation_index;
- result = true;
- }
- }
- return result;
- }
- inline bool analyze_cluster_intersection(signed_size_type& turn_index,
- int& op_index, sbs_type const& sbs) const
- {
- sort_by_side::rank_type const selected_rank = select_rank(sbs, true);
- if (selected_rank > 0)
- {
- typename turn_operation_type::comparable_distance_type
- min_remaining_distance = 0;
- std::size_t selected_index = sbs.m_ranked_points.size();
- for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
- {
- typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
- if (ranked_point.rank == selected_rank)
- {
- turn_operation_type const& op = operation_from_rank(ranked_point);
- if (op.visited.finalized())
- {
- // This direction is already traveled before, the same
- // cannot be traveled again
- continue;
- }
- // Take turn with the smallest remaining distance
- if (selected_index == sbs.m_ranked_points.size()
- || op.remaining_distance < min_remaining_distance)
- {
- selected_index = i;
- min_remaining_distance = op.remaining_distance;
- }
- }
- }
- if (selected_index < sbs.m_ranked_points.size())
- {
- typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[selected_index];
- turn_index = ranked_point.turn_index;
- op_index = ranked_point.operation_index;
- return true;
- }
- }
- return false;
- }
- inline signed_size_type get_rank(sbs_type const& sbs,
- linked_turn_op_info const& info) const
- {
- for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
- {
- typename sbs_type::rp const& rp = sbs.m_ranked_points[i];
- if (rp.turn_index == info.turn_index
- && rp.operation_index == info.op_index
- && rp.direction == sort_by_side::dir_to)
- {
- return rp.rank;
- }
- }
- return -1;
- }
- // Function checks simple cases, such as a cluster with two turns,
- // arriving at the first turn, first turn points to second turn,
- // second turn points further.
- inline bool select_turn_from_cluster_linked(signed_size_type& turn_index,
- int& op_index,
- std::set<signed_size_type> const& ids,
- segment_identifier const& previous_seg_id) const
- {
- typedef typename std::set<signed_size_type>::const_iterator sit_type;
- std::vector<linked_turn_op_info> possibilities;
- std::vector<linked_turn_op_info> blocked;
- for (sit_type it = ids.begin(); it != ids.end(); ++it)
- {
- signed_size_type cluster_turn_index = *it;
- turn_type const& cluster_turn = m_turns[cluster_turn_index];
- if (cluster_turn.discarded)
- {
- continue;
- }
- if (cluster_turn.both(target_operation))
- {
- // Not (yet) supported, can be cluster of u/u turns
- return false;
- }
- for (int i = 0; i < 2; i++)
- {
- turn_operation_type const& op = cluster_turn.operations[i];
- turn_operation_type const& other_op = cluster_turn.operations[1 - i];
- signed_size_type const ni = op.enriched.get_next_turn_index();
- if (op.operation == target_operation
- || op.operation == operation_continue)
- {
- if (ni == cluster_turn_index)
- {
- // Not (yet) supported, traveling to itself, can be
- // hole
- return false;
- }
- possibilities.push_back(
- linked_turn_op_info(cluster_turn_index, i, ni));
- }
- else if (op.operation == operation_blocked
- && ! (ni == other_op.enriched.get_next_turn_index())
- && ids.count(ni) == 0)
- {
- // Points to turn, not part of this cluster,
- // and that way is blocked. But if the other operation
- // points at the same turn, it is still fine.
- blocked.push_back(
- linked_turn_op_info(cluster_turn_index, i, ni));
- }
- }
- }
- typedef typename std::vector<linked_turn_op_info>::const_iterator const_it_type;
- if (! blocked.empty())
- {
- sbs_type sbs(m_strategy);
- if (! fill_sbs(sbs, turn_index, ids, previous_seg_id))
- {
- return false;
- }
- for (typename std::vector<linked_turn_op_info>::iterator it = possibilities.begin();
- it != possibilities.end(); ++it)
- {
- linked_turn_op_info& info = *it;
- info.rank_index = get_rank(sbs, info);
- }
- for (typename std::vector<linked_turn_op_info>::iterator it = blocked.begin();
- it != blocked.end(); ++it)
- {
- linked_turn_op_info& info = *it;
- info.rank_index = get_rank(sbs, info);
- }
- for (const_it_type it = possibilities.begin();
- it != possibilities.end(); ++it)
- {
- linked_turn_op_info const& lti = *it;
- for (const_it_type bit = blocked.begin();
- bit != blocked.end(); ++bit)
- {
- linked_turn_op_info const& blti = *bit;
- if (blti.next_turn_index == lti.next_turn_index
- && blti.rank_index == lti.rank_index)
- {
- return false;
- }
- }
- }
- }
- // Traversal can either enter the cluster in the first turn,
- // or it can start halfway.
- // If there is one (and only one) possibility pointing outside
- // the cluster, take that one.
- linked_turn_op_info target;
- for (const_it_type it = possibilities.begin();
- it != possibilities.end(); ++it)
- {
- linked_turn_op_info const& lti = *it;
- if (ids.count(lti.next_turn_index) == 0)
- {
- if (target.turn_index >= 0
- && target.next_turn_index != lti.next_turn_index)
- {
- // Points to different target
- return false;
- }
- if (BOOST_GEOMETRY_CONDITION(OverlayType == overlay_buffer)
- && target.turn_index > 0)
- {
- // Target already assigned, so there are more targets
- // or more ways to the same target
- return false;
- }
- target = lti;
- }
- }
- if (target.turn_index < 0)
- {
- return false;
- }
- turn_index = target.turn_index;
- op_index = target.op_index;
- return true;
- }
- inline bool fill_sbs(sbs_type& sbs,
- signed_size_type turn_index,
- std::set<signed_size_type> const& ids,
- segment_identifier const& previous_seg_id) const
- {
- for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
- sit != ids.end(); ++sit)
- {
- signed_size_type cluster_turn_index = *sit;
- turn_type const& cluster_turn = m_turns[cluster_turn_index];
- bool const departure_turn = cluster_turn_index == turn_index;
- if (cluster_turn.discarded)
- {
- // Defensive check, discarded turns should not be in cluster
- continue;
- }
- for (int i = 0; i < 2; i++)
- {
- sbs.add(cluster_turn.operations[i],
- cluster_turn_index, i, previous_seg_id,
- m_geometry1, m_geometry2,
- departure_turn);
- }
- }
- if (! sbs.has_origin())
- {
- return false;
- }
- turn_type const& turn = m_turns[turn_index];
- sbs.apply(turn.point);
- return true;
- }
- inline bool select_turn_from_cluster(signed_size_type& turn_index,
- int& op_index,
- signed_size_type start_turn_index, int start_op_index,
- segment_identifier const& previous_seg_id) const
- {
- bool const is_union = target_operation == operation_union;
- turn_type const& turn = m_turns[turn_index];
- BOOST_ASSERT(turn.is_clustered());
- typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id);
- BOOST_ASSERT(mit != m_clusters.end());
- cluster_info const& cinfo = mit->second;
- std::set<signed_size_type> const& ids = cinfo.turn_indices;
- if (select_turn_from_cluster_linked(turn_index, op_index, ids, previous_seg_id))
- {
- return true;
- }
- sbs_type sbs(m_strategy);
- if (! fill_sbs(sbs, turn_index, ids, previous_seg_id))
- {
- return false;
- }
- bool result = false;
- if (is_union)
- {
- result = select_from_cluster_union(turn_index, op_index, sbs,
- start_turn_index, start_op_index);
- }
- else
- {
- result = analyze_cluster_intersection(turn_index, op_index, sbs);
- }
- return result;
- }
- inline bool analyze_ii_intersection(signed_size_type& turn_index, int& op_index,
- turn_type const& current_turn,
- segment_identifier const& previous_seg_id)
- {
- sbs_type sbs(m_strategy);
- // Add this turn to the sort-by-side sorter
- for (int i = 0; i < 2; i++)
- {
- sbs.add(current_turn.operations[i],
- turn_index, i, previous_seg_id,
- m_geometry1, m_geometry2,
- true);
- }
- if (! sbs.has_origin())
- {
- return false;
- }
- sbs.apply(current_turn.point);
- bool result = analyze_cluster_intersection(turn_index, op_index, sbs);
- return result;
- }
- inline void change_index_for_self_turn(signed_size_type& to_vertex_index,
- turn_type const& start_turn,
- turn_operation_type const& start_op,
- int start_op_index) const
- {
- if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_buffer
- && OverlayType != overlay_dissolve))
- {
- return;
- }
- const bool allow_uu = OverlayType != overlay_buffer;
- // It travels to itself, can happen. If this is a buffer, it can
- // sometimes travel to itself in the following configuration:
- //
- // +---->--+
- // | |
- // | +---*----+ *: one turn, with segment index 2/7
- // | | | |
- // | +---C | C: closing point (start/end)
- // | |
- // +------------+
- //
- // If it starts on segment 2 and travels to itself on segment 2, that
- // should be corrected to 7 because that is the shortest path
- //
- // Also a uu turn (touching with another buffered ring) might have this
- // apparent configuration, but there it should
- // always travel the whole ring
- turn_operation_type const& other_op
- = start_turn.operations[1 - start_op_index];
- bool const correct
- = (allow_uu || ! start_turn.both(operation_union))
- && start_op.seg_id.source_index == other_op.seg_id.source_index
- && start_op.seg_id.multi_index == other_op.seg_id.multi_index
- && start_op.seg_id.ring_index == other_op.seg_id.ring_index
- && start_op.seg_id.segment_index == to_vertex_index;
- #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
- std::cout << " WARNING: self-buffer "
- << " correct=" << correct
- << " turn=" << operation_char(start_turn.operations[0].operation)
- << operation_char(start_turn.operations[1].operation)
- << " start=" << start_op.seg_id.segment_index
- << " from=" << to_vertex_index
- << " to=" << other_op.enriched.travels_to_vertex_index
- << std::endl;
- #endif
- if (correct)
- {
- to_vertex_index = other_op.enriched.travels_to_vertex_index;
- }
- }
- bool select_turn_from_enriched(signed_size_type& turn_index,
- segment_identifier& previous_seg_id,
- signed_size_type& to_vertex_index,
- signed_size_type start_turn_index,
- int start_op_index,
- turn_type const& previous_turn,
- turn_operation_type const& previous_op,
- bool is_start) const
- {
- to_vertex_index = -1;
- if (previous_op.enriched.next_ip_index < 0)
- {
- // There is no next IP on this segment
- if (previous_op.enriched.travels_to_vertex_index < 0
- || previous_op.enriched.travels_to_ip_index < 0)
- {
- return false;
- }
- to_vertex_index = previous_op.enriched.travels_to_vertex_index;
- if (is_start &&
- previous_op.enriched.travels_to_ip_index == start_turn_index)
- {
- change_index_for_self_turn(to_vertex_index, previous_turn,
- previous_op, start_op_index);
- }
- turn_index = previous_op.enriched.travels_to_ip_index;
- previous_seg_id = previous_op.seg_id;
- }
- else
- {
- // Take the next IP on this segment
- turn_index = previous_op.enriched.next_ip_index;
- previous_seg_id = previous_op.seg_id;
- }
- return true;
- }
- bool select_turn(signed_size_type start_turn_index, int start_op_index,
- signed_size_type& turn_index,
- int& op_index,
- int previous_op_index,
- signed_size_type previous_turn_index,
- segment_identifier const& previous_seg_id,
- bool is_start, bool has_points)
- {
- turn_type const& current_turn = m_turns[turn_index];
- if (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection))
- {
- if (has_points)
- {
- bool const back_at_start_cluster
- = current_turn.is_clustered()
- && m_turns[start_turn_index].cluster_id == current_turn.cluster_id;
- if (turn_index == start_turn_index || back_at_start_cluster)
- {
- // Intersection can always be finished if returning
- turn_index = start_turn_index;
- op_index = start_op_index;
- return true;
- }
- }
- if (! current_turn.is_clustered()
- && current_turn.both(operation_intersection))
- {
- if (analyze_ii_intersection(turn_index, op_index,
- current_turn, previous_seg_id))
- {
- return true;
- }
- }
- }
- if (current_turn.is_clustered())
- {
- if (! select_turn_from_cluster(turn_index, op_index,
- start_turn_index, start_op_index, previous_seg_id))
- {
- return false;
- }
- if (is_start && turn_index == previous_turn_index)
- {
- op_index = previous_op_index;
- }
- }
- else
- {
- op_index = starting_operation_index(current_turn);
- if (op_index == -1)
- {
- if (both_finished(current_turn))
- {
- return false;
- }
- if (! select_operation(current_turn, turn_index,
- start_turn_index,
- previous_seg_id,
- op_index))
- {
- return false;
- }
- }
- }
- return true;
- }
- private :
- Geometry1 const& m_geometry1;
- Geometry2 const& m_geometry2;
- Turns& m_turns;
- Clusters const& m_clusters;
- RobustPolicy const& m_robust_policy;
- SideStrategy m_strategy;
- Visitor& m_visitor;
- };
- }} // namespace detail::overlay
- #endif // DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
|