[Boost-commit] svn:boost r69948 - in trunk/boost/geometry/algorithms/detail: . overlay

Subject: [Boost-commit] svn:boost r69948 - in trunk/boost/geometry/algorithms/detail: . overlay
From: barend.gehrels_at_[hidden]
Date: 2011-03-13 11:22:33

Author: barendgehrels
Date: 2011-03-13 11:22:31 EDT (Sun, 13 Mar 2011)
New Revision: 69948
URL: http://svn.boost.org/trac/boost/changeset/69948

Log:
Added check in partition to check if partitioning is necessary, saves building up index vector(s)
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp |     4 +-                                      
   trunk/boost/geometry/algorithms/detail/partition.hpp         |    73 +++++++++++++++++++++++++++------------ 
   2 files changed, 53 insertions(+), 24 deletions(-)

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-03-13 11:22:31 EDT (Sun, 13 Mar 2011)
@@ -405,7 +405,7 @@
         typedef typename boost::range_value<Turns>::type ip_type;
         typedef typename ip_type::point_type point_type;
         typedef model::box<point_type> box_type;
-        typedef typename geometry::sections<box_type, 2> sections_type;
+        typedef typename geometry::sections<box_type, 1> sections_type;
 
         sections_type sec1, sec2;
 
@@ -423,7 +423,7 @@
         geometry::partition
             <
                 box_type, get_section_box, ovelaps_section_box
-            >::apply(sec1, sec2, visitor, 2);
+            >::apply(sec1, sec2, visitor, 4);
     }
 };
 

Modified: trunk/boost/geometry/algorithms/detail/partition.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/partition.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/partition.hpp	2011-03-13 11:22:31 EDT (Sun, 13 Mar 2011)
@@ -294,33 +294,62 @@
     template <typename InputCollection, typename Visitor>
     static inline void apply(InputCollection const& collection, Visitor& visitor, int min_elements = 16)
     {
-        index_vector_type index_vector;
-        Box total;
-        assign_inverse(total);
-        expand_to_collection(collection, total, index_vector);
-
-        detail::partition_one_collection
-            <
-                0, Box, OverlapsPolicy
-            >::apply(total, collection, index_vector, 0, min_elements, visitor);
+        if (boost::size(collection) > min_elements)
+        {
+            index_vector_type index_vector;
+            Box total;
+            assign_inverse(total);
+            expand_to_collection(collection, total, index_vector);
+
+            detail::partition_one_collection
+                <
+                    0, Box, OverlapsPolicy
+                >::apply(total, collection, index_vector, 0, min_elements, visitor);
+        }
+        else
+        {
+            typedef typename boost::range_iterator<InputCollection const>::type iterator_type;
+            for(iterator_type it1 = boost::begin(collection); it1 != boost::end(collection); ++it1)
+            {
+                iterator_type it2 = it1;
+                for(++it2; it2 != boost::end(collection); ++it2)
+                {
+                    visitor.apply(*it1, *it2);
+                }
+            }
+        }
     }
 
     template <typename InputCollection, typename Visitor>
     static inline void apply(InputCollection const& collection1, InputCollection const& collection2, Visitor& visitor, int min_elements = 16)
     {
-        index_vector_type index_vector1, index_vector2;
-        Box total;
-        assign_inverse(total);
-        expand_to_collection(collection1, total, index_vector1);
-        expand_to_collection(collection2, total, index_vector2);
-
-        detail::partition_two_collections
-            <
-                0, Box, OverlapsPolicy
-            >::apply(total, 
-                collection1, index_vector1, 
-                collection2, index_vector2, 
-                0, min_elements, visitor);
+        if (boost::size(collection1) > min_elements && boost::size(collection2) > min_elements)
+        {
+            index_vector_type index_vector1, index_vector2;
+            Box total;
+            assign_inverse(total);
+            expand_to_collection(collection1, total, index_vector1);
+            expand_to_collection(collection2, total, index_vector2);
+
+            detail::partition_two_collections
+                <
+                    0, Box, OverlapsPolicy
+                >::apply(total, 
+                    collection1, index_vector1, 
+                    collection2, index_vector2, 
+                    0, min_elements, visitor);
+        }
+        else
+        {
+            typedef typename boost::range_iterator<InputCollection const>::type iterator_type;
+            for(iterator_type it1 = boost::begin(collection1); it1 != boost::end(collection1); ++it1)
+            {
+                for(iterator_type it2 = boost::begin(collection2); it2 != boost::end(collection2); ++it2)
+                {
+                    visitor.apply(*it1, *it2);
+                }
+            }
+        }
     }
 
 };