path: root/boost/geometry/algorithms/detail/get_left_turns.hpp

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

// Copyright (c) 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_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP

#include <boost/geometry/iterators/ever_circling_iterator.hpp>

namespace boost { namespace geometry
{


#ifndef DOXYGEN_NO_DETAIL
namespace detail
{

// TODO: move this to /util/
template <typename T>
static inline std::pair<T, T> ordered_pair(T const& first, T const& second)
{
    return first < second ? std::make_pair(first, second) : std::make_pair(second, first);
}

template <typename AngleInfo>
inline void debug_left_turn(AngleInfo const& ai, AngleInfo const& previous)
{
#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
    std::cout << "Angle: " << (ai.incoming ? "i" : "o") 
        << " " << si(ai.seg_id) 
        << " " << (math::r2d * (ai.angle) )
        << " turn: " << ai.turn_index << "[" << ai.operation_index << "]"
        ;

    if (ai.turn_index != previous.turn_index
        || ai.operation_index != previous.operation_index)
    {
        std::cout << " diff: " << math::r2d * math::abs(previous.angle - ai.angle);
    }
    std::cout << std::endl;
#endif
}

template <typename AngleInfo>
inline void debug_left_turn(std::string const& caption, AngleInfo const& ai, AngleInfo const& previous,
            int code = -99, int code2 = -99, int code3 = -99, int code4 = -99)
{
#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
    std::cout << " " << caption
            << " turn: " << ai.turn_index << "[" << ai.operation_index << "]"
            << " " << si(ai.seg_id) 
            << " " << (ai.incoming ? "i" : "o") 
            << " " << (math::r2d * (ai.angle) )
            << " turn: " << previous.turn_index << "[" << previous.operation_index << "]"
            << " " << si(previous.seg_id) 
            << " " << (previous.incoming ? "i" : "o") 
            << " " << (math::r2d * (previous.angle) )
            ;

    if (code != -99)
    {
        std::cout << " code: " << code << " , " << code2 << " , " << code3 << " , " << code4;
    }
    std::cout << std::endl;
#endif
}


template <typename Operation>
inline bool include_operation(Operation const& op, 
                segment_identifier const& outgoing_seg_id,
                segment_identifier const& incoming_seg_id)
{
    return op.seg_id == outgoing_seg_id
        && op.other_id == incoming_seg_id
        && (op.operation == detail::overlay::operation_union
            ||op.operation == detail::overlay::operation_continue)
            ;
}

template <typename Turn>
inline bool process_include(segment_identifier const& outgoing_seg_id, segment_identifier const& incoming_seg_id,
                int turn_index, Turn& turn,
                std::set<int>& keep_indices, int priority)
{
    bool result = false;
    for (int i = 0; i < 2; i++)
    {
        if (include_operation(turn.operations[i], outgoing_seg_id, incoming_seg_id))
        {
            turn.operations[i].include_in_occupation_map = true;
            if (priority > turn.priority)
            {
                turn.priority = priority;
            }
            keep_indices.insert(turn_index);
            result = true;
        }
    }
    return result;
}

template <typename AngleInfo, typename Turns, typename TurnSegmentIndices>
inline bool include_left_turn_of_all(
                AngleInfo const& outgoing, AngleInfo const& incoming,
                Turns& turns, TurnSegmentIndices const& turn_segment_indices,
                std::set<int>& keep_indices, int priority)
{
    segment_identifier const& outgoing_seg_id = turns[outgoing.turn_index].operations[outgoing.operation_index].seg_id;
    segment_identifier const& incoming_seg_id = turns[incoming.turn_index].operations[incoming.operation_index].seg_id;

    if (outgoing.turn_index == incoming.turn_index)
    {
        return process_include(outgoing_seg_id, incoming_seg_id, outgoing.turn_index, turns[outgoing.turn_index], keep_indices, priority);
    }

    bool result = false;
    std::pair<segment_identifier, segment_identifier> pair = ordered_pair(outgoing_seg_id, incoming_seg_id);
    auto it = turn_segment_indices.find(pair);
    if (it != turn_segment_indices.end())
    {
        for (auto sit = it->second.begin(); sit != it->second.end(); ++sit)
        {
            if (process_include(outgoing_seg_id, incoming_seg_id, *sit, turns[*sit], keep_indices, priority))
            {
                result = true;
            }
        }
    }
    return result;
}

template <std::size_t Index, typename Turn>
inline bool corresponds(Turn const& turn, segment_identifier const& seg_id)
{
    return turn.operations[Index].operation == detail::overlay::operation_union
        && turn.operations[Index].seg_id == seg_id;
}


template <typename Turns, typename TurnSegmentIndices>
inline bool prefer_by_other(Turns const& turns,
            TurnSegmentIndices const& turn_segment_indices,
            std::set<int>& indices)
{
    std::map<segment_identifier, int> map;
    for (auto sit = indices.begin(); sit != indices.end(); ++sit)
    {
        map[turns[*sit].operations[0].seg_id]++;
        map[turns[*sit].operations[1].seg_id]++;
    }

    std::set<segment_identifier> segment_occuring_once;
    for (auto mit = map.begin(); mit != map.end(); ++mit)
    {
        if (mit->second == 1)
        {
            segment_occuring_once.insert(mit->first);
        }
#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_PREFER
        std::cout << si(mit->first) << " " << mit->second << std::endl;
#endif
    }

    if (segment_occuring_once.size() == 2)
    {
        // Try to find within all turns a turn with these two segments

        std::set<segment_identifier>::const_iterator soo_it = segment_occuring_once.begin();
        segment_identifier front = *soo_it;
        soo_it++;
        segment_identifier back = *soo_it;

        std::pair<segment_identifier, segment_identifier> pair = ordered_pair(front, back);
        auto it = turn_segment_indices.find(pair);
        if (it != turn_segment_indices.end())
        {
            // debug_turns_by_indices("Found", it->second);
            // Check which is the union/continue
            segment_identifier good;
            for (auto sit = it->second.begin(); sit != it->second.end(); ++sit)
            {
                if (turns[*sit].operations[0].operation == detail::overlay::operation_union)
                {
                    good = turns[*sit].operations[0].seg_id;
                }
                else if (turns[*sit].operations[1].operation == detail::overlay::operation_union)
                {
                    good = turns[*sit].operations[1].seg_id;
                }
            }

#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_PREFER
            std::cout << "Good: " << si(good) << std::endl;
#endif

            // Find in indexes-to-keep this segment with the union. Discard the other one
            std::set<int> ok_indices;
            for (auto sit = indices.begin(); sit != indices.end(); ++sit)
            {
                if (corresponds<0>(turns[*sit], good) || corresponds<1>(turns[*sit], good))
                {
                    ok_indices.insert(*sit);
                }
            }
            if (ok_indices.size() > 0 && ok_indices.size() < indices.size())
            {
                indices = ok_indices;
                std::cout << "^";
                return true;
            }
        }
    }
    return false;
}

template <typename Turns>
inline void prefer_by_priority(Turns const& turns, std::set<int>& indices)
{
    // Find max prio
    int min_prio = 1024, max_prio = 0;
    for (auto sit = indices.begin(); sit != indices.end(); ++sit)
    {
        if (turns[*sit].priority > max_prio)
        {
            max_prio = turns[*sit].priority;
        }
        if (turns[*sit].priority < min_prio)
        {
            min_prio = turns[*sit].priority;
        }
    }

    if (min_prio == max_prio)
    {
        return;
    }

    // Only keep indices with high prio
    std::set<int> ok_indices;
    for (auto sit = indices.begin(); sit != indices.end(); ++sit)
    {
        if (turns[*sit].priority >= max_prio)
        {
            ok_indices.insert(*sit);
        }
    }
    if (ok_indices.size() > 0 && ok_indices.size() < indices.size())
    {
        indices = ok_indices;
        std::cout << "%";
    }
}

template <typename AngleInfo, typename Angles, typename Turns, typename TurnSegmentIndices>
inline void calculate_left_turns(Angles const& angles, 
                Turns& turns, TurnSegmentIndices const& turn_segment_indices,
                std::set<int>& keep_indices)
{
    bool debug_indicate_size = false;

    typedef typename strategy::side::services::default_strategy
        <
            typename cs_tag<typename AngleInfo::point_type>::type
        >::type side_strategy;

    std::size_t i = 0;
    std::size_t n = boost::size(angles);

    typedef geometry::ever_circling_range_iterator<Angles const> circling_iterator;
    circling_iterator cit(angles);

    debug_left_turn(*cit, *cit);
    for(circling_iterator prev = cit++; i < n; prev = cit++, i++)
    {
        debug_left_turn(*cit, *prev);

        bool const include = ! geometry::math::equals(prev->angle, cit->angle)
            && ! prev->incoming
            && cit->incoming;

        if (include)
        {
            // Go back to possibly include more same left outgoing angles:
            // Because we check on side too we can take a large "epsilon"
            circling_iterator back = prev - 1;

            typename AngleInfo::angle_type eps = 0.00001;
            int b = 1;
            for(std::size_t d = 0; 
                    math::abs(prev->angle - back->angle) < eps 
                        && ! back->incoming 
                        && d < n;
                d++)
            {
                --back;
                ++b;
            }

            // Same but forward to possibly include more incoming angles
            int f = 1;
            circling_iterator forward = cit + 1;
            for(std::size_t d = 0;
                    math::abs(cit->angle - forward->angle) < eps 
                        && forward->incoming 
                        && d < n;
                    d++)
            {
                ++forward;
                ++f;
            }

#ifdef BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
            std::cout << "HANDLE " << b << "/" << f << " ANGLES" << std::endl;
#endif
            for(circling_iterator bit = prev; bit != back; --bit)
            {
                int code = side_strategy::apply(bit->direction_point, prev->intersection_point, prev->direction_point);
                int code2 = side_strategy::apply(prev->direction_point, bit->intersection_point, bit->direction_point);
                for(circling_iterator fit = cit; fit != forward; ++fit)
                {
                    int code3 = side_strategy::apply(fit->direction_point, cit->intersection_point, cit->direction_point);
                    int code4 = side_strategy::apply(cit->direction_point, fit->intersection_point, fit->direction_point);

                    int priority = 2;
                    if (code == -1 && code2 == 1)
                    {
                        // This segment is lying right of the other one.
                        // Cannot ignore it (because of robustness, see a.o. #rt_p21 from unit test).
                        // But if we find more we can prefer later by priority
                        // (a.o. necessary for #rt_o2 from unit test)
                        priority = 1;
                    }

                    bool included = include_left_turn_of_all(*bit, *fit, turns, turn_segment_indices, keep_indices, priority);
                    debug_left_turn(included ? "KEEP" : "SKIP", *fit, *bit, code, code2, code3, code4);
                }
            }
        }
    }

    if (debug_indicate_size)
    {
        std::cout << " size=" << keep_indices.size();
    }

    if (keep_indices.size() >= 2)
    {
        prefer_by_other(turns, turn_segment_indices, keep_indices);
    }
    if (keep_indices.size() >= 2)
    {
            prefer_by_priority(turns, keep_indices);
    }
}

} // namespace detail
#endif // DOXYGEN_NO_DETAIL


}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_GET_LEFT_TURNS_HPP