Subject: [Boost-commit] svn:boost r71544 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-04-27 14:14:46
Author: awulkiew
Date: 2011-04-27 14:14:45 EDT (Wed, 27 Apr 2011)
New Revision: 71544
URL: http://svn.boost.org/trac/boost/changeset/71544
Log:
reinsertions disabled + minor changes
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp | 5 +
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp | 83 ++++++++++++++++++++++----------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 2
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp | 2
sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp | 1
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 101 ++++++++++++++++++++++-----------------
6 files changed, 121 insertions(+), 73 deletions(-)
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert.hpp 2011-04-27 14:14:45 EDT (Wed, 27 Apr 2011)
@@ -36,7 +36,10 @@
inline explicit insert(node* & root, Value const& v, size_t min_elements, size_t max_elements, Translator const& t)
: m_root(root)
, m_impl(root, v, min_elements, max_elements, t)
- {}
+ {
+ // TODO
+ // assert - check if Box is correct
+ }
inline void operator()(internal_node & n)
{
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/insert_impl.hpp 2011-04-27 14:14:45 EDT (Wed, 27 Apr 2011)
@@ -28,6 +28,10 @@
#include <boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp>
#include <boost/geometry/extensions/index/rtree/rstar/split.hpp>
+//TEST
+#include <boost/geometry/extensions/index/rtree/visitors/print.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/are_boxes_ok.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace detail { namespace rtree { namespace rstar {
@@ -39,6 +43,9 @@
class insert_impl : public insert_base<Value, Translator, Box, Element>
{
typedef insert_base<Value, Translator, Box, Element> base;
+ typedef typename base::node node;
+ typedef typename base::internal_node internal_node;
+ typedef typename base::leaf leaf;
public:
inline insert_impl(
@@ -54,20 +61,20 @@
inline void operator()(internal_node & n)
{
- if ( m_current_level < m_level )
+ if ( base::m_current_level < base::m_level )
{
// next traversing step
base::traverse(*this, n);
}
else
{
- assert( m_level == m_current_level );
+ assert( base::m_level == base::m_current_level );
// push new child node
- n.children.push_back(m_element);
+ n.children.push_back(base::m_element);
}
- if ( m_max_elems_per_node < n.children.size() )
+ if ( base::m_max_elems_per_node < n.children.size() )
base::overflow_treatment(n);
}
@@ -81,6 +88,9 @@
class insert_impl<Value, Translator, Box, Value> : public insert_base<Value, Translator, Box, Value>
{
typedef insert_base<Value, Translator, Box, Value> base;
+ typedef typename base::node node;
+ typedef typename base::internal_node internal_node;
+ typedef typename base::leaf leaf;
public:
inline insert_impl(
@@ -96,23 +106,23 @@
inline void operator()(internal_node & n)
{
- assert(m_current_level < m_level);
+ assert(base::m_current_level < base::m_level);
// next traversing step
base::traverse(*this, n);
- if ( m_max_elems_per_node < n.children.size() )
+ if ( base::m_max_elems_per_node < n.children.size() )
base::overflow_treatment(n);
}
inline void operator()(leaf & n)
{
- assert( m_level == m_current_level ||
- m_level == std::numeric_limits<size_t>::max() );
+ assert( base::m_level == base::m_current_level ||
+ base::m_level == std::numeric_limits<size_t>::max() );
- n.values.push_back(m_element);
+ n.values.push_back(base::m_element);
- if ( m_max_elems_per_node < n.values.size() )
+ if ( base::m_max_elems_per_node < n.values.size() )
base::overflow_treatment(n);
}
};
@@ -132,7 +142,7 @@
size_t max_elements,
Translator const& t,
size_t level = std::numeric_limits<size_t>::max()
- )
+ )
: m_element(el)
, m_tr(t)
, m_min_elems_per_node(min_elements)
@@ -150,11 +160,32 @@
size_t choosen_node_index = rstar::choose_next_node<Value, Box>::
apply(n, rtree::element_indexable(m_element, m_tr));
+ //TEST
+ /*{
+ std::ofstream log("log.txt", std::ofstream::trunc);
+ log << std::fixed << "internal node " << m_current_level << " " << m_level << '\n';
+ boost::geometry::index::detail::rtree::visitors::detail::print_indexable(log, rtree::element_indexable(m_element, m_tr));
+ log << '\n' << "choosen node: " << choosen_node_index << "\n";
+ log << "before: ";
+ boost::geometry::index::detail::rtree::visitors::detail::print_indexable(log, n.children[choosen_node_index].first);
+ log << "\n";
+ }*/
+
// expand the node to contain value
geometry::expand(
n.children[choosen_node_index].first,
rtree::element_indexable(m_element, m_tr));
+ //TEST
+ /*{
+ std::ofstream log("log.txt", std::ofstream::app);
+ log << std::fixed << choosen_node_index << "after: ";
+ boost::geometry::index::detail::rtree::visitors::detail::print_indexable(log, n.children[choosen_node_index].first);
+ log << '\n';
+ boost::geometry::index::detail::rtree::visitors::print<Value, Translator, Box, rstar_tag> print_v(log, m_tr);
+ boost::apply_visitor(print_v, *m_root_node);
+ }*/
+
// apply traversing visitor
traverse_apply_visitor(d, n, choosen_node_index);
}
@@ -188,32 +219,32 @@
// TODO: awulkiew - replace this condition with tag dispatched template
// first time insert
- if ( m_parent != 0 &&
- m_level == std::numeric_limits<size_t>::max() &&
- 0 < m_reinserted_elements_count )
+ /*if ( m_parent != 0 &&
+ m_level == std::numeric_limits<size_t>::max() &&
+ 0 < m_reinserted_elements_count )
{
reinsert(n);
}
// second time insert
else
- {
+ {*/
rstar::split<Value, Translator, Box>::
apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
- }
+ //}
}
- template <typename Distance, typename Element>
+ template <typename Distance, typename El>
static inline bool distances_asc(
- std::pair<Distance, Element> const& d1,
- std::pair<Distance, Element> const& d2)
+ std::pair<Distance, El> const& d1,
+ std::pair<Distance, El> const& d2)
{
return d1.first < d2.first;
}
- template <typename Distance, typename Element>
+ template <typename Distance, typename El>
static inline bool distances_dsc(
- std::pair<Distance, Element> const& d1,
- std::pair<Distance, Element> const& d2)
+ std::pair<Distance, El> const& d1,
+ std::pair<Distance, El> const& d2)
{
return d1.first > d2.first;
}
@@ -226,7 +257,7 @@
typedef typename geometry::point_type<Box>::type point_type;
// TODO: awulkiew - use distance_result
typedef typename index::traits::coordinate_type<point_type>::type distance_type;
-
+
assert(m_parent != 0);
assert(0 < m_reinserted_elements_count);
@@ -246,7 +277,7 @@
geometry::centroid( index::detail::rtree::element_indexable(
elements[i],
m_tr
- ), element_center);
+ ), element_center);
distances[i].first = geometry::distance(node_center, element_center);
distances[i].second = elements[i];
@@ -272,7 +303,7 @@
// calulate node's new box
m_parent->children[m_current_child_index].first =
elements_box<Box>(elements.begin(), elements.end(), m_tr);
-
+
// reinsert children starting from the minimum distance
for ( size_t i = m_reinserted_elements_count ; 0 < i ; --i )
{
@@ -291,7 +322,7 @@
const size_t m_reinserted_elements_count;
const size_t m_level;
-
+
node* & m_root_node;
// traversing input parameters
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp 2011-04-27 14:14:45 EDT (Wed, 27 Apr 2011)
@@ -67,7 +67,7 @@
}
template <typename Geometry>
- inline std::vector<value_type> find(Geometry const& geom) const
+ inline std::deque<value_type> find(Geometry const& geom) const
{
detail::rtree::visitors::find<value_type, translator_type, box_type, tag_type, Geometry> find_v(geom, m_translator);
boost::apply_visitor(find_v, *m_root);
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp 2011-04-27 14:14:45 EDT (Wed, 27 Apr 2011)
@@ -56,7 +56,7 @@
Geometry const& geom;
Translator const& tr;
- std::vector<Value> result;
+ std::deque<Value> result;
};
}}} // namespace detail::rtree::visitors
Modified: sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp 2011-04-27 14:14:45 EDT (Wed, 27 Apr 2011)
@@ -1,5 +1,4 @@
#include <gl/glut.h>
-#define BOOST_GEOMETRY_INDEX_RTREE_ENABLE_GL_DRAW
#include <boost/geometry/extensions/index/rtree/rtree.hpp>
Modified: sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp 2011-04-27 14:14:45 EDT (Wed, 27 Apr 2011)
@@ -6,70 +6,85 @@
#include <boost/timer.hpp>
#include <boost/foreach.hpp>
-template <typename Box>
-void print(Box const& b)
-{
- using namespace boost::geometry;
- std::cout << boost::geometry::get<min_corner, 0>(b) << ", ";
- std::cout << boost::geometry::get<min_corner, 1>(b) << " x ";
- std::cout << boost::geometry::get<max_corner, 0>(b) << ", ";
- std::cout << boost::geometry::get<max_corner, 1>(b)<< std::endl;
-}
-
int main()
{
- {
- typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
- typedef boost::geometry::model::box<P> B;
-
- boost::geometry::index::rtree<B>::leaf l;
- boost::geometry::index::rtree<B>::internal_node n;
-
- std::cout << "internal node size: " << sizeof(n) << '\n';
- std::cout << "leaf size: " << sizeof(l) << '\n';
- }
-
boost::timer tim;
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
// randomize boxes
- const size_t n = 100000;
- std::vector<B> v(n);
+ const size_t n = 1000000;
+ //const size_t n = 300;
+ const size_t ns = 100000;
+
+ std::ifstream file_cfg("config.txt");
+ std::ifstream file("test_coords.txt");
+
+ std::cout << "loading data\n";
+ std::vector< std::pair<float, float> > coords(n);
for ( size_t i = 0 ; i < n ; ++i )
{
- float x = float( rand() % 100000 );
- float y = float( rand() % 100000 );
- float w = float( rand() % 100 );
- float h = float( rand() % 100 );
- v[i] = B(P(x - w, y - h),P(x + w, y + h));
+ file >> coords[i].first;
+ file >> coords[i].second;
}
-
+ std::cout << "loaded\n";
+
+ //std::cin.get();
+
+ size_t max_elems, min_elems;
+ file_cfg >> max_elems;
+ file_cfg >> min_elems;
+ std::cout << "max: " << max_elems << ", min: " << min_elems << "\n";
+
+ std::cout << "inserting time test...\n";
+ tim.restart();
+ boost::geometry::index::rtree< std::pair<B, size_t> > t(max_elems, min_elems);
+ for (size_t i = 0 ; i < n ; ++i )
{
- boost::geometry::index::rtree<B> t(4, 2);
+ float x = coords[i].first;
+ float y = coords[i].second;
+ B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
+
+ // Zle wyswietla dane, obcina czesc ulamkowa
+ // Zle buduje drzewo dla i == 228
- std::cout << "inserting time test...\n";
+ //TEST
+ /*if ( i == 228 )
+ {
+ std::cout << std::fixed << x << ", " << y << "\n";
+ boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, b);
+ }*/
- tim.restart();
+ t.insert(std::make_pair(b, i));
- for (size_t i = 0 ; i < n ; ++i )
+ //TEST
+ /*if ( !boost::geometry::index::are_boxes_ok(t) )
{
- B const& b = v[i];
- boost::geometry::index::insert(t, b);
- }
-
- std::cout << "time: " << tim.elapsed() << "s\n";
-
- std::cout << "deleting time test...\n";
- tim.restart();
+ std::ofstream log("log1.txt", std::ofstream::trunc);
+ log << std::fixed << i << " - " << x << ", " << y << " - inserted: ";
+ boost::geometry::index::detail::rtree::visitors::detail::print_indexable(log, b);
+ log << '\n';
+ log << ( boost::geometry::index::are_boxes_ok(t) ? "boxes OK" : "WRONG BOXES!" );
+ log << '\n' << t;
+ }*/
}
+ std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << "searching time test...\n";
+ tim.restart();
+ size_t temp = 0;
+ for (size_t i = 0 ; i < ns ; ++i )
+ {
+ float x = coords[i].first;
+ float y = coords[i].second;
+ std::deque< std::pair<B, size_t> > result = t.find(B(P(x - 10, y - 10), P(x + 10, y + 10)));
+ temp += result.size();
+ }
std::cout << "time: " << tim.elapsed() << "s\n";
+ std::cout << temp << "\n";
-#ifdef _MSC_VER
std::cin.get();
-#endif
return 0;
}