1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2020 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_CLUSTER_EXITS_HPP 10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLUSTER_EXITS_HPP 11 12 #include <boost/geometry/core/access.hpp> 13 #include <boost/geometry/core/assert.hpp> 14 #include <boost/geometry/util/condition.hpp> 15 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> 16 #include <boost/geometry/algorithms/detail/signed_size_type.hpp> 17 18 #include <cstddef> 19 #include <set> 20 #include <vector> 21 22 #include <boost/range.hpp> 23 24 25 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \ 26 || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \ 27 || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE) 28 # include <string> 29 # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> 30 # include <boost/geometry/io/wkt/wkt.hpp> 31 #endif 32 33 namespace boost { namespace geometry 34 { 35 36 #ifndef DOXYGEN_NO_DETAIL 37 namespace detail { namespace overlay 38 { 39 40 // Structure to check relatively simple cluster cases 41 template <overlay_type OverlayType, 42 typename Turns, 43 typename Sbs> 44 struct cluster_exits 45 { 46 private : 47 static const operation_type target_operation = operation_from_overlay<OverlayType>::value; 48 typedef typename boost::range_value<Turns>::type turn_type; 49 typedef typename turn_type::turn_operation_type turn_operation_type; 50 51 struct linked_turn_op_info 52 { linked_turn_op_infoboost::geometry::detail::overlay::cluster_exits::linked_turn_op_info53 explicit linked_turn_op_info(signed_size_type ti = -1, int oi = -1, 54 signed_size_type nti = -1) 55 : turn_index(ti) 56 , op_index(oi) 57 , next_turn_index(nti) 58 , rank_index(-1) 59 {} 60 61 signed_size_type turn_index; 62 int op_index; 63 signed_size_type next_turn_index; 64 signed_size_type rank_index; 65 }; 66 67 typedef typename std::vector<linked_turn_op_info>::const_iterator const_it_type; 68 typedef typename std::vector<linked_turn_op_info>::iterator it_type; 69 typedef typename std::set<signed_size_type>::const_iterator sit_type; 70 get_rankboost::geometry::detail::overlay::cluster_exits71 inline signed_size_type get_rank(Sbs const& sbs, 72 linked_turn_op_info const& info) const 73 { 74 for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) 75 { 76 typename Sbs::rp const& rp = sbs.m_ranked_points[i]; 77 if (rp.turn_index == info.turn_index 78 && rp.operation_index == info.op_index 79 && rp.direction == sort_by_side::dir_to) 80 { 81 return rp.rank; 82 } 83 } 84 return -1; 85 } 86 87 std::set<signed_size_type> const& m_ids; 88 std::vector<linked_turn_op_info> possibilities; 89 std::vector<linked_turn_op_info> blocked; 90 91 bool m_valid; 92 collectboost::geometry::detail::overlay::cluster_exits93 bool collect(Turns const& turns) 94 { 95 for (sit_type it = m_ids.begin(); it != m_ids.end(); ++it) 96 { 97 signed_size_type cluster_turn_index = *it; 98 turn_type const& cluster_turn = turns[cluster_turn_index]; 99 if (cluster_turn.discarded) 100 { 101 continue; 102 } 103 if (cluster_turn.both(target_operation)) 104 { 105 // Not (yet) supported, can be cluster of u/u turns 106 return false; 107 } 108 for (int i = 0; i < 2; i++) 109 { 110 turn_operation_type const& op = cluster_turn.operations[i]; 111 turn_operation_type const& other_op = cluster_turn.operations[1 - i]; 112 signed_size_type const ni = op.enriched.get_next_turn_index(); 113 114 if (op.operation == target_operation 115 || op.operation == operation_continue) 116 { 117 if (ni == cluster_turn_index) 118 { 119 // Not (yet) supported, traveling to itself, can be 120 // hole 121 return false; 122 } 123 possibilities.push_back( 124 linked_turn_op_info(cluster_turn_index, i, ni)); 125 } 126 else if (op.operation == operation_blocked 127 && ! (ni == other_op.enriched.get_next_turn_index()) 128 && m_ids.count(ni) == 0) 129 { 130 // Points to turn, not part of this cluster, 131 // and that way is blocked. But if the other operation 132 // points at the same turn, it is still fine. 133 blocked.push_back( 134 linked_turn_op_info(cluster_turn_index, i, ni)); 135 } 136 } 137 } 138 return true; 139 } 140 check_blockedboost::geometry::detail::overlay::cluster_exits141 bool check_blocked(Sbs const& sbs) 142 { 143 if (blocked.empty()) 144 { 145 return true; 146 } 147 148 for (it_type it = possibilities.begin(); it != possibilities.end(); ++it) 149 { 150 linked_turn_op_info& info = *it; 151 info.rank_index = get_rank(sbs, info); 152 } 153 for (it_type it = blocked.begin(); it != blocked.end(); ++it) 154 { 155 linked_turn_op_info& info = *it; 156 info.rank_index = get_rank(sbs, info); 157 } 158 159 for (const_it_type it = possibilities.begin(); it != possibilities.end(); ++it) 160 { 161 linked_turn_op_info const& lti = *it; 162 for (const_it_type bit = blocked.begin(); bit != blocked.end(); ++bit) 163 { 164 linked_turn_op_info const& blti = *bit; 165 if (blti.next_turn_index == lti.next_turn_index 166 && blti.rank_index == lti.rank_index) 167 { 168 return false; 169 } 170 } 171 } 172 return true; 173 } 174 175 public : cluster_exitsboost::geometry::detail::overlay::cluster_exits176 cluster_exits(Turns const& turns, 177 std::set<signed_size_type> const& ids, 178 Sbs const& sbs) 179 : m_ids(ids) 180 , m_valid(collect(turns) && check_blocked(sbs)) 181 { 182 } 183 applyboost::geometry::detail::overlay::cluster_exits184 inline bool apply(signed_size_type& turn_index, 185 int& op_index, 186 bool first_run = true) const 187 { 188 if (! m_valid) 189 { 190 return false; 191 } 192 193 // Traversal can either enter the cluster in the first turn, 194 // or it can start halfway. 195 // If there is one (and only one) possibility pointing outside 196 // the cluster, take that one. 197 linked_turn_op_info target; 198 for (const_it_type it = possibilities.begin(); 199 it != possibilities.end(); ++it) 200 { 201 linked_turn_op_info const& lti = *it; 202 if (m_ids.count(lti.next_turn_index) == 0) 203 { 204 if (target.turn_index >= 0 205 && target.next_turn_index != lti.next_turn_index) 206 { 207 // Points to different target 208 return false; 209 } 210 if (first_run 211 && BOOST_GEOMETRY_CONDITION(OverlayType == overlay_buffer) 212 && target.turn_index >= 0) 213 { 214 // Target already assigned, so there are more targets 215 // or more ways to the same target 216 return false; 217 } 218 219 target = lti; 220 } 221 } 222 if (target.turn_index < 0) 223 { 224 return false; 225 } 226 227 turn_index = target.turn_index; 228 op_index = target.op_index; 229 230 return true; 231 } 232 }; 233 234 }} // namespace detail::overlay 235 #endif // DOXYGEN_NO_DETAIL 236 237 }} // namespace boost::geometry 238 239 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_CLUSTER_EXITS_HPP 240