[ceph.git] / ceph / src / boost / boost / geometry / algorithms / detail / overlay / get_turn_info_for_endpoint.hpp

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

// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.

// This file was modified by Oracle on 2013, 2014, 2017, 2018.
// Modifications copyright (c) 2013-2018 Oracle and/or its affiliates.

// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle

// 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_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_FOR_ENDPOINT_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_FOR_ENDPOINT_HPP

#include <boost/core/ignore_unused.hpp>

#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/policies/robustness/no_rescale_policy.hpp>

namespace boost { namespace geometry {

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay {

// SEGMENT_INTERSECTION RESULT

//                   C  H0  H1  A0  A1   O              IP1 IP2

// D0 and D1 == 0

// |-------->        2   0   0   0   0   F              i/i x/x
// |-------->
//
// |-------->        2   0   0   0   0   T              i/x x/i
// <--------|
//
// |----->           1   0   0   0   0   T              x/x
//       <-----|
//

// |--------->       2   0   0   0   1   T              i/x x/i
//      <----|
//
// |--------->       2   0   0   0   0   F              i/i x/x
//      |---->
//
// |--------->       2   0   0  -1   1   F              i/i u/x
// |---->
//
// |--------->       2   0   0  -1   0   T              i/x u/i
// <----|

// |------->         2   0   0   1  -1   F   and        i/i x/u
//     |------->     2   0   0  -1   1   F   symmetric  i/i u/x
// |------->
//
//     |------->     2   0   0  -1  -1   T              i/u u/i
// <-------|
//
// |------->         2   0   0   1   1   T              i/x x/i
//     <-------|
//
// |-------->        2   0   0  -1   1   F              i/i u/x
//   |---->
//
// |-------->        2   0   0  -1   1   T              i/x u/i
//   <----|

//       |----->     1  -1  -1  -1  -1   T              u/u
// <-----|
//
//       |----->     1  -1   0  -1   0   F   and        u/x
// |----->           1   0  -1   0  -1   F   symmetric  x/u
//       |----->

// D0 or D1 != 0

//          ^
//          |
//          +        1  -1   1  -1   1   F   and        u/x  (P is vertical)
// |-------->        1   1  -1   1  -1   F   symmetric  x/u  (P is horizontal)
// ^
// |
// +
//
//          +
//          |
//          v
// |-------->        1   1   1   1   1   F              x/x  (P is vertical)
//
// ^
// |
// +
// |-------->        1  -1  -1  -1  -1   F              u/u  (P is vertical)
//
//      ^
//      |
//      +
// |-------->        1   0  -1   0  -1   F              u/u  (P is vertical)
//
//      +
//      |
//      v
// |-------->        1   0   1   0   1   F              u/x  (P is vertical)
//

class linear_intersections
{
public:
    template <typename Point1, typename Point2, typename IntersectionResult, typename EqPPStrategy>
    linear_intersections(Point1 const& pi,
                         Point2 const& qi,
                         IntersectionResult const& result,
                         bool is_p_last, bool is_q_last,
                         EqPPStrategy const& strategy)
    {
        int arrival_a = result.template get<1>().arrival[0];
        int arrival_b = result.template get<1>().arrival[1];
        bool same_dirs = result.template get<1>().dir_a == 0
                      && result.template get<1>().dir_b == 0;

        if ( same_dirs )
        {
            if ( result.template get<0>().count == 2 )
            {
                if ( ! result.template get<1>().opposite )
                {
                    ips[0].p_operation = operation_intersection;
                    ips[0].q_operation = operation_intersection;
                    ips[1].p_operation = union_or_blocked_same_dirs(arrival_a, is_p_last);
                    ips[1].q_operation = union_or_blocked_same_dirs(arrival_b, is_q_last);

                    ips[0].is_pi
                        = equals::equals_point_point(
                            pi, result.template get<0>().intersections[0], strategy);
                    ips[0].is_qi
                        = equals::equals_point_point(
                            qi, result.template get<0>().intersections[0], strategy);
                    ips[1].is_pj = arrival_a != -1;
                    ips[1].is_qj = arrival_b != -1;
                }
                else
                {
                    ips[0].p_operation = operation_intersection;
                    ips[0].q_operation = union_or_blocked_same_dirs(arrival_b, is_q_last);
                    ips[1].p_operation = union_or_blocked_same_dirs(arrival_a, is_p_last);
                    ips[1].q_operation = operation_intersection;

                    ips[0].is_pi = arrival_b != 1;
                    ips[0].is_qj = arrival_b != -1;
                    ips[1].is_pj = arrival_a != -1;
                    ips[1].is_qi = arrival_a != 1;
                }
            }
            else
            {
                BOOST_GEOMETRY_ASSERT(result.template get<0>().count == 1);
                ips[0].p_operation = union_or_blocked_same_dirs(arrival_a, is_p_last);
                ips[0].q_operation = union_or_blocked_same_dirs(arrival_b, is_q_last);

                ips[0].is_pi = arrival_a == -1;
                ips[0].is_qi = arrival_b == -1;
                ips[0].is_pj = arrival_a == 0;
                ips[0].is_qj = arrival_b == 0;
            }
        }
        else
        {
            ips[0].p_operation = union_or_blocked_different_dirs(arrival_a, is_p_last);
            ips[0].q_operation = union_or_blocked_different_dirs(arrival_b, is_q_last);

            ips[0].is_pi = arrival_a == -1;
            ips[0].is_qi = arrival_b == -1;
            ips[0].is_pj = arrival_a == 1;
            ips[0].is_qj = arrival_b == 1;
        }
    }

    struct ip_info
    {
        inline ip_info()
            : p_operation(operation_none), q_operation(operation_none)
            , is_pi(false), is_pj(false), is_qi(false), is_qj(false)
        {}

        operation_type p_operation, q_operation;
        bool is_pi, is_pj, is_qi, is_qj;
    };

    template <std::size_t I>
    ip_info const& get() const
    {
        BOOST_STATIC_ASSERT(I < 2);
        return ips[I];
    }
    
private:

    // only if collinear (same_dirs)
    static inline operation_type union_or_blocked_same_dirs(int arrival, bool is_last)
    {
        if ( arrival == 1 )
            return operation_blocked;
        else if ( arrival == -1 )
            return operation_union;
        else
            return is_last ? operation_blocked : operation_union;
            //return operation_blocked;
    }

    // only if not collinear (!same_dirs)
    static inline operation_type union_or_blocked_different_dirs(int arrival, bool is_last)
    {
        if ( arrival == 1 )
            //return operation_blocked;
            return is_last ? operation_blocked : operation_union;
        else
            return operation_union;
    }

    ip_info ips[2];
};

template <bool EnableFirst, bool EnableLast>
struct get_turn_info_for_endpoint
{
    typedef std::pair<operation_type, operation_type> operations_pair;

    BOOST_STATIC_ASSERT(EnableFirst || EnableLast);

    template<typename UniqueSubRange1,
             typename UniqueSubRange2,
             typename TurnInfo,
             typename IntersectionInfo,
             typename OutputIterator,
             typename EqPPStrategy
    >
    static inline bool apply(UniqueSubRange1 const& range_p,
                             UniqueSubRange2 const& range_q,
                             TurnInfo const& tp_model,
                             IntersectionInfo const& inters,
                             method_type /*method*/,
                             OutputIterator out,
                             EqPPStrategy const& strategy)
    {
        std::size_t ip_count = inters.i_info().count;
        // no intersection points
        if (ip_count == 0)
        {
            return false;
        }

        if (! range_p.is_first_segment()
            && ! range_q.is_first_segment()
            && ! range_p.is_last_segment()
            && ! range_q.is_last_segment())
        {
            // Not an end-point from segment p or q
            return false;
        }

        linear_intersections intersections(range_p.at(0),
                                           range_q.at(0),
                                           inters.result(),
                                           range_p.is_last_segment(),
                                           range_q.is_last_segment(),
                                           strategy);

        bool append0_last
            = analyse_segment_and_assign_ip(range_p, range_q,
                                            intersections.template get<0>(),
                                            tp_model, inters, 0, out);

        // NOTE: opposite && ip_count == 1 may be true!
        bool opposite = inters.d_info().opposite;

        // don't ignore only for collinear opposite
        bool result_ignore_ip0 = append0_last && ( ip_count == 1 || !opposite );

        if ( intersections.template get<1>().p_operation == operation_none )
            return result_ignore_ip0;
        
        bool append1_last
            = analyse_segment_and_assign_ip(range_p, range_q,
                                            intersections.template get<1>(),
                                            tp_model, inters, 1, out);

        // don't ignore only for collinear opposite
        bool result_ignore_ip1 = append1_last && !opposite /*&& ip_count == 2*/;

        return result_ignore_ip0 || result_ignore_ip1;
    }

    template <typename UniqueSubRange1,
              typename UniqueSubRange2,
              typename TurnInfo,
              typename IntersectionInfo,
              typename OutputIterator>
    static inline
    bool analyse_segment_and_assign_ip(UniqueSubRange1 const& range_p,
                                       UniqueSubRange2 const& range_q,
                                       linear_intersections::ip_info const& ip_info,
                                       TurnInfo const& tp_model,
                                       IntersectionInfo const& inters,
                                       unsigned int ip_index,
                                       OutputIterator out)
    {
        // TODO - calculate first/last only if needed
        bool is_p_first_ip = range_p.is_first_segment() && ip_info.is_pi;
        bool is_p_last_ip = range_p.is_last_segment() && ip_info.is_pj;
        bool is_q_first_ip = range_q.is_first_segment() && ip_info.is_qi;
        bool is_q_last_ip = range_q.is_last_segment() && ip_info.is_qj;
        bool append_first = EnableFirst && (is_p_first_ip || is_q_first_ip);
        bool append_last = EnableLast && (is_p_last_ip || is_q_last_ip);

        operation_type p_operation = ip_info.p_operation;
        operation_type q_operation = ip_info.q_operation;

        if ( append_first || append_last )
        {
            bool handled = handle_internal<0>(range_p, range_q,
                                              is_p_first_ip, is_p_last_ip,
                                              is_q_first_ip, is_q_last_ip,
                                              ip_info.is_qi, ip_info.is_qj,
                                              tp_model, inters, ip_index,
                                              p_operation, q_operation);
            if ( !handled )
            {
                // Reverse p/q
                handle_internal<1>(range_q, range_p,
                                   is_q_first_ip, is_q_last_ip,
                                   is_p_first_ip, is_p_last_ip,
                                   ip_info.is_pi, ip_info.is_pj,
                                   tp_model, inters, ip_index,
                                   q_operation, p_operation);
            }

            if ( p_operation != operation_none )
            {
                method_type method = endpoint_ip_method(ip_info.is_pi, ip_info.is_pj,
                                                        ip_info.is_qi, ip_info.is_qj);
                turn_position p_pos = ip_position(is_p_first_ip, is_p_last_ip);
                turn_position q_pos = ip_position(is_q_first_ip, is_q_last_ip);

                // handle spikes

                // P is spike and should be handled
                if (ip_info.is_pj // this check is redundant (also in is_spike_p) but faster
                  && inters.i_info().count == 2
                  && inters.is_spike_p() )
                {
                    assign(inters.result(), ip_index, method, operation_blocked, q_operation,
                           p_pos, q_pos, is_p_first_ip, is_q_first_ip, true, false, tp_model, out);
                    assign(inters.result(), ip_index, method, operation_intersection, q_operation,
                           p_pos, q_pos, is_p_first_ip, is_q_first_ip, true, false, tp_model, out);
                }
                // Q is spike and should be handled
                else if (ip_info.is_qj // this check is redundant (also in is_spike_q) but faster
                       && inters.i_info().count == 2
                       && inters.is_spike_q() )
                {
                    assign(inters.result(), ip_index, method, p_operation, operation_blocked,
                           p_pos, q_pos, is_p_first_ip, is_q_first_ip, false, true, tp_model, out);
                    assign(inters.result(), ip_index, method, p_operation, operation_intersection,
                           p_pos, q_pos, is_p_first_ip, is_q_first_ip, false, true, tp_model, out);
                }
                // no spikes
                else
                {
                    assign(inters.result(), ip_index, method, p_operation, q_operation,
                           p_pos, q_pos, is_p_first_ip, is_q_first_ip, false, false, tp_model, out);
                }
            }
        }

        return append_last;
    }

    // TODO: IT'S ALSO PROBABLE THAT ALL THIS FUNCTION COULD BE INTEGRATED WITH handle_segment
    //       however now it's lazily calculated and then it would be always calculated

    template<std::size_t G1Index,
             typename UniqueRange1,
             typename UniqueRange2,
             typename TurnInfo,
             typename IntersectionInfo
    >
    static inline bool handle_internal(UniqueRange1 const& range1,
                                       UniqueRange2 const& range2,
                                       bool first1, bool last1, bool first2, bool last2,
                                       bool ip_i2, bool ip_j2, TurnInfo const& tp_model,
                                       IntersectionInfo const& inters, unsigned int ip_index,
                                       operation_type & op1, operation_type & op2)
    {
        boost::ignore_unused(ip_index, tp_model);

        typename IntersectionInfo::side_strategy_type const& sides
                = inters.get_side_strategy();

        if ( !first2 && !last2 )
        {
            if ( first1 )
            {
#ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS_LINEAR_LINEAR
                // may this give false positives for INTs?
                typename IntersectionResult::point_type const&
                    inters_pt = inters.i_info().intersections[ip_index];
                BOOST_GEOMETRY_ASSERT(ip_i2 == equals::equals_point_point(i2, inters_pt));
                BOOST_GEOMETRY_ASSERT(ip_j2 == equals::equals_point_point(j2, inters_pt));
#endif
                if ( ip_i2 )
                {
                    // don't output this IP - for the first point of other geometry segment
                    op1 = operation_none;
                    op2 = operation_none;
                    return true;
                }
                else if ( ip_j2 )
                {
                    int const side_pj_q2 = sides.apply(range2.at(1), range2.at(2), range1.at(1));
                    int const side_pj_q1 = sides.apply(range2.at(0), range2.at(1), range1.at(1));
                    int const side_qk_q1 = sides.apply(range2.at(0), range2.at(1), range2.at(2));

                    operations_pair operations = operations_of_equal(side_pj_q2, side_pj_q1, side_qk_q1);

// TODO: must the above be calculated?
// wouldn't it be enough to check if segments are collinear?

                    if ( operations_both(operations, operation_continue) )
                    {
                        if ( op1 != operation_union 
                          || op2 != operation_union
                          || ! ( G1Index == 0 ? inters.is_spike_q() : inters.is_spike_p() ) )
                        {
                            // THIS IS WRT THE ORIGINAL SEGMENTS! NOT THE ONES ABOVE!
                            bool opposite = inters.d_info().opposite;

                            op1 = operation_intersection;
                            op2 = opposite ? operation_union : operation_intersection;
                        }
                    }
                    else
                    {
                        BOOST_GEOMETRY_ASSERT(operations_combination(operations, operation_intersection, operation_union));
                        //op1 = operation_union;
                        //op2 = operation_union;
                    }

                    return true;
                }
                // else do nothing - shouldn't be handled this way
            }
            else if ( last1 )
            {
#ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS_LINEAR_LINEAR
                // may this give false positives for INTs?
                typename IntersectionResult::point_type const&
                    inters_pt = inters.i_info().intersections[ip_index];
                BOOST_GEOMETRY_ASSERT(ip_i2 == equals::equals_point_point(i2, inters_pt));
                BOOST_GEOMETRY_ASSERT(ip_j2 == equals::equals_point_point(j2, inters_pt));
#endif
                if ( ip_i2 )
                {
                    // don't output this IP - for the first point of other geometry segment
                    op1 = operation_none;
                    op2 = operation_none;
                    return true;
                }
                else if ( ip_j2 )
                {
                    int const side_pi_q2 = sides.apply(range2.at(1), range2.at(2), range1.at(0));
                    int const side_pi_q1 = sides.apply(range2.at(0), range2.at(1), range1.at(0));
                    int const side_qk_q1 = sides.apply(range2.at(0), range2.at(1), range2.at(2));

                    operations_pair operations = operations_of_equal(side_pi_q2, side_pi_q1, side_qk_q1);

// TODO: must the above be calculated?
// wouldn't it be enough to check if segments are collinear?

                    if ( operations_both(operations, operation_continue) )
                    {
                        if ( op1 != operation_blocked
                          || op2 != operation_union
                          || ! ( G1Index == 0 ? inters.is_spike_q() : inters.is_spike_p() ) )
                        {
                            // THIS IS WRT THE ORIGINAL SEGMENTS! NOT THE ONES ABOVE!
                            bool second_going_out = inters.i_info().count > 1;

                            op1 = operation_blocked;
                            op2 = second_going_out ? operation_union : operation_intersection;
                        }
                    }
                    else
                    {
                        BOOST_GEOMETRY_ASSERT(operations_combination(operations, operation_intersection, operation_union));
                        //op1 = operation_blocked;
                        //op2 = operation_union;
                    }

                    return true;
                }
                // else do nothing - shouldn't be handled this way
            }
            // else do nothing - shouldn't be handled this way
        }

        return false;
    }

    static inline method_type endpoint_ip_method(bool ip_pi, bool ip_pj, bool ip_qi, bool ip_qj)
    {
        if ( (ip_pi || ip_pj) && (ip_qi || ip_qj) )
            return method_touch;
        else
            return method_touch_interior;
    }

    static inline turn_position ip_position(bool is_ip_first_i, bool is_ip_last_j)
    {
        return is_ip_first_i ? position_front :
               ( is_ip_last_j ? position_back : position_middle );
    }

    template <typename IntersectionResult,
              typename TurnInfo,
              typename OutputIterator>
    static inline void assign(IntersectionResult const& result,
                              unsigned int ip_index,
                              method_type method,
                              operation_type op0, operation_type op1,
                              turn_position pos0, turn_position pos1,
                              bool is_p_first_ip, bool is_q_first_ip,
                              bool is_p_spike, bool is_q_spike,
                              TurnInfo const& tp_model,
                              OutputIterator out)
    {
        TurnInfo tp = tp_model;
        
        //geometry::convert(ip, tp.point);
        //tp.method = method;
        base_turn_handler::assign_point(tp, method, result.template get<0>(), ip_index);

        tp.operations[0].operation = op0;
        tp.operations[1].operation = op1;
        tp.operations[0].position = pos0;
        tp.operations[1].position = pos1;

        if ( result.template get<0>().count > 1 )
        {
            // NOTE: is_collinear is NOT set for the first endpoint
            // for which there is no preceding segment

            //BOOST_GEOMETRY_ASSERT( result.template get<1>().dir_a == 0 && result.template get<1>().dir_b == 0 );
            if ( ! is_p_first_ip )
            {
                tp.operations[0].is_collinear = op0 != operation_intersection
                                             || is_p_spike;
            }

            if ( ! is_q_first_ip )
            {
                tp.operations[1].is_collinear = op1 != operation_intersection
                                             || is_q_spike;
            }
        }
        else //if ( result.template get<0>().count == 1 )
        {
            if ( op0 == operation_blocked && op1 == operation_intersection )
            {
                tp.operations[0].is_collinear = true;
            }
            else if ( op0 == operation_intersection && op1 == operation_blocked )
            {
                tp.operations[1].is_collinear = true;
            }
        }

        *out++ = tp;
    }

    static inline operations_pair operations_of_equal(int side_px_q2,
                                                      int side_px_q1,
                                                      int side_qk_q1)
    {
        // If px (pi or pj) is collinear with qj-qk (q2), they continue collinearly.
        // This can be on either side of q1, or collinear
        // The second condition checks if they do not continue
        // oppositely
        if (side_px_q2 == 0 && side_px_q1 == side_qk_q1)
        {
            return std::make_pair(operation_continue, operation_continue);
        }

        // If they turn to same side (not opposite sides)
        if ( ! base_turn_handler::opposite(side_px_q1, side_qk_q1) )
        {
            // If px is left of q2 or collinear: p: union, q: intersection
            if (side_px_q2 != -1 )
            {
                return std::make_pair(operation_union, operation_intersection);
            }
            else
            {
               return std::make_pair(operation_intersection, operation_union);
            }
        }
        else
        {
            // They turn opposite sides. If p turns left (or collinear),
           // p: union, q: intersection
            if (side_px_q1 != -1 )
            {
                return std::make_pair(operation_union, operation_intersection);
            }
           else
            {
                return std::make_pair(operation_intersection, operation_union);
            }
        }
   }

    static inline bool operations_both(operations_pair const& operations,
                                       operation_type const op)
    {
        return operations.first == op && operations.second == op;
    }

    static inline bool operations_combination(operations_pair const& operations,
                                              operation_type const op1,
                                              operation_type const op2)
    {
        return ( operations.first == op1 && operations.second == op2 )
            || ( operations.first == op2 && operations.second == op1 );
    }
};

}} // namespace detail::overlay
#endif // DOXYGEN_NO_DETAIL

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_FOR_ENDPOINT_HPP
Commit	Line	Data
7c673cae FG	1	// Boost.Geometry (aka GGL, Generic Geometry Library)
	2
	3	// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
	4
92f5a8d4 TL	5	// This file was modified by Oracle on 2013, 2014, 2017, 2018.
92f5a8d4 TL	6	// Modifications copyright (c) 2013-2018 Oracle and/or its affiliates.
b32b8144 FG	7
b32b8144 FG	8	// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
7c673cae FG	9
	10	// Use, modification and distribution is subject to the Boost Software License,
	11	// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
	12	// http://www.boost.org/LICENSE_1_0.txt)
	13
7c673cae FG	14	#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_FOR_ENDPOINT_HPP
	15	#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_FOR_ENDPOINT_HPP
	16
92f5a8d4 TL	17	#include <boost/core/ignore_unused.hpp>
	18
	19	#include <boost/geometry/algorithms/detail/equals/point_point.hpp>
7c673cae	20	#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
92f5a8d4	21	#include <boost/geometry/core/assert.hpp>
7c673cae FG	22	#include <boost/geometry/policies/robustness/no_rescale_policy.hpp>
	23
	24	namespace boost { namespace geometry {
	25
	26	#ifndef DOXYGEN_NO_DETAIL
	27	namespace detail { namespace overlay {
	28
	29	// SEGMENT_INTERSECTION RESULT
	30
	31	// C H0 H1 A0 A1 O IP1 IP2
	32
	33	// D0 and D1 == 0
	34
	35	// \|--------> 2 0 0 0 0 F i/i x/x
	36	// \|-------->
	37	//
	38	// \|--------> 2 0 0 0 0 T i/x x/i
	39	// <--------\|
	40	//
	41	// \|-----> 1 0 0 0 0 T x/x
	42	// <-----\|
	43	//
	44
	45	// \|---------> 2 0 0 0 1 T i/x x/i
	46	// <----\|
	47	//
	48	// \|---------> 2 0 0 0 0 F i/i x/x
	49	// \|---->
	50	//
	51	// \|---------> 2 0 0 -1 1 F i/i u/x
	52	// \|---->
	53	//
	54	// \|---------> 2 0 0 -1 0 T i/x u/i
	55	// <----\|
	56
	57	// \|-------> 2 0 0 1 -1 F and i/i x/u
92f5a8d4	58	// \|-------> 2 0 0 -1 1 F symmetric i/i u/x
7c673cae FG	59	// \|------->
	60	//
	61	// \|-------> 2 0 0 -1 -1 T i/u u/i
	62	// <-------\|
	63	//
	64	// \|-------> 2 0 0 1 1 T i/x x/i
	65	// <-------\|
	66	//
	67	// \|--------> 2 0 0 -1 1 F i/i u/x
	68	// \|---->
	69	//
	70	// \|--------> 2 0 0 -1 1 T i/x u/i
	71	// <----\|
	72
	73	// \|-----> 1 -1 -1 -1 -1 T u/u
	74	// <-----\|
	75	//
	76	// \|-----> 1 -1 0 -1 0 F and u/x
92f5a8d4	77	// \|-----> 1 0 -1 0 -1 F symmetric x/u
7c673cae FG	78	// \|----->
	79
	80	// D0 or D1 != 0
	81
	82	// ^
	83	// \|
	84	// + 1 -1 1 -1 1 F and u/x (P is vertical)
92f5a8d4	85	// \|--------> 1 1 -1 1 -1 F symmetric x/u (P is horizontal)
7c673cae FG	86	// ^
	87	// \|
	88	// +
	89	//
	90	// +
	91	// \|
	92	// v
	93	// \|--------> 1 1 1 1 1 F x/x (P is vertical)
	94	//
	95	// ^
	96	// \|
	97	// +
	98	// \|--------> 1 -1 -1 -1 -1 F u/u (P is vertical)
	99	//
	100	// ^
	101	// \|
	102	// +
	103	// \|--------> 1 0 -1 0 -1 F u/u (P is vertical)
	104	//
	105	// +
	106	// \|
	107	// v
	108	// \|--------> 1 0 1 0 1 F u/x (P is vertical)
	109	//
	110
	111	class linear_intersections
	112	{
	113	public:
92f5a8d4	114	template <typename Point1, typename Point2, typename IntersectionResult, typename EqPPStrategy>
7c673cae FG	115	linear_intersections(Point1 const& pi,
	116	Point2 const& qi,
	117	IntersectionResult const& result,
92f5a8d4 TL	118	bool is_p_last, bool is_q_last,
92f5a8d4 TL	119	EqPPStrategy const& strategy)
7c673cae FG	120	{
	121	int arrival_a = result.template get<1>().arrival[0];
	122	int arrival_b = result.template get<1>().arrival[1];
	123	bool same_dirs = result.template get<1>().dir_a == 0
	124	&& result.template get<1>().dir_b == 0;
	125
	126	if ( same_dirs )
	127	{
	128	if ( result.template get<0>().count == 2 )
	129	{
	130	if ( ! result.template get<1>().opposite )
	131	{
	132	ips[0].p_operation = operation_intersection;
	133	ips[0].q_operation = operation_intersection;
	134	ips[1].p_operation = union_or_blocked_same_dirs(arrival_a, is_p_last);
	135	ips[1].q_operation = union_or_blocked_same_dirs(arrival_b, is_q_last);
	136
	137	ips[0].is_pi
	138	= equals::equals_point_point(
92f5a8d4	139	pi, result.template get<0>().intersections[0], strategy);
7c673cae FG	140	ips[0].is_qi
7c673cae FG	141	= equals::equals_point_point(
92f5a8d4	142	qi, result.template get<0>().intersections[0], strategy);
7c673cae FG	143	ips[1].is_pj = arrival_a != -1;
	144	ips[1].is_qj = arrival_b != -1;
	145	}
	146	else
	147	{
	148	ips[0].p_operation = operation_intersection;
	149	ips[0].q_operation = union_or_blocked_same_dirs(arrival_b, is_q_last);
	150	ips[1].p_operation = union_or_blocked_same_dirs(arrival_a, is_p_last);
	151	ips[1].q_operation = operation_intersection;
	152
	153	ips[0].is_pi = arrival_b != 1;
	154	ips[0].is_qj = arrival_b != -1;
	155	ips[1].is_pj = arrival_a != -1;
	156	ips[1].is_qi = arrival_a != 1;
	157	}
	158	}
	159	else
	160	{
	161	BOOST_GEOMETRY_ASSERT(result.template get<0>().count == 1);
	162	ips[0].p_operation = union_or_blocked_same_dirs(arrival_a, is_p_last);
	163	ips[0].q_operation = union_or_blocked_same_dirs(arrival_b, is_q_last);
	164
	165	ips[0].is_pi = arrival_a == -1;
	166	ips[0].is_qi = arrival_b == -1;
	167	ips[0].is_pj = arrival_a == 0;
	168	ips[0].is_qj = arrival_b == 0;
	169	}
	170	}
	171	else
	172	{
	173	ips[0].p_operation = union_or_blocked_different_dirs(arrival_a, is_p_last);
	174	ips[0].q_operation = union_or_blocked_different_dirs(arrival_b, is_q_last);
	175
	176	ips[0].is_pi = arrival_a == -1;
	177	ips[0].is_qi = arrival_b == -1;
	178	ips[0].is_pj = arrival_a == 1;
	179	ips[0].is_qj = arrival_b == 1;
	180	}
	181	}
	182
	183	struct ip_info
	184	{
	185	inline ip_info()
	186	: p_operation(operation_none), q_operation(operation_none)
	187	, is_pi(false), is_pj(false), is_qi(false), is_qj(false)
	188	{}
	189
	190	operation_type p_operation, q_operation;
	191	bool is_pi, is_pj, is_qi, is_qj;
	192	};
	193
	194	template <std::size_t I>
	195	ip_info const& get() const
	196	{
	197	BOOST_STATIC_ASSERT(I < 2);
	198	return ips[I];
	199	}
	200
	201	private:
	202
	203	// only if collinear (same_dirs)
	204	static inline operation_type union_or_blocked_same_dirs(int arrival, bool is_last)
	205	{
	206	if ( arrival == 1 )
207	return operation_blocked;
208	else if ( arrival == -1 )
209	return operation_union;
210	else
211	return is_last ? operation_blocked : operation_union;
212	//return operation_blocked;
213	}
214
215	// only if not collinear (!same_dirs)
216	static inline operation_type union_or_blocked_different_dirs(int arrival, bool is_last)
217	{
218	if ( arrival == 1 )
219	//return operation_blocked;
220	return is_last ? operation_blocked : operation_union;
221	else
222	return operation_union;
223	}
224
225	ip_info ips[2];
226	};
227
92f5a8d4	228	template <bool EnableFirst, bool EnableLast>
7c673cae FG	229	struct get_turn_info_for_endpoint
7c673cae FG	230	{
92f5a8d4 TL	231	typedef std::pair<operation_type, operation_type> operations_pair;
92f5a8d4 TL	232
7c673cae FG	233	BOOST_STATIC_ASSERT(EnableFirst \|\| EnableLast);
7c673cae FG	234
92f5a8d4 TL	235	template<typename UniqueSubRange1,
92f5a8d4 TL	236	typename UniqueSubRange2,
7c673cae FG	237	typename TurnInfo,
7c673cae FG	238	typename IntersectionInfo,
92f5a8d4 TL	239	typename OutputIterator,
92f5a8d4 TL	240	typename EqPPStrategy
7c673cae	241	>
92f5a8d4 TL	242	static inline bool apply(UniqueSubRange1 const& range_p,
92f5a8d4 TL	243	UniqueSubRange2 const& range_q,
7c673cae FG	244	TurnInfo const& tp_model,
	245	IntersectionInfo const& inters,
	246	method_type /method/,
92f5a8d4 TL	247	OutputIterator out,
92f5a8d4 TL	248	EqPPStrategy const& strategy)
7c673cae FG	249	{
	250	std::size_t ip_count = inters.i_info().count;
	251	// no intersection points
92f5a8d4 TL	252	if (ip_count == 0)
92f5a8d4 TL	253	{
7c673cae	254	return false;
92f5a8d4	255	}
7c673cae	256
92f5a8d4 TL	257	if (! range_p.is_first_segment()
	258	&& ! range_q.is_first_segment()
	259	&& ! range_p.is_last_segment()
	260	&& ! range_q.is_last_segment())
	261	{
	262	// Not an end-point from segment p or q
7c673cae	263	return false;
92f5a8d4	264	}
7c673cae	265
92f5a8d4 TL	266	linear_intersections intersections(range_p.at(0),
	267	range_q.at(0),
	268	inters.result(),
	269	range_p.is_last_segment(),
	270	range_q.is_last_segment(),
	271	strategy);
7c673cae FG	272
7c673cae FG	273	bool append0_last
92f5a8d4	274	= analyse_segment_and_assign_ip(range_p, range_q,
7c673cae FG	275	intersections.template get<0>(),
	276	tp_model, inters, 0, out);
	277
	278	// NOTE: opposite && ip_count == 1 may be true!
	279	bool opposite = inters.d_info().opposite;
	280
	281	// don't ignore only for collinear opposite
	282	bool result_ignore_ip0 = append0_last && ( ip_count == 1 \|\| !opposite );
	283
	284	if ( intersections.template get<1>().p_operation == operation_none )
	285	return result_ignore_ip0;
	286
	287	bool append1_last
92f5a8d4	288	= analyse_segment_and_assign_ip(range_p, range_q,
7c673cae FG	289	intersections.template get<1>(),
	290	tp_model, inters, 1, out);
	291
	292	// don't ignore only for collinear opposite
	293	bool result_ignore_ip1 = append1_last && !opposite /&& ip_count == 2/;
	294
	295	return result_ignore_ip0 \|\| result_ignore_ip1;
	296	}
	297
92f5a8d4 TL	298	template <typename UniqueSubRange1,
92f5a8d4 TL	299	typename UniqueSubRange2,
7c673cae FG	300	typename TurnInfo,
	301	typename IntersectionInfo,
	302	typename OutputIterator>
	303	static inline
92f5a8d4 TL	304	bool analyse_segment_and_assign_ip(UniqueSubRange1 const& range_p,
92f5a8d4 TL	305	UniqueSubRange2 const& range_q,
7c673cae FG	306	linear_intersections::ip_info const& ip_info,
	307	TurnInfo const& tp_model,
	308	IntersectionInfo const& inters,
	309	unsigned int ip_index,
	310	OutputIterator out)
	311	{
7c673cae	312	// TODO - calculate first/last only if needed
92f5a8d4 TL	313	bool is_p_first_ip = range_p.is_first_segment() && ip_info.is_pi;
	314	bool is_p_last_ip = range_p.is_last_segment() && ip_info.is_pj;
	315	bool is_q_first_ip = range_q.is_first_segment() && ip_info.is_qi;
	316	bool is_q_last_ip = range_q.is_last_segment() && ip_info.is_qj;
7c673cae FG	317	bool append_first = EnableFirst && (is_p_first_ip \|\| is_q_first_ip);
	318	bool append_last = EnableLast && (is_p_last_ip \|\| is_q_last_ip);
	319
	320	operation_type p_operation = ip_info.p_operation;
	321	operation_type q_operation = ip_info.q_operation;
	322
	323	if ( append_first \|\| append_last )
	324	{
92f5a8d4	325	bool handled = handle_internal<0>(range_p, range_q,
7c673cae FG	326	is_p_first_ip, is_p_last_ip,
	327	is_q_first_ip, is_q_last_ip,
	328	ip_info.is_qi, ip_info.is_qj,
	329	tp_model, inters, ip_index,
	330	p_operation, q_operation);
	331	if ( !handled )
	332	{
92f5a8d4 TL	333	// Reverse p/q
92f5a8d4 TL	334	handle_internal<1>(range_q, range_p,
7c673cae FG	335	is_q_first_ip, is_q_last_ip,
	336	is_p_first_ip, is_p_last_ip,
	337	ip_info.is_pi, ip_info.is_pj,
	338	tp_model, inters, ip_index,
	339	q_operation, p_operation);
	340	}
	341
	342	if ( p_operation != operation_none )
	343	{
	344	method_type method = endpoint_ip_method(ip_info.is_pi, ip_info.is_pj,
	345	ip_info.is_qi, ip_info.is_qj);
	346	turn_position p_pos = ip_position(is_p_first_ip, is_p_last_ip);
	347	turn_position q_pos = ip_position(is_q_first_ip, is_q_last_ip);
	348
	349	// handle spikes
	350
	351	// P is spike and should be handled
92f5a8d4	352	if (ip_info.is_pj // this check is redundant (also in is_spike_p) but faster
7c673cae FG	353	&& inters.i_info().count == 2
	354	&& inters.is_spike_p() )
	355	{
92f5a8d4	356	assign(inters.result(), ip_index, method, operation_blocked, q_operation,
7c673cae	357	p_pos, q_pos, is_p_first_ip, is_q_first_ip, true, false, tp_model, out);
92f5a8d4	358	assign(inters.result(), ip_index, method, operation_intersection, q_operation,
7c673cae FG	359	p_pos, q_pos, is_p_first_ip, is_q_first_ip, true, false, tp_model, out);
	360	}
	361	// Q is spike and should be handled
92f5a8d4	362	else if (ip_info.is_qj // this check is redundant (also in is_spike_q) but faster
7c673cae FG	363	&& inters.i_info().count == 2
	364	&& inters.is_spike_q() )
	365	{
92f5a8d4	366	assign(inters.result(), ip_index, method, p_operation, operation_blocked,
7c673cae	367	p_pos, q_pos, is_p_first_ip, is_q_first_ip, false, true, tp_model, out);
92f5a8d4	368	assign(inters.result(), ip_index, method, p_operation, operation_intersection,
7c673cae FG	369	p_pos, q_pos, is_p_first_ip, is_q_first_ip, false, true, tp_model, out);
	370	}
	371	// no spikes
	372	else
	373	{
92f5a8d4	374	assign(inters.result(), ip_index, method, p_operation, q_operation,
7c673cae FG	375	p_pos, q_pos, is_p_first_ip, is_q_first_ip, false, false, tp_model, out);
	376	}
	377	}
	378	}
	379
	380	return append_last;
	381	}
	382
	383	// TODO: IT'S ALSO PROBABLE THAT ALL THIS FUNCTION COULD BE INTEGRATED WITH handle_segment
	384	// however now it's lazily calculated and then it would be always calculated
	385
	386	template<std::size_t G1Index,
92f5a8d4 TL	387	typename UniqueRange1,
92f5a8d4 TL	388	typename UniqueRange2,
7c673cae FG	389	typename TurnInfo,
	390	typename IntersectionInfo
	391	>
92f5a8d4 TL	392	static inline bool handle_internal(UniqueRange1 const& range1,
92f5a8d4 TL	393	UniqueRange2 const& range2,
7c673cae FG	394	bool first1, bool last1, bool first2, bool last2,
	395	bool ip_i2, bool ip_j2, TurnInfo const& tp_model,
	396	IntersectionInfo const& inters, unsigned int ip_index,
	397	operation_type & op1, operation_type & op2)
	398	{
92f5a8d4	399	boost::ignore_unused(ip_index, tp_model);
7c673cae	400
92f5a8d4 TL	401	typename IntersectionInfo::side_strategy_type const& sides
92f5a8d4 TL	402	= inters.get_side_strategy();
7c673cae FG	403
	404	if ( !first2 && !last2 )
	405	{
	406	if ( first1 )
	407	{
	408	#ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS_LINEAR_LINEAR
	409	// may this give false positives for INTs?
	410	typename IntersectionResult::point_type const&
	411	inters_pt = inters.i_info().intersections[ip_index];
	412	BOOST_GEOMETRY_ASSERT(ip_i2 == equals::equals_point_point(i2, inters_pt));
	413	BOOST_GEOMETRY_ASSERT(ip_j2 == equals::equals_point_point(j2, inters_pt));
	414	#endif
	415	if ( ip_i2 )
	416	{
	417	// don't output this IP - for the first point of other geometry segment
	418	op1 = operation_none;
	419	op2 = operation_none;
	420	return true;
	421	}
	422	else if ( ip_j2 )
	423	{
92f5a8d4 TL	424	int const side_pj_q2 = sides.apply(range2.at(1), range2.at(2), range1.at(1));
	425	int const side_pj_q1 = sides.apply(range2.at(0), range2.at(1), range1.at(1));
	426	int const side_qk_q1 = sides.apply(range2.at(0), range2.at(1), range2.at(2));
7c673cae	427
92f5a8d4	428	operations_pair operations = operations_of_equal(side_pj_q2, side_pj_q1, side_qk_q1);
7c673cae FG	429
	430	// TODO: must the above be calculated?
	431	// wouldn't it be enough to check if segments are collinear?
	432
	433	if ( operations_both(operations, operation_continue) )
	434	{
	435	if ( op1 != operation_union
	436	\|\| op2 != operation_union
	437	\|\| ! ( G1Index == 0 ? inters.is_spike_q() : inters.is_spike_p() ) )
	438	{
	439	// THIS IS WRT THE ORIGINAL SEGMENTS! NOT THE ONES ABOVE!
	440	bool opposite = inters.d_info().opposite;
	441
	442	op1 = operation_intersection;
	443	op2 = opposite ? operation_union : operation_intersection;
	444	}
	445	}
	446	else
	447	{
	448	BOOST_GEOMETRY_ASSERT(operations_combination(operations, operation_intersection, operation_union));
	449	//op1 = operation_union;
	450	//op2 = operation_union;
	451	}
	452
	453	return true;
	454	}
	455	// else do nothing - shouldn't be handled this way
	456	}
	457	else if ( last1 )
	458	{
	459	#ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS_LINEAR_LINEAR
	460	// may this give false positives for INTs?
	461	typename IntersectionResult::point_type const&
	462	inters_pt = inters.i_info().intersections[ip_index];
	463	BOOST_GEOMETRY_ASSERT(ip_i2 == equals::equals_point_point(i2, inters_pt));
	464	BOOST_GEOMETRY_ASSERT(ip_j2 == equals::equals_point_point(j2, inters_pt));
	465	#endif
	466	if ( ip_i2 )
	467	{
	468	// don't output this IP - for the first point of other geometry segment
	469	op1 = operation_none;
	470	op2 = operation_none;
	471	return true;
	472	}
	473	else if ( ip_j2 )
	474	{
92f5a8d4 TL	475	int const side_pi_q2 = sides.apply(range2.at(1), range2.at(2), range1.at(0));
	476	int const side_pi_q1 = sides.apply(range2.at(0), range2.at(1), range1.at(0));
	477	int const side_qk_q1 = sides.apply(range2.at(0), range2.at(1), range2.at(2));
	478
	479	operations_pair operations = operations_of_equal(side_pi_q2, side_pi_q1, side_qk_q1);
7c673cae FG	480
	481	// TODO: must the above be calculated?
	482	// wouldn't it be enough to check if segments are collinear?
	483
	484	if ( operations_both(operations, operation_continue) )
	485	{
	486	if ( op1 != operation_blocked
	487	\|\| op2 != operation_union
	488	\|\| ! ( G1Index == 0 ? inters.is_spike_q() : inters.is_spike_p() ) )
	489	{
	490	// THIS IS WRT THE ORIGINAL SEGMENTS! NOT THE ONES ABOVE!
	491	bool second_going_out = inters.i_info().count > 1;
	492
	493	op1 = operation_blocked;
	494	op2 = second_going_out ? operation_union : operation_intersection;
	495	}
	496	}
	497	else
	498	{
	499	BOOST_GEOMETRY_ASSERT(operations_combination(operations, operation_intersection, operation_union));
	500	//op1 = operation_blocked;
	501	//op2 = operation_union;
	502	}
	503
	504	return true;
	505	}
	506	// else do nothing - shouldn't be handled this way
	507	}
	508	// else do nothing - shouldn't be handled this way
	509	}
	510
	511	return false;
	512	}
	513
	514	static inline method_type endpoint_ip_method(bool ip_pi, bool ip_pj, bool ip_qi, bool ip_qj)
	515	{
	516	if ( (ip_pi \|\| ip_pj) && (ip_qi \|\| ip_qj) )
	517	return method_touch;
	518	else
	519	return method_touch_interior;
	520	}
	521
	522	static inline turn_position ip_position(bool is_ip_first_i, bool is_ip_last_j)
	523	{
	524	return is_ip_first_i ? position_front :
	525	( is_ip_last_j ? position_back : position_middle );
	526	}
	527
92f5a8d4	528	template <typename IntersectionResult,
7c673cae FG	529	typename TurnInfo,
7c673cae FG	530	typename OutputIterator>
92f5a8d4	531	static inline void assign(IntersectionResult const& result,
7c673cae FG	532	unsigned int ip_index,
	533	method_type method,
	534	operation_type op0, operation_type op1,
	535	turn_position pos0, turn_position pos1,
	536	bool is_p_first_ip, bool is_q_first_ip,
	537	bool is_p_spike, bool is_q_spike,
	538	TurnInfo const& tp_model,
	539	OutputIterator out)
	540	{
	541	TurnInfo tp = tp_model;
	542
	543	//geometry::convert(ip, tp.point);
	544	//tp.method = method;
	545	base_turn_handler::assign_point(tp, method, result.template get<0>(), ip_index);
	546
	547	tp.operations[0].operation = op0;
	548	tp.operations[1].operation = op1;
	549	tp.operations[0].position = pos0;
	550	tp.operations[1].position = pos1;
	551
	552	if ( result.template get<0>().count > 1 )
	553	{
	554	// NOTE: is_collinear is NOT set for the first endpoint
	555	// for which there is no preceding segment
	556
	557	//BOOST_GEOMETRY_ASSERT( result.template get<1>().dir_a == 0 && result.template get<1>().dir_b == 0 );
	558	if ( ! is_p_first_ip )
	559	{
	560	tp.operations[0].is_collinear = op0 != operation_intersection
	561	\|\| is_p_spike;
	562	}
	563
	564	if ( ! is_q_first_ip )
	565	{
	566	tp.operations[1].is_collinear = op1 != operation_intersection
	567	\|\| is_q_spike;
	568	}
	569	}
	570	else //if ( result.template get<0>().count == 1 )
	571	{
	572	if ( op0 == operation_blocked && op1 == operation_intersection )
	573	{
	574	tp.operations[0].is_collinear = true;
	575	}
	576	else if ( op0 == operation_intersection && op1 == operation_blocked )
	577	{
	578	tp.operations[1].is_collinear = true;
	579	}
	580	}
	581
7c673cae FG	582	*out++ = tp;
	583	}
	584
92f5a8d4 TL	585	static inline operations_pair operations_of_equal(int side_px_q2,
	586	int side_px_q1,
	587	int side_qk_q1)
7c673cae	588	{
92f5a8d4 TL	589	// If px (pi or pj) is collinear with qj-qk (q2), they continue collinearly.
92f5a8d4 TL	590	// This can be on either side of q1, or collinear
7c673cae FG	591	// The second condition checks if they do not continue
7c673cae FG	592	// oppositely
92f5a8d4	593	if (side_px_q2 == 0 && side_px_q1 == side_qk_q1)
7c673cae FG	594	{
	595	return std::make_pair(operation_continue, operation_continue);
	596	}
	597
	598	// If they turn to same side (not opposite sides)
92f5a8d4	599	if ( ! base_turn_handler::opposite(side_px_q1, side_qk_q1) )
7c673cae	600	{
92f5a8d4 TL	601	// If px is left of q2 or collinear: p: union, q: intersection
92f5a8d4 TL	602	if (side_px_q2 != -1 )
7c673cae FG	603	{
	604	return std::make_pair(operation_union, operation_intersection);
	605	}
	606	else
	607	{
	608	return std::make_pair(operation_intersection, operation_union);
	609	}
	610	}
	611	else
	612	{
	613	// They turn opposite sides. If p turns left (or collinear),
	614	// p: union, q: intersection
92f5a8d4	615	if (side_px_q1 != -1 )
7c673cae FG	616	{
	617	return std::make_pair(operation_union, operation_intersection);
	618	}
	619	else
	620	{
	621	return std::make_pair(operation_intersection, operation_union);
	622	}
	623	}
	624	}
	625
92f5a8d4 TL	626	static inline bool operations_both(operations_pair const& operations,
92f5a8d4 TL	627	operation_type const op)
7c673cae FG	628	{
	629	return operations.first == op && operations.second == op;
	630	}
	631
92f5a8d4 TL	632	static inline bool operations_combination(operations_pair const& operations,
	633	operation_type const op1,
	634	operation_type const op2)
7c673cae FG	635	{
	636	return ( operations.first == op1 && operations.second == op2 )
	637	\|\| ( operations.first == op2 && operations.second == op1 );
	638	}
	639	};
	640
	641	}} // namespace detail::overlay
	642	#endif // DOXYGEN_NO_DETAIL
	643
	644	}} // namespace boost::geometry
	645
	646	#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_FOR_ENDPOINT_HPP