ceph/src/boost/boost/geometry/policies/relate/direction.hpp

   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
  37     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
  53     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     >
 124     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>
 167     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>
 190     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
 209     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
 222     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>
 242     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>
 300     static inline return_type degenerate(Segment const& , bool)
 301     {
 302         return return_type('0', false);
 303     }
 304
 305     template <typename Segment, typename Ratio>
 306     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
 314     static inline return_type disjoint()
 315     {
 316         return return_type('d', false);
 317     }
 318
 319     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>
 330     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>
 338     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
 346     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
 370     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
 379     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