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;
    // THIS IS EQUAL TO arrival_a, arrival_b - they probably can go now we have robust fractions
    int arrival[2]; // 1=arrival, -1=departure, 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

};

struct segments_direction
{
    typedef direction_type return_type;

    template
    <
        typename Segment1,
        typename Segment2,
        typename SegmentIntersectionInfo
    >
    static inline return_type segments_crosses(side_info const& sides,
                    SegmentIntersectionInfo const& ,
                    Segment1 const& , Segment2 const& )
    {
        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, 'f', -1, -1)

            // opposite and point to each other (TO)
            : ra1 && rb1 ? calculate_side<0>(sides, '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, 'a', 1, -1)

            // not opposite, forming a angle, first b then a,
            // directed either both left, or both right
            : ra0 && rb1 ? angle<0>(sides, 'a', -1, 1)

            // b starts from interior of a
            : rb0 ? starts_from_middle(sides, 'B', 0, -1)

            // a starts from interior of b (#39)
            : ra0 ? starts_from_middle(sides, 'A', -1, 0)

            // b ends at interior of a, calculate direction of A from IP
            : rb1 ? b_ends_at_middle(sides)

            // a ends at interior of b
            : ra1 ? a_ends_at_middle(sides)

            // normal intersection
            : calculate_side<1>(sides, 'i', -1, -1)
            ;
    }

    template <typename Ratio>
    static inline int arrival_value(Ratio const& r_from, Ratio const& r_to)
    {
        //     a1--------->a2
        // b1----->b2
        // a departs: -1

        // a1--------->a2
        //         b1----->b2
        // a arrives: 1

        // a1--------->a2
        //     b1----->b2
        // both arrive there -> r-to = 1/1, or 0/1 (on_segment)

        // First check the TO (for arrival), then FROM (for departure)
        return r_to.in_segment() ? 1
            : r_to.on_segment() ? 0
            : r_from.on_segment() ? -1
            : -1
            ;
    }

    template <typename Ratio>
    static inline void analyze(Ratio const& r,
        int& in_segment_count,
        int& on_end_count,
        int& outside_segment_count)
    {
        if (r.on_end())
        {
            on_end_count++;
        }
        else if (r.in_segment())
        {
            in_segment_count++;
        }
        else
        {
            outside_segment_count++;
        }
    }

    static inline int arrival_from_position_value(int /*v_from*/, int v_to)
    {
        return v_to == 2 ? 1
             : v_to == 1 || v_to == 3 ? 0
             //: v_from >= 1 && v_from <= 3 ? -1
             : -1;

        // NOTE: this should be an equivalent of the above for the other order
        /* (v_from < 3 && v_to > 3) || (v_from > 3 && v_to < 3) ? 1
         : v_from == 3 || v_to == 3 ? 0
         : -1;*/
    }

    static inline void analyse_position_value(int pos_val,
                                              int & in_segment_count,
                                              int & on_end_count,
                                              int & outside_segment_count)
    {
        if ( pos_val == 1 || pos_val == 3 )
        {
            on_end_count++;
        }
        else if ( pos_val == 2 )
        {
            in_segment_count++;
        }
        else
        {
            outside_segment_count++;
        }
    }

    template <typename Segment1, typename Segment2, typename Ratio>
    static inline return_type segments_collinear(
        Segment1 const& , Segment2 const& , bool opposite,
        int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a,
        Ratio const& /*ra_from_wrt_b*/, Ratio const& /*ra_to_wrt_b*/,
        Ratio const& /*rb_from_wrt_a*/, Ratio const& /*rb_to_wrt_a*/)
    {
        return_type r('c', opposite);

        // IMPORTANT: the order of conditions is different as in intersection_points.hpp
        // We assign A in 0 and B in 1
        r.arrival[0] = arrival_from_position_value(a1_wrt_b, a2_wrt_b);
        r.arrival[1] = arrival_from_position_value(b1_wrt_a, b2_wrt_a);

        // Analyse them
        int a_in_segment_count = 0;
        int a_on_end_count = 0;
        int a_outside_segment_count = 0;
        int b_in_segment_count = 0;
        int b_on_end_count = 0;
        int b_outside_segment_count = 0;
        analyse_position_value(a1_wrt_b,
            a_in_segment_count, a_on_end_count, a_outside_segment_count);
        analyse_position_value(a2_wrt_b,
            a_in_segment_count, a_on_end_count, a_outside_segment_count);
        analyse_position_value(b1_wrt_a,
            b_in_segment_count, b_on_end_count, b_outside_segment_count);
        analyse_position_value(b2_wrt_a,
            b_in_segment_count, b_on_end_count, b_outside_segment_count);

        if (a_on_end_count == 1
            && b_on_end_count == 1
            && a_outside_segment_count == 1
            && b_outside_segment_count == 1)
        {
            // This is a collinear touch
            // -------->             A (or B)
            //         <----------   B (or A)
            // We adapt the "how"
            // TODO: how was to be refactored anyway,
            if (! opposite)
            {
                r.how = 'a';
            }
            else
            {
                r.how = r.arrival[0] == 0 ? 't' : 'f';
            }
        }
        else if (a_on_end_count == 2
                 && b_on_end_count == 2)
        {
            r.how = 'e';
        }

        return r;
    }

    template <typename Segment>
    static inline return_type degenerate(Segment const& , bool)
    {
        return return_type('0', false);
    }

    template <typename Segment, typename Ratio>
    static inline return_type one_degenerate(Segment const& ,
            Ratio const& ,
            bool)
    {
        // To be decided
        return return_type('0', false);
    }

    static inline return_type 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 :

    template <std::size_t I>
    static inline return_type calculate_side(side_info const& sides,
                char how, int how_a, int how_b)
    {
        int const dir = sides.get<1, I>() == 1 ? 1 : -1;
        return return_type(sides, how, how_a, how_b, -dir, dir);
    }

    template <std::size_t I>
    static inline return_type angle(side_info const& sides,
                char how, int how_a, int how_b)
    {
        int const dir = sides.get<1, I>() == 1 ? 1 : -1;
        return return_type(sides, how, how_a, how_b, dir, dir);
    }


    static inline return_type starts_from_middle(side_info const& sides,
                char which,
                int how_a, int how_b)
    {
        // Calculate ARROW of b segment w.r.t. s1
        int dir = sides.get<1, 1>() == 1 ? 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)
    {
        // Ending at the middle, one ARRIVES, the other one is NEUTRAL
        // (because it both "arrives"  and "departs" there)
        int const dir = sides.get<1, 1>() == 1 ? 1 : -1;
        return return_type(sides, 'm', 1, 0, dir, dir);
    }


    static inline return_type b_ends_at_middle(side_info const& sides)
    {
        int const dir = sides.get<0, 1>() == 1 ? 1 : -1;
        return return_type(sides, 'm', 0, 1, dir, dir);
    }

};

}} // namespace policies::relate

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_DIRECTION_HPP