Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@101: // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
Chris@101: 
Chris@101: // This file was modified by Oracle on 2014.
Chris@101: // Modifications copyright (c) 2014 Oracle and/or its affiliates.
Chris@101: 
Chris@101: // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
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_FOLLOW_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
Chris@16: 
Chris@16: #include <cstddef>
Chris@16: 
Chris@16: #include <boost/range.hpp>
Chris@16: #include <boost/mpl/assert.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/detail/point_on_border.hpp>
Chris@16: #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.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: 
Chris@16: #include <boost/geometry/algorithms/covered_by.hpp>
Chris@101: #include <boost/geometry/algorithms/clear.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail { namespace overlay
Chris@16: {
Chris@16: 
Chris@16: namespace following
Chris@16: {
Chris@101: 
Chris@16: template <typename Turn, typename Operation>
Chris@16: static inline bool is_entering(Turn const& /* TODO remove this parameter */, Operation const& op)
Chris@16: {
Chris@16:     // (Blocked means: blocked for polygon/polygon intersection, because
Chris@16:     // they are reversed. But for polygon/line it is similar to continue)
Chris@16:     return op.operation == operation_intersection
Chris@16:         || op.operation == operation_continue
Chris@16:         || op.operation == operation_blocked
Chris@16:         ;
Chris@16: }
Chris@16: 
Chris@101: template
Chris@16: <
Chris@101:     typename Turn,
Chris@101:     typename Operation,
Chris@101:     typename LineString,
Chris@16:     typename Polygon
Chris@16: >
Chris@101: static inline bool last_covered_by(Turn const& turn, Operation const& op,
Chris@16:                 LineString const& linestring, Polygon const& polygon)
Chris@16: {
Chris@101:     // Check any point between the this one and the first IP
Chris@16:     typedef typename geometry::point_type<LineString>::type point_type;
Chris@16:     point_type point_in_between;
Chris@16:     detail::point_on_border::midpoint_helper
Chris@16:         <
Chris@16:             point_type,
Chris@16:             0, dimension<point_type>::value
Chris@101:         >::apply(point_in_between, *(::boost::begin(linestring) + op.seg_id.segment_index), turn.point);
Chris@16: 
Chris@16:     return geometry::covered_by(point_in_between, polygon);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@101: template
Chris@16: <
Chris@101:     typename Turn,
Chris@101:     typename Operation,
Chris@101:     typename LineString,
Chris@16:     typename Polygon
Chris@16: >
Chris@101: static inline bool is_leaving(Turn const& turn, Operation const& op,
Chris@101:                 bool entered, bool first,
Chris@16:                 LineString const& linestring, Polygon const& polygon)
Chris@16: {
Chris@16:     if (op.operation == operation_union)
Chris@16:     {
Chris@101:         return entered
Chris@16:             || turn.method == method_crosses
Chris@16:             || (first && last_covered_by(turn, op, linestring, polygon))
Chris@16:             ;
Chris@16:     }
Chris@16:     return false;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@101: template
Chris@16: <
Chris@101:     typename Turn,
Chris@101:     typename Operation,
Chris@101:     typename LineString,
Chris@16:     typename Polygon
Chris@16: >
Chris@101: static inline bool is_staying_inside(Turn const& turn, Operation const& op,
Chris@101:                 bool entered, bool first,
Chris@16:                 LineString const& linestring, Polygon const& polygon)
Chris@16: {
Chris@16:     if (turn.method == method_crosses)
Chris@16:     {
Chris@101:         // The normal case, this is completely covered with entering/leaving
Chris@16:         // so stay out of this time consuming "covered_by"
Chris@16:         return false;
Chris@16:     }
Chris@16: 
Chris@16:     if (is_entering(turn, op))
Chris@16:     {
Chris@16:         return entered || (first && last_covered_by(turn, op, linestring, polygon));
Chris@16:     }
Chris@16: 
Chris@16:     return false;
Chris@16: }
Chris@16: 
Chris@101: template
Chris@16: <
Chris@101:     typename Turn,
Chris@101:     typename Operation,
Chris@101:     typename Linestring,
Chris@16:     typename Polygon
Chris@16: >
Chris@16: static inline bool was_entered(Turn const& turn, Operation const& op, bool first,
Chris@16:                 Linestring const& linestring, Polygon const& polygon)
Chris@16: {
Chris@16:     if (first && (turn.method == method_collinear || turn.method == method_equal))
Chris@16:     {
Chris@16:         return last_covered_by(turn, op, linestring, polygon);
Chris@16:     }
Chris@16:     return false;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // Template specialization structure to call the right actions for the right type
Chris@101: template <overlay_type OverlayType, bool RemoveSpikes = true>
Chris@16: struct action_selector
Chris@16: {
Chris@16:     // If you get here the overlay type is not intersection or difference
Chris@16:     // BOOST_MPL_ASSERT(false);
Chris@16: };
Chris@16: 
Chris@16: // Specialization for intersection, containing the implementation
Chris@101: template <bool RemoveSpikes>
Chris@101: struct action_selector<overlay_intersection, RemoveSpikes>
Chris@16: {
Chris@16:     template
Chris@16:     <
Chris@101:         typename OutputIterator,
Chris@101:         typename LineStringOut,
Chris@101:         typename LineString,
Chris@101:         typename Point,
Chris@101:         typename Operation,
Chris@101:         typename RobustPolicy
Chris@16:     >
Chris@16:     static inline void enter(LineStringOut& current_piece,
Chris@101:                 LineString const& ,
Chris@16:                 segment_identifier& segment_id,
Chris@101:                 signed_index_type , Point const& point,
Chris@101:                 Operation const& operation,
Chris@101:                 RobustPolicy const& ,
Chris@101:                 OutputIterator& )
Chris@16:     {
Chris@16:         // On enter, append the intersection point and remember starting point
Chris@101:         // TODO: we don't check on spikes for linestrings (?). Consider this.
Chris@16:         detail::overlay::append_no_duplicates(current_piece, point);
Chris@16:         segment_id = operation.seg_id;
Chris@16:     }
Chris@16: 
Chris@16:     template
Chris@16:     <
Chris@101:         typename OutputIterator,
Chris@101:         typename LineStringOut,
Chris@101:         typename LineString,
Chris@101:         typename Point,
Chris@101:         typename Operation,
Chris@101:         typename RobustPolicy
Chris@16:     >
Chris@16:     static inline void leave(LineStringOut& current_piece,
Chris@16:                 LineString const& linestring,
Chris@16:                 segment_identifier& segment_id,
Chris@101:                 signed_index_type index, Point const& point,
Chris@101:                 Operation const& ,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@101:                 OutputIterator& out)
Chris@16:     {
Chris@16:         // On leave, copy all segments from starting point, append the intersection point
Chris@16:         // and add the output piece
Chris@101:         detail::copy_segments::copy_segments_linestring
Chris@101:             <
Chris@101:                 false, RemoveSpikes
Chris@101:             >::apply(linestring, segment_id, index, robust_policy, current_piece);
Chris@16:         detail::overlay::append_no_duplicates(current_piece, point);
Chris@101:         if (::boost::size(current_piece) > 1)
Chris@16:         {
Chris@16:             *out++ = current_piece;
Chris@16:         }
Chris@101: 
Chris@101:         geometry::clear(current_piece);
Chris@101:     }
Chris@101: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename OutputIterator,
Chris@101:         typename LineStringOut,
Chris@101:         typename LineString,
Chris@101:         typename Point,
Chris@101:         typename Operation
Chris@101:     >
Chris@101:     static inline void isolated_point(LineStringOut&,
Chris@101:                 LineString const&,
Chris@101:                 segment_identifier&,
Chris@101:                 signed_index_type, Point const& point,
Chris@101:                 Operation const& , OutputIterator& out)
Chris@101:     {
Chris@101:         LineStringOut isolated_point_ls;
Chris@101:         geometry::append(isolated_point_ls, point);
Chris@101: 
Chris@101: #ifndef BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
Chris@101:         geometry::append(isolated_point_ls, point);
Chris@101: #endif // BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
Chris@101: 
Chris@101:         *out++ = isolated_point_ls;
Chris@16:     }
Chris@16: 
Chris@16:     static inline bool is_entered(bool entered)
Chris@16:     {
Chris@16:         return entered;
Chris@16:     }
Chris@16: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename Point,
Chris@101:         typename Geometry,
Chris@101:         typename RobustPolicy
Chris@101:     >
Chris@101:     static inline bool included(Point const& point,
Chris@101:             Geometry const& geometry,
Chris@101:             RobustPolicy const& )
Chris@16:     {
Chris@16:         return geometry::covered_by(point, geometry);
Chris@16:     }
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: // Specialization for difference, which reverses these actions
Chris@101: template <bool RemoveSpikes>
Chris@101: struct action_selector<overlay_difference, RemoveSpikes>
Chris@16: {
Chris@101:     typedef action_selector<overlay_intersection, RemoveSpikes> normal_action;
Chris@16: 
Chris@16:     template
Chris@16:     <
Chris@101:         typename OutputIterator,
Chris@101:         typename LineStringOut,
Chris@101:         typename LineString,
Chris@101:         typename Point,
Chris@101:         typename Operation,
Chris@101:         typename RobustPolicy
Chris@16:     >
Chris@101:     static inline void enter(LineStringOut& current_piece,
Chris@101:                 LineString const& linestring,
Chris@101:                 segment_identifier& segment_id,
Chris@101:                 signed_index_type index, Point const& point,
Chris@101:                 Operation const& operation,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@101:                 OutputIterator& out)
Chris@16:     {
Chris@101:         normal_action::leave(current_piece, linestring, segment_id, index,
Chris@101:                     point, operation, robust_policy, out);
Chris@16:     }
Chris@16: 
Chris@16:     template
Chris@16:     <
Chris@101:         typename OutputIterator,
Chris@101:         typename LineStringOut,
Chris@101:         typename LineString,
Chris@101:         typename Point,
Chris@101:         typename Operation,
Chris@101:         typename RobustPolicy
Chris@16:     >
Chris@16:     static inline void leave(LineStringOut& current_piece,
Chris@16:                 LineString const& linestring,
Chris@16:                 segment_identifier& segment_id,
Chris@101:                 signed_index_type index, Point const& point,
Chris@101:                 Operation const& operation,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@101:                 OutputIterator& out)
Chris@16:     {
Chris@16:         normal_action::enter(current_piece, linestring, segment_id, index,
Chris@101:                     point, operation, robust_policy, out);
Chris@101:     }
Chris@101: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename OutputIterator,
Chris@101:         typename LineStringOut,
Chris@101:         typename LineString,
Chris@101:         typename Point,
Chris@101:         typename Operation
Chris@101:     >
Chris@101:     static inline void isolated_point(LineStringOut&,
Chris@101:                 LineString const&,
Chris@101:                 segment_identifier&,
Chris@101:                 signed_index_type, Point const&,
Chris@101:                 Operation const&, OutputIterator&)
Chris@101:     {
Chris@16:     }
Chris@16: 
Chris@16:     static inline bool is_entered(bool entered)
Chris@16:     {
Chris@16:         return ! normal_action::is_entered(entered);
Chris@16:     }
Chris@16: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename Point,
Chris@101:         typename Geometry,
Chris@101:         typename RobustPolicy
Chris@101:     >
Chris@101:     static inline bool included(Point const& point,
Chris@101:         Geometry const& geometry,
Chris@101:         RobustPolicy const& robust_policy)
Chris@16:     {
Chris@101:         return ! normal_action::included(point, geometry, robust_policy);
Chris@16:     }
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: /*!
Chris@16: \brief Follows a linestring from intersection point to intersection point, outputting which
Chris@16:     is inside, or outside, a ring or polygon
Chris@16: \ingroup overlay
Chris@16:  */
Chris@16: template
Chris@16: <
Chris@16:     typename LineStringOut,
Chris@16:     typename LineString,
Chris@16:     typename Polygon,
Chris@101:     overlay_type OverlayType,
Chris@101:     bool RemoveSpikes = true
Chris@16: >
Chris@16: class follow
Chris@16: {
Chris@16: 
Chris@101:     template <typename Turn>
Chris@16:     struct sort_on_segment
Chris@16:     {
Chris@16:         // In case of turn point at the same location, we want to have continue/blocked LAST
Chris@16:         // because that should be followed (intersection) or skipped (difference).
Chris@16:         inline int operation_order(Turn const& turn) const
Chris@16:         {
Chris@16:             operation_type const& operation = turn.operations[0].operation;
Chris@16:             switch(operation)
Chris@16:             {
Chris@16:                 case operation_opposite : return 0;
Chris@16:                 case operation_none : return 0;
Chris@16:                 case operation_union : return 1;
Chris@16:                 case operation_intersection : return 2;
Chris@16:                 case operation_blocked : return 3;
Chris@16:                 case operation_continue : return 4;
Chris@16:             }
Chris@16:             return -1;
Chris@16:         };
Chris@16: 
Chris@16:         inline bool use_operation(Turn const& left, Turn const& right) const
Chris@16:         {
Chris@101:             // If they are the same, OK.
Chris@16:             return operation_order(left) < operation_order(right);
Chris@16:         }
Chris@16: 
Chris@16:         inline bool use_distance(Turn const& left, Turn const& right) const
Chris@16:         {
Chris@101:             return left.operations[0].fraction == right.operations[0].fraction
Chris@16:                 ? use_operation(left, right)
Chris@101:                 : left.operations[0].fraction < right.operations[0].fraction
Chris@16:                 ;
Chris@16:         }
Chris@16: 
Chris@16:         inline bool operator()(Turn const& left, Turn const& right) const
Chris@16:         {
Chris@16:             segment_identifier const& sl = left.operations[0].seg_id;
Chris@16:             segment_identifier const& sr = right.operations[0].seg_id;
Chris@16: 
Chris@16:             return sl == sr
Chris@16:                 ? use_distance(left, right)
Chris@16:                 : sl < sr
Chris@16:                 ;
Chris@16: 
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16: 
Chris@16: 
Chris@16: public :
Chris@16: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename Point,
Chris@101:         typename Geometry,
Chris@101:         typename RobustPolicy
Chris@101:     >
Chris@101:     static inline bool included(Point const& point,
Chris@101:             Geometry const& geometry,
Chris@101:             RobustPolicy const& robust_policy)
Chris@16:     {
Chris@101:         return following::action_selector
Chris@101:             <
Chris@101:                 OverlayType, RemoveSpikes
Chris@101:             >::included(point, geometry, robust_policy);
Chris@16:     }
Chris@16: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename Turns,
Chris@101:         typename OutputIterator,
Chris@101:         typename RobustPolicy
Chris@101:     >
Chris@16:     static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
Chris@16:                 detail::overlay::operation_type ,  // TODO: this parameter might be redundant
Chris@101:                 Turns& turns,
Chris@101:                 RobustPolicy const& robust_policy,
Chris@101:                 OutputIterator out)
Chris@16:     {
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@101:         typedef following::action_selector<OverlayType, RemoveSpikes> action;
Chris@16: 
Chris@16:         // Sort intersection points on segments-along-linestring, and distance
Chris@16:         // (like in enrich is done for poly/poly)
Chris@16:         std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>());
Chris@16: 
Chris@16:         LineStringOut current_piece;
Chris@16:         geometry::segment_identifier current_segment_id(0, -1, -1, -1);
Chris@16: 
Chris@16:         // Iterate through all intersection points (they are ordered along the line)
Chris@16:         bool entered = false;
Chris@16:         bool first = true;
Chris@16:         for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
Chris@16:         {
Chris@16:             turn_operation_iterator_type iit = boost::begin(it->operations);
Chris@16: 
Chris@16:             if (following::was_entered(*it, *iit, first, linestring, polygon))
Chris@16:             {
Chris@16:                 debug_traverse(*it, *iit, "-> Was entered");
Chris@16:                 entered = true;
Chris@16:             }
Chris@16: 
Chris@16:             if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon))
Chris@16:             {
Chris@16:                 debug_traverse(*it, *iit, "-> Staying inside");
Chris@16: 
Chris@16:                 entered = true;
Chris@16:             }
Chris@16:             else if (following::is_entering(*it, *iit))
Chris@16:             {
Chris@16:                 debug_traverse(*it, *iit, "-> Entering");
Chris@16: 
Chris@16:                 entered = true;
Chris@101:                 action::enter(current_piece, linestring, current_segment_id,
Chris@101:                     iit->seg_id.segment_index, it->point, *iit,
Chris@101:                     robust_policy,
Chris@101:                     out);
Chris@16:             }
Chris@16:             else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon))
Chris@16:             {
Chris@16:                 debug_traverse(*it, *iit, "-> Leaving");
Chris@16: 
Chris@16:                 entered = false;
Chris@101:                 action::leave(current_piece, linestring, current_segment_id,
Chris@101:                     iit->seg_id.segment_index, it->point, *iit,
Chris@101:                     robust_policy,
Chris@101:                     out);
Chris@16:             }
Chris@16:             first = false;
Chris@16:         }
Chris@16: 
Chris@16:         if (action::is_entered(entered))
Chris@16:         {
Chris@101:             detail::copy_segments::copy_segments_linestring
Chris@101:                 <
Chris@101:                     false, RemoveSpikes
Chris@101:                 >::apply(linestring,
Chris@101:                          current_segment_id,
Chris@101:                          static_cast<signed_index_type>(boost::size(linestring) - 1),
Chris@101:                          robust_policy,
Chris@101:                          current_piece);
Chris@16:         }
Chris@16: 
Chris@16:         // Output the last one, if applicable
Chris@101:         if (::boost::size(current_piece) > 1)
Chris@16:         {
Chris@16:             *out++ = current_piece;
Chris@16:         }
Chris@16:         return out;
Chris@16:     }
Chris@16: 
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: }} // namespace detail::overlay
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP