[Boost-commit] svn:boost r73599 - in trunk/boost/geometry: algorithms/detail algorithms/detail/overlay strategies/cartesian

Subject: [Boost-commit] svn:boost r73599 - in trunk/boost/geometry: algorithms/detail algorithms/detail/overlay strategies/cartesian
From: barend.gehrels_at_[hidden]
Date: 2011-08-07 12:46:34

Author: barendgehrels
Date: 2011-08-07 12:46:33 EDT (Sun, 07 Aug 2011)
New Revision: 73599
URL: http://svn.boost.org/trac/boost/changeset/73599

Log:
Fixed performance issue on self intersections
Text files modified: 
   trunk/boost/geometry/algorithms/detail/has_self_intersections.hpp   |     2                                         
   trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp        |    11 +--                                     
   trunk/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp |   112 +++++++++++++++++++++++++++------------ 
   trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp        |     2                                         
   4 files changed, 84 insertions(+), 43 deletions(-)

Modified: trunk/boost/geometry/algorithms/detail/has_self_intersections.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/has_self_intersections.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/has_self_intersections.hpp	2011-08-07 12:46:33 EDT (Sun, 07 Aug 2011)
@@ -62,7 +62,7 @@
     typedef typename point_type<Geometry>::type point_type;
     typedef detail::overlay::turn_info<point_type> turn_info;
     std::deque<turn_info> turns;
-    detail::get_turns::no_interrupt_policy policy;
+    detail::disjoint::disjoint_interrupt_policy policy;
     geometry::self_turns<detail::overlay::assign_null_policy>(geometry, turns, policy);
     
 #ifdef BOOST_GEOMETRY_DEBUG_HAS_SELF_INTERSECTIONS

Modified: trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp	2011-08-07 12:46:33 EDT (Sun, 07 Aug 2011)
@@ -147,11 +147,8 @@
                             >::type, 
                         areal_tag
                     >::value
-               && 
-                (
-                    (index2 == 0 && index1 >= n - 2)
-                    || (index1 == 0 && index2 >= n - 2)
-                )
+               && index1 == 0 
+               && index2 >= n - 2
                 ;
     }
 
@@ -232,8 +229,8 @@
                     // Also skip if index1 < index2 to avoid getting all
                     // intersections twice (only do this on same source!)
 
-                    skip = index2 >= index1
-                        || ndi1 == ndi2 + 1
+                    skip = index1 >= index2
+                        || ndi2 == ndi1 + 1
                         || neighbouring<Geometry1>(sec1, index1, index2)
                         ;
                 }

Modified: trunk/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/self_turn_points.hpp	2011-08-07 12:46:33 EDT (Sun, 07 Aug 2011)
@@ -19,6 +19,7 @@
 #include <boost/geometry/geometries/concepts/check.hpp>
 
 #include <boost/geometry/algorithms/detail/disjoint.hpp>
+#include <boost/geometry/algorithms/detail/partition.hpp>
 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
 
 #include <boost/geometry/geometries/box.hpp>
@@ -31,6 +32,60 @@
 namespace detail { namespace self_get_turn_points
 {
 
+class self_ip_exception : public geometry::exception {};
+
+template
+<
+    typename Geometry,
+    typename Turns,
+    typename TurnPolicy,
+    typename InterruptPolicy
+>
+struct self_section_visitor
+{
+    Geometry const& m_geometry;
+    Turns& m_turns;
+    InterruptPolicy& m_interrupt_policy;
+
+    inline self_section_visitor(Geometry const& g,
+            Turns& turns, InterruptPolicy& ip)
+        : m_geometry(g)
+        , m_turns(turns)
+        , m_interrupt_policy(ip)
+    {}
+
+    template <typename Section>
+    inline bool apply(Section const& sec1, Section const& sec2)
+    {
+        if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box)
+                && ! sec1.duplicate
+                && ! sec2.duplicate)
+        {
+            detail::get_turns::get_turns_in_sections
+                    <
+                        Geometry, Geometry,
+                        false, false,
+                        Section, Section,
+                        Turns, TurnPolicy,
+                        InterruptPolicy
+                    >::apply(
+                            0, m_geometry, sec1,
+                            0, m_geometry, sec2,
+                            m_turns, m_interrupt_policy);
+        }
+        if (m_interrupt_policy.has_intersections)
+        {
+            // TODO: we should give partition an interrupt policy.
+            // Now we throw, and catch below, to stop the partition loop.
+            throw self_ip_exception();
+        }
+        return true;
+    }
+
+};
+
+
+
 template
 <
     typename Geometry,
@@ -45,49 +100,38 @@
             Turns& turns,
             InterruptPolicy& interrupt_policy)
     {
+        typedef model::box
+            <
+                typename geometry::point_type<Geometry>::type
+            > box_type;
         typedef typename geometry::sections
             <
-                model::box <typename geometry::point_type<Geometry>::type>,
-                1
+                box_type, 1
             > sections_type;
 
         sections_type sec;
         geometry::sectionalize<false>(geometry, sec);
 
-        for (typename boost::range_iterator<sections_type const>::type
-                    it1 = sec.begin();
-            it1 != sec.end();
-            ++it1)
+        self_section_visitor
+            <
+                Geometry,
+                Turns, TurnPolicy, InterruptPolicy
+            > visitor(geometry, turns, interrupt_policy);
+
+        try
         {
-            for (typename boost::range_iterator<sections_type const>::type
-                        it2 = sec.begin();
-                it2 != sec.end();
-                ++it2)
-            {
-                if (! geometry::detail::disjoint::disjoint_box_box(
-                                it1->bounding_box, it2->bounding_box)
-                    && ! it1->duplicate
-                    && ! it2->duplicate
-                    )
-                {
-                    if (! geometry::detail::get_turns::get_turns_in_sections
-                        <
-                            Geometry, Geometry,
-                            false, false,
-                            typename boost::range_value<sections_type>::type,
-                            typename boost::range_value<sections_type>::type,
-                            Turns, TurnPolicy,
-                            InterruptPolicy
-                        >::apply(
-                                0, geometry, *it1,
-                                0, geometry, *it2,
-                                turns, interrupt_policy))
-                    {
-                        return false;
-                    }
-                }
-            }
+            geometry::partition
+                <
+                    box_type, 
+                    detail::get_turns::get_section_box, 
+                    detail::get_turns::ovelaps_section_box
+                >::apply(sec, visitor);
         }
+        catch(self_ip_exception const& )
+        {
+            return false;
+        }
+
         return true;
     }
 };

Modified: trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp
==============================================================================
--- trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp	(original)
+++ trunk/boost/geometry/strategies/cartesian/cart_intersect.hpp	2011-08-07 12:46:33 EDT (Sun, 07 Aug 2011)
@@ -193,7 +193,7 @@
 
         bool collinear = sides.collinear();
 
-        // Get the same type, but at least a double (also used for divisions
+        // Get the same type, but at least a double (also used for divisions)
         typedef typename select_most_precise
             <
                 coordinate_type, double