[Boost-commit] svn:boost r73546 - in trunk/boost/geometry: algorithms/detail/overlay extensions/algorithms

Subject: [Boost-commit] svn:boost r73546 - in trunk/boost/geometry: algorithms/detail/overlay extensions/algorithms
From: barend.gehrels_at_[hidden]
Date: 2011-08-05 09:14:23

Author: barendgehrels
Date: 2011-08-05 09:14:22 EDT (Fri, 05 Aug 2011)
New Revision: 73546
URL: http://svn.boost.org/trac/boost/changeset/73546

Log:
Reorganized backtracking in a separate strategy, different for normal overlay and dissolve. Checking on self-intersections is now done in that strategy (for overlay). It is not part of the normal path anymore. This can increase the speed drastically, in some cases.
Added:
   trunk/boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp      |    23 -                                       
   trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp |     9                                         
   trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp     |   363 +++++++++++++++------------------------ 
   trunk/boost/geometry/extensions/algorithms/dissolve.hpp         |    47 ++++                                    
   4 files changed, 195 insertions(+), 247 deletions(-)

Added: trunk/boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp	2011-08-05 09:14:22 EDT (Fri, 05 Aug 2011)
@@ -0,0 +1,181 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2011 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_BACKTRACK_CHECK_SI_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_BACKTRACK_CHECK_SI_HPP
+
+
+#include <cstddef>
+
+#include <string>
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+#include <boost/geometry/core/access.hpp>
+
+#  include <boost/geometry/algorithms/detail/has_self_intersections.hpp>
+
+
+#if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT)
+#  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
+#  include <boost/geometry/domains/gis/io/wkt/wkt.hpp>
+#endif
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+
+template <typename Turns>
+inline void clear_visit_info(Turns& turns)
+{
+    typedef typename boost::range_value<Turns>::type tp_type;
+
+    for (typename boost::range_iterator<Turns>::type
+        it = boost::begin(turns);
+        it != boost::end(turns);
+        ++it)
+    {
+        for (typename boost::range_iterator
+            <
+                typename tp_type::container_type
+            >::type op_it = boost::begin(it->operations);
+            op_it != boost::end(it->operations);
+            ++op_it)
+        {
+            op_it->visited.clear();
+        }
+        it->discarded = false;
+    }
+}
+
+struct backtrack_state
+{
+    bool m_good;
+    
+    inline backtrack_state() : m_good(true) {}         
+    inline void reset() { m_good = true; }
+    inline bool good() const { return m_good; }
+};
+
+
+template
+<
+    typename Geometry1,
+    typename Geometry2
+>
+class backtrack_check_self_intersections
+{
+    struct state : public backtrack_state
+    {
+        bool m_checked;
+        inline state()
+            : m_checked()
+        {}
+    };
+public :
+    typedef state state_type;
+
+    template <typename Operation, typename Rings, typename Turns>
+    static inline void apply(std::size_t size_at_start, 
+                Rings& rings, typename boost::range_value<Rings>::type& ring,
+                Turns& turns, Operation& operation,
+                std::string const& ,
+                Geometry1 const& geometry1,
+                Geometry2 const& geometry2,
+                state_type& state
+                )
+    {
+        state.m_good = false;
+        
+        // Check self-intersections and throw exception if appropriate
+        if (! state.m_checked)
+        {
+            state.m_checked = true;
+            has_self_intersections(geometry1);
+            has_self_intersections(geometry2);
+        }
+
+        // Make bad output clean
+        rings.resize(size_at_start);
+        ring.clear();
+
+        // Reject this as a starting point
+        operation.visited.set_rejected();
+
+        // And clear all visit info
+        clear_visit_info(turns);
+    }
+};
+
+#ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
+template
+<
+    typename Geometry1,
+    typename Geometry2
+>
+class backtrack_debug
+{
+public :
+    typedef backtrack_state state_type;
+
+    template <typename Operation, typename Rings, typename Turns>
+    static inline void apply(std::size_t size_at_start, 
+                Rings& rings, typename boost::range_value<Rings>::type& ring,
+                Turns& turns, Operation& operation,
+                std::string const& reason,
+                Geometry1 const& geometry1,
+                Geometry2 const& geometry2,
+                state_type& state
+                )
+    {
+        std::cout << " REJECT " << reason << std::endl;
+        
+        state.m_good = false;
+
+        rings.resize(size_at_start);
+        ring.clear();
+        operation.visited.set_rejected();
+        clear_visit_info(turns);
+
+        int c = 0;
+        for (int i = 0; i < turns.size(); i++)
+        {
+            for (int j = 0; j < 2; j++)
+            {
+                if (turns[i].operations[j].visited.rejected())
+                {
+                    c++;
+                }
+            }
+        }
+        std::cout << "BACKTRACK (" << reason << " )"
+            << " " << c << " of " << turns.size() << " rejected"
+            << std::endl;
+        std::cout
+            << geometry::wkt(geometry1) << std::endl
+            << geometry::wkt(geometry2) << std::endl;
+    }
+};
+#endif // BOOST_GEOMETRY_OVERLAY_REPORT_WKT
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_BACKTRACK_CHECK_SI_HPP

Modified: trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/overlay.hpp	2011-08-05 09:14:22 EDT (Fri, 05 Aug 2011)
@@ -9,6 +9,7 @@
 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
 
+
 #include <deque>
 #include <map>
 
@@ -25,10 +26,6 @@
 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
 
-#if ! defined(BOOST_GEOMETRY_OVERLAY_SKIP_CHECK_SELF_INTERSECTIONS)
-#  include <boost/geometry/algorithms/detail/has_self_intersections.hpp>
-#endif
-
 
 #include <boost/geometry/algorithms/num_points.hpp>
 #include <boost/geometry/algorithms/reverse.hpp>
@@ -171,11 +168,6 @@
                 >(geometry1, geometry2, out);
         }
         
-#if ! defined(BOOST_GEOMETRY_OVERLAY_SKIP_CHECK_SELF_INTERSECTIONS)
-        has_self_intersections(geometry1);
-        has_self_intersections(geometry2);
-#endif
-
         container_type turn_points;
 
 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
@@ -219,11 +211,14 @@
         // Note that these rings are always in clockwise order, even in CCW polygons,
         // and are marked as "to be reversed" below
         ring_container_type rings;
-        geometry::traverse<Reverse1, Reverse2>(geometry1, geometry2,
-                Direction == overlay_union
-                    ? geometry::detail::overlay::operation_union
-                    : geometry::detail::overlay::operation_intersection,
-                turn_points, rings);
+        traverse<Reverse1, Reverse2, Geometry1, Geometry2>::apply
+                (
+                    geometry1, geometry2,
+                    Direction == overlay_union
+                        ? geometry::detail::overlay::operation_union
+                        : geometry::detail::overlay::operation_intersection,
+                    turn_points, rings
+                );
 
 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
         std::cout << "traverse: " << timer.elapsed() << std::endl;

Modified: trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/select_rings.hpp	2011-08-05 09:14:22 EDT (Fri, 05 Aug 2011)
@@ -271,16 +271,17 @@
     typename IntersectionMap, typename SelectionMap
 >
 inline void select_rings(Geometry const& geometry,
-            IntersectionMap const& intersection_map, SelectionMap& selection_map)
+            IntersectionMap const& intersection_map, 
+            SelectionMap& selection_map, bool midpoint)
 {
     typedef typename geometry::tag<Geometry>::type tag;
 
     SelectionMap map_with_all;
     dispatch::select_rings<tag, Geometry>::apply(geometry, 
-                ring_identifier(0, -1, -1), map_with_all);
+                ring_identifier(0, -1, -1), map_with_all, midpoint);
 
-    update_selection_map<OverlayType>(intersection_map, map_with_all, 
-                selection_map);
+    update_selection_map<OverlayType>(geometry, geometry, intersection_map, 
+                map_with_all, selection_map);
 }
 
 

Modified: trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp	2011-08-05 09:14:22 EDT (Fri, 05 Aug 2011)
@@ -15,8 +15,9 @@
 #include <boost/range.hpp>
 
 #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
-#include <boost/geometry/algorithms/detail/overlay/turn_info.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/core/access.hpp>
 #include <boost/geometry/core/coordinate_dimension.hpp>
 #include <boost/geometry/geometries/concepts/check.hpp>
@@ -59,30 +60,6 @@
 }
 
 
-template <typename Turns>
-inline void clear_visit_info(Turns& turns)
-{
-    typedef typename boost::range_value<Turns>::type tp_type;
-
-    for (typename boost::range_iterator<Turns>::type
-        it = boost::begin(turns);
-        it != boost::end(turns);
-        ++it)
-    {
-        for (typename boost::range_iterator
-            <
-                typename tp_type::container_type
-            >::type op_it = boost::begin(it->operations);
-            op_it != boost::end(it->operations);
-            ++op_it)
-        {
-            op_it->visited.clear();
-        }
-        it->discarded = false;
-    }
-}
-
-
 template <typename Info, typename Turn>
 inline void set_visited_for_continue(Info& info, Turn const& turn)
 {
@@ -233,76 +210,6 @@
 
 
 
-template
-<
-    typename Rings,
-    typename Turns,
-    typename Operation,
-    typename Geometry1,
-    typename Geometry2
->
-inline void backtrack(std::size_t size_at_start, bool& fail,
-            Rings& rings, typename boost::range_value<Rings>::type& ring,
-            Turns& turns, Operation& operation,
-
-#ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
-            std::string const& reason,
-            Geometry1 const& geometry1,
-            Geometry2 const& geometry2
-#else
-            std::string const& reason,
-            Geometry1 const& ,
-            Geometry2 const&
-#endif
-            )
-{
-#ifdef BOOST_GEOMETRY_DEBUG_ENRICH
-    std::cout << " REJECT " << reason << std::endl;
-#endif
-    fail = true;
-
-    // Make bad output clean
-    rings.resize(size_at_start);
-    ring.clear();
-
-    // Reject this as a starting point
-    operation.visited.set_rejected();
-
-    // And clear all visit info
-    clear_visit_info(turns);
-
-    /***
-    int c = 0;
-    for (int i = 0; i < turns.size(); i++)
-    {
-        for (int j = 0; j < 2; j++)
-        {
-            if (turns[i].operations[j].visited.rejected())
-            {
-                c++;
-            }
-        }
-    }
-    std::cout << "BACKTRACK (" << reason << " )"
-        << " " << c << " of " << turns.size() << " rejected"
-        << std::endl;
-    ***/
-
-
-
-#ifdef BOOST_GEOMETRY_OVERLAY_REPORT_WKT
-    std::cout << " BT (" << reason << " )";
-    std::cout
-        << geometry::wkt(geometry1) << std::endl
-        << geometry::wkt(geometry2) << std::endl;
-#endif
-
-}
-
-}} // namespace detail::overlay
-#endif // DOXYGEN_NO_DETAIL
-
-
 /*!
     \brief Traverses through intersection points / geometries
     \ingroup overlay
@@ -312,165 +219,173 @@
     bool Reverse1, bool Reverse2,
     typename Geometry1,
     typename Geometry2,
-    typename Turns,
-    typename Rings
+    typename Backtrack = backtrack_check_self_intersections<Geometry1, Geometry2>
 >
-inline void traverse(Geometry1 const& geometry1,
-            Geometry2 const& geometry2,
-            detail::overlay::operation_type operation,
-            Turns& turns, Rings& rings)
+class traverse
 {
-    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;
+public :
+    template <typename Turns, typename Rings>
+    static inline void apply(Geometry1 const& geometry1,
+                Geometry2 const& geometry2,
+                detail::overlay::operation_type operation,
+                Turns& turns, Rings& rings)
+    {
+        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 size_at_start = boost::size(rings);
+        std::size_t size_at_start = boost::size(rings);
 
-    bool fail = false;
-    do
-    {
-        fail = false;
-        // Iterate through all unvisited points
-        for (turn_iterator it = boost::begin(turns);
-            ! fail && it != boost::end(turns);
-            ++it)
+        typename Backtrack::state_type state;
+        do
         {
-            // Skip discarded ones
-            if (! (it->is_discarded() || it->blocked()))
+            state.reset();
+
+            // Iterate through all unvisited points
+            for (turn_iterator it = boost::begin(turns);
+                state.good() && it != boost::end(turns);
+                ++it)
             {
-                for (turn_operation_iterator_type iit = boost::begin(it->operations);
-                    ! fail && iit != boost::end(it->operations);
-                    ++iit)
+                // Skip discarded ones
+                if (! (it->is_discarded() || it->blocked()))
                 {
-                    if (iit->visited.none()
-                        && ! iit->visited.rejected()
-                        && (iit->operation == operation
-                            || iit->operation == detail::overlay::operation_continue)
-                        )
+                    for (turn_operation_iterator_type iit = boost::begin(it->operations);
+                        state.good() && iit != boost::end(it->operations);
+                        ++iit)
                     {
-                        set_visited_for_continue(*it, *iit);
-
-                        typename boost::range_value<Rings>::type current_output;
-                        detail::overlay::append_no_duplicates(current_output, 
-                                    it->point, true);
-
-                        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))
-                        {
-                            detail::overlay::backtrack(
-                                size_at_start, fail,
-                                rings, current_output, turns, *current_iit,
-                                "No next IP",
-                                geometry1, geometry2);
-                        }
-
-                        if (! detail::overlay::select_next_ip(
-                                        operation,
-                                        *current,
-                                        current_seg_id,
-                                        current_iit))
-                        {
-                            detail::overlay::backtrack(
-                                size_at_start, fail,
-                                rings, current_output, turns, *iit,
-                                "Dead end at start",
-                                geometry1, geometry2);
-                        }
-                        else
+                        if (iit->visited.none()
+                            && ! iit->visited.rejected()
+                            && (iit->operation == operation
+                                || iit->operation == detail::overlay::operation_continue)
+                            )
                         {
+                            set_visited_for_continue(*it, *iit);
 
-                            iit->visited.set_started();
-                            detail::overlay::debug_traverse(*it, *iit, "-> Started");
-                            detail::overlay::debug_traverse(*current, *current_iit, "Selected  ");
+                            typename boost::range_value<Rings>::type current_output;
+                            detail::overlay::append_no_duplicates(current_output, 
+                                        it->point, true);
 
+                            turn_iterator current = it;
+                            turn_operation_iterator_type current_iit = iit;
+                            segment_identifier current_seg_id;
 
-                            unsigned int i = 0;
+                            if (! detail::overlay::assign_next_ip<Reverse1, Reverse2>(
+                                        geometry1, geometry2,
+                                        turns,
+                                        current, current_output,
+                                        *iit, current_seg_id))
+                            {
+                                Backtrack::apply(
+                                    size_at_start, 
+                                    rings, current_output, turns, *current_iit,
+                                    "No next IP",
+                                    geometry1, geometry2, state);
+                            }
 
-                            while (current_iit != iit && ! fail)
+                            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, state);
+                            }
+                            else
                             {
-                                if (current_iit->visited.visited())
-                                {
-                                    // It visits a visited node again, without passing the start node.
-                                    // This makes it suspicious for endless loops
-                                    detail::overlay::backtrack(
-                                        size_at_start, fail,
-                                        rings,  current_output, turns, *iit,
-                                        "Visit again",
-                                        geometry1, geometry2);
-                                }
-                                else
-                                {
 
+                                iit->visited.set_started();
+                                detail::overlay::debug_traverse(*it, *iit, "-> Started");
+                                detail::overlay::debug_traverse(*current, *current_iit, "Selected  ");
 
-                                    // 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);
+                                unsigned int i = 0;
 
-                                    if (! detail::overlay::select_next_ip(
-                                                operation,
-                                                *current,
-                                                current_seg_id,
-                                                current_iit))
+                                while (current_iit != iit && state.good())
+                                {
+                                    if (current_iit->visited.visited())
                                     {
-                                        // Should not occur in valid (non-self-intersecting) polygons
-                                        // Should not occur in self-intersecting polygons without spikes
-                                        // Might occur in polygons with spikes
-                                        detail::overlay::backtrack(
-                                            size_at_start, fail,
+                                        // 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,
-                                            "Dead end",
-                                            geometry1, geometry2);
+                                            "Visit again",
+                                            geometry1, geometry2, state);
                                     }
-                                    detail::overlay::debug_traverse(*current, *current_iit, "Selected  ");
-
-                                    if (i++ > 2 + 2 * turns.size())
+                                    else
                                     {
-                                        // Sanity check: there may be never more loops
-                                        // than turn points.
-                                        // Turn points marked as "ii" can be visited twice.
-                                        detail::overlay::backtrack(
-                                            size_at_start, fail,
-                                            rings,  current_output, turns, *iit,
-                                            "Endless loop",
-                                            geometry1, geometry2);
+
+
+                                        // 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);
+
+                                        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, state);
+                                        }
+                                        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, state);
+                                        }
                                     }
                                 }
-                            }
 
-                            if (! fail)
-                            {
-                                iit->visited.set_finished();
-                                detail::overlay::debug_traverse(*current, *iit, "->Finished");
-                                rings.push_back(current_output);
+                                if (state.good())
+                                {
+                                    iit->visited.set_finished();
+                                    detail::overlay::debug_traverse(*current, *iit, "->Finished");
+                                    rings.push_back(current_output);
+                                }
                             }
                         }
                     }
                 }
             }
-        }
-    } while (fail);
-}
+        } while (! state.good());
+    }
+};
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
 
 
 }} // namespace boost::geometry

Modified: trunk/boost/geometry/extensions/algorithms/dissolve.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/dissolve.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/dissolve.hpp	2011-08-05 09:14:22 EDT (Fri, 05 Aug 2011)
@@ -46,6 +46,36 @@
 namespace detail { namespace dissolve
 {
 
+template<typename Geometry>
+class backtrack_for_dissolve
+{
+public :
+    typedef detail::overlay::backtrack_state state_type;
+
+    template <typename Operation, typename Rings, typename Turns>
+    static inline void apply(std::size_t size_at_start, 
+                Rings& rings, typename boost::range_value<Rings>::type& ring,
+                Turns& turns, Operation& operation,
+                std::string const& ,
+                Geometry const& ,
+                Geometry const& ,
+                state_type& state
+                )
+    {
+        state.m_good = false;
+        
+        // Make bad output clean
+        rings.resize(size_at_start);
+        ring.clear();
+
+        // Reject this as a starting point
+        operation.visited.set_rejected();
+
+        // And clear all visit info
+        clear_visit_info(turns);
+    }
+};
+
 
 template <typename Geometry, typename GeometryOut>
 struct dissolve_ring_or_polygon
@@ -62,7 +92,7 @@
 
         std::vector<turn_info> turns;
         detail::get_turns::no_interrupt_policy policy;
-        geometry::get_turns
+        geometry::self_turns
             <
                 detail::overlay::calculate_distance_policy
             >(geometry, turns, policy);
@@ -86,9 +116,16 @@
                         geometry, geometry,
                         side_strategy_type());
 
+            typedef detail::overlay::traverse
+                <
+                    false, false, 
+                    Geometry, Geometry,
+                    backtrack_for_dissolve<Geometry>
+                > traverser;
+
 
             // Traverse the polygons twice for union...
-            traverse<false, false>(geometry, geometry,
+            traverser::apply(geometry, geometry,
                             detail::overlay::operation_union,
                             turns, rings);
 
@@ -101,7 +138,7 @@
 
 
             // ... and for intersection
-            traverse<false, false>(geometry, geometry,
+            traverser::apply(geometry, geometry,
                             detail::overlay::operation_intersection,
                             turns, rings);
 
@@ -112,7 +149,7 @@
 
             std::map<ring_identifier, properties> selected;
 
-            detail::overlay::select_rings<overlay_union>(geometry, map, selected);
+            detail::overlay::select_rings<overlay_union>(geometry, map, selected, true);
 
             // Add intersected rings
             {
@@ -122,7 +159,7 @@
                         it != boost::end(rings);
                         ++it)
                 {
-                    selected[id] = properties(*it);
+                    selected[id] = properties(*it, true);
                     id.multi_index++;
                 }
             }