// Boost.Geometry (aka GGL, Generic Geometry Library) // Copyright (c) 2007-2011 Barend Gehrels, Amsterdam, the Netherlands. // Use, modification and distribution is subject to the Boost Software License, // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP #include #include #include #include #include #include #include namespace boost { namespace geometry { namespace policies { namespace relate { struct direction_type { inline direction_type(side_info const& s, char h, int ha, int hb, int da = 0, int db = 0, bool op = false) : how(h) , opposite(op) , how_a(ha) , how_b(hb) , dir_a(da) , dir_b(db) , sides(s) { arrival[0] = ha; arrival[1] = hb; } inline direction_type(char h, bool op, int ha = 0, int hb = 0) : how(h) , opposite(op) , how_a(ha) , how_b(hb) , dir_a(0) , dir_b(0) { arrival[0] = ha; arrival[1] = hb; } // "How" is the intersection formed? char how; // Is it opposite (for collinear/equal cases) bool opposite; // Information on how A arrives at intersection, how B arrives at intersection // 1: arrives at intersection // -1: starts from intersection int how_a; int how_b; // Direction: how is A positioned from B // 1: points left, seen from IP // -1: points right, seen from IP // In case of intersection: B's TO direction // In case that B's TO direction is at A: B's from direction // In collinear cases: it is 0 int dir_a; // Direction of A-s TO from IP int dir_b; // Direction of B-s TO from IP // New information side_info sides; int arrival[2]; // 1=arrival, -1departure, 0=neutral; == how_a//how_b // About arrival[0] (== arrival of a2 w.r.t. b) for COLLINEAR cases // Arrival 1: a1--------->a2 (a arrives within b) // b1----->b2 // Arrival 1: (a in b) // // Arrival -1: a1--------->a2 (a does not arrive within b) // b1----->b2 // Arrival -1: (b in a) a_1-------------a_2 // b_1---b_2 // Arrival 0: a1------->a2 (a arrives at TO-border of b) // b1--->b2 }; template struct segments_direction { typedef direction_type return_type; typedef S1 segment_type1; typedef S2 segment_type2; typedef typename select_calculation_type < S1, S2, CalculationType >::type coordinate_type; // Get the same type, but at least a double typedef typename select_most_precise::type rtype; static inline return_type segments_intersect(side_info const& sides, coordinate_type const& dx1, coordinate_type const& dy1, coordinate_type const& dx2, coordinate_type const& dy2, S1 const& s1, S2 const& s2) { bool const ra0 = sides.get<0,0>() == 0; bool const ra1 = sides.get<0,1>() == 0; bool const rb0 = sides.get<1,0>() == 0; bool const rb1 = sides.get<1,1>() == 0; return // opposite and same starting point (FROM) ra0 && rb0 ? calculate_side<1>(sides, dx1, dy1, s1, s2, 'f', -1, -1) // opposite and point to each other (TO) : ra1 && rb1 ? calculate_side<0>(sides, dx1, dy1, s1, s2, 't', 1, 1) // not opposite, forming an angle, first a then b, // directed either both left, or both right // Check side of B2 from A. This is not calculated before : ra1 && rb0 ? angle<1>(sides, dx1, dy1, s1, s2, 'a', 1, -1) // not opposite, forming a angle, first b then a, // directed either both left, or both right : ra0 && rb1 ? angle<0>(sides, dx1, dy1, s1, s2, 'a', -1, 1) // b starts from interior of a : rb0 ? starts_from_middle(sides, dx1, dy1, s1, s2, 'B', 0, -1) // a starts from interior of b (#39) : ra0 ? starts_from_middle(sides, dx1, dy1, s1, s2, 'A', -1, 0) // b ends at interior of a, calculate direction of A from IP : rb1 ? b_ends_at_middle(sides, dx2, dy2, s1, s2) // a ends at interior of b : ra1 ? a_ends_at_middle(sides, dx1, dy1, s1, s2) // normal intersection : calculate_side<1>(sides, dx1, dy1, s1, s2, 'i', -1, -1) ; } static inline return_type collinear_touch( coordinate_type const& , coordinate_type const& , int arrival_a, int arrival_b) { // Though this is 'collinear', we handle it as To/From/Angle because it is the same. // It only does NOT have a direction. side_info sides; //int const arrive = how == 'T' ? 1 : -1; bool opposite = arrival_a == arrival_b; return ! opposite ? return_type(sides, 'a', arrival_a, arrival_b) : return_type(sides, arrival_a == 0 ? 't' : 'f', arrival_a, arrival_b, 0, 0, true); } template static inline return_type collinear_interior_boundary_intersect(S const& , bool, int arrival_a, int arrival_b, bool opposite) { return_type r('c', opposite); r.arrival[0] = arrival_a; r.arrival[1] = arrival_b; return r; } static inline return_type collinear_a_in_b(S1 const& , bool opposite) { return_type r('c', opposite); r.arrival[0] = 1; r.arrival[1] = -1; return r; } static inline return_type collinear_b_in_a(S2 const& , bool opposite) { return_type r('c', opposite); r.arrival[0] = -1; r.arrival[1] = 1; return r; } static inline return_type collinear_overlaps( coordinate_type const& , coordinate_type const& , coordinate_type const& , coordinate_type const& , int arrival_a, int arrival_b, bool opposite) { return_type r('c', opposite); r.arrival[0] = arrival_a; r.arrival[1] = arrival_b; return r; } static inline return_type segment_equal(S1 const& , bool opposite) { return return_type('e', opposite); } static inline return_type degenerate(S1 const& , bool) { return return_type('0', false); } static inline return_type disjoint() { return return_type('d', false); } static inline return_type collinear_disjoint() { return return_type('d', false); } static inline return_type parallel() { return return_type('p', false); } static inline return_type error(std::string const& msg) { // msg return return_type('d', false); } private : template static inline return_type calculate_side(side_info const& sides, coordinate_type const& dx1, coordinate_type const& dy1, S1 const& s1, S2 const& s2, char how, int how_a, int how_b) { coordinate_type dpx = get(s2) - get<0, 0>(s1); coordinate_type dpy = get(s2) - get<0, 1>(s1); // This is a "side calculation" as in the strategies, but here two terms are precalculated // We might merge this with side, offering a pre-calculated term // Waiting for implementing spherical... return dx1 * dpy - dy1 * dpx > 0 ? return_type(sides, how, how_a, how_b, -1, 1) : return_type(sides, how, how_a, how_b, 1, -1); } template static inline return_type angle(side_info const& sides, coordinate_type const& dx1, coordinate_type const& dy1, S1 const& s1, S2 const& s2, char how, int how_a, int how_b) { coordinate_type dpx = get(s2) - get<0, 0>(s1); coordinate_type dpy = get(s2) - get<0, 1>(s1); return dx1 * dpy - dy1 * dpx > 0 ? return_type(sides, how, how_a, how_b, 1, 1) : return_type(sides, how, how_a, how_b, -1, -1); } static inline return_type starts_from_middle(side_info const& sides, coordinate_type const& dx1, coordinate_type const& dy1, S1 const& s1, S2 const& s2, char which, int how_a, int how_b) { // Calculate ARROW of b segment w.r.t. s1 coordinate_type dpx = get<1, 0>(s2) - get<0, 0>(s1); coordinate_type dpy = get<1, 1>(s2) - get<0, 1>(s1); int dir = dx1 * dpy - dy1 * dpx > 0 ? 1 : -1; // From other perspective, then reverse bool const is_a = which == 'A'; if (is_a) { dir = -dir; } return return_type(sides, 's', how_a, how_b, is_a ? dir : -dir, ! is_a ? dir : -dir); } // To be harmonized static inline return_type a_ends_at_middle(side_info const& sides, coordinate_type const& dx, coordinate_type const& dy, S1 const& s1, S2 const& s2) { coordinate_type dpx = get<1, 0>(s2) - get<0, 0>(s1); coordinate_type dpy = get<1, 1>(s2) - get<0, 1>(s1); // Ending at the middle, one ARRIVES, the other one is NEUTRAL // (because it both "arrives" and "departs" there return dx * dpy - dy * dpx > 0 ? return_type(sides, 'm', 1, 0, 1, 1) : return_type(sides, 'm', 1, 0, -1, -1); } static inline return_type b_ends_at_middle(side_info const& sides, coordinate_type const& dx, coordinate_type const& dy, S1 const& s1, S2 const& s2) { coordinate_type dpx = get<1, 0>(s1) - get<0, 0>(s2); coordinate_type dpy = get<1, 1>(s1) - get<0, 1>(s2); return dx * dpy - dy * dpx > 0 ? return_type(sides, 'm', 0, 1, 1, 1) : return_type(sides, 'm', 0, 1, -1, -1); } }; }} // namespace policies::relate }} // namespace boost::geometry #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP