Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r69942 - trunk/boost/geometry/algorithms/detail
From: barend.gehrels_at_[hidden]
Date: 2011-03-13 10:43:20


Author: barendgehrels
Date: 2011-03-13 10:43:17 EDT (Sun, 13 Mar 2011)
New Revision: 69942
URL: http://svn.boost.org/trac/boost/changeset/69942

Log:
Implemented partition for two ranges
Text files modified:
   trunk/boost/geometry/algorithms/detail/partition.hpp | 272 +++++++++++++++++++++++++++++----------
   1 files changed, 201 insertions(+), 71 deletions(-)

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 10:43:17 EDT (Sun, 13 Mar 2011)
@@ -1,6 +1,6 @@
 // Boost.Geometry (aka GGL, Generic Geometry Library)
 //
-// Copyright Barend Gehrels 2010, Geodan, Amsterdam, the Netherlands.
+// Copyright Barend Gehrels 2011, Geodan, 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)
@@ -19,57 +19,120 @@
 namespace detail
 {
 
+template <int Dimension, typename Box>
+inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
+{
+ typedef typename coordinate_type<Box>::type ctype;
+
+ // Divide input box into two parts, e.g. left/right
+ ctype two = 2;
+ ctype mid = (geometry::get<min_corner, Dimension>(box)
+ + geometry::get<max_corner, Dimension>(box)) / two;
+
+ lower_box = box;
+ upper_box = box;
+ geometry::set<max_corner, Dimension>(lower_box, mid);
+ geometry::set<min_corner, Dimension>(upper_box, mid);
+}
+
 template
 <
- int Dimension,
     typename Box,
     typename OverlapsPolicy
>
-class partition
+class partition_generic
 {
- typedef typename coordinate_type<Box>::type ctype;
     typedef std::vector<std::size_t> index_vector_type;
+protected :
     typedef boost::range_iterator<index_vector_type const>::type index_iterator_type;
- typedef partition
- <
- 1 - Dimension,
- Box,
- OverlapsPolicy
- > sub_divide;
 
+ // Divide collection into three subsets: lower, upper and oversized (not-fitting)
+ // (lower == left or bottom, upper == right or top)
+ template <typename InputCollection>
+ static inline void divide_into_subsets(Box const& lower_box, Box const& upper_box,
+ InputCollection const& collection,
+ index_vector_type const& input,
+ index_vector_type& lower, index_vector_type& upper, index_vector_type& exceeding)
+ {
+ for(index_iterator_type it = boost::begin(input);
+ it != boost::end(input);
+ ++it)
+ {
+ bool const lower_overlapping = OverlapsPolicy::apply(lower_box, collection[*it]);
+ bool const upper_overlapping = OverlapsPolicy::apply(upper_box, collection[*it]);
 
+ if (lower_overlapping && upper_overlapping)
+ {
+ exceeding.push_back(*it);
+ }
+ else if (lower_overlapping)
+ {
+ lower.push_back(*it);
+ }
+ else if (upper_overlapping)
+ {
+ upper.push_back(*it);
+ }
+ else
+ {
+ // Is nowhere! Should not occur!
+ BOOST_ASSERT(true);
+ }
+ }
+ }
+
+ // Match collection 1 with collection 2
     template <typename InputCollection, typename Policy>
- static inline void handle(InputCollection const& collection,
+ static inline void handle_one(InputCollection const& collection,
             index_vector_type const& input,
             Policy& policy)
     {
         // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
         for(index_iterator_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
         {
- for(index_iterator_type it2 = boost::begin(input); it2 != boost::end(input); ++it2)
+ index_iterator_type it2 = it1;
+ for(++it2; it2 != boost::end(input); ++it2)
             {
                 policy.apply(collection[*it1], collection[*it2]);
             }
         }
     }
 
+ // Match collection 1 with collection 2
     template <typename InputCollection, typename Policy>
- static inline void handle_exceeding(InputCollection const& collection,
- index_vector_type const& exceeding,
- index_vector_type const& input,
+ static inline void handle_two(
+ InputCollection const& collection1, index_vector_type const& input1,
+ InputCollection const& collection2, index_vector_type const& input2,
             Policy& policy)
     {
- if (boost::size(input) > 0)
+ for(index_iterator_type it1 = boost::begin(input1); it1 != boost::end(input1); ++it1)
         {
- for(index_iterator_type it1 = boost::begin(exceeding); it1 != boost::end(exceeding); ++it1)
+ for(index_iterator_type it2 = boost::begin(input2); it2 != boost::end(input2); ++it2)
             {
- for(index_iterator_type it2 = boost::begin(input); it2 != boost::end(input); ++it2)
- {
- policy.apply(collection[*it1], collection[*it2]);
- }
+ policy.apply(collection1[*it1], collection2[*it2]);
             }
         }
     }
+};
+
+
+
+template
+<
+ int Dimension,
+ typename Box,
+ typename OverlapsPolicy
+>
+class partition_one_collection : public partition_generic<Box, OverlapsPolicy>
+{
+ typedef std::vector<std::size_t> index_vector_type;
+ typedef typename coordinate_type<Box>::type ctype;
+ typedef partition_one_collection
+ <
+ 1 - Dimension,
+ Box,
+ OverlapsPolicy
+ > sub_divide;
 
     template <typename InputCollection, typename Policy>
     static inline void next_level(Box const& box,
@@ -86,7 +149,7 @@
             }
             else
             {
- handle(collection, input, policy);
+ handle_one(collection, input, policy);
             }
         }
     }
@@ -100,62 +163,106 @@
             int min_elements,
             Policy& policy)
     {
- typedef typename boost::range_value<InputCollection>::type item_type;
-
- // Divide input box into two parts, e.g. left/right
- ctype two = 2;
- ctype mid = (geometry::get<min_corner, Dimension>(box)
- + geometry::get<max_corner, Dimension>(box)) / two;
-
- Box lower_box = box, upper_box = box;
- geometry::set<max_corner, Dimension>(lower_box, mid);
- geometry::set<min_corner, Dimension>(upper_box, mid);
+ Box lower_box, upper_box;
+ divide_box<Dimension>(box, lower_box, upper_box);
 
- // Divide collection into three subsets: lower, upper and oversized (not-fitting)
- // (lower == left or bottom, upper == right or top)
         index_vector_type lower, upper, exceeding;
- for(index_iterator_type it = boost::begin(input);
- it != boost::end(input);
- ++it)
+ divide_into_subsets(lower_box, upper_box, collection, input, lower, upper, exceeding);
+
+ if (boost::size(exceeding) > 0)
         {
- bool const lower_overlapping = OverlapsPolicy::apply(lower_box, collection[*it]);
- bool const upper_overlapping = OverlapsPolicy::apply(upper_box, collection[*it]);
+ // All what is not fitting a partition should be combined
+ // with each other, and with all which is fitting.
+ handle_one(collection, exceeding, policy);
+ handle_two(collection, exceeding, collection, lower, policy);
+ handle_two(collection, exceeding, collection, upper, policy);
+ }
 
- if (lower_overlapping && upper_overlapping)
- {
- exceeding.push_back(*it);
- }
- else if (lower_overlapping)
- {
- lower.push_back(*it);
- }
- else if (upper_overlapping)
+ // Recursively call operation both parts
+ next_level(lower_box, collection, lower, level, min_elements, policy);
+ next_level(upper_box, collection, upper, level, min_elements, policy);
+ }
+};
+
+
+template
+<
+ int Dimension,
+ typename Box,
+ typename OverlapsPolicy
+>
+class partition_two_collections : public partition_generic<Box, OverlapsPolicy>
+{
+ typedef std::vector<std::size_t> index_vector_type;
+ typedef typename coordinate_type<Box>::type ctype;
+ typedef partition_two_collections
+ <
+ 1 - Dimension,
+ Box,
+ OverlapsPolicy
+ > sub_divide;
+
+ template <typename InputCollection, typename Policy>
+ static inline void next_level(Box const& box,
+ InputCollection const& collection1, index_vector_type const& input1,
+ InputCollection const& collection2, index_vector_type const& input2,
+ int level, int min_elements,
+ Policy& policy)
+ {
+ if (boost::size(input1) > 0 && boost::size(input2) > 0)
+ {
+ if (boost::size(input1) > min_elements
+ && boost::size(input2) > min_elements
+ && level < 100)
             {
- upper.push_back(*it);
+ sub_divide::apply(box, collection1, input1, collection2, input2, level + 1, min_elements, policy);
             }
             else
             {
- // Is nowhere! Should not occur!
- BOOST_ASSERT(true);
+ handle_two(collection1, input1, collection2, input2, policy);
             }
         }
+ }
 
- if (boost::size(exceeding) > 0)
+public :
+ template <typename InputCollection, typename Policy>
+ static inline void apply(Box const& box,
+ InputCollection const& collection1, index_vector_type const& input1,
+ InputCollection const& collection2, index_vector_type const& input2,
+ int level,
+ int min_elements,
+ Policy& policy)
+ {
+ Box lower_box, upper_box;
+ divide_box<Dimension>(box, lower_box, upper_box);
+
+ index_vector_type lower1, upper1, exceeding1;
+ index_vector_type lower2, upper2, exceeding2;
+ divide_into_subsets(lower_box, upper_box, collection1, input1, lower1, upper1, exceeding1);
+ divide_into_subsets(lower_box, upper_box, collection2, input2, lower2, upper2, exceeding2);
+
+ if (boost::size(exceeding1) > 0)
         {
- // All what is not fitting a partition should be combined
- // with each other, and with all which is fitting.
- handle(collection, exceeding, policy);
- handle_exceeding(collection, exceeding, lower, policy);
- handle_exceeding(collection, exceeding, upper, policy);
+ // All exceeding from 1 with 2:
+ handle_two(collection1, exceeding1, collection2, exceeding2, policy);
+
+ // All exceeding from 1 with lower and upper of 2:
+ handle_two(collection1, exceeding1, collection2, lower2, policy);
+ handle_two(collection1, exceeding1, collection2, upper2, policy);
+ }
+ if (boost::size(exceeding2) > 0)
+ {
+ // All exceeding from 2 with lower and upper of 1:
+ handle_two(collection1, lower1, collection2, exceeding2, policy);
+ handle_two(collection1, upper1, collection2, exceeding2, policy);
         }
 
- // Recursively call operation both halves
- next_level(lower_box, collection, lower, level, min_elements, policy);
- next_level(upper_box, collection, upper, level, min_elements, policy);
+ next_level(lower_box, collection1, lower1, collection2, lower2, level, min_elements, policy);
+ next_level(upper_box, collection1, upper1, collection2, upper2, level, min_elements, policy);
     }
 };
 
-}
+} // namespace detail
 
 
 template
@@ -168,15 +275,9 @@
 {
     typedef std::vector<std::size_t> index_vector_type;
 
-public :
- template <typename InputCollection, typename Visitor>
- static inline void apply(InputCollection const& collection, Visitor& visitor, int min_elements = 16)
+ template <typename InputCollection>
+ static inline void expand_to_collection(InputCollection const& collection, Box& total, index_vector_type& index_vector)
     {
- index_vector_type index_vector;
-
- // Determine total box
- Box total;
- assign_inverse(total);
         std::size_t index = 0;
         for(typename boost::range_iterator<InputCollection const>::type it
             = boost::begin(collection);
@@ -186,13 +287,42 @@
             ExpandPolicy::apply(total, *it);
             index_vector.push_back(index);
         }
+ }
 
- // Start recursion
- detail::partition
+
+public :
+ 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);
     }
+
+ 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);
+ }
+
 };
 
 


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk