Imported Upstream version 1.60.0

Change-Id: Ie709530d6d5841088ceaba025cbe175a4ef43050
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>

14 files changed, 557 insertions, 69 deletions

diff --git a/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp b/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp
index b1a25c9f5e..8cb37d6954 100644
--- a/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp
+++ b/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp
@@ -51,14 +51,14 @@ class liang_barsky
 private:
     typedef model::referring_segment<Point> segment_type;
 
-    template <typename T>
-    inline bool check_edge(T const& p, T const& q, T& t1, T& t2) const
+    template <typename CoordinateType, typename CalcType>
+    inline bool check_edge(CoordinateType const& p, CoordinateType const& q, CalcType& t1, CalcType& t2) const
     {
         bool visible = true;
 
         if(p < 0)
         {
-            T const r = q / p;
+            CalcType const r = static_cast<CalcType>(q) / p;
             if (r > t2)
                 visible = false;
             else if (r > t1)
@@ -66,7 +66,7 @@ private:
         }
         else if(p > 0)
         {
-            T const r = q / p;
+            CalcType const r = static_cast<CalcType>(q) / p;
             if (r < t1)
                 visible = false;
             else if (r < t2)
@@ -86,9 +86,10 @@ public:
     inline bool clip_segment(Box const& b, segment_type& s, bool& sp1_clipped, bool& sp2_clipped) const
     {
         typedef typename select_coordinate_type<Box, Point>::type coordinate_type;
+        typedef typename select_most_precise<coordinate_type, double>::type calc_type;
 
-        coordinate_type t1 = 0;
-        coordinate_type t2 = 1;
+        calc_type t1 = 0;
+        calc_type t2 = 1;
 
         coordinate_type const dx = get<1, 0>(s) - get<0, 0>(s);
         coordinate_type const dy = get<1, 1>(s) - get<0, 1>(s);
diff --git a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
index 3f81c4dca9..bc84286241 100644
--- a/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
+++ b/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp
@@ -26,7 +26,9 @@
 
 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
+#include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp>
 #include <boost/geometry/algorithms/detail/overlay/handle_tangencies.hpp>
+#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
 #include <boost/geometry/policies/robustness/robust_type.hpp>
 #include <boost/geometry/strategies/side.hpp>
 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
@@ -466,6 +468,7 @@ inline void create_map(TurnPoints const& turn_points, MappedVector& mapped_vecto
 template
 <
     bool Reverse1, bool Reverse2,
+    overlay_type OverlayType,
     typename TurnPoints,
     typename Geometry1, typename Geometry2,
     typename RobustPolicy,
@@ -490,10 +493,9 @@ inline void enrich_intersection_points(TurnPoints& turn_points,
             std::vector<indexed_turn_operation>
         > mapped_vector_type;
 
-    // DISCARD ALL UU
-    // #76 is the reason that this is necessary...
-    // With uu, at all points there is the risk that rings are being traversed twice or more.
-    // Without uu, all rings having only uu will be untouched and gathered by assemble
+    // Iterate through turns and discard uu
+    // and check if there are possible colocations
+    bool check_colocations = false;
     for (typename boost::range_iterator<TurnPoints>::type
             it = boost::begin(turn_points);
          it != boost::end(turn_points);
@@ -501,14 +503,34 @@ inline void enrich_intersection_points(TurnPoints& turn_points,
     {
         if (it->both(detail::overlay::operation_union))
         {
+            // Discard  (necessary for a.o. #76). With uu, at all points there
+            // is the risk that rings are being traversed twice or more.
+            // Without uu, all rings having only uu will be untouched
+            // and gathered by assemble
             it->discarded = true;
+            check_colocations = true;
         }
-        if (it->both(detail::overlay::operation_none))
+        else if (it->combination(detail::overlay::operation_union,
+                                 detail::overlay::operation_blocked))
+        {
+            check_colocations = true;
+        }
+        else if (OverlayType == overlay_difference
+                 && it->both(detail::overlay::operation_intersection))
+        {
+            // For difference operation (u/u -> i/i)
+            check_colocations = true;
+        }
+        else if (it->both(detail::overlay::operation_none))
         {
             it->discarded = true;
         }
     }
 
+    if (check_colocations)
+    {
+        detail::overlay::handle_colocations<OverlayType>(turn_points);
+    }
 
     // Create a map of vectors of indexed operation-types to be able
     // to sort intersection points PER RING
diff --git a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp
index b2c3836712..b9e48cdbfc 100644
--- a/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp
+++ b/boost/geometry/algorithms/detail/overlay/follow_linear_linear.hpp
@@ -1,6 +1,6 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
-// Copyright (c) 2014, Oracle and/or its affiliates.
+// Copyright (c) 2014-2015, Oracle and/or its affiliates.
 
 // Licensed under the Boost Software License version 1.0.
 // http://www.boost.org/users/license.html
@@ -22,6 +22,7 @@
 
 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
 #include <boost/geometry/algorithms/detail/overlay/follow.hpp>
+#include <boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp>
 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
@@ -35,24 +36,6 @@
 namespace boost { namespace geometry
 {
 
-#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
-class inconsistent_turns_exception : public geometry::exception
-{
-public:
-
-    inline inconsistent_turns_exception() {}
-
-    virtual ~inconsistent_turns_exception() throw()
-    {}
-
-    virtual char const* what() const throw()
-    {
-        return "Boost.Geometry Inconsistent Turns exception";
-    }
-};
-#endif
-
-
 #ifndef DOXYGEN_NO_DETAIL
 namespace detail { namespace overlay
 {
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
index 717f0b47a9..ac36c530bf 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
@@ -585,8 +585,8 @@ struct collinear : public base_turn_handler
         typename SidePolicy
     >
     static inline void apply(
-                Point1 const& , Point1 const& , Point1 const& ,
-                Point2 const& , Point2 const& , Point2 const& ,
+                Point1 const& , Point1 const& pj, Point1 const& pk,
+                Point2 const& , Point2 const& qj, Point2 const& qk,
                 TurnInfo& ti,
                 IntersectionInfo const& info,
                 DirInfo const& dir_info,
@@ -623,8 +623,30 @@ struct collinear : public base_turn_handler
         {
             ui_else_iu(product == 1, ti);
         }
+
+        // Calculate remaining distance. If it continues collinearly it is
+        // measured until the end of the next segment
+        ti.operations[0].remaining_distance
+                = side_p == 0
+                ? distance_measure(ti.point, pk)
+                : distance_measure(ti.point, pj);
+        ti.operations[1].remaining_distance
+                = side_q == 0
+                ? distance_measure(ti.point, qk)
+                : distance_measure(ti.point, qj);
     }
 
+    template <typename Point1, typename Point2>
+    static inline typename geometry::coordinate_type<Point1>::type
+            distance_measure(Point1 const& a, Point2 const& b)
+    {
+        // TODO: use comparable distance for point-point instead - but that
+        // causes currently cycling include problems
+        typedef typename geometry::coordinate_type<Point1>::type ctype;
+        ctype const dx = get<0>(a) - get<0>(b);
+        ctype const dy = get<1>(b) - get<1>(b);
+        return dx * dx + dy * dy;
+    }
 };
 
 template
diff --git a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp
index e4f8de42e1..ee0a93ae7e 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turn_info_helpers.hpp
@@ -23,9 +23,9 @@ namespace detail { namespace overlay {
 
 enum turn_position { position_middle, position_front, position_back };
 
-template <typename SegmentRatio>
+template <typename Point, typename SegmentRatio>
 struct turn_operation_linear
-    : public turn_operation<SegmentRatio>
+    : public turn_operation<Point, SegmentRatio>
 {
     turn_operation_linear()
         : position(position_middle)
diff --git a/boost/geometry/algorithms/detail/overlay/get_turns.hpp b/boost/geometry/algorithms/detail/overlay/get_turns.hpp
index 098c7b5642..b2b97c0337 100644
--- a/boost/geometry/algorithms/detail/overlay/get_turns.hpp
+++ b/boost/geometry/algorithms/detail/overlay/get_turns.hpp
@@ -802,19 +802,19 @@ template <typename Geometry1, typename Geometry2, typename SegmentRatio,
           typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
 struct turn_operation_type
 {
-    typedef overlay::turn_operation<SegmentRatio> type;
+    typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type;
 };
 
 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag>
 {
-    typedef overlay::turn_operation_linear<SegmentRatio> type;
+    typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
 };
 
 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag>
 {
-    typedef overlay::turn_operation_linear<SegmentRatio> type;
+    typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
 };
 
 }} // namespace detail::get_turns
diff --git a/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp
new file mode 100644
index 0000000000..6f332ddff2
--- /dev/null
+++ b/boost/geometry/algorithms/detail/overlay/handle_colocations.hpp
@@ -0,0 +1,278 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2015 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_HANDLE_COLOCATIONS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
+
+#include <cstddef>
+#include <algorithm>
+#include <map>
+#include <vector>
+
+#include <boost/range.hpp>
+#include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+#include <boost/geometry/algorithms/detail/ring_identifier.hpp>
+#include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
+
+#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
+#  include <iostream>
+#  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
+#  include <boost/geometry/io/wkt/wkt.hpp>
+#  define BOOST_GEOMETRY_DEBUG_IDENTIFIER
+#endif
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+struct turn_operation_index
+{
+    turn_operation_index(signed_size_type ti = -1,
+                         signed_size_type oi = -1)
+        : turn_index(ti)
+        , op_index(oi)
+    {}
+
+    signed_size_type turn_index;
+    signed_size_type op_index; // basically only 0,1
+};
+
+
+template <typename TurnPoints>
+struct less_by_fraction_and_type
+{
+    inline less_by_fraction_and_type(TurnPoints const& turn_points)
+        : m_turns(turn_points)
+    {
+    }
+
+    inline bool operator()(turn_operation_index const& left,
+                           turn_operation_index const& right) const
+    {
+        typedef typename boost::range_value<TurnPoints>::type turn_type;
+        typedef typename turn_type::turn_operation_type turn_operation_type;
+
+        turn_type const& left_turn = m_turns[left.turn_index];
+        turn_type const& right_turn = m_turns[right.turn_index];
+        turn_operation_type const& left_op
+                = left_turn.operations[left.op_index];
+
+        turn_operation_type const& right_op
+                = right_turn.operations[right.op_index];
+
+        if (! (left_op.fraction == right_op.fraction))
+        {
+            return left_op.fraction < right_op.fraction;
+        }
+
+        turn_operation_type const& left_other_op
+                = left_turn.operations[1 - left.op_index];
+
+        turn_operation_type const& right_other_op
+                = right_turn.operations[1 - right.op_index];
+
+        // Fraction is the same, now sort on ring id, first outer ring,
+        // then interior rings
+        return left_other_op.seg_id < right_other_op.seg_id;
+    }
+
+private:
+    TurnPoints const& m_turns;
+};
+
+template <overlay_type OverlayType, typename TurnPoints, typename OperationVector>
+inline void handle_colocation_cluster(TurnPoints& turn_points,
+       segment_identifier const& current_ring_seg_id,
+       OperationVector const& vec)
+{
+    typedef typename boost::range_value<TurnPoints>::type turn_type;
+    typedef typename turn_type::turn_operation_type turn_operation_type;
+
+    std::vector<turn_operation_index>::const_iterator vit = vec.begin();
+
+    turn_type cluster_turn = turn_points[vit->turn_index];
+    turn_operation_type cluster_op
+            = cluster_turn.operations[vit->op_index];
+    segment_identifier cluster_other_id
+            = cluster_turn.operations[1 - vit->op_index].seg_id;
+    bool const discard_colocated
+            = cluster_turn.both(operation_union)
+            || cluster_turn.combination(operation_blocked, operation_union);
+
+    for (++vit; vit != vec.end(); ++vit)
+    {
+        turn_operation_index const& toi = *vit;
+        turn_type& turn = turn_points[toi.turn_index];
+        turn_operation_type const& op = turn.operations[toi.op_index];
+        segment_identifier const& other_id
+                = turn.operations[1 - toi.op_index].seg_id;
+
+        if (cluster_op.fraction == op.fraction)
+        {
+            // Two turns of current ring with same source are colocated,
+            // one is from exterior ring, one from interior ring
+            bool const colocated_ext_int
+                = cluster_other_id.multi_index == other_id.multi_index
+                   && cluster_other_id.ring_index == -1
+                   && other_id.ring_index >= 0;
+
+            // Turn of current interior ring with other interior ring
+            bool const touch_int_int
+                = current_ring_seg_id.ring_index >= 0
+                   && other_id.ring_index >= 0;
+
+            if (discard_colocated && colocated_ext_int)
+            {
+                // If the two turns on this same segment are a
+                // colocation with two different segments on the
+                // other geometry, of the same polygon but with
+                // the outer (u/u or u/x) and the inner ring (non u/u),
+                // that turn with inner ring should be discarded
+                turn.discarded = true;
+                turn.colocated = true;
+            }
+            else if (cluster_turn.colocated
+                     && touch_int_int
+                     && turn.both(operation_intersection))
+            {
+                // Two holes touch each other at a point where the
+                // exterior ring also touches
+                turn.discarded = true;
+                turn.colocated = true;
+            }
+            else if (OverlayType == overlay_difference
+                     && turn.both(operation_intersection)
+                     && colocated_ext_int)
+            {
+                // For difference (polygon inside out) we need to
+                // discard i/i instead, in case of colocations
+                turn.discarded = true;
+                turn.colocated = true;
+            }
+        }
+        else
+        {
+            // Not on same fraction on this segment
+            // assign for next potential cluster
+            cluster_turn = turn;
+            cluster_op = op;
+            cluster_other_id = other_id;
+        }
+
+    }
+}
+
+
+// Checks colocated turns and flags combinations of uu/other, possibly a
+// combination of a ring touching another geometry's interior ring which is
+// tangential to the exterior ring
+
+// This function can be extended to replace handle_tangencies: at each
+// colocation incoming and outgoing vectors should be inspected
+
+template <overlay_type OverlayType, typename TurnPoints>
+inline void handle_colocations(TurnPoints& turn_points)
+{
+    typedef std::map
+        <
+            segment_identifier,
+            std::vector<turn_operation_index>
+        > map_type;
+
+    // Create and fill map on segment-identifier Map is sorted on seg_id,
+    // meaning it is sorted on ring_identifier too. This means that exterior
+    // rings are handled first. If there is a colocation on the exterior ring,
+    // that information can be used for the interior ring too
+    map_type map;
+
+    int index = 0;
+    for (typename boost::range_iterator<TurnPoints>::type
+            it = boost::begin(turn_points);
+         it != boost::end(turn_points);
+         ++it, ++index)
+    {
+        map[it->operations[0].seg_id].push_back(turn_operation_index(index, 0));
+        map[it->operations[1].seg_id].push_back(turn_operation_index(index, 1));
+    }
+
+    // Check if there are multiple turns on one or more segments,
+    // if not then nothing is to be done
+    bool colocations = 0;
+    for (typename map_type::const_iterator it = map.begin();
+         it != map.end();
+         ++it)
+    {
+        if (it->second.size() > 1u)
+        {
+            colocations = true;
+            break;
+        }
+    }
+
+    if (! colocations)
+    {
+        return;
+    }
+
+    // Sort all vectors, per same segment
+    less_by_fraction_and_type<TurnPoints> less(turn_points);
+    for (typename map_type::iterator it = map.begin();
+         it != map.end(); ++it)
+    {
+        std::sort(it->second.begin(), it->second.end(), less);
+    }
+
+    for (typename map_type::const_iterator it = map.begin();
+         it != map.end(); ++it)
+    {
+        if (it->second.size() > 1)
+        {
+            handle_colocation_cluster<OverlayType>(turn_points,
+                    it->first, it->second);
+        }
+    }
+
+#if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS)
+    std::cout << "*** Colocations " << map.size() << std::endl;
+    for (typename map_type::const_iterator it = map.begin();
+         it != map.end(); ++it)
+    {
+        std::cout << it->first << std::endl;
+        for (std::vector<turn_operation_index>::const_iterator vit
+             = it->second.begin(); vit != it->second.end(); ++vit)
+        {
+            turn_operation_index const& toi = *vit;
+            std::cout << geometry::wkt(turn_points[toi.turn_index].point)
+                << std::boolalpha
+                << " discarded=" << turn_points[toi.turn_index].discarded
+                << " colocated=" << turn_points[toi.turn_index].colocated
+                << " " << operation_char(turn_points[toi.turn_index].operations[0].operation)
+                << " "  << turn_points[toi.turn_index].operations[0].seg_id
+                << " "  << turn_points[toi.turn_index].operations[0].fraction
+                << " // " << operation_char(turn_points[toi.turn_index].operations[1].operation)
+                << " "  << turn_points[toi.turn_index].operations[1].seg_id
+                << " "  << turn_points[toi.turn_index].operations[1].fraction
+                << std::endl;
+        }
+    }
+#endif // DEBUG
+
+}
+
+
+}} // namespace detail::overlay
+#endif //DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP
diff --git a/boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp b/boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp
new file mode 100644
index 0000000000..1486f94fbd
--- /dev/null
+++ b/boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp
@@ -0,0 +1,38 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2014-2015, 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_INCONSISTENT_TURNS_EXCEPTION_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INCONSISTENT_TURNS_EXCEPTION_HPP
+
+#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
+#include <boost/geometry/core/exception.hpp>
+
+namespace boost { namespace geometry
+{
+
+class inconsistent_turns_exception : public geometry::exception
+{
+public:
+
+    inline inconsistent_turns_exception() {}
+
+    virtual ~inconsistent_turns_exception() throw()
+    {}
+
+    virtual char const* what() const throw()
+    {
+        return "Boost.Geometry Inconsistent Turns exception";
+    }
+};
+
+}} // boost::geometry
+
+#endif // BOOST_GEOMETRY_OVERLAY_NO_THROW
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INCONSISTENT_TURNS_EXCEPTION_HPP
diff --git a/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp b/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp
index dd041b0d7d..c62b7d2834 100644
--- a/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp
+++ b/boost/geometry/algorithms/detail/overlay/intersection_box_box.hpp
@@ -1,6 +1,11 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 
-// Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
+// Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
+
+// This file was modified by Oracle on 2015.
+// Modifications copyright (c) 2015, Oracle and/or its affiliates.
+
+// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
 
 // Use, modification and distribution is subject to the Boost Software License,
 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
@@ -39,19 +44,26 @@ struct intersection_box_box
     {
         typedef typename coordinate_type<BoxOut>::type ct;
 
-        ct min1 = get<min_corner, Dimension>(box1);
-        ct min2 = get<min_corner, Dimension>(box2);
         ct max1 = get<max_corner, Dimension>(box1);
+        ct min2 = get<min_corner, Dimension>(box2);
+
+        if (max1 < min2)
+        {
+            return false;
+        }
+
         ct max2 = get<max_corner, Dimension>(box2);
+        ct min1 = get<min_corner, Dimension>(box1);
 
-        if (max1 < min2 || max2 < min1)
+        if (max2 < min1)
         {
             return false;
         }
+
         // Set dimensions of output coordinate
         set<min_corner, Dimension>(box_out, min1 < min2 ? min2 : min1);
         set<max_corner, Dimension>(box_out, max1 > max2 ? max2 : max1);
-
+        
         return intersection_box_box<Dimension + 1, DimensionCount>
                ::apply(box1, box2, robust_policy, box_out, strategy);
     }
diff --git a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
index af0731f5a9..59c8f6f1ff 100644
--- a/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
+++ b/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
@@ -41,6 +41,7 @@
 #include <boost/geometry/views/segment_view.hpp>
 #include <boost/geometry/views/detail/boundary_view.hpp>
 
+#include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
 #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp>
 #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
 #include <boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp>
@@ -175,21 +176,115 @@ template
 struct intersection_of_linestring_with_areal
 {
 #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
-        template <typename Turn, typename Operation>
-        static inline void debug_follow(Turn const& turn, Operation op,
-                    int index)
+    template <typename Turn, typename Operation>
+    static inline void debug_follow(Turn const& turn, Operation op,
+                                    int index)
+    {
+        std::cout << index
+                  << " 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;
+    }
+
+    template <typename Turn>
+    static inline void debug_turn(Turn const& t, bool non_crossing)
+    {
+        std::cout << "checking turn @"
+                  << geometry::wkt(t.point)
+                  << "; " << method_char(t.method)
+                  << ":" << operation_char(t.operations[0].operation)
+                  << "/" << operation_char(t.operations[1].operation)
+                  << "; non-crossing? "
+                  << std::boolalpha << non_crossing << std::noboolalpha
+                  << std::endl;
+    }
+#endif
+
+    class is_crossing_turn
+    {
+        // return true is the operation is intersection or blocked
+        template <std::size_t Index, typename Turn>
+        static inline bool has_op_i_or_b(Turn const& t)
         {
-            std::cout << index
-                << " 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;
+            return
+                t.operations[Index].operation == overlay::operation_intersection
+                ||
+                t.operations[Index].operation == overlay::operation_blocked;
         }
+
+        template <typename Turn>
+        static inline bool has_method_crosses(Turn const& t)
+        {
+            return t.method == overlay::method_crosses;
+        }
+
+        template <typename Turn>
+        static inline bool is_cc(Turn const& t)
+        {
+            return
+                (t.method == overlay::method_touch_interior
+                 ||
+                 t.method == overlay::method_equal
+                 ||
+                 t.method == overlay::method_collinear)
+                &&
+                t.operations[0].operation == t.operations[1].operation
+                &&
+                t.operations[0].operation == overlay::operation_continue
+                ;
+        }
+
+        template <typename Turn>
+        static inline bool has_i_or_b_ops(Turn const& t)
+        {
+            return
+                (t.method == overlay::method_touch
+                 ||
+                 t.method == overlay::method_touch_interior
+                 ||
+                 t.method == overlay::method_collinear)
+                &&
+                t.operations[1].operation != t.operations[0].operation
+                &&
+                (has_op_i_or_b<0>(t) || has_op_i_or_b<1>(t));
+        }
+
+    public:
+        template <typename Turn>
+        static inline bool apply(Turn const& t)
+        {
+            bool const is_crossing
+                = has_method_crosses(t) || is_cc(t) || has_i_or_b_ops(t);
+#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
+            debug_turn(t, ! is_crossing);
 #endif
+            return is_crossing;
+        }
+    };
+
+    struct is_non_crossing_turn
+    {
+        template <typename Turn>
+        static inline bool apply(Turn const& t)
+        {
+            return ! is_crossing_turn::apply(t);
+        }
+    };
+
+    template <typename Turns>
+    static inline bool no_crossing_turns_or_empty(Turns const& turns)
+    {
+        return detail::check_iterator_range
+            <
+                is_non_crossing_turn,
+                true // allow an empty turns range
+            >::apply(boost::begin(turns), boost::end(turns));
+    }
 
     template
     <
@@ -212,7 +307,8 @@ struct intersection_of_linestring_with_areal
                     LineStringOut,
                     LineString,
                     Areal,
-                    OverlayType
+                    OverlayType,
+                    false // do not remove spikes for linear geometries
                 > follower;
 
         typedef typename point_type<LineStringOut>::type point_type;
@@ -231,7 +327,7 @@ struct intersection_of_linestring_with_areal
                 detail::overlay::assign_null_policy
             >(linestring, areal, robust_policy, turns, policy);
 
-        if (turns.empty())
+        if (no_crossing_turns_or_empty(turns))
         {
             // No intersection points, it is either completely
             // inside (interior + borders)
diff --git a/boost/geometry/algorithms/detail/overlay/overlay.hpp b/boost/geometry/algorithms/detail/overlay/overlay.hpp
index baf9d4777d..6eb0b8864c 100644
--- a/boost/geometry/algorithms/detail/overlay/overlay.hpp
+++ b/boost/geometry/algorithms/detail/overlay/overlay.hpp
@@ -78,6 +78,11 @@ inline void get_ring_turn_info(TurnInfoMap& turn_info_map,
             && ! turn_info.both(operation_intersection)
             ;
 
+        if (! both_uu && turn_info.colocated)
+        {
+            skip = true;
+        }
+
         for (typename boost::range_iterator<container_type const>::type
                 op_it = boost::begin(turn_info.operations);
             op_it != boost::end(turn_info.operations);
@@ -105,7 +110,7 @@ inline void get_ring_turn_info(TurnInfoMap& turn_info_map,
 
 template
 <
-    typename GeometryOut, overlay_type Direction, bool ReverseOut,
+    typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
     typename Geometry1, typename Geometry2,
     typename OutputIterator
 >
@@ -129,8 +134,8 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
     // Union: return either of them
     // Intersection: return nothing
     // Difference: return first of them
-    if (Direction == overlay_intersection
-        || (Direction == overlay_difference && geometry::is_empty(geometry1)))
+    if (OverlayType == overlay_intersection
+        || (OverlayType == overlay_difference && geometry::is_empty(geometry1)))
     {
         return out;
     }
@@ -143,7 +148,7 @@ inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
     std::map<ring_identifier, ring_turn_info> empty;
     std::map<ring_identifier, properties> all_of_one_of_them;
 
-    select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them);
+    select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them);
     ring_container_type rings;
     assign_parents(geometry1, geometry2, rings, all_of_one_of_them);
     return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
@@ -155,7 +160,7 @@ template
     typename Geometry1, typename Geometry2,
     bool Reverse1, bool Reverse2, bool ReverseOut,
     typename GeometryOut,
-    overlay_type Direction
+    overlay_type OverlayType
 >
 struct overlay
 {
@@ -178,7 +183,7 @@ struct overlay
         {
             return return_if_one_input_is_empty
                 <
-                    GeometryOut, Direction, ReverseOut
+                    GeometryOut, OverlayType, ReverseOut
                 >(geometry1, geometry2, out);
         }
 
@@ -211,8 +216,8 @@ std::cout << "get turns" << std::endl;
 std::cout << "enrich" << std::endl;
 #endif
         typename Strategy::side_strategy_type side_strategy;
-        geometry::enrich_intersection_points<Reverse1, Reverse2>(turn_points,
-                Direction == overlay_union
+        geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turn_points,
+                OverlayType == overlay_union
                     ? geometry::detail::overlay::operation_union
                     : geometry::detail::overlay::operation_intersection,
                     geometry1, geometry2,
@@ -229,7 +234,7 @@ std::cout << "traverse" << std::endl;
         traverse<Reverse1, Reverse2, Geometry1, Geometry2>::apply
                 (
                     geometry1, geometry2,
-                    Direction == overlay_union
+                    OverlayType == overlay_union
                         ? geometry::detail::overlay::operation_union
                         : geometry::detail::overlay::operation_intersection,
                     robust_policy,
@@ -246,7 +251,7 @@ std::cout << "traverse" << std::endl;
 
         // Select all rings which are NOT touched by any intersection point
         std::map<ring_identifier, properties> selected_ring_properties;
-        select_rings<Direction>(geometry1, geometry2, turn_info_per_ring,
+        select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring,
                 selected_ring_properties);
 
         // Add rings created during traversal
diff --git a/boost/geometry/algorithms/detail/overlay/traversal_info.hpp b/boost/geometry/algorithms/detail/overlay/traversal_info.hpp
index 6ee32c17c0..8cabfb0d8d 100644
--- a/boost/geometry/algorithms/detail/overlay/traversal_info.hpp
+++ b/boost/geometry/algorithms/detail/overlay/traversal_info.hpp
@@ -25,7 +25,7 @@ namespace detail { namespace overlay
 
 
 template <typename Point, typename SegmentRatio>
-struct traversal_turn_operation : public turn_operation<SegmentRatio>
+struct traversal_turn_operation : public turn_operation<Point, SegmentRatio>
 {
     enrichment_info<Point> enriched;
     visit_info visited;
diff --git a/boost/geometry/algorithms/detail/overlay/traverse.hpp b/boost/geometry/algorithms/detail/overlay/traverse.hpp
index 803a164711..45e15d13d0 100644
--- a/boost/geometry/algorithms/detail/overlay/traverse.hpp
+++ b/boost/geometry/algorithms/detail/overlay/traverse.hpp
@@ -174,7 +174,17 @@ inline bool select_next_ip(operation_type operation,
     {
         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);
@@ -206,10 +216,24 @@ inline bool select_next_ip(operation_type operation,
                 )
             )
         {
+            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)
diff --git a/boost/geometry/algorithms/detail/overlay/turn_info.hpp b/boost/geometry/algorithms/detail/overlay/turn_info.hpp
index 26669a4b1f..1ac77d5796 100644
--- a/boost/geometry/algorithms/detail/overlay/turn_info.hpp
+++ b/boost/geometry/algorithms/detail/overlay/turn_info.hpp
@@ -12,6 +12,7 @@
 
 #include <boost/array.hpp>
 
+#include <boost/geometry/core/coordinate_type.hpp>
 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
 
 namespace boost { namespace geometry
@@ -54,15 +55,19 @@ enum method_type
         The class is to be included in the turn_info class, either direct
         or a derived or similar class with more (e.g. enrichment) information.
  */
-template <typename SegmentRatio>
+template <typename Point, typename SegmentRatio>
 struct turn_operation
 {
     operation_type operation;
     segment_identifier seg_id;
     SegmentRatio fraction;
 
+    typedef typename coordinate_type<Point>::type comparable_distance_type;
+    comparable_distance_type remaining_distance;
+
     inline turn_operation()
         : operation(operation_none)
+        , remaining_distance(0)
     {}
 };
 
@@ -80,7 +85,7 @@ template
 <
     typename Point,
     typename SegmentRatio,
-    typename Operation = turn_operation<SegmentRatio>,
+    typename Operation = turn_operation<Point, SegmentRatio>,
     typename Container = boost::array<Operation, 2>
 >
 struct turn_info
@@ -93,6 +98,7 @@ struct turn_info
     method_type method;
     bool discarded;
     bool selectable_start; // Can be used as starting-turn in traverse
+    bool colocated;
 
 
     Container operations;
@@ -101,6 +107,7 @@ struct turn_info
         : method(method_none)
         , discarded(false)
         , selectable_start(true)
+        , colocated(false)
     {}
 
     inline bool both(operation_type type) const