detail/overlay/traverse.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_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP

#include <cstddef>

#include <boost/range.hpp>

#include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp>
#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/algorithms/num_points.hpp>
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/core/closure.hpp>
#include <boost/geometry/core/coordinate_dimension.hpp>
#include <boost/geometry/geometries/concepts/check.hpp>

#if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
    || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
    || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
#  include <string>
#  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
#  include <boost/geometry/io/wkt/wkt.hpp>
#endif

namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{

template <typename Turn, typename Operation>
#ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
inline void debug_traverse(Turn const& turn, Operation op,
                std::string const& header)
{
    std::cout << header
        << " at " << op.seg_id
        << " meth: " << method_char(turn.method)
        << " op: " << operation_char(op.operation)
        << " vis: " << visited_char(op.visited)
        << " of:  " << operation_char(turn.operations[0].operation)
        << operation_char(turn.operations[1].operation)
        << " " << geometry::wkt(turn.point)
        << std::endl;

    if (boost::contains(header, "Finished"))
    {
        std::cout << std::endl;
    }
}
#else
inline void debug_traverse(Turn const& , Operation, const char*)
{
}
#endif


template <typename Info, typename Turn>
inline void set_visited_for_continue(Info& info, Turn const& turn)
{
    // On "continue", set "visited" for ALL directions
    if (turn.operation == detail::overlay::operation_continue)
    {
        for (typename boost::range_iterator
            <
                typename Info::container_type
            >::type it = boost::begin(info.operations);
            it != boost::end(info.operations);
            ++it)
        {
            if (it->visited.none())
            {
                it->visited.set_visited();
            }
        }
    }
}


template
<
    bool Reverse1, bool Reverse2,
    typename GeometryOut,
    typename G1,
    typename G2,
    typename Turns,
    typename IntersectionInfo,
    typename RobustPolicy
>
inline bool assign_next_ip(G1 const& g1, G2 const& g2,
            Turns& turns,
            typename boost::range_iterator<Turns>::type& ip,
            GeometryOut& current_output,
            IntersectionInfo& info,
            segment_identifier& seg_id,
            RobustPolicy const& robust_policy)
{
    info.visited.set_visited();
    set_visited_for_continue(*ip, info);

    // If there is no next IP on this segment
    if (info.enriched.next_ip_index < 0)
    {
        if (info.enriched.travels_to_vertex_index < 0
            || info.enriched.travels_to_ip_index < 0)
        {
            return false;
        }

        BOOST_GEOMETRY_ASSERT(info.enriched.travels_to_vertex_index >= 0);
        BOOST_GEOMETRY_ASSERT(info.enriched.travels_to_ip_index >= 0);

        if (info.seg_id.source_index == 0)
        {
            geometry::copy_segments<Reverse1>(g1, info.seg_id,
                    info.enriched.travels_to_vertex_index,
                    robust_policy,
                    current_output);
        }
        else
        {
            geometry::copy_segments<Reverse2>(g2, info.seg_id,
                    info.enriched.travels_to_vertex_index,
                    robust_policy,
                    current_output);
        }
        seg_id = info.seg_id;
        ip = boost::begin(turns) + info.enriched.travels_to_ip_index;
    }
    else
    {
        ip = boost::begin(turns) + info.enriched.next_ip_index;
        seg_id = info.seg_id;
    }

    detail::overlay::append_no_dups_or_spikes(current_output, ip->point,
        robust_policy);

    return true;
}


inline bool select_source(operation_type operation,
                          signed_size_type source1,
                          signed_size_type source2)
{
    return (operation == operation_intersection && source1 != source2)
        || (operation == operation_union && source1 == source2)
        ;
}


template
<
    typename Turn,
    typename Iterator
>
inline bool select_next_ip(operation_type operation,
            Turn& turn,
            segment_identifier const& seg_id,
            Iterator& selected)
{
    if (turn.discarded)
    {
        return false;
    }

    bool has_tp = false;

    typedef typename std::iterator_traits
    <
        Iterator
    >::value_type operation_type;

    typename operation_type::comparable_distance_type
            max_remaining_distance = 0;

    selected = boost::end(turn.operations);
    for (Iterator it = boost::begin(turn.operations);
        it != boost::end(turn.operations);
        ++it)
    {
        if (it->visited.started())
        {
            selected = it;
            //std::cout << " RETURN";
            return true;
        }

        // In some cases there are two alternatives.
        // For "ii", take the other one (alternate)
        //           UNLESS the other one is already visited
        // For "uu", take the same one (see above);
        // For "cc", take either one, but if there is a starting one,
        //           take that one.
        if (   (it->operation == operation_continue
                && (! has_tp || it->visited.started()
                    )
                )
            || (it->operation == operation
                && ! it->visited.finished()
                && (! has_tp
                    || select_source(operation,
                            it->seg_id.source_index, seg_id.source_index)
                    )
                )
            )
        {
            if (it->operation == operation_continue)
            {
                max_remaining_distance = it->remaining_distance;
            }
            selected = it;
            debug_traverse(turn, *it, " Candidate");
            has_tp = true;
        }

        if (it->operation == operation_continue && has_tp)
        {
            if (it->remaining_distance > max_remaining_distance)
            {
                max_remaining_distance = it->remaining_distance;
                selected = it;
                debug_traverse(turn, *it, " Candidate override");
            }
        }
    }

    if (has_tp)
    {
       debug_traverse(turn, *selected, "  Accepted");
    }


    return has_tp;
}


/*!
    \brief Traverses through intersection points / geometries
    \ingroup overlay
 */
template
<
    bool Reverse1, bool Reverse2,
    typename Geometry1,
    typename Geometry2,
    typename Backtrack = backtrack_check_self_intersections<Geometry1, Geometry2>
>
class traverse
{
public :
    template <typename RobustPolicy, typename Turns, typename Rings>
    static inline void apply(Geometry1 const& geometry1,
                Geometry2 const& geometry2,
                detail::overlay::operation_type operation,
                RobustPolicy const& robust_policy,
                Turns& turns, Rings& rings)
    {
        typedef typename boost::range_value<Rings>::type ring_type;
        typedef typename boost::range_iterator<Turns>::type turn_iterator;
        typedef typename boost::range_value<Turns>::type turn_type;
        typedef typename boost::range_iterator
            <
                typename turn_type::container_type
            >::type turn_operation_iterator_type;

        std::size_t const min_num_points
                = core_detail::closure::minimum_ring_size
                        <
                            geometry::closure<ring_type>::value
                        >::value;

        std::size_t size_at_start = boost::size(rings);

        typename Backtrack::state_type state;
        do
        {
            state.reset();

            // Iterate through all unvisited points
            for (turn_iterator it = boost::begin(turns);
                state.good() && it != boost::end(turns);
                ++it)
            {
                // Skip discarded ones
                if (! (it->discarded || ! it->selectable_start || it->blocked()))
                {
                    for (turn_operation_iterator_type iit = boost::begin(it->operations);
                        state.good() && iit != boost::end(it->operations);
                        ++iit)
                    {
                        if (iit->visited.none()
                            && ! iit->visited.rejected()
                            && (iit->operation == operation
                                || iit->operation == detail::overlay::operation_continue)
                            )
                        {
                            set_visited_for_continue(*it, *iit);

                            ring_type current_output;
                            detail::overlay::append_no_dups_or_spikes(current_output,
                                it->point, robust_policy);

                            turn_iterator current = it;
                            turn_operation_iterator_type current_iit = iit;
                            segment_identifier current_seg_id;

                            if (! detail::overlay::assign_next_ip<Reverse1, Reverse2>(
                                        geometry1, geometry2,
                                        turns,
                                        current, current_output,
                                        *iit, current_seg_id,
                                        robust_policy))
                            {
                                Backtrack::apply(
                                    size_at_start,
                                    rings, current_output, turns, *current_iit,
                                    "No next IP",
                                    geometry1, geometry2, robust_policy, state);
                            }

                            if (! detail::overlay::select_next_ip(
                                            operation,
                                            *current,
                                            current_seg_id,
                                            current_iit))
                            {
                                Backtrack::apply(
                                    size_at_start,
                                    rings, current_output, turns, *iit,
                                    "Dead end at start",
                                    geometry1, geometry2, robust_policy, state);
                            }
                            else
                            {

                                iit->visited.set_started();
                                detail::overlay::debug_traverse(*it, *iit, "-> Started");
                                detail::overlay::debug_traverse(*current, *current_iit, "Selected  ");


                                typename boost::range_size<Turns>::type i = 0;

                                while (current_iit != iit && state.good())
                                {
                                    if (current_iit->visited.visited())
                                    {
                                        // It visits a visited node again, without passing the start node.
                                        // This makes it suspicious for endless loops
                                        Backtrack::apply(
                                            size_at_start,
                                            rings,  current_output, turns, *iit,
                                            "Visit again",
                                            geometry1, geometry2, robust_policy, state);
                                    }
                                    else
                                    {


                                        // We assume clockwise polygons only, non self-intersecting, closed.
                                        // However, the input might be different, and checking validity
                                        // is up to the library user.

                                        // Therefore we make here some sanity checks. If the input
                                        // violates the assumptions, the output polygon will not be correct
                                        // but the routine will stop and output the current polygon, and
                                        // will continue with the next one.

                                        // Below three reasons to stop.
                                        detail::overlay::assign_next_ip<Reverse1, Reverse2>(
                                            geometry1, geometry2,
                                            turns, current, current_output,
                                            *current_iit, current_seg_id,
                                            robust_policy);

                                        if (! detail::overlay::select_next_ip(
                                                    operation,
                                                    *current,
                                                    current_seg_id,
                                                    current_iit))
                                        {
                                            // Should not occur in valid (non-self-intersecting) polygons
                                            // Should not occur in self-intersecting polygons without spikes
                                            // Might occur in polygons with spikes
                                            Backtrack::apply(
                                                size_at_start,
                                                rings,  current_output, turns, *iit,
                                                "Dead end",
                                                geometry1, geometry2, robust_policy, state);
                                        }
                                        else
                                        {
                                            detail::overlay::debug_traverse(*current, *current_iit, "Selected  ");
                                        }

                                        if (i++ > 2 + 2 * turns.size())
                                        {
                                            // Sanity check: there may be never more loops
                                            // than turn points.
                                            // Turn points marked as "ii" can be visited twice.
                                            Backtrack::apply(
                                                size_at_start,
                                                rings,  current_output, turns, *iit,
                                                "Endless loop",
                                                geometry1, geometry2, robust_policy, state);
                                        }
                                    }
                                }

                                if (state.good())
                                {
                                    iit->visited.set_finished();
                                    detail::overlay::debug_traverse(*current, *iit, "->Finished");
                                    if (geometry::num_points(current_output) >= min_num_points)
                                    {
                                        clean_closing_dups_and_spikes(current_output, robust_policy);
                                        rings.push_back(current_output);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        } while (! state.good());
    }
};

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

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP