path: root/boost/geometry/policies/relate/direction.hpp

// Boost.Geometry (aka GGL, Generic Geometry Library)

// Copyright (c) 2007-2012 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 <cstddef>
#include <string>

#include <boost/concept_check.hpp>

#include <boost/geometry/arithmetic/determinant.hpp>
#include <boost/geometry/strategies/side_info.hpp>

#include <boost/geometry/util/math.hpp>
#include <boost/geometry/util/select_calculation_type.hpp>
#include <boost/geometry/util/select_most_precise.hpp>


namespace boost { namespace geometry
{


namespace policies { namespace relate
{

struct direction_type
{
    // NOTE: "char" will be replaced by enum in future version

    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;
    }


    // TODO: replace this
    // NOTE: "char" will be replaced by enum in future version
    // "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 <typename S1, typename S2, typename CalculationType = void>
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<coordinate_type, double>::type rtype;


	template <typename R>
    static inline return_type segments_intersect(side_info const& sides,
					R const&,
                    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 <typename S>
    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 error(std::string const&)
    {
        // Return "E" to denote error
        // This will throw an error in get_turn_info
        // TODO: change to enum or similar
        return return_type('E', false);
    }

private :

    static inline bool is_left
        (
            coordinate_type const& ux, 
            coordinate_type const& uy,
            coordinate_type const& vx,
            coordinate_type const& vy
        )
    {
        // This is a "side calculation" as in the strategies, but here terms are precalculated
        // We might merge this with side, offering a pre-calculated term (in fact already done using cross-product)
        // Waiting for implementing spherical...

        rtype const zero = rtype();
        return geometry::detail::determinant<rtype>(ux, uy, vx, vy) > zero;
    }

    template <std::size_t I>
    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<I, 0>(s2) - get<0, 0>(s1);
        coordinate_type dpy = get<I, 1>(s2) - get<0, 1>(s1);

        return is_left(dx1, dy1, dpx, dpy)
            ? return_type(sides, how, how_a, how_b, -1, 1)
            : return_type(sides, how, how_a, how_b, 1, -1);
    }

    template <std::size_t I>
    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<I, 0>(s2) - get<0, 0>(s1);
        coordinate_type dpy = get<I, 1>(s2) - get<0, 1>(s1);

        return is_left(dx1, dy1, dpx, dpy)
            ? 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 = is_left(dx1, dy1, dpx, dpy) ? 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 is_left(dx, dy, dpx, dpy)
            ? 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 is_left(dx, dy, dpx, dpy)
            ? 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