Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP
Chris@16: 
Chris@16: #include <cstddef>
Chris@16: 
Chris@16: #include <boost/range.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
Chris@16: #include <boost/geometry/algorithms/num_points.hpp>
Chris@16: #include <boost/geometry/core/access.hpp>
Chris@16: #include <boost/geometry/core/closure.hpp>
Chris@16: #include <boost/geometry/core/coordinate_dimension.hpp>
Chris@16: #include <boost/geometry/geometries/concepts/check.hpp>
Chris@16: 
Chris@16: #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
Chris@16:     || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
Chris@16:     || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
Chris@16: #  include <string>
Chris@16: #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
Chris@16: #  include <boost/geometry/io/wkt/wkt.hpp>
Chris@16: #endif
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail { namespace overlay
Chris@16: {
Chris@16: 
Chris@16: template <typename Turn, typename Operation>
Chris@16: #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
Chris@101: inline void debug_traverse(Turn const& turn, Operation op,
Chris@16:                 std::string const& header)
Chris@16: {
Chris@16:     std::cout << header
Chris@16:         << " at " << op.seg_id
Chris@16:         << " meth: " << method_char(turn.method)
Chris@16:         << " op: " << operation_char(op.operation)
Chris@16:         << " vis: " << visited_char(op.visited)
Chris@16:         << " of:  " << operation_char(turn.operations[0].operation)
Chris@16:         << operation_char(turn.operations[1].operation)
Chris@16:         << " " << geometry::wkt(turn.point)
Chris@16:         << std::endl;
Chris@16: 
Chris@16:     if (boost::contains(header, "Finished"))
Chris@16:     {
Chris@16:         std::cout << std::endl;
Chris@16:     }
Chris@16: }
Chris@16: #else
Chris@16: inline void debug_traverse(Turn const& , Operation, const char*)
Chris@16: {
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: template <typename Info, typename Turn>
Chris@16: inline void set_visited_for_continue(Info& info, Turn const& turn)
Chris@16: {
Chris@16:     // On "continue", set "visited" for ALL directions
Chris@16:     if (turn.operation == detail::overlay::operation_continue)
Chris@16:     {
Chris@16:         for (typename boost::range_iterator
Chris@16:             <
Chris@16:                 typename Info::container_type
Chris@16:             >::type it = boost::begin(info.operations);
Chris@16:             it != boost::end(info.operations);
Chris@16:             ++it)
Chris@16:         {
Chris@16:             if (it->visited.none())
Chris@16:             {
Chris@16:                 it->visited.set_visited();
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     bool Reverse1, bool Reverse2,
Chris@16:     typename GeometryOut,
Chris@16:     typename G1,
Chris@16:     typename G2,
Chris@16:     typename Turns,
Chris@101:     typename IntersectionInfo,
Chris@101:     typename RobustPolicy
Chris@16: >
Chris@16: inline bool assign_next_ip(G1 const& g1, G2 const& g2,
Chris@16:             Turns& turns,
Chris@16:             typename boost::range_iterator<Turns>::type& ip,
Chris@16:             GeometryOut& current_output,
Chris@16:             IntersectionInfo& info,
Chris@101:             segment_identifier& seg_id,
Chris@101:             RobustPolicy const& robust_policy)
Chris@16: {
Chris@16:     info.visited.set_visited();
Chris@16:     set_visited_for_continue(*ip, info);
Chris@16: 
Chris@16:     // If there is no next IP on this segment
Chris@16:     if (info.enriched.next_ip_index < 0)
Chris@16:     {
Chris@101:         if (info.enriched.travels_to_vertex_index < 0
Chris@16:             || info.enriched.travels_to_ip_index < 0)
Chris@16:         {
Chris@16:             return false;
Chris@16:         }
Chris@16: 
Chris@16:         BOOST_ASSERT(info.enriched.travels_to_vertex_index >= 0);
Chris@16:         BOOST_ASSERT(info.enriched.travels_to_ip_index >= 0);
Chris@16: 
Chris@16:         if (info.seg_id.source_index == 0)
Chris@16:         {
Chris@16:             geometry::copy_segments<Reverse1>(g1, info.seg_id,
Chris@16:                     info.enriched.travels_to_vertex_index,
Chris@101:                     robust_policy,
Chris@16:                     current_output);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             geometry::copy_segments<Reverse2>(g2, info.seg_id,
Chris@16:                     info.enriched.travels_to_vertex_index,
Chris@101:                     robust_policy,
Chris@16:                     current_output);
Chris@16:         }
Chris@16:         seg_id = info.seg_id;
Chris@16:         ip = boost::begin(turns) + info.enriched.travels_to_ip_index;
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@16:         ip = boost::begin(turns) + info.enriched.next_ip_index;
Chris@16:         seg_id = info.seg_id;
Chris@16:     }
Chris@16: 
Chris@101:     detail::overlay::append_no_dups_or_spikes(current_output, ip->point,
Chris@101:         robust_policy);
Chris@16: 
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@101: inline bool select_source(operation_type operation,
Chris@101:                           signed_index_type source1,
Chris@101:                           signed_index_type source2)
Chris@16: {
Chris@16:     return (operation == operation_intersection && source1 != source2)
Chris@16:         || (operation == operation_union && source1 == source2)
Chris@16:         ;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: template
Chris@16: <
Chris@16:     typename Turn,
Chris@16:     typename Iterator
Chris@16: >
Chris@16: inline bool select_next_ip(operation_type operation,
Chris@16:             Turn& turn,
Chris@16:             segment_identifier const& seg_id,
Chris@16:             Iterator& selected)
Chris@16: {
Chris@16:     if (turn.discarded)
Chris@16:     {
Chris@16:         return false;
Chris@16:     }
Chris@16:     bool has_tp = false;
Chris@16:     selected = boost::end(turn.operations);
Chris@16:     for (Iterator it = boost::begin(turn.operations);
Chris@16:         it != boost::end(turn.operations);
Chris@16:         ++it)
Chris@16:     {
Chris@16:         if (it->visited.started())
Chris@16:         {
Chris@16:             selected = it;
Chris@16:             //std::cout << " RETURN";
Chris@16:             return true;
Chris@16:         }
Chris@16: 
Chris@16:         // In some cases there are two alternatives.
Chris@16:         // For "ii", take the other one (alternate)
Chris@16:         //           UNLESS the other one is already visited
Chris@16:         // For "uu", take the same one (see above);
Chris@16:         // For "cc", take either one, but if there is a starting one,
Chris@16:         //           take that one.
Chris@16:         if (   (it->operation == operation_continue
Chris@16:                 && (! has_tp || it->visited.started()
Chris@16:                     )
Chris@16:                 )
Chris@16:             || (it->operation == operation
Chris@16:                 && ! it->visited.finished()
Chris@16:                 && (! has_tp
Chris@16:                     || select_source(operation,
Chris@16:                             it->seg_id.source_index, seg_id.source_index)
Chris@16:                     )
Chris@16:                 )
Chris@16:             )
Chris@16:         {
Chris@16:             selected = it;
Chris@16:             debug_traverse(turn, *it, " Candidate");
Chris@16:             has_tp = true;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     if (has_tp)
Chris@16:     {
Chris@16:        debug_traverse(turn, *selected, "  Accepted");
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     return has_tp;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: /*!
Chris@16:     \brief Traverses through intersection points / geometries
Chris@16:     \ingroup overlay
Chris@16:  */
Chris@16: template
Chris@16: <
Chris@16:     bool Reverse1, bool Reverse2,
Chris@16:     typename Geometry1,
Chris@16:     typename Geometry2,
Chris@16:     typename Backtrack = backtrack_check_self_intersections<Geometry1, Geometry2>
Chris@16: >
Chris@16: class traverse
Chris@16: {
Chris@16: public :
Chris@101:     template <typename RobustPolicy, typename Turns, typename Rings>
Chris@16:     static inline void apply(Geometry1 const& geometry1,
Chris@16:                 Geometry2 const& geometry2,
Chris@16:                 detail::overlay::operation_type operation,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@16:                 Turns& turns, Rings& rings)
Chris@16:     {
Chris@16:         typedef typename boost::range_value<Rings>::type ring_type;
Chris@16:         typedef typename boost::range_iterator<Turns>::type turn_iterator;
Chris@16:         typedef typename boost::range_value<Turns>::type turn_type;
Chris@16:         typedef typename boost::range_iterator
Chris@16:             <
Chris@16:                 typename turn_type::container_type
Chris@16:             >::type turn_operation_iterator_type;
Chris@16: 
Chris@16:         std::size_t const min_num_points
Chris@16:                 = core_detail::closure::minimum_ring_size
Chris@16:                         <
Chris@16:                             geometry::closure<ring_type>::value
Chris@16:                         >::value;
Chris@16: 
Chris@16:         std::size_t size_at_start = boost::size(rings);
Chris@16: 
Chris@16:         typename Backtrack::state_type state;
Chris@16:         do
Chris@16:         {
Chris@16:             state.reset();
Chris@16: 
Chris@16:             // Iterate through all unvisited points
Chris@16:             for (turn_iterator it = boost::begin(turns);
Chris@16:                 state.good() && it != boost::end(turns);
Chris@16:                 ++it)
Chris@16:             {
Chris@16:                 // Skip discarded ones
Chris@101:                 if (! (it->discarded || ! it->selectable_start || it->blocked()))
Chris@16:                 {
Chris@16:                     for (turn_operation_iterator_type iit = boost::begin(it->operations);
Chris@16:                         state.good() && iit != boost::end(it->operations);
Chris@16:                         ++iit)
Chris@16:                     {
Chris@16:                         if (iit->visited.none()
Chris@16:                             && ! iit->visited.rejected()
Chris@16:                             && (iit->operation == operation
Chris@16:                                 || iit->operation == detail::overlay::operation_continue)
Chris@16:                             )
Chris@16:                         {
Chris@16:                             set_visited_for_continue(*it, *iit);
Chris@16: 
Chris@16:                             ring_type current_output;
Chris@101:                             detail::overlay::append_no_dups_or_spikes(current_output,
Chris@101:                                 it->point, robust_policy);
Chris@16: 
Chris@16:                             turn_iterator current = it;
Chris@16:                             turn_operation_iterator_type current_iit = iit;
Chris@16:                             segment_identifier current_seg_id;
Chris@16: 
Chris@16:                             if (! detail::overlay::assign_next_ip<Reverse1, Reverse2>(
Chris@16:                                         geometry1, geometry2,
Chris@16:                                         turns,
Chris@16:                                         current, current_output,
Chris@101:                                         *iit, current_seg_id,
Chris@101:                                         robust_policy))
Chris@16:                             {
Chris@16:                                 Backtrack::apply(
Chris@101:                                     size_at_start,
Chris@16:                                     rings, current_output, turns, *current_iit,
Chris@16:                                     "No next IP",
Chris@101:                                     geometry1, geometry2, robust_policy, state);
Chris@16:                             }
Chris@16: 
Chris@16:                             if (! detail::overlay::select_next_ip(
Chris@16:                                             operation,
Chris@16:                                             *current,
Chris@16:                                             current_seg_id,
Chris@16:                                             current_iit))
Chris@16:                             {
Chris@16:                                 Backtrack::apply(
Chris@101:                                     size_at_start,
Chris@16:                                     rings, current_output, turns, *iit,
Chris@16:                                     "Dead end at start",
Chris@101:                                     geometry1, geometry2, robust_policy, state);
Chris@16:                             }
Chris@16:                             else
Chris@16:                             {
Chris@16: 
Chris@16:                                 iit->visited.set_started();
Chris@16:                                 detail::overlay::debug_traverse(*it, *iit, "-> Started");
Chris@16:                                 detail::overlay::debug_traverse(*current, *current_iit, "Selected  ");
Chris@16: 
Chris@16: 
Chris@101:                                 typename boost::range_size<Turns>::type i = 0;
Chris@16: 
Chris@16:                                 while (current_iit != iit && state.good())
Chris@16:                                 {
Chris@16:                                     if (current_iit->visited.visited())
Chris@16:                                     {
Chris@16:                                         // It visits a visited node again, without passing the start node.
Chris@16:                                         // This makes it suspicious for endless loops
Chris@16:                                         Backtrack::apply(
Chris@101:                                             size_at_start,
Chris@16:                                             rings,  current_output, turns, *iit,
Chris@16:                                             "Visit again",
Chris@101:                                             geometry1, geometry2, robust_policy, state);
Chris@16:                                     }
Chris@16:                                     else
Chris@16:                                     {
Chris@16: 
Chris@16: 
Chris@16:                                         // We assume clockwise polygons only, non self-intersecting, closed.
Chris@16:                                         // However, the input might be different, and checking validity
Chris@16:                                         // is up to the library user.
Chris@16: 
Chris@16:                                         // Therefore we make here some sanity checks. If the input
Chris@16:                                         // violates the assumptions, the output polygon will not be correct
Chris@16:                                         // but the routine will stop and output the current polygon, and
Chris@16:                                         // will continue with the next one.
Chris@16: 
Chris@16:                                         // Below three reasons to stop.
Chris@16:                                         detail::overlay::assign_next_ip<Reverse1, Reverse2>(
Chris@16:                                             geometry1, geometry2,
Chris@16:                                             turns, current, current_output,
Chris@101:                                             *current_iit, current_seg_id,
Chris@101:                                             robust_policy);
Chris@16: 
Chris@16:                                         if (! detail::overlay::select_next_ip(
Chris@16:                                                     operation,
Chris@16:                                                     *current,
Chris@16:                                                     current_seg_id,
Chris@16:                                                     current_iit))
Chris@16:                                         {
Chris@16:                                             // Should not occur in valid (non-self-intersecting) polygons
Chris@16:                                             // Should not occur in self-intersecting polygons without spikes
Chris@16:                                             // Might occur in polygons with spikes
Chris@16:                                             Backtrack::apply(
Chris@101:                                                 size_at_start,
Chris@16:                                                 rings,  current_output, turns, *iit,
Chris@16:                                                 "Dead end",
Chris@101:                                                 geometry1, geometry2, robust_policy, state);
Chris@16:                                         }
Chris@16:                                         else
Chris@16:                                         {
Chris@16:                                             detail::overlay::debug_traverse(*current, *current_iit, "Selected  ");
Chris@16:                                         }
Chris@16: 
Chris@16:                                         if (i++ > 2 + 2 * turns.size())
Chris@16:                                         {
Chris@16:                                             // Sanity check: there may be never more loops
Chris@16:                                             // than turn points.
Chris@16:                                             // Turn points marked as "ii" can be visited twice.
Chris@16:                                             Backtrack::apply(
Chris@101:                                                 size_at_start,
Chris@16:                                                 rings,  current_output, turns, *iit,
Chris@16:                                                 "Endless loop",
Chris@101:                                                 geometry1, geometry2, robust_policy, state);
Chris@16:                                         }
Chris@16:                                     }
Chris@16:                                 }
Chris@16: 
Chris@16:                                 if (state.good())
Chris@16:                                 {
Chris@16:                                     iit->visited.set_finished();
Chris@16:                                     detail::overlay::debug_traverse(*current, *iit, "->Finished");
Chris@16:                                     if (geometry::num_points(current_output) >= min_num_points)
Chris@16:                                     {
Chris@101:                                         clean_closing_dups_and_spikes(current_output, robust_policy);
Chris@16:                                         rings.push_back(current_output);
Chris@16:                                     }
Chris@16:                                 }
Chris@16:                             }
Chris@16:                         }
Chris@16:                     }
Chris@16:                 }
Chris@16:             }
Chris@16:         } while (! state.good());
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: }} // namespace detail::overlay
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSE_HPP