|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r72714 - in sandbox-branches/geometry/index: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/rstar tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-06-21 15:29:45
Author: awulkiew
Date: 2011-06-21 15:29:44 EDT (Tue, 21 Jun 2011)
New Revision: 72714
URL: http://svn.boost.org/trac/boost/changeset/72714
Log:
Implemented R* choose_next_node algorithm version choosing by nearly min overlap cost
Text files modified:
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp | 10 ++--
sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 81 +++++++++++++++++++++++++++++++++++++--
sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp | 17 ++++---
3 files changed, 90 insertions(+), 18 deletions(-)
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/options.hpp 2011-06-21 15:29:44 EDT (Tue, 21 Jun 2011)
@@ -62,14 +62,14 @@
template <size_t MaxElements,
size_t MinElements,
- bool UseNearlyMinimumCost = false,
+ size_t OverlapCostThreshold = 0,
size_t ReinsertedElements = options::detail::default_rstar_reinserted_elements<MaxElements>::value
>
struct rstar
{
static const size_t max_elements = MaxElements;
static const size_t min_elements = MinElements;
- static const bool use_nearly_minimum_cost = UseNearlyMinimumCost;
+ static const size_t overlap_cost_threshold = OverlapCostThreshold;
static const size_t reinserted_elements = ReinsertedElements;
};
@@ -131,11 +131,11 @@
> type;
};
-template <size_t MaxElements, size_t MinElements, bool UseNearlyMinimumCost, size_t ReinsertedElements>
-struct options_type< rstar<MaxElements, MinElements, UseNearlyMinimumCost, ReinsertedElements> >
+template <size_t MaxElements, size_t MinElements, size_t OverlapCostThreshold, size_t ReinsertedElements>
+struct options_type< rstar<MaxElements, MinElements, OverlapCostThreshold, ReinsertedElements> >
{
typedef options::rtree<
- rstar<MaxElements, MinElements, UseNearlyMinimumCost, ReinsertedElements>,
+ rstar<MaxElements, MinElements, OverlapCostThreshold, ReinsertedElements>,
reinsert_tag,
choose_by_overlap_diff_tag,
rstar_tag,
Modified: sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp (original)
+++ sandbox-branches/geometry/index/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp 2011-06-21 15:29:44 EDT (Tue, 21 Jun 2011)
@@ -35,6 +35,7 @@
typedef typename rtree::leaf<Value, typename Options::parameters_type, Box, typename Options::node_tag>::type leaf;
typedef typename rtree::elements_type<internal_node>::type children_type;
+ typedef typename children_type::value_type child_type;
typedef typename Options::parameters_type parameters_type;
@@ -50,7 +51,8 @@
// children are leafs
if ( node_relative_level <= 1 )
{
- if ( parameters_type::use_nearly_minimum_cost )
+ if ( 0 < parameters_type::overlap_cost_threshold &&
+ parameters_type::overlap_cost_threshold < children.size() )
return choose_by_nearly_minimum_overlap_cost(children, indexable);
else
return choose_by_minimum_overlap_cost(children, indexable);
@@ -75,7 +77,6 @@
// for each child node
for (size_t i = 0 ; i < children_count ; ++i )
{
- typedef typename children_type::value_type child_type;
child_type const& ch_i = children[i];
Box box_exp(ch_i.first);
@@ -121,12 +122,81 @@
template <typename Indexable>
static inline size_t choose_by_nearly_minimum_overlap_cost(children_type const& children, Indexable const& indexable)
{
- // TODO - awulkiew: implement this function
+ const size_t children_count = children.size();
- return choose_by_minimum_overlap_cost(children, indexable);
+ // create container of children sorted by area enlargement needed to include the new value
+ std::vector< boost::tuple<size_t, area_type, area_type> > sorted_children(children_count);
+ for ( size_t i = 0 ; i < children_count ; ++i )
+ {
+ child_type const& ch_i = children[i];
+
+ // expanded child node's box
+ Box box_exp(ch_i.first);
+ geometry::expand(box_exp, indexable);
+
+ // areas difference
+ area_type area = index::area(box_exp);
+ area_type area_diff = area - index::area(ch_i.first);
+
+ sorted_children[i] = boost::make_tuple(i, area_diff, area);
+ }
+
+ // sort by area_diff
+ std::sort(sorted_children.begin(), sorted_children.end(), area_diff_less);
+
+ BOOST_GEOMETRY_INDEX_ASSERT(parameters_type::overlap_cost_threshold <= children_count, "there are not enough children");
+
+ // for overlap_cost_threshold child nodes find the one with smallest overlap value
+ size_t choosen_index = 0;
+ overlap_type smallest_overlap_diff = std::numeric_limits<overlap_type>::max();
+
+ // for each node
+ for (size_t i = 0 ; i < parameters_type::overlap_cost_threshold ; ++i )
+ {
+ size_t child_index = boost::get<0>(sorted_children[i]);
+
+ typedef typename children_type::value_type child_type;
+ child_type const& ch_i = children[child_index];
+
+ Box box_exp(ch_i.first);
+ // calculate expanded box of child node ch_i
+ geometry::expand(box_exp, indexable);
+
+ overlap_type overlap = 0;
+ overlap_type overlap_exp = 0;
+
+ // calculate overlap
+ for ( size_t j = 0 ; j < children_count ; ++j )
+ {
+ if ( child_index != j )
+ {
+ child_type const& ch_j = children[j];
+
+ overlap += index::overlap(ch_i.first, ch_j.first);
+ overlap_exp += index::overlap(box_exp, ch_j.first);
+ }
+ }
+
+ overlap_type overlap_diff = overlap_exp - overlap;
+
+ // update result
+ if ( overlap_diff < smallest_overlap_diff )
+ {
+ smallest_overlap_diff = overlap_diff;
+ choosen_index = child_index;
+ }
+ }
+
+ return choosen_index;
}
- template <typename Indexable>
+ static inline bool area_diff_less(boost::tuple<size_t, area_type, area_type> const& p1, boost::tuple<size_t, area_type, area_type> const& p2)
+ {
+ return boost::get<1>(p1) < boost::get<1>(p2) ||
+ (boost::get<1>(p1) == boost::get<1>(p2) && boost::get<2>(p1) < boost::get<2>(p2));
+ }
+
+ template <typename Indexable>
static inline size_t choose_by_minimum_area_cost(children_type const& children, Indexable const& indexable)
{
size_t children_count = children.size();
@@ -139,7 +209,6 @@
// choose the child which requires smallest box expansion to store the indexable
for ( size_t i = 0 ; i < children_count ; ++i )
{
- typedef typename children_type::value_type child_type;
child_type const& ch_i = children[i];
// expanded child node's box
Modified: sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index/tests/additional_sizes_and_times.cpp 2011-06-21 15:29:44 EDT (Tue, 21 Jun 2011)
@@ -30,11 +30,11 @@
typedef bg::model::box<P> B;
//typedef bgi::rtree<std::pair<B, size_t>, bgi::linear<32, 8> > RT;
//typedef bgi::rtree<std::pair<B, size_t>, bgi::quadratic<32, 8> > RT;
- //typedef bgi::rtree<std::pair<B, size_t>, bgi::rstar<32, 8, true> > RT;
- typedef bgi::rtree<
+ typedef bgi::rtree<std::pair<B, size_t>, bgi::rstar<32, 8> > RT;
+ /*typedef bgi::rtree<
std::pair<B, size_t>,
- bgi::options::rtree<bgi::linear<32, 8>, bgi::insert_tag, bgi::choose_by_area_diff_tag, bgi::quadratic_tag, bgi::default_static_tag>
- > RT;
+ bgi::options::rtree<bgi::rstar<32, 8, 0, 10>, bgi::reinsert_tag, bgi::choose_by_area_diff_tag, bgi::rstar_tag, bgi::default_tag>
+ > RT;*/
// load config file
std::ifstream file_cfg("config.txt");
@@ -93,10 +93,13 @@
else
{
boost::mt19937 rng;
- float max_val = static_cast<float>(values_count / 2);
+ //rng.seed(static_cast<unsigned int>(std::time(0)));
+
+ float max_val = static_cast<float>(values_count / 2);
boost::uniform_real<float> range(-max_val, max_val);
- boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
-
+
+ boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
+
std::cout << "randomizing data\n";
for ( size_t i = 0 ; i < values_count ; ++i )
{
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