Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP
Chris@16: #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP
Chris@16: 
Chris@16: 
Chris@16: #include <cstddef>
Chris@16: #include <string>
Chris@16: 
Chris@16: #include <boost/concept_check.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/arithmetic/determinant.hpp>
Chris@16: #include <boost/geometry/strategies/side_info.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/util/math.hpp>
Chris@16: #include <boost/geometry/util/select_calculation_type.hpp>
Chris@16: #include <boost/geometry/util/select_most_precise.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: namespace policies { namespace relate
Chris@16: {
Chris@16: 
Chris@16: struct direction_type
Chris@16: {
Chris@16:     // NOTE: "char" will be replaced by enum in future version
Chris@16: 
Chris@16:     inline direction_type(side_info const& s, char h,
Chris@16:                 int ha, int hb,
Chris@16:                 int da = 0, int db = 0,
Chris@16:                 bool op = false)
Chris@16:         : how(h)
Chris@16:         , opposite(op)
Chris@16:         , how_a(ha)
Chris@16:         , how_b(hb)
Chris@16:         , dir_a(da)
Chris@16:         , dir_b(db)
Chris@16:         , sides(s)
Chris@16:     {
Chris@16:         arrival[0] = ha;
Chris@16:         arrival[1] = hb;
Chris@16:     }
Chris@16: 
Chris@16:     inline direction_type(char h, bool op, int ha = 0, int hb = 0)
Chris@16:         : how(h)
Chris@16:         , opposite(op)
Chris@16:         , how_a(ha)
Chris@16:         , how_b(hb)
Chris@16:         , dir_a(0)
Chris@16:         , dir_b(0)
Chris@16:     {
Chris@16:         arrival[0] = ha;
Chris@16:         arrival[1] = hb;
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     // TODO: replace this
Chris@16:     // NOTE: "char" will be replaced by enum in future version
Chris@16:     // "How" is the intersection formed?
Chris@16:     char how;
Chris@16: 
Chris@16:     // Is it opposite (for collinear/equal cases)
Chris@16:     bool opposite;
Chris@16: 
Chris@16:     // Information on how A arrives at intersection, how B arrives at intersection
Chris@16:     // 1: arrives at intersection
Chris@16:     // -1: starts from intersection
Chris@16:     int how_a;
Chris@16:     int how_b;
Chris@16: 
Chris@16:     // Direction: how is A positioned from B
Chris@16:     // 1: points left, seen from IP
Chris@16:     // -1: points right, seen from IP
Chris@16:     // In case of intersection: B's TO direction
Chris@16:     // In case that B's TO direction is at A: B's from direction
Chris@16:     // In collinear cases: it is 0
Chris@16:     int dir_a; // Direction of A-s TO from IP
Chris@16:     int dir_b; // Direction of B-s TO from IP
Chris@16: 
Chris@16:     // New information
Chris@16:     side_info sides;
Chris@101:     // THIS IS EQUAL TO arrival_a, arrival_b - they probably can go now we have robust fractions
Chris@101:     int arrival[2]; // 1=arrival, -1=departure, 0=neutral; == how_a//how_b
Chris@16: 
Chris@16: 
Chris@16:     // About arrival[0] (== arrival of a2 w.r.t. b) for COLLINEAR cases
Chris@16:     // Arrival  1: a1--------->a2         (a arrives within b)
Chris@16:     //                      b1----->b2
Chris@16: 
Chris@16:     // Arrival  1: (a in b)
Chris@16:     //
Chris@16: 
Chris@16: 
Chris@16:     // Arrival -1:      a1--------->a2     (a does not arrive within b)
Chris@16:     //             b1----->b2
Chris@16: 
Chris@16:     // Arrival -1: (b in a)               a_1-------------a_2
Chris@16:     //                                         b_1---b_2
Chris@16: 
Chris@16:     // Arrival  0:                        a1------->a2  (a arrives at TO-border of b)
Chris@16:     //                                        b1--->b2
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: struct segments_direction
Chris@16: {
Chris@16:     typedef direction_type return_type;
Chris@16: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename Segment1,
Chris@101:         typename Segment2,
Chris@101:         typename SegmentIntersectionInfo
Chris@101:     >
Chris@101:     static inline return_type segments_crosses(side_info const& sides,
Chris@101:                     SegmentIntersectionInfo const& ,
Chris@101:                     Segment1 const& , Segment2 const& )
Chris@16:     {
Chris@16:         bool const ra0 = sides.get<0,0>() == 0;
Chris@16:         bool const ra1 = sides.get<0,1>() == 0;
Chris@16:         bool const rb0 = sides.get<1,0>() == 0;
Chris@16:         bool const rb1 = sides.get<1,1>() == 0;
Chris@16: 
Chris@16:         return
Chris@16:             // opposite and same starting point (FROM)
Chris@101:             ra0 && rb0 ? calculate_side<1>(sides, 'f', -1, -1)
Chris@16: 
Chris@16:             // opposite and point to each other (TO)
Chris@101:             : ra1 && rb1 ? calculate_side<0>(sides, 't', 1, 1)
Chris@16: 
Chris@16:             // not opposite, forming an angle, first a then b,
Chris@16:             // directed either both left, or both right
Chris@16:             // Check side of B2 from A. This is not calculated before
Chris@101:             : ra1 && rb0 ? angle<1>(sides, 'a', 1, -1)
Chris@16: 
Chris@16:             // not opposite, forming a angle, first b then a,
Chris@16:             // directed either both left, or both right
Chris@101:             : ra0 && rb1 ? angle<0>(sides, 'a', -1, 1)
Chris@16: 
Chris@16:             // b starts from interior of a
Chris@101:             : rb0 ? starts_from_middle(sides, 'B', 0, -1)
Chris@16: 
Chris@16:             // a starts from interior of b (#39)
Chris@101:             : ra0 ? starts_from_middle(sides, 'A', -1, 0)
Chris@16: 
Chris@16:             // b ends at interior of a, calculate direction of A from IP
Chris@101:             : rb1 ? b_ends_at_middle(sides)
Chris@16: 
Chris@16:             // a ends at interior of b
Chris@101:             : ra1 ? a_ends_at_middle(sides)
Chris@16: 
Chris@16:             // normal intersection
Chris@101:             : calculate_side<1>(sides, 'i', -1, -1)
Chris@16:             ;
Chris@16:     }
Chris@16: 
Chris@101:     template <typename Ratio>
Chris@101:     static inline int arrival_value(Ratio const& r_from, Ratio const& r_to)
Chris@16:     {
Chris@101:         //     a1--------->a2
Chris@101:         // b1----->b2
Chris@101:         // a departs: -1
Chris@101: 
Chris@101:         // a1--------->a2
Chris@101:         //         b1----->b2
Chris@101:         // a arrives: 1
Chris@101: 
Chris@101:         // a1--------->a2
Chris@101:         //     b1----->b2
Chris@101:         // both arrive there -> r-to = 1/1, or 0/1 (on_segment)
Chris@101: 
Chris@101:         // First check the TO (for arrival), then FROM (for departure)
Chris@101:         return r_to.in_segment() ? 1
Chris@101:             : r_to.on_segment() ? 0
Chris@101:             : r_from.on_segment() ? -1
Chris@101:             : -1
Chris@101:             ;
Chris@16:     }
Chris@16: 
Chris@101:     template <typename Ratio>
Chris@101:     static inline void analyze(Ratio const& r,
Chris@101:         int& in_segment_count,
Chris@101:         int& on_end_count,
Chris@101:         int& outside_segment_count)
Chris@101:     {
Chris@101:         if (r.on_end())
Chris@101:         {
Chris@101:             on_end_count++;
Chris@101:         }
Chris@101:         else if (r.in_segment())
Chris@101:         {
Chris@101:             in_segment_count++;
Chris@101:         }
Chris@101:         else
Chris@101:         {
Chris@101:             outside_segment_count++;
Chris@101:         }
Chris@101:     }
Chris@101: 
Chris@101:     static inline int arrival_from_position_value(int /*v_from*/, int v_to)
Chris@101:     {
Chris@101:         return v_to == 2 ? 1
Chris@101:              : v_to == 1 || v_to == 3 ? 0
Chris@101:              //: v_from >= 1 && v_from <= 3 ? -1
Chris@101:              : -1;
Chris@101: 
Chris@101:         // NOTE: this should be an equivalent of the above for the other order
Chris@101:         /* (v_from < 3 && v_to > 3) || (v_from > 3 && v_to < 3) ? 1
Chris@101:          : v_from == 3 || v_to == 3 ? 0
Chris@101:          : -1;*/
Chris@101:     }
Chris@101: 
Chris@101:     static inline void analyse_position_value(int pos_val,
Chris@101:                                               int & in_segment_count,
Chris@101:                                               int & on_end_count,
Chris@101:                                               int & outside_segment_count)
Chris@101:     {
Chris@101:         if ( pos_val == 1 || pos_val == 3 )
Chris@101:         {
Chris@101:             on_end_count++;
Chris@101:         }
Chris@101:         else if ( pos_val == 2 )
Chris@101:         {
Chris@101:             in_segment_count++;
Chris@101:         }
Chris@101:         else
Chris@101:         {
Chris@101:             outside_segment_count++;
Chris@101:         }
Chris@101:     }
Chris@101: 
Chris@101:     template <typename Segment1, typename Segment2, typename Ratio>
Chris@101:     static inline return_type segments_collinear(
Chris@101:         Segment1 const& , Segment2 const& , bool opposite,
Chris@101:         int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a,
Chris@101:         Ratio const& /*ra_from_wrt_b*/, Ratio const& /*ra_to_wrt_b*/,
Chris@101:         Ratio const& /*rb_from_wrt_a*/, Ratio const& /*rb_to_wrt_a*/)
Chris@16:     {
Chris@16:         return_type r('c', opposite);
Chris@101: 
Chris@101:         // IMPORTANT: the order of conditions is different as in intersection_points.hpp
Chris@101:         // We assign A in 0 and B in 1
Chris@101:         r.arrival[0] = arrival_from_position_value(a1_wrt_b, a2_wrt_b);
Chris@101:         r.arrival[1] = arrival_from_position_value(b1_wrt_a, b2_wrt_a);
Chris@101: 
Chris@101:         // Analyse them
Chris@101:         int a_in_segment_count = 0;
Chris@101:         int a_on_end_count = 0;
Chris@101:         int a_outside_segment_count = 0;
Chris@101:         int b_in_segment_count = 0;
Chris@101:         int b_on_end_count = 0;
Chris@101:         int b_outside_segment_count = 0;
Chris@101:         analyse_position_value(a1_wrt_b,
Chris@101:             a_in_segment_count, a_on_end_count, a_outside_segment_count);
Chris@101:         analyse_position_value(a2_wrt_b,
Chris@101:             a_in_segment_count, a_on_end_count, a_outside_segment_count);
Chris@101:         analyse_position_value(b1_wrt_a,
Chris@101:             b_in_segment_count, b_on_end_count, b_outside_segment_count);
Chris@101:         analyse_position_value(b2_wrt_a,
Chris@101:             b_in_segment_count, b_on_end_count, b_outside_segment_count);
Chris@101: 
Chris@101:         if (a_on_end_count == 1
Chris@101:             && b_on_end_count == 1
Chris@101:             && a_outside_segment_count == 1
Chris@101:             && b_outside_segment_count == 1)
Chris@101:         {
Chris@101:             // This is a collinear touch
Chris@101:             // -------->             A (or B)
Chris@101:             //         <----------   B (or A)
Chris@101:             // We adapt the "how"
Chris@101:             // TODO: how was to be refactored anyway,
Chris@101:             if (! opposite)
Chris@101:             {
Chris@101:                 r.how = 'a';
Chris@101:             }
Chris@101:             else
Chris@101:             {
Chris@101:                 r.how = r.arrival[0] == 0 ? 't' : 'f';
Chris@101:             }
Chris@101:         }
Chris@101:         else if (a_on_end_count == 2
Chris@101:                  && b_on_end_count == 2)
Chris@101:         {
Chris@101:             r.how = 'e';
Chris@101:         }
Chris@101: 
Chris@16:         return r;
Chris@16:     }
Chris@16: 
Chris@101:     template <typename Segment>
Chris@101:     static inline return_type degenerate(Segment const& , bool)
Chris@16:     {
Chris@16:         return return_type('0', false);
Chris@16:     }
Chris@16: 
Chris@101:     template <typename Segment, typename Ratio>
Chris@101:     static inline return_type one_degenerate(Segment const& ,
Chris@101:             Ratio const& ,
Chris@101:             bool)
Chris@16:     {
Chris@101:         // To be decided
Chris@101:         return return_type('0', false);
Chris@16:     }
Chris@16: 
Chris@101:     static inline return_type disjoint()
Chris@16:     {
Chris@16:         return return_type('d', false);
Chris@16:     }
Chris@16: 
Chris@16:     static inline return_type error(std::string const&)
Chris@16:     {
Chris@16:         // Return "E" to denote error
Chris@16:         // This will throw an error in get_turn_info
Chris@16:         // TODO: change to enum or similar
Chris@16:         return return_type('E', false);
Chris@16:     }
Chris@16: 
Chris@16: private :
Chris@16: 
Chris@16:     template <std::size_t I>
Chris@16:     static inline return_type calculate_side(side_info const& sides,
Chris@16:                 char how, int how_a, int how_b)
Chris@16:     {
Chris@101:         int const dir = sides.get<1, I>() == 1 ? 1 : -1;
Chris@101:         return return_type(sides, how, how_a, how_b, -dir, dir);
Chris@16:     }
Chris@16: 
Chris@16:     template <std::size_t I>
Chris@16:     static inline return_type angle(side_info const& sides,
Chris@16:                 char how, int how_a, int how_b)
Chris@16:     {
Chris@101:         int const dir = sides.get<1, I>() == 1 ? 1 : -1;
Chris@101:         return return_type(sides, how, how_a, how_b, dir, dir);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     static inline return_type starts_from_middle(side_info const& sides,
Chris@16:                 char which,
Chris@16:                 int how_a, int how_b)
Chris@16:     {
Chris@16:         // Calculate ARROW of b segment w.r.t. s1
Chris@101:         int dir = sides.get<1, 1>() == 1 ? 1 : -1;
Chris@16: 
Chris@16:         // From other perspective, then reverse
Chris@16:         bool const is_a = which == 'A';
Chris@16:         if (is_a)
Chris@16:         {
Chris@16:             dir = -dir;
Chris@16:         }
Chris@16: 
Chris@16:         return return_type(sides, 's',
Chris@16:             how_a,
Chris@16:             how_b,
Chris@16:             is_a ? dir : -dir,
Chris@16:             ! is_a ? dir : -dir);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16:     // To be harmonized
Chris@101:     static inline return_type a_ends_at_middle(side_info const& sides)
Chris@16:     {
Chris@16:         // Ending at the middle, one ARRIVES, the other one is NEUTRAL
Chris@101:         // (because it both "arrives"  and "departs" there)
Chris@101:         int const dir = sides.get<1, 1>() == 1 ? 1 : -1;
Chris@101:         return return_type(sides, 'm', 1, 0, dir, dir);
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@101:     static inline return_type b_ends_at_middle(side_info const& sides)
Chris@16:     {
Chris@101:         int const dir = sides.get<0, 1>() == 1 ? 1 : -1;
Chris@101:         return return_type(sides, 'm', 0, 1, dir, dir);
Chris@16:     }
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: }} // namespace policies::relate
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP