text: // Boost.Geometry (aka GGL, Generic Geometry Library)
  
  // Copyright (c) 2014, Oracle and/or its affiliates.
  
  // Licensed under the Boost Software License version 1.0.
  // http://www.boost.org/users/license.html
  
  // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  
  
  #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
  #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
  
  #include <algorithm>
  #include <vector>
  
  #include <boost/range.hpp>
  
  #include <boost/geometry/core/tag.hpp>
  #include <boost/geometry/core/tags.hpp>
  
  #include <boost/geometry/algorithms/detail/relate/turns.hpp>
  
  #include <boost/geometry/algorithms/detail/turns/compare_turns.hpp>
  #include <boost/geometry/algorithms/detail/turns/filter_continue_turns.hpp>
  #include <boost/geometry/algorithms/detail/turns/remove_duplicate_turns.hpp>
  
  #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  #include <boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp>
  
  #include <boost/geometry/algorithms/convert.hpp>
  
  
  
  namespace boost { namespace geometry
  {
  
  
  #ifndef DOXYGEN_NO_DETAIL
  namespace detail { namespace overlay
  {
  
  
  template
  <
      typename LineStringOut,
      overlay_type OverlayType,
      typename Geometry,
      typename GeometryTag
  >
  struct linear_linear_no_intersections;
  
  
  template <typename LineStringOut, typename LineString>
  struct linear_linear_no_intersections
      <
          LineStringOut, overlay_difference, LineString, linestring_tag
      >
  {
      template <typename OutputIterator>
      static inline OutputIterator apply(LineString const& linestring,
                                         OutputIterator oit)
      {
          LineStringOut ls_out;
          geometry::convert(linestring, ls_out);
          *oit++ = ls_out;
          return oit;
      }
  };
  
  
  template <typename LineStringOut, typename MultiLineString>
  struct linear_linear_no_intersections
      <
          LineStringOut,
          overlay_difference,
          MultiLineString,
          multi_linestring_tag
      >
  {
      template <typename OutputIterator>
      static inline OutputIterator apply(MultiLineString const& multilinestring,
                                         OutputIterator oit)
      {
          for (typename boost::range_iterator<MultiLineString const>::type
                   it = boost::begin(multilinestring);
               it != boost::end(multilinestring); ++it)
          {
              LineStringOut ls_out;
              geometry::convert(*it, ls_out);
              *oit++ = ls_out;
          }
          return oit;
      }
  };
  
  
  template <typename LineStringOut, typename Geometry, typename GeometryTag>
  struct linear_linear_no_intersections
      <
          LineStringOut, overlay_intersection, Geometry, GeometryTag
      >
  {
      template <typename OutputIterator>
      static inline OutputIterator apply(Geometry const&,
                                         OutputIterator oit)
      {
          return oit;
      }
  };
  
  
  
  
  
  
  
  template
  <
      typename Linear1,
      typename Linear2,
      typename LinestringOut,
      overlay_type OverlayType,
      bool EnableFilterContinueTurns = false,
      bool EnableRemoveDuplicateTurns = false,
      bool EnableDegenerateTurns = true,
  #ifdef BOOST_GEOMETRY_INTERSECTION_DO_NOT_INCLUDE_ISOLATED_POINTS
      bool EnableFollowIsolatedPoints = false
  #else
      bool EnableFollowIsolatedPoints = true
  #endif
  >
  class linear_linear_linestring
  {
  protected:
      struct assign_policy
      {
          static bool const include_no_turn = false;
          static bool const include_degenerate = EnableDegenerateTurns;
          static bool const include_opposite = false;
  
          template
          <
              typename Info,
              typename Point1,
              typename Point2,
              typename IntersectionInfo
          >
          static inline void apply(Info& , Point1 const& , Point2 const& ,
                                   IntersectionInfo const& )
          {
          }
      };
  
  
      template
      <
          typename Turns,
          typename LinearGeometry1,
          typename LinearGeometry2
      >
      static inline void compute_turns(Turns& turns,
                                       LinearGeometry1 const& linear1,
                                       LinearGeometry2 const& linear2)
      {
          turns.clear();
          geometry::detail::relate::turns::get_turns
              <
                  LinearGeometry1,
                  LinearGeometry2,
                  detail::get_turns::get_turn_info_type
                  <
                      LinearGeometry1,
                      LinearGeometry2,
                      assign_policy
                  >
              >::apply(turns, linear1, linear2);
      }
  
  
      template
      <
          overlay_type OverlayTypeForFollow,
          bool FollowIsolatedPoints,
          typename Turns,
          typename LinearGeometry1,
          typename LinearGeometry2,
          typename OutputIterator
      >
      static inline OutputIterator
      sort_and_follow_turns(Turns& turns,
                            LinearGeometry1 const& linear1,
                            LinearGeometry2 const& linear2,
                            OutputIterator oit)
      {
          // remove turns that have no added value
          turns::filter_continue_turns
              <
                  Turns,
                  EnableFilterContinueTurns && OverlayType != overlay_intersection
              >::apply(turns);
  
          // sort by seg_id, distance, and operation
          std::sort(boost::begin(turns), boost::end(turns),
                    detail::turns::less_seg_fraction_other_op<>());
  
          // remove duplicate turns
          turns::remove_duplicate_turns
              <
                  Turns, EnableRemoveDuplicateTurns
              >::apply(turns);
  
          return detail::overlay::following::linear::follow
              <
                  LinestringOut,
                  LinearGeometry1,
                  LinearGeometry2,
                  OverlayTypeForFollow,
                  FollowIsolatedPoints,
                  !EnableFilterContinueTurns || OverlayType == overlay_intersection
              >::apply(linear1, linear2, boost::begin(turns), boost::end(turns),
                       oit);
      }
  
  public:
      template
      <
          typename RobustPolicy, typename OutputIterator, typename Strategy
      >
      static inline OutputIterator apply(Linear1 const& linear1,
                                         Linear2 const& linear2,
                                         RobustPolicy const&,
                                         OutputIterator oit,
                                         Strategy const& )
      {
          typedef typename detail::relate::turns::get_turns
              <
                  Linear1, Linear2
              >::turn_info turn_info;
  
          typedef std::vector<turn_info> turns_container;
  
          turns_container turns;
          compute_turns(turns, linear1, linear2);
  
          if ( turns.empty() )
          {
              // the two linear geometries are disjoint
              return linear_linear_no_intersections
                  <
                      LinestringOut,
                      OverlayType,
                      Linear1,
                      typename tag<Linear1>::type
                  >::apply(linear1, oit);
          }
  
          return sort_and_follow_turns
              <
                  OverlayType,
                  EnableFollowIsolatedPoints
                  && OverlayType == overlay_intersection
              >(turns, linear1, linear2, oit);
      }
  };
  
  
  
  
  template
  <
      typename Linear1,
      typename Linear2,
      typename LinestringOut,
      bool EnableFilterContinueTurns,
      bool EnableRemoveDuplicateTurns,
      bool EnableDegenerateTurns,
      bool EnableFollowIsolatedPoints
  >
  struct linear_linear_linestring
      <
          Linear1, Linear2, LinestringOut, overlay_union,
          EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
          EnableDegenerateTurns, EnableFollowIsolatedPoints
      >
  {
      template
      <
          typename RobustPolicy, typename OutputIterator, typename Strategy
      >
      static inline OutputIterator apply(Linear1 const& linear1,
                                         Linear2 const& linear2,
                                         RobustPolicy const& robust_policy,
                                         OutputIterator oit,
                                         Strategy const& strategy)
      {
          oit = linear_linear_no_intersections
              <
                  LinestringOut,
                  overlay_difference,
                  Linear1,
                  typename tag<Linear1>::type
              >::apply(linear1, oit);
  
          return linear_linear_linestring
              <
                  Linear2, Linear1, LinestringOut, overlay_difference,
                  EnableFilterContinueTurns, EnableRemoveDuplicateTurns,
                  EnableDegenerateTurns, EnableFollowIsolatedPoints
              >::apply(linear2, linear1, robust_policy, oit, strategy);
      }
  };
  
  
  
  
  }} // namespace detail::overlay
  #endif // DOXYGEN_NO_DETAIL
  
  
  }} // namespace boost::geometry
  
  
  
  #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_LINEAR_LINEAR_HPP
  