policies/relate/direction.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // Use, modification and distribution is subject to the Boost Software License,
0006 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP
0010 #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP
0011
0012
0013 #include <cstddef>
0014 #include <string>
0015
0016 #include <boost/concept_check.hpp>
0017
0018 #include <boost/geometry/arithmetic/determinant.hpp>
0019 #include <boost/geometry/strategies/side_info.hpp>
0020
0021 #include <boost/geometry/util/math.hpp>
0022 #include <boost/geometry/util/select_calculation_type.hpp>
0023 #include <boost/geometry/util/select_most_precise.hpp>
0024
0025
0026 namespace boost { namespace geometry
0027 {
0028
0029
0030 namespace policies { namespace relate
0031 {
0032
0033 struct direction_type
0034 {
0035     // NOTE: "char" will be replaced by enum in future version
0036
0037     inline direction_type(side_info const& s, char h,
0038                 int ha, int hb,
0039                 int da = 0, int db = 0,
0040                 bool op = false)
0041         : how(h)
0042         , opposite(op)
0043         , how_a(ha)
0044         , how_b(hb)
0045         , dir_a(da)
0046         , dir_b(db)
0047         , sides(s)
0048     {
0049         arrival[0] = ha;
0050         arrival[1] = hb;
0051     }
0052
0053     inline direction_type(char h, bool op, int ha = 0, int hb = 0)
0054         : how(h)
0055         , opposite(op)
0056         , how_a(ha)
0057         , how_b(hb)
0058         , dir_a(0)
0059         , dir_b(0)
0060     {
0061         arrival[0] = ha;
0062         arrival[1] = hb;
0063     }
0064
0065
0066     // TODO: replace this
0067     // NOTE: "char" will be replaced by enum in future version
0068     // "How" is the intersection formed?
0069     char how;
0070
0071     // Is it opposite (for collinear/equal cases)
0072     bool opposite;
0073
0074     // Information on how A arrives at intersection, how B arrives at intersection
0075     // 1: arrives at intersection
0076     // -1: starts from intersection
0077     int how_a;
0078     int how_b;
0079
0080     // Direction: how is A positioned from B
0081     // 1: points left, seen from IP
0082     // -1: points right, seen from IP
0083     // In case of intersection: B's TO direction
0084     // In case that B's TO direction is at A: B's from direction
0085     // In collinear cases: it is 0
0086     int dir_a; // Direction of A-s TO from IP
0087     int dir_b; // Direction of B-s TO from IP
0088
0089     // New information
0090     side_info sides;
0091     // THIS IS EQUAL TO arrival_a, arrival_b - they probably can go now we have robust fractions
0092     int arrival[2]; // 1=arrival, -1=departure, 0=neutral; == how_a//how_b
0093
0094
0095     // About arrival[0] (== arrival of a2 w.r.t. b) for COLLINEAR cases
0096     // Arrival  1: a1--------->a2         (a arrives within b)
0097     //                      b1----->b2
0098
0099     // Arrival  1: (a in b)
0100     //
0101
0102
0103     // Arrival -1:      a1--------->a2     (a does not arrive within b)
0104     //             b1----->b2
0105
0106     // Arrival -1: (b in a)               a_1-------------a_2
0107     //                                         b_1---b_2
0108
0109     // Arrival  0:                        a1------->a2  (a arrives at TO-border of b)
0110     //                                        b1--->b2
0111
0112 };
0113
0114 struct segments_direction
0115 {
0116     typedef direction_type return_type;
0117
0118     template
0119     <
0120         typename Segment1,
0121         typename Segment2,
0122         typename SegmentIntersectionInfo
0123     >
0124     static inline return_type segments_crosses(side_info const& sides,
0125                     SegmentIntersectionInfo const& ,
0126                     Segment1 const& , Segment2 const& )
0127     {
0128         bool const ra0 = sides.get<0,0>() == 0;
0129         bool const ra1 = sides.get<0,1>() == 0;
0130         bool const rb0 = sides.get<1,0>() == 0;
0131         bool const rb1 = sides.get<1,1>() == 0;
0132
0133         return
0134             // opposite and same starting point (FROM)
0135             ra0 && rb0 ? calculate_side<1>(sides, 'f', -1, -1)
0136
0137             // opposite and point to each other (TO)
0138             : ra1 && rb1 ? calculate_side<0>(sides, 't', 1, 1)
0139
0140             // not opposite, forming an angle, first a then b,
0141             // directed either both left, or both right
0142             // Check side of B2 from A. This is not calculated before
0143             : ra1 && rb0 ? angle<1>(sides, 'a', 1, -1)
0144
0145             // not opposite, forming a angle, first b then a,
0146             // directed either both left, or both right
0147             : ra0 && rb1 ? angle<0>(sides, 'a', -1, 1)
0148
0149             // b starts from interior of a
0150             : rb0 ? starts_from_middle(sides, 'B', 0, -1)
0151
0152             // a starts from interior of b (#39)
0153             : ra0 ? starts_from_middle(sides, 'A', -1, 0)
0154
0155             // b ends at interior of a, calculate direction of A from IP
0156             : rb1 ? b_ends_at_middle(sides)
0157
0158             // a ends at interior of b
0159             : ra1 ? a_ends_at_middle(sides)
0160
0161             // normal intersection
0162             : calculate_side<1>(sides, 'i', -1, -1)
0163             ;
0164     }
0165
0166     template <typename SegmentIntersectionInfo, typename Point>
0167     static inline return_type segments_share_common_point(side_info const& sides,
0168                                                           SegmentIntersectionInfo const& ,
0169                                                           Point const&)
0170     {
0171         return segments_crosses(sides, sides, sides, sides);
0172     }
0173
0174     template <typename Ratio>
0175     static inline int arrival_value(Ratio const& r_from, Ratio const& r_to)
0176     {
0177         //     a1--------->a2
0178         // b1----->b2
0179         // a departs: -1
0180
0181         // a1--------->a2
0182         //         b1----->b2
0183         // a arrives: 1
0184
0185         // a1--------->a2
0186         //     b1----->b2
0187         // both arrive there -> r-to = 1/1, or 0/1 (on_segment)
0188
0189         // First check the TO (for arrival), then FROM (for departure)
0190         return r_to.in_segment() ? 1
0191             : r_to.on_segment() ? 0
0192             : r_from.on_segment() ? -1
0193             : -1
0194             ;
0195     }
0196
0197     template <typename Ratio>
0198     static inline void analyze(Ratio const& r,
0199         int& in_segment_count,
0200         int& on_end_count,
0201         int& outside_segment_count)
0202     {
0203         if (r.on_end())
0204         {
0205             on_end_count++;
0206         }
0207         else if (r.in_segment())
0208         {
0209             in_segment_count++;
0210         }
0211         else
0212         {
0213             outside_segment_count++;
0214         }
0215     }
0216
0217     static inline int arrival_from_position_value(int /*v_from*/, int v_to)
0218     {
0219         return v_to == 2 ? 1
0220              : v_to == 1 || v_to == 3 ? 0
0221              //: v_from >= 1 && v_from <= 3 ? -1
0222              : -1;
0223
0224         // NOTE: this should be an equivalent of the above for the other order
0225         /* (v_from < 3 && v_to > 3) || (v_from > 3 && v_to < 3) ? 1
0226          : v_from == 3 || v_to == 3 ? 0
0227          : -1;*/
0228     }
0229
0230     static inline void analyse_position_value(int pos_val,
0231                                               int & in_segment_count,
0232                                               int & on_end_count,
0233                                               int & outside_segment_count)
0234     {
0235         if ( pos_val == 1 || pos_val == 3 )
0236         {
0237             on_end_count++;
0238         }
0239         else if ( pos_val == 2 )
0240         {
0241             in_segment_count++;
0242         }
0243         else
0244         {
0245             outside_segment_count++;
0246         }
0247     }
0248
0249     template <typename Segment1, typename Segment2, typename Ratio>
0250     static inline return_type segments_collinear(
0251         Segment1 const& , Segment2 const& , bool opposite,
0252         int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a,
0253         Ratio const& /*ra_from_wrt_b*/, Ratio const& /*ra_to_wrt_b*/,
0254         Ratio const& /*rb_from_wrt_a*/, Ratio const& /*rb_to_wrt_a*/)
0255     {
0256         return_type r('c', opposite);
0257
0258         // IMPORTANT: the order of conditions is different as in intersection_points.hpp
0259         // We assign A in 0 and B in 1
0260         r.arrival[0] = arrival_from_position_value(a1_wrt_b, a2_wrt_b);
0261         r.arrival[1] = arrival_from_position_value(b1_wrt_a, b2_wrt_a);
0262
0263         // Analyse them
0264         int a_in_segment_count = 0;
0265         int a_on_end_count = 0;
0266         int a_outside_segment_count = 0;
0267         int b_in_segment_count = 0;
0268         int b_on_end_count = 0;
0269         int b_outside_segment_count = 0;
0270         analyse_position_value(a1_wrt_b,
0271             a_in_segment_count, a_on_end_count, a_outside_segment_count);
0272         analyse_position_value(a2_wrt_b,
0273             a_in_segment_count, a_on_end_count, a_outside_segment_count);
0274         analyse_position_value(b1_wrt_a,
0275             b_in_segment_count, b_on_end_count, b_outside_segment_count);
0276         analyse_position_value(b2_wrt_a,
0277             b_in_segment_count, b_on_end_count, b_outside_segment_count);
0278
0279         if (a_on_end_count == 1
0280             && b_on_end_count == 1
0281             && a_outside_segment_count == 1
0282             && b_outside_segment_count == 1)
0283         {
0284             // This is a collinear touch
0285             // -------->             A (or B)
0286             //         <----------   B (or A)
0287             // We adapt the "how"
0288             // TODO: how was to be refactored anyway,
0289             if (! opposite)
0290             {
0291                 r.how = 'a';
0292             }
0293             else
0294             {
0295                 r.how = r.arrival[0] == 0 ? 't' : 'f';
0296             }
0297         }
0298         else if (a_on_end_count == 2
0299                  && b_on_end_count == 2)
0300         {
0301             r.how = 'e';
0302         }
0303
0304         return r;
0305     }
0306
0307     template <typename Segment>
0308     static inline return_type degenerate(Segment const& , bool)
0309     {
0310         return return_type('0', false);
0311     }
0312
0313     template <typename Segment, typename Ratio>
0314     static inline return_type one_degenerate(Segment const& ,
0315             Ratio const& ,
0316             bool)
0317     {
0318         // To be decided
0319         return return_type('0', false);
0320     }
0321
0322     static inline return_type disjoint()
0323     {
0324         return return_type('d', false);
0325     }
0326
0327     static inline return_type error(std::string const&)
0328     {
0329         // Return "E" to denote error
0330         // This will throw an error in get_turn_info
0331         // TODO: change to enum or similar
0332         return return_type('E', false);
0333     }
0334
0335 private :
0336
0337     template <std::size_t I>
0338     static inline return_type calculate_side(side_info const& sides,
0339                 char how, int how_a, int how_b)
0340     {
0341         int const dir = sides.get<1, I>() == 1 ? 1 : -1;
0342         return return_type(sides, how, how_a, how_b, -dir, dir);
0343     }
0344
0345     template <std::size_t I>
0346     static inline return_type angle(side_info const& sides,
0347                 char how, int how_a, int how_b)
0348     {
0349         int const dir = sides.get<1, I>() == 1 ? 1 : -1;
0350         return return_type(sides, how, how_a, how_b, dir, dir);
0351     }
0352
0353
0354     static inline return_type starts_from_middle(side_info const& sides,
0355                 char which,
0356                 int how_a, int how_b)
0357     {
0358         // Calculate ARROW of b segment w.r.t. s1
0359         int dir = sides.get<1, 1>() == 1 ? 1 : -1;
0360
0361         // From other perspective, then reverse
0362         bool const is_a = which == 'A';
0363         if (is_a)
0364         {
0365             dir = -dir;
0366         }
0367
0368         return return_type(sides, 's',
0369             how_a,
0370             how_b,
0371             is_a ? dir : -dir,
0372             ! is_a ? dir : -dir);
0373     }
0374
0375
0376
0377     // To be harmonized
0378     static inline return_type a_ends_at_middle(side_info const& sides)
0379     {
0380         // Ending at the middle, one ARRIVES, the other one is NEUTRAL
0381         // (because it both "arrives"  and "departs" there)
0382         int const dir = sides.get<1, 1>() == 1 ? 1 : -1;
0383         return return_type(sides, 'm', 1, 0, dir, dir);
0384     }
0385
0386
0387     static inline return_type b_ends_at_middle(side_info const& sides)
0388     {
0389         int const dir = sides.get<0, 1>() == 1 ? 1 : -1;
0390         return return_type(sides, 'm', 0, 1, dir, dir);
0391     }
0392
0393 };
0394
0395 }} // namespace policies::relate
0396
0397 }} // namespace boost::geometry
0398
0399 #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP