1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2012 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_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP 10 #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP 11 12 13 #include <cstddef> 14 #include <string> 15 16 #include <boost/concept_check.hpp> 17 18 #include <boost/geometry/arithmetic/determinant.hpp> 19 #include <boost/geometry/strategies/side_info.hpp> 20 21 #include <boost/geometry/util/math.hpp> 22 #include <boost/geometry/util/select_calculation_type.hpp> 23 #include <boost/geometry/util/select_most_precise.hpp> 24 25 26 namespace boost { namespace geometry 27 { 28 29 30 namespace policies { namespace relate 31 { 32 33 struct direction_type 34 { 35 // NOTE: "char" will be replaced by enum in future version 36 direction_typeboost::geometry::policies::relate::direction_type37 inline direction_type(side_info const& s, char h, 38 int ha, int hb, 39 int da = 0, int db = 0, 40 bool op = false) 41 : how(h) 42 , opposite(op) 43 , how_a(ha) 44 , how_b(hb) 45 , dir_a(da) 46 , dir_b(db) 47 , sides(s) 48 { 49 arrival[0] = ha; 50 arrival[1] = hb; 51 } 52 direction_typeboost::geometry::policies::relate::direction_type53 inline direction_type(char h, bool op, int ha = 0, int hb = 0) 54 : how(h) 55 , opposite(op) 56 , how_a(ha) 57 , how_b(hb) 58 , dir_a(0) 59 , dir_b(0) 60 { 61 arrival[0] = ha; 62 arrival[1] = hb; 63 } 64 65 66 // TODO: replace this 67 // NOTE: "char" will be replaced by enum in future version 68 // "How" is the intersection formed? 69 char how; 70 71 // Is it opposite (for collinear/equal cases) 72 bool opposite; 73 74 // Information on how A arrives at intersection, how B arrives at intersection 75 // 1: arrives at intersection 76 // -1: starts from intersection 77 int how_a; 78 int how_b; 79 80 // Direction: how is A positioned from B 81 // 1: points left, seen from IP 82 // -1: points right, seen from IP 83 // In case of intersection: B's TO direction 84 // In case that B's TO direction is at A: B's from direction 85 // In collinear cases: it is 0 86 int dir_a; // Direction of A-s TO from IP 87 int dir_b; // Direction of B-s TO from IP 88 89 // New information 90 side_info sides; 91 // THIS IS EQUAL TO arrival_a, arrival_b - they probably can go now we have robust fractions 92 int arrival[2]; // 1=arrival, -1=departure, 0=neutral; == how_a//how_b 93 94 95 // About arrival[0] (== arrival of a2 w.r.t. b) for COLLINEAR cases 96 // Arrival 1: a1--------->a2 (a arrives within b) 97 // b1----->b2 98 99 // Arrival 1: (a in b) 100 // 101 102 103 // Arrival -1: a1--------->a2 (a does not arrive within b) 104 // b1----->b2 105 106 // Arrival -1: (b in a) a_1-------------a_2 107 // b_1---b_2 108 109 // Arrival 0: a1------->a2 (a arrives at TO-border of b) 110 // b1--->b2 111 112 }; 113 114 struct segments_direction 115 { 116 typedef direction_type return_type; 117 118 template 119 < 120 typename Segment1, 121 typename Segment2, 122 typename SegmentIntersectionInfo 123 > segments_crossesboost::geometry::policies::relate::segments_direction124 static inline return_type segments_crosses(side_info const& sides, 125 SegmentIntersectionInfo const& , 126 Segment1 const& , Segment2 const& ) 127 { 128 bool const ra0 = sides.get<0,0>() == 0; 129 bool const ra1 = sides.get<0,1>() == 0; 130 bool const rb0 = sides.get<1,0>() == 0; 131 bool const rb1 = sides.get<1,1>() == 0; 132 133 return 134 // opposite and same starting point (FROM) 135 ra0 && rb0 ? calculate_side<1>(sides, 'f', -1, -1) 136 137 // opposite and point to each other (TO) 138 : ra1 && rb1 ? calculate_side<0>(sides, 't', 1, 1) 139 140 // not opposite, forming an angle, first a then b, 141 // directed either both left, or both right 142 // Check side of B2 from A. This is not calculated before 143 : ra1 && rb0 ? angle<1>(sides, 'a', 1, -1) 144 145 // not opposite, forming a angle, first b then a, 146 // directed either both left, or both right 147 : ra0 && rb1 ? angle<0>(sides, 'a', -1, 1) 148 149 // b starts from interior of a 150 : rb0 ? starts_from_middle(sides, 'B', 0, -1) 151 152 // a starts from interior of b (#39) 153 : ra0 ? starts_from_middle(sides, 'A', -1, 0) 154 155 // b ends at interior of a, calculate direction of A from IP 156 : rb1 ? b_ends_at_middle(sides) 157 158 // a ends at interior of b 159 : ra1 ? a_ends_at_middle(sides) 160 161 // normal intersection 162 : calculate_side<1>(sides, 'i', -1, -1) 163 ; 164 } 165 166 template <typename Ratio> arrival_valueboost::geometry::policies::relate::segments_direction167 static inline int arrival_value(Ratio const& r_from, Ratio const& r_to) 168 { 169 // a1--------->a2 170 // b1----->b2 171 // a departs: -1 172 173 // a1--------->a2 174 // b1----->b2 175 // a arrives: 1 176 177 // a1--------->a2 178 // b1----->b2 179 // both arrive there -> r-to = 1/1, or 0/1 (on_segment) 180 181 // First check the TO (for arrival), then FROM (for departure) 182 return r_to.in_segment() ? 1 183 : r_to.on_segment() ? 0 184 : r_from.on_segment() ? -1 185 : -1 186 ; 187 } 188 189 template <typename Ratio> analyzeboost::geometry::policies::relate::segments_direction190 static inline void analyze(Ratio const& r, 191 int& in_segment_count, 192 int& on_end_count, 193 int& outside_segment_count) 194 { 195 if (r.on_end()) 196 { 197 on_end_count++; 198 } 199 else if (r.in_segment()) 200 { 201 in_segment_count++; 202 } 203 else 204 { 205 outside_segment_count++; 206 } 207 } 208 arrival_from_position_valueboost::geometry::policies::relate::segments_direction209 static inline int arrival_from_position_value(int /*v_from*/, int v_to) 210 { 211 return v_to == 2 ? 1 212 : v_to == 1 || v_to == 3 ? 0 213 //: v_from >= 1 && v_from <= 3 ? -1 214 : -1; 215 216 // NOTE: this should be an equivalent of the above for the other order 217 /* (v_from < 3 && v_to > 3) || (v_from > 3 && v_to < 3) ? 1 218 : v_from == 3 || v_to == 3 ? 0 219 : -1;*/ 220 } 221 analyse_position_valueboost::geometry::policies::relate::segments_direction222 static inline void analyse_position_value(int pos_val, 223 int & in_segment_count, 224 int & on_end_count, 225 int & outside_segment_count) 226 { 227 if ( pos_val == 1 || pos_val == 3 ) 228 { 229 on_end_count++; 230 } 231 else if ( pos_val == 2 ) 232 { 233 in_segment_count++; 234 } 235 else 236 { 237 outside_segment_count++; 238 } 239 } 240 241 template <typename Segment1, typename Segment2, typename Ratio> segments_collinearboost::geometry::policies::relate::segments_direction242 static inline return_type segments_collinear( 243 Segment1 const& , Segment2 const& , bool opposite, 244 int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a, 245 Ratio const& /*ra_from_wrt_b*/, Ratio const& /*ra_to_wrt_b*/, 246 Ratio const& /*rb_from_wrt_a*/, Ratio const& /*rb_to_wrt_a*/) 247 { 248 return_type r('c', opposite); 249 250 // IMPORTANT: the order of conditions is different as in intersection_points.hpp 251 // We assign A in 0 and B in 1 252 r.arrival[0] = arrival_from_position_value(a1_wrt_b, a2_wrt_b); 253 r.arrival[1] = arrival_from_position_value(b1_wrt_a, b2_wrt_a); 254 255 // Analyse them 256 int a_in_segment_count = 0; 257 int a_on_end_count = 0; 258 int a_outside_segment_count = 0; 259 int b_in_segment_count = 0; 260 int b_on_end_count = 0; 261 int b_outside_segment_count = 0; 262 analyse_position_value(a1_wrt_b, 263 a_in_segment_count, a_on_end_count, a_outside_segment_count); 264 analyse_position_value(a2_wrt_b, 265 a_in_segment_count, a_on_end_count, a_outside_segment_count); 266 analyse_position_value(b1_wrt_a, 267 b_in_segment_count, b_on_end_count, b_outside_segment_count); 268 analyse_position_value(b2_wrt_a, 269 b_in_segment_count, b_on_end_count, b_outside_segment_count); 270 271 if (a_on_end_count == 1 272 && b_on_end_count == 1 273 && a_outside_segment_count == 1 274 && b_outside_segment_count == 1) 275 { 276 // This is a collinear touch 277 // --------> A (or B) 278 // <---------- B (or A) 279 // We adapt the "how" 280 // TODO: how was to be refactored anyway, 281 if (! opposite) 282 { 283 r.how = 'a'; 284 } 285 else 286 { 287 r.how = r.arrival[0] == 0 ? 't' : 'f'; 288 } 289 } 290 else if (a_on_end_count == 2 291 && b_on_end_count == 2) 292 { 293 r.how = 'e'; 294 } 295 296 return r; 297 } 298 299 template <typename Segment> degenerateboost::geometry::policies::relate::segments_direction300 static inline return_type degenerate(Segment const& , bool) 301 { 302 return return_type('0', false); 303 } 304 305 template <typename Segment, typename Ratio> one_degenerateboost::geometry::policies::relate::segments_direction306 static inline return_type one_degenerate(Segment const& , 307 Ratio const& , 308 bool) 309 { 310 // To be decided 311 return return_type('0', false); 312 } 313 disjointboost::geometry::policies::relate::segments_direction314 static inline return_type disjoint() 315 { 316 return return_type('d', false); 317 } 318 errorboost::geometry::policies::relate::segments_direction319 static inline return_type error(std::string const&) 320 { 321 // Return "E" to denote error 322 // This will throw an error in get_turn_info 323 // TODO: change to enum or similar 324 return return_type('E', false); 325 } 326 327 private : 328 329 template <std::size_t I> calculate_sideboost::geometry::policies::relate::segments_direction330 static inline return_type calculate_side(side_info const& sides, 331 char how, int how_a, int how_b) 332 { 333 int const dir = sides.get<1, I>() == 1 ? 1 : -1; 334 return return_type(sides, how, how_a, how_b, -dir, dir); 335 } 336 337 template <std::size_t I> angleboost::geometry::policies::relate::segments_direction338 static inline return_type angle(side_info const& sides, 339 char how, int how_a, int how_b) 340 { 341 int const dir = sides.get<1, I>() == 1 ? 1 : -1; 342 return return_type(sides, how, how_a, how_b, dir, dir); 343 } 344 345 starts_from_middleboost::geometry::policies::relate::segments_direction346 static inline return_type starts_from_middle(side_info const& sides, 347 char which, 348 int how_a, int how_b) 349 { 350 // Calculate ARROW of b segment w.r.t. s1 351 int dir = sides.get<1, 1>() == 1 ? 1 : -1; 352 353 // From other perspective, then reverse 354 bool const is_a = which == 'A'; 355 if (is_a) 356 { 357 dir = -dir; 358 } 359 360 return return_type(sides, 's', 361 how_a, 362 how_b, 363 is_a ? dir : -dir, 364 ! is_a ? dir : -dir); 365 } 366 367 368 369 // To be harmonized a_ends_at_middleboost::geometry::policies::relate::segments_direction370 static inline return_type a_ends_at_middle(side_info const& sides) 371 { 372 // Ending at the middle, one ARRIVES, the other one is NEUTRAL 373 // (because it both "arrives" and "departs" there) 374 int const dir = sides.get<1, 1>() == 1 ? 1 : -1; 375 return return_type(sides, 'm', 1, 0, dir, dir); 376 } 377 378 b_ends_at_middleboost::geometry::policies::relate::segments_direction379 static inline return_type b_ends_at_middle(side_info const& sides) 380 { 381 int const dir = sides.get<0, 1>() == 1 ? 1 : -1; 382 return return_type(sides, 'm', 0, 1, dir, dir); 383 } 384 385 }; 386 387 }} // namespace policies::relate 388 389 }} // namespace boost::geometry 390 391 #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP 392