|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r71634 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/linear boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-04-30 16:54:02
Author: awulkiew
Date: 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
New Revision: 71634
URL: http://svn.boost.org/trac/boost/changeset/71634
Log:
new creation algorithm added
Added:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/choose_next_node.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/insert.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/linear.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/load.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/save.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/tests/additional_load_time_vis.cpp (contents, props changed)
Removed:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/tags.hpp
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp | 10 +-
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp | 2
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp | 7 ++
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 26 ++++++++
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp | 119 +++++++++++++++++++++++++--------------
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 51 +++++++++++-----
6 files changed, 147 insertions(+), 68 deletions(-)
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/choose_next_node.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/choose_next_node.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -0,0 +1,80 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree ChooseNextNode algorithm - per traverse level ChooseSubtree
+//
+// Copyright 2011 Adam Wulkiewicz.
+// 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_LINEAR_LINEAR_CHOOSE_NEXT_NODE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_LINEAR_LINEAR_CHOOSE_NEXT_NODE_HPP
+
+#include <algorithm>
+
+#include <boost/geometry/algorithms/expand.hpp>
+
+#include <boost/geometry/extensions/index/algorithms/area.hpp>
+#include <boost/geometry/extensions/index/algorithms/overlap.hpp>
+#include <boost/geometry/extensions/index/algorithms/union_area.hpp>
+
+#include <boost/geometry/extensions/index/rtree/node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace linear {
+
+template <typename Value, typename Box, typename Tag>
+struct choose_next_node
+{
+ typedef typename rtree::node<Value, Box, Tag>::type node;
+ typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
+ typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
+
+ typedef typename internal_node::children_type children_type;
+
+ typedef typename index::default_area_result<Box>::type area_type;
+
+ template <typename Indexable>
+ static inline size_t apply(internal_node & n, Indexable const& indexable)
+ {
+ assert(!n.children.empty());
+
+ size_t children_count = n.children.size();
+
+ // choose index with smallest area change or smallest area
+ size_t choosen_index = 0;
+ area_type smallest_area_diff = std::numeric_limits<area_type>::max();
+ area_type smallest_area = std::numeric_limits<area_type>::max();
+
+ // caculate areas and areas of all nodes' boxes
+ for ( size_t i = 0 ; i < children_count ; ++i )
+ {
+ typedef typename children_type::value_type child_type;
+ child_type const& ch_i = n.children[i];
+
+ Box box_exp(ch_i.first);
+ geometry::expand(box_exp, indexable);
+
+ area_type area = index::area(box_exp);
+ area_type area_diff = area - index::area(ch_i.first);
+
+ if ( area_diff < smallest_area_diff ||
+ ( area_diff == smallest_area_diff && area < smallest_area ) )
+ {
+ smallest_area_diff = area_diff;
+ smallest_area = area;
+ choosen_index = i;
+ }
+ }
+
+ return choosen_index;
+ }
+};
+
+}}} // namespace detail::rtree:linear
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_LINEAR_LINEAR_CHOOSE_NEXT_NODE_HPP
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/insert.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/insert.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -0,0 +1,112 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree insert algorithm implementation
+//
+// Copyright 2011 Adam Wulkiewicz.
+// 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_INSERT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_INSERT_HPP
+
+#include <boost/geometry/extensions/index/algorithms/area.hpp>
+#include <boost/geometry/extensions/index/algorithms/margin.hpp>
+#include <boost/geometry/extensions/index/algorithms/overlap.hpp>
+#include <boost/geometry/extensions/index/algorithms/union_area.hpp>
+
+#include <boost/geometry/extensions/index/rtree/node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/insert.hpp>
+
+#include <boost/geometry/extensions/index/rtree/linear/choose_next_node.hpp>
+#include <boost/geometry/extensions/index/rtree/linear/split.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace visitors {
+
+template <typename Value, typename Translator, typename Box>
+class insert<Value, Translator, Box, linear_tag> : public boost::static_visitor<>
+{
+ typedef typename rtree::node<Value, Box, linear_tag>::type node;
+ typedef typename rtree::internal_node<Value, Box, linear_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, Box, linear_tag>::type leaf;
+
+public:
+ inline explicit insert(node* & root, Value const& v, size_t min_elements, size_t max_elements, Translator const& t)
+ : m_value(v), m_tr(t), m_min_elems_per_node(min_elements), m_max_elems_per_node(max_elements)
+ , m_root_node(root)
+ , m_parent(0), m_current_child_index(0), m_current_level(0)
+ {
+ // TODO
+ // assert - check if Box is correct
+ }
+
+ inline void operator()(internal_node & n)
+ {
+ // choose next node
+ size_t choosen_node_index = linear::choose_next_node<Value, Box, linear_tag>::
+ apply(n, rtree::element_indexable(m_value, m_tr));
+
+ // expand the node to contain value
+ geometry::expand(n.children[choosen_node_index].first, m_tr(m_value));
+
+ // next traversing step
+ traverse_apply_visitor(n, choosen_node_index);
+
+ // handle overflow
+ if ( m_max_elems_per_node < n.children.size() )
+ linear::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);
+ }
+
+ inline void operator()(leaf & n)
+ {
+ // push value
+ n.values.push_back(m_value);
+
+ // handle overflow
+ if ( m_max_elems_per_node < n.values.size() )
+ linear::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);
+ }
+
+private:
+ inline void traverse_apply_visitor(internal_node &n, size_t choosen_node_index)
+ {
+ // save previous traverse inputs and set new ones
+ internal_node * parent_bckup = m_parent;
+ size_t current_child_index_bckup = m_current_child_index;
+ size_t current_level_bckup = m_current_level;
+
+ m_parent = &n;
+ m_current_child_index = choosen_node_index;
+ ++m_current_level;
+
+ // next traversing step
+ boost::apply_visitor(*this, *n.children[choosen_node_index].second);
+
+ // restore previous traverse inputs
+ m_parent = parent_bckup;
+ m_current_child_index = current_child_index_bckup;
+ m_current_level = current_level_bckup;
+ }
+
+ Value const& m_value;
+ Translator const& m_tr;
+ const size_t m_min_elems_per_node;
+ const size_t m_max_elems_per_node;
+
+ node* & m_root_node;
+
+ // traversing input parameters
+ internal_node *m_parent;
+ size_t m_current_child_index;
+ size_t m_current_level;
+};
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_INSERT_HPP
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/linear.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/linear.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -0,0 +1,21 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree
+//
+// Copyright 2011 Adam Wulkiewicz.
+// 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_LINEAR_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_LINEAR_HPP
+
+namespace boost { namespace geometry { namespace index {
+
+struct linear_tag {};
+
+}}} // namespace boost::geometry::index
+
+#include <boost/geometry/extensions/index/rtree/linear/insert.hpp>
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_LINEAR_HPP
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -0,0 +1,374 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R*-tree split algorithm implementation
+//
+// Copyright 2008 Federico J. Fernandez.
+// Copyright 2011 Adam Wulkiewicz.
+// 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_SPLIT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_SPLIT_HPP
+
+#include <algorithm>
+
+#include <boost/tuple/tuple.hpp>
+
+#include <boost/geometry/extensions/index/algorithms/area.hpp>
+#include <boost/geometry/extensions/index/algorithms/union_area.hpp>
+
+#include <boost/geometry/extensions/index/rtree/node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/insert.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/is_leaf.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace linear {
+
+// from void find_normalized_separations(std::vector<Box> const& boxes, T& separation, unsigned int& first, unsigned int& second) const
+
+template <typename Elements, typename Translator, size_t DimensionIndex>
+struct find_greatest_normalized_separation
+{
+ typedef typename Elements::value_type element_type;
+ typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
+
+ static inline void apply(Elements const& elements,
+ Translator const& tr,
+ coordinate_type & separation,
+ size_t & seed1,
+ size_t & seed2)
+ {
+ size_t elements_count = elements.size();
+
+ assert(2 <= elements_count);
+
+ // find the lowest low, highest high
+ coordinate_type lowest_low = geometry::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[0], tr));
+ coordinate_type highest_high = geometry::get<max_corner, DimensionIndex>(rtree::element_indexable(elements[0], tr));
+ // and the lowest high
+ coordinate_type lowest_high = highest_high;
+ size_t lowest_high_index = 0;
+ for ( size_t i = 1 ; i < elements_count ; ++i )
+ {
+ coordinate_type min_coord = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[i], tr));
+ coordinate_type max_coord = index::get<max_corner, DimensionIndex>(rtree::element_indexable(elements[i], tr));
+
+ if ( max_coord < lowest_high )
+ {
+ lowest_high = max_coord;
+ lowest_high_index = i;
+ }
+
+ if ( min_coord < lowest_low )
+ lowest_low = min_coord;
+
+ if ( highest_high < max_coord )
+ highest_high = max_coord;
+ }
+
+ // find the highest low
+ size_t highest_low_index = lowest_high_index == 0 ? 1 : 0;
+ coordinate_type highest_low = geometry::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[highest_low_index], tr));
+ for ( size_t i = highest_low_index ; i < elements_count ; ++i )
+ {
+ coordinate_type min_coord = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[i], tr));
+ if ( highest_low < min_coord &&
+ i != lowest_high_index )
+ {
+ highest_low = min_coord;
+ highest_low_index = i;
+ }
+ }
+
+ coordinate_type const width = highest_high - lowest_low;
+
+ separation = (highest_low - lowest_high) / width;
+ seed1 = highest_low_index;
+ seed2 = lowest_high_index;
+ }
+};
+
+namespace dispatch {
+
+template <typename Elements, typename Translator, size_t DimensionIndex>
+struct choose_axis_impl
+{
+ BOOST_STATIC_ASSERT(0 < DimensionIndex);
+
+ typedef typename Elements::value_type element_type;
+ typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
+
+ static inline void apply(Elements const& elements,
+ Translator const& tr,
+ size_t & axis,
+ coordinate_type & separation,
+ size_t & seed1,
+ size_t & seed2)
+ {
+ choose_axis_impl<Elements, Translator, DimensionIndex - 1>::apply(elements, tr, axis, separation, seed1, seed2);
+
+ coordinate_type current_separation;
+ size_t s1, s2;
+ find_greatest_normalized_separation<Elements, Translator, DimensionIndex - 1>::apply(elements, tr, current_separation, s1, s2);
+
+ // TODO: operator test!, change <= to < later
+ if ( separation <= current_separation )
+ {
+ separation = current_separation;
+ seed1 = s1;
+ seed2 = s2;
+ axis = DimensionIndex - 1;
+ }
+ }
+};
+
+template <typename Elements, typename Translator>
+struct choose_axis_impl<Elements, Translator, 1>
+{
+ typedef typename Elements::value_type element_type;
+ typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
+
+ static inline void apply(Elements const& elements,
+ Translator const& tr,
+ size_t & axis,
+ coordinate_type & separation,
+ size_t & seed1,
+ size_t & seed2)
+ {
+ find_greatest_normalized_separation<Elements, Translator, 0>::apply(elements, tr, separation, seed1, seed2);
+ axis = 0;
+ }
+};
+
+} // namespace dispatch
+
+// from void linear_pick_seeds(node_pointer const& n, unsigned int &seed1, unsigned int &seed2) const
+
+template <typename Elements, typename Translator>
+struct choose_axis
+{
+ typedef typename Elements::value_type element_type;
+ typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
+
+ static const size_t dimension = index::traits::dimension<indexable_type>::value;
+
+ static inline size_t apply(Elements const& elements,
+ Translator const& tr,
+ size_t & seed1,
+ size_t & seed2)
+ {
+ size_t axis = 0;
+ coordinate_type separation = 0;
+ dispatch::choose_axis_impl<Elements, Translator, dimension>::apply(elements, tr, axis, separation, seed1, seed2);
+ return axis;
+ }
+};
+
+// from void split_node(node_pointer const& n, node_pointer& n1, node_pointer& n2) const
+
+template <typename Value, typename Translator, typename Box>
+struct redistribute_elements
+{
+ typedef typename rtree::node<Value, Box, rstar_tag>::type node;
+ typedef typename rtree::internal_node<Value, Box, rstar_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, Box, rstar_tag>::type leaf;
+
+ template <typename Node>
+ static inline void apply(Node & n,
+ Node & second_node,
+ Box & box1,
+ Box & box2,
+ size_t min_elems,
+ size_t max_elems,
+ Translator const& tr)
+ {
+ typedef typename rtree::elements_type<Node>::type elements_type;
+ typedef typename elements_type::value_type element_type;
+ typedef typename rtree::element_indexable_type<element_type, Translator>::type indexable_type;
+ typedef typename index::traits::coordinate_type<indexable_type>::type coordinate_type;
+ typedef typename index::default_area_result<Box>::type area_type;
+
+ static const size_t dimension = index::traits::dimension<indexable_type>::value;
+
+ // copy original elements
+ elements_type elements_copy = rtree::elements_get(n);
+ size_t elements_count = elements_copy.size();
+
+ // calculate initial seeds
+ size_t seed1 = 0;
+ size_t seed2 = 0;
+ choose_axis<elements_type, Translator>::apply(elements_copy, tr, seed1, seed2);
+
+ // prepare nodes' elements containers
+ elements_type & elements1 = rtree::elements_get(n);
+ elements_type & elements2 = rtree::elements_get(second_node);
+ elements1.clear();
+ assert(elements2.empty());
+
+ // add seeds
+ elements1.push_back(elements_copy[seed1]);
+ elements2.push_back(elements_copy[seed2]);
+
+ // calculate boxes
+ geometry::convert(rtree::element_indexable(elements_copy[seed1], tr), box1);
+ geometry::convert(rtree::element_indexable(elements_copy[seed2], tr), box2);
+
+ // initialize areas
+ area_type area1 = index::area(box1);
+ area_type area2 = index::area(box2);
+
+ assert(2 <= elements_count);
+ size_t remaining = elements_count - 2;
+
+ // redistribute the rest of the elements
+ for ( size_t i = 0 ; i < elements_count ; ++i )
+ {
+ if (i != seed1 && i != seed2)
+ {
+ element_type const& elem = elements_copy[i];
+ indexable_type const& indexable = rtree::element_indexable(elem, tr);
+
+ // TODO: awulkiew - is this needed?
+ if ( elements1.size() + remaining == min_elems )
+ {
+ elements1.push_back(elem);
+ geometry::expand(box1, indexable);
+ area1 = index::area(box1);
+ continue;
+ }
+ if ( elements2.size() + remaining == min_elems )
+ {
+ elements2.push_back(elem);
+ geometry::expand(box2, indexable);
+ area2 = index::area(box2);
+ continue;
+ }
+
+ assert(0 < remaining);
+ remaining--;
+
+ // calculate enlarged boxes and areas
+ Box enlarged_box1(box1);
+ Box enlarged_box2(box2);
+ geometry::expand(enlarged_box1, indexable);
+ geometry::expand(enlarged_box2, indexable);
+ area_type enlarged_area1 = index::area(enlarged_box1);
+ area_type enlarged_area2 = index::area(enlarged_box2);
+
+ area_type areas_diff1 = enlarged_area1 - area1;
+ area_type areas_diff2 = enlarged_area2 - area2;
+
+ // choose group which box area have to be enlarged least
+ if ( areas_diff1 < areas_diff2 )
+ {
+ elements1.push_back(elem);
+ box1 = enlarged_box1;
+ area1 = enlarged_area1;
+ }
+ else if ( areas_diff2 < areas_diff1 )
+ {
+ elements2.push_back(elem);
+ box2 = enlarged_box2;
+ area2 = enlarged_area2;
+ }
+ else
+ {
+ // choose group which box has smaller area
+ if ( area1 < area2 )
+ {
+ elements1.push_back(elem);
+ box1 = enlarged_box1;
+ area1 = enlarged_area1;
+ }
+ else if ( area2 < area1 )
+ {
+ elements2.push_back(elem);
+ box2 = enlarged_box2;
+ area2 = enlarged_area2;
+ }
+ else
+ {
+ // choose group with fewer elements
+ if ( elements1.size() <= elements2.size() )
+ {
+ elements1.push_back(elem);
+ box1 = enlarged_box1;
+ area1 = enlarged_area1;
+ }
+ else
+ {
+ elements2.push_back(elem);
+ box2 = enlarged_box2;
+ area2 = enlarged_area2;
+ }
+ }
+ }
+ }
+ }
+ }
+};
+
+// split
+
+template <typename Value, typename Translator, typename Box>
+class split
+{
+ typedef typename rtree::node<Value, Box, linear_tag>::type node;
+ typedef typename rtree::internal_node<Value, Box, linear_tag>::type internal_node;
+ typedef typename rtree::leaf<Value, Box, linear_tag>::type leaf;
+
+ static const size_t dimension = index::traits::dimension<Box>::value;
+
+public:
+ template <typename Node>
+ static inline void apply(
+ Node & n,
+ internal_node *parent,
+ size_t current_child_index,
+ node *& root,
+ size_t min_elems,
+ size_t max_elems,
+ Translator const& tr)
+ {
+ node * second_node = rtree::create_node(Node());
+
+ // redistribute elements
+ Box box1, box2;
+ linear::redistribute_elements<Value, Translator, Box>::
+ apply(n, boost::get<Node>(*second_node), box1, box2, min_elems, max_elems, tr);
+
+ // node is not the root
+ if ( parent != 0 )
+ {
+ // update old node's box
+ parent->children[current_child_index].first = box1;
+ // add new node to the parent's children
+ parent->children.push_back(std::make_pair(box2, second_node));
+ }
+ // node is the root
+ else
+ {
+ assert(&n == boost::get<Node>(root));
+
+ // create new root and add nodes
+ node * new_root = rtree::create_node(internal_node());
+
+ boost::get<internal_node>(*new_root).children.push_back(std::make_pair(box1, root));
+ boost::get<internal_node>(*new_root).children.push_back(std::make_pair(box2, second_node));
+
+ root = new_root;
+ }
+ }
+};
+
+}}} // namespace detail::rtree:linear
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_SPLIT_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/node.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -107,11 +107,11 @@
return n.values;
}
-template <typename Node>
-struct element_type
-{
- typedef typename elements_type<Node>::type::value_type type;
-};
+//template <typename Node>
+//struct element_type
+//{
+// typedef typename elements_type<Node>::type::value_type type;
+//};
// uniform indexable type for child node element's box and value's indexable
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -128,7 +128,7 @@
{
size_t children_count = n.children.size();
- // choose index with smallest overlap change value, or area change or smallest area
+ // choose index with smallest area change or smallest area
size_t choosen_index = 0;
area_type smallest_area_change = std::numeric_limits<area_type>::max();
area_type smallest_area = std::numeric_limits<area_type>::max();
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rstar.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -10,7 +10,12 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_RSTAR_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_RSTAR_HPP
-#include <boost/geometry/extensions/index/tags.hpp>
+namespace boost { namespace geometry { namespace index {
+
+struct rstar_tag {};
+
+}}} // namespace boost::geometry::index
+
#include <boost/geometry/extensions/index/rtree/rstar/insert.hpp>
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_RSTAR_HPP
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-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -19,6 +19,10 @@
#include <boost/geometry/extensions/index/rtree/visitors/destroy.hpp>
#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
+#include <boost/geometry/extensions/index/rtree/linear/linear.hpp>
+
+//TEST
+//#include <boost/geometry/extensions/index/rtree/visitors/load.hpp>
namespace boost { namespace geometry { namespace index {
@@ -27,7 +31,7 @@
template <
typename Value,
typename Translator = default_parameter,
- typename Tag = rstar_tag
+ typename Tag = linear_tag
>
class rtree
{
@@ -100,6 +104,26 @@
return m_values_count;
}
+ //TEST
+ //inline void load(std::istream &is)
+ //{
+ // std::string t;
+ // size_t n;
+ // is >> t;
+ // is >> n;
+
+ // if ( t == "i" )
+ // m_root = detail::rtree::create_node(internal_node());
+ // else
+ // m_root = detail::rtree::create_node(leaf());
+
+ // detail::rtree::visitors::load<value_type, translator_type, box_type, tag_type>
+ // load_v(is, m_translator);
+
+ // for ( size_t i = 0 ; i < n ; ++i )
+ // boost::apply_visitor(load_v, *m_root);
+ //}
+
private:
size_t m_values_count;
size_t m_max_elems_per_node;
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -10,6 +10,7 @@
#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_GL_DRAW_HPP
#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_GL_DRAW_HPP
+#include <boost/geometry/extensions/index/indexable.hpp>
#include <boost/geometry/extensions/index/rtree/node.hpp>
namespace boost { namespace geometry { namespace index {
@@ -25,10 +26,10 @@
template <typename Point>
struct gl_draw_point<Point, 2>
{
- static inline void apply(Point const& p, size_t level)
+ static inline void apply(Point const& p, typename index::traits::coordinate_type<Point>::type z)
{
glBegin(GL_POINT);
- glVertex2f(geometry::get<0>(p), geometry::get<1>(p), level);
+ glVertex3f(geometry::get<0>(p), geometry::get<1>(p), z);
glEnd();
}
};
@@ -40,13 +41,13 @@
template <typename Box>
struct gl_draw_box<Box, 2>
{
- static inline void apply(Box const& b, size_t level)
+ static inline void apply(Box const& b, typename index::traits::coordinate_type<Box>::type z)
{
glBegin(GL_LINE_LOOP);
- glVertex3f(geometry::get<min_corner, 0>(b), geometry::get<min_corner, 1>(b), level);
- glVertex3f(geometry::get<max_corner, 0>(b), geometry::get<min_corner, 1>(b), level);
- glVertex3f(geometry::get<max_corner, 0>(b), geometry::get<max_corner, 1>(b), level);
- glVertex3f(geometry::get<min_corner, 0>(b), geometry::get<max_corner, 1>(b), level);
+ glVertex3f(geometry::get<min_corner, 0>(b), geometry::get<min_corner, 1>(b), z);
+ glVertex3f(geometry::get<max_corner, 0>(b), geometry::get<min_corner, 1>(b), z);
+ glVertex3f(geometry::get<max_corner, 0>(b), geometry::get<max_corner, 1>(b), z);
+ glVertex3f(geometry::get<min_corner, 0>(b), geometry::get<max_corner, 1>(b), z);
glEnd();
}
};
@@ -61,9 +62,9 @@
{
static const size_t dimension = index::traits::dimension<Indexable>::value;
- static inline void apply(Indexable const& i, size_t level)
+ static inline void apply(Indexable const& i, typename index::traits::coordinate_type<Indexable>::type z)
{
- gl_draw_box<Indexable, dimension>::apply(i, level);
+ gl_draw_box<Indexable, dimension>::apply(i, z);
}
};
@@ -72,9 +73,9 @@
{
static const size_t dimension = index::traits::dimension<Indexable>::value;
- static inline void apply(Indexable const& i, size_t level)
+ static inline void apply(Indexable const& i, typename index::traits::coordinate_type<Indexable>::type z)
{
- gl_draw_point<Indexable, dimension>::apply(i, level);
+ gl_draw_point<Indexable, dimension>::apply(i, z);
}
};
@@ -83,12 +84,12 @@
namespace detail {
template <typename Indexable>
-inline void gl_draw_indexable(Indexable const& i, size_t level)
+inline void gl_draw_indexable(Indexable const& i, typename index::traits::coordinate_type<Indexable>::type z)
{
dispatch::gl_draw_indexable<
Indexable,
typename index::traits::tag<Indexable>::type
- >::apply(i, level);
+ >::apply(i, z);
}
} // namespace detail
@@ -99,42 +100,58 @@
typedef typename rtree::internal_node<Value, Box, Tag>::type internal_node;
typedef typename rtree::leaf<Value, Box, Tag>::type leaf;
- inline gl_draw(Translator const& t)
- : tr(t), level(0)
+ inline gl_draw(Translator const& t,
+ size_t level_first = 0,
+ size_t level_last = std::numeric_limits<size_t>::max(),
+ typename index::traits::coordinate_type<Box>::type z_coord_level_multiplier = 1
+ )
+ : tr(t)
+ , level_f(level_first)
+ , level_l(level_last)
+ , z_mul(z_coord_level_multiplier)
+ , level(0)
{}
inline void operator()(internal_node const& n)
{
typedef typename internal_node::children_type children_type;
- if ( level == 0 )
- glColor3f(1.0f, 0.0f, 0.0f);
- else if ( level == 1 )
- glColor3f(0.0f, 1.0f, 0.0f);
- else if ( level == 2 )
- glColor3f(0.0f, 0.0f, 1.0f);
- else if ( level == 3 )
- glColor3f(1.0f, 1.0f, 0.0f);
- else if ( level == 4 )
- glColor3f(1.0f, 0.0f, 1.0f);
- else if ( level == 5 )
- glColor3f(0.0f, 1.0f, 1.0f);
- else
- glColor3f(0.5f, 0.5f, 0.5f);
-
- for (typename children_type::const_iterator it = n.children.begin();
- it != n.children.end(); ++it)
+ if ( level_f <= level )
{
- detail::gl_draw_indexable(it->first, level);
+ size_t level_rel = level - level_f;
+
+ if ( level_rel == 0 )
+ glColor3f(1.0f, 0.0f, 0.0f);
+ else if ( level_rel == 1 )
+ glColor3f(0.0f, 1.0f, 0.0f);
+ else if ( level_rel == 2 )
+ glColor3f(0.0f, 0.0f, 1.0f);
+ else if ( level_rel == 3 )
+ glColor3f(1.0f, 1.0f, 0.0f);
+ else if ( level_rel == 4 )
+ glColor3f(1.0f, 0.0f, 1.0f);
+ else if ( level_rel == 5 )
+ glColor3f(0.0f, 1.0f, 1.0f);
+ else
+ glColor3f(0.5f, 0.5f, 0.5f);
+
+ for (typename children_type::const_iterator it = n.children.begin();
+ it != n.children.end(); ++it)
+ {
+ detail::gl_draw_indexable(it->first, level_rel * z_mul);
+ }
}
size_t level_backup = level;
++level;
- for (typename children_type::const_iterator it = n.children.begin();
- it != n.children.end(); ++it)
+ if ( level < level_l )
{
- boost::apply_visitor(*this, *it->second);
+ for (typename children_type::const_iterator it = n.children.begin();
+ it != n.children.end(); ++it)
+ {
+ boost::apply_visitor(*this, *it->second);
+ }
}
level = level_backup;
@@ -144,16 +161,24 @@
{
typedef typename leaf::values_type values_type;
- glColor3f(1.0f, 1.0f, 1.0f);
-
- for (typename values_type::const_iterator it = n.values.begin();
- it != n.values.end(); ++it)
+ if ( level_f <= level )
{
- detail::gl_draw_indexable(tr(*it), level);
+ size_t level_rel = level - level_f;
+
+ glColor3f(1.0f, 1.0f, 1.0f);
+
+ for (typename values_type::const_iterator it = n.values.begin();
+ it != n.values.end(); ++it)
+ {
+ detail::gl_draw_indexable(tr(*it), level_rel * z_mul);
+ }
}
}
Translator const& tr;
+ size_t level_f;
+ size_t level_l;
+ typename index::traits::coordinate_type<Box>::type z_mul;
size_t level;
};
@@ -161,7 +186,13 @@
}}} // namespace detail::rtree::visitors
template <typename Value, typename Translator, typename Tag>
-void gl_draw(rtree<Value, Translator, Tag> const& tree)
+void gl_draw(rtree<Value, Translator, Tag> const& tree,
+ size_t level_first = 0,
+ size_t level_last = std::numeric_limits<size_t>::max(),
+ typename index::traits::coordinate_type<
+ typename rtree<Value, Translator, Tag>::box_type
+ >::type z_coord_level_multiplier = 1
+ )
{
typedef typename rtree<Value, Translator, Tag>::value_type value_type;
typedef typename rtree<Value, Translator, Tag>::translator_type translator_type;
@@ -170,7 +201,9 @@
glClear(GL_COLOR_BUFFER_BIT);
- detail::rtree::visitors::gl_draw<value_type, translator_type, box_type, tag_type> gl_draw_v(tree.get_translator());
+ detail::rtree::visitors::gl_draw<value_type, translator_type, box_type, tag_type>
+ gl_draw_v(tree.get_translator(), level_first, level_last, z_coord_level_multiplier);
+
tree.apply_visitor(gl_draw_v);
glFlush();
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/load.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/load.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -0,0 +1,111 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree loading visitor
+//
+// Copyright 2011 Adam Wulkiewicz.
+// 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_LOAD_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_LOAD_HPP
+
+#include <iostream>
+
+#include <boost/geometry/extensions/index/rtree/node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace visitors {
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct load;
+
+template <typename Translator, typename Box, typename Tag>
+struct load<
+ std::pair<
+ boost::geometry::model::box<
+ boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian>
+ >,
+ size_t
+ >,
+ typename Translator,
+ Box,
+ Tag
+>
+: public boost::static_visitor<>
+{
+ typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> point_type;
+
+ typedef std::pair<
+ boost::geometry::model::box<
+ point_type
+ >,
+ size_t
+ > value_type;
+
+ typedef typename rtree::node<value_type, Box, Tag>::type node;
+ typedef typename rtree::internal_node<value_type, Box, Tag>::type internal_node;
+ typedef typename rtree::leaf<value_type, Box, Tag>::type leaf;
+
+ inline load(std::istream & i, Translator const& t)
+ : is(i), tr(t)
+ {}
+
+ inline void operator()(internal_node & n)
+ {
+ std::string node_type;
+ float min_x, min_y, max_x, max_y;
+ size_t c;
+
+ is >> node_type;
+ is >> min_x;
+ is >> min_y;
+ is >> max_x;
+ is >> max_y;
+ is >> c;
+
+ Box b(point_type(min_x, min_y), point_type(max_x, max_y));
+ node * new_n = 0;
+
+ if ( node_type == "i" )
+ new_n = rtree::create_node(internal_node());
+ else if ( node_type == "l" )
+ new_n = rtree::create_node(leaf());
+ else
+ assert(0);
+
+ n.children.push_back(std::make_pair(b, new_n));
+
+ for ( size_t i = 0 ; i < c ; ++i )
+ boost::apply_visitor(*this, *new_n);
+ }
+
+ inline void operator()(leaf & n)
+ {
+ std::string node_type;
+ float min_x, min_y, max_x, max_y;
+ size_t id;
+
+ is >> node_type;
+ is >> min_x;
+ is >> min_y;
+ is >> max_x;
+ is >> max_y;
+ is >> id;
+
+ assert(id == "v");
+
+ Box b(point_type(min_x, min_y), point_type(max_x, max_y));
+ n.values.push_back(std::make_pair(b, id));
+ }
+
+ std::istream & is;
+ Translator const& tr;
+};
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_LOAD_HPP
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/save.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/save.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -0,0 +1,97 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree saving visitor
+//
+// Copyright 2011 Adam Wulkiewicz.
+// 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)
+
+#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_SAVE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_SAVE_HPP
+
+#include <iostream>
+
+#include <boost/geometry/extensions/index/rtree/node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace detail { namespace rtree { namespace visitors {
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct save;
+
+template <typename Translator, typename Box, typename Tag>
+struct save<
+ std::pair<
+ boost::geometry::model::box<
+ boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian>
+ >,
+ size_t
+ >,
+ typename Translator,
+ Box,
+ Tag
+>
+: public boost::static_visitor<>
+{
+ typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> point_type;
+
+ typedef std::pair<
+ boost::geometry::model::box<
+ point_type
+ >,
+ size_t
+ > value_type;
+
+ typedef typename rtree::node<value_type, Box, Tag>::type node;
+ typedef typename rtree::internal_node<value_type, Box, Tag>::type internal_node;
+ typedef typename rtree::leaf<value_type, Box, Tag>::type leaf;
+
+ inline save(std::ostream & o, Translator const& t)
+ : os(o), tr(t)
+ {}
+
+ inline void operator()(internal_node & n)
+ {
+ os << n.children.size() << '\n';
+
+ for ( size_t i = 0 ; i < n.children.size() ; ++i )
+ {
+ if ( boost::apply_visitor(visitors::is_leaf<value_type, Box, Tag>(), *(n.children[i].second)) )
+ os << "l ";
+ else
+ os << "i ";
+ os << geometry::get<min_corner, 0>(n.children[i].first) << ' ';
+ os << geometry::get<min_corner, 1>(n.children[i].first) << ' ';
+ os << geometry::get<max_corner, 0>(n.children[i].first) << ' ';
+ os << geometry::get<max_corner, 1>(n.children[i].first) << ' ';
+
+ boost::apply_visitor(*this, *(n.children[i].second));
+ }
+ }
+
+ inline void operator()(leaf & n)
+ {
+ os << n.values.size() << '\n';
+
+ for ( size_t i = 0 ; i < n.values.size() ; ++i )
+ {
+ os << "v ";
+ os << geometry::get<min_corner, 0>(n.values[i].first) << ' ';
+ os << geometry::get<min_corner, 1>(n.values[i].first) << ' ';
+ os << geometry::get<max_corner, 0>(n.values[i].first) << ' ';
+ os << geometry::get<max_corner, 1>(n.values[i].first) << ' ';
+ os << n.values[i].second << '\n';
+ }
+ }
+
+ std::ostream & os;
+ Translator const& tr;
+};
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_SAVE_HPP
Deleted: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/tags.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/tags.hpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
+++ (empty file)
@@ -1,19 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-//
-// Boost.Index - R*-tree tag
-//
-// Copyright 2011 Adam Wulkiewicz.
-// 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)
-
-#ifndef BOOST_GEOMETRY_EXTENSIONS_INDEX_TAGS_HPP
-#define BOOST_GEOMETRY_EXTENSIONS_INDEX_TAGS_HPP
-
-namespace boost { namespace geometry { namespace index {
-
-struct rstar_tag {};
-
-}}} // namespace boost::geometry::index
-
-#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_TAGS_HPP
Added: sandbox-branches/geometry/index_080_new/tests/additional_load_time_vis.cpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/tests/additional_load_time_vis.cpp 2011-04-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -0,0 +1,141 @@
+#include <boost/geometry/extensions/index/rtree/rtree.hpp>
+
+#include <iostream>
+#include <fstream>
+
+#include <boost/timer.hpp>
+#include <boost/foreach.hpp>
+
+//TEST
+#include <gl/glut.h>
+#include <boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp>
+
+typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
+typedef boost::geometry::model::box<P> B;
+boost::geometry::index::rtree< std::pair<B, size_t> > t;
+
+void render_scene(void)
+{
+ boost::geometry::index::gl_draw(t, 0, 1, 20000.0f);
+}
+
+void resize(int w, int h)
+{
+ if ( h == 0 )
+ h = 1;
+
+ float ratio = float(w) / h;
+
+ glMatrixMode(GL_PROJECTION);
+ glLoadIdentity();
+
+ glViewport(0, 0, w, h);
+
+ gluPerspective(45.0, ratio, 1, 10000000.0);
+ glMatrixMode(GL_MODELVIEW);
+ glLoadIdentity();
+ gluLookAt(
+ 2000000.0, 2000000.0, 2000000.0,
+ 0.0, 0.0, -1.0,
+ 0.0, 1.0, 0.0);
+}
+
+int main(int argc, char **argv)
+{
+ boost::timer tim;
+
+ // randomize boxes
+ 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 )
+ {
+ 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";
+
+ t = boost::geometry::index::rtree< std::pair<B, size_t> > (max_elems, min_elems);
+
+ //std::cout << "inserting time test...\n";
+ //tim.restart();
+ //for (size_t i = 0 ; i < n ; ++i )
+ //{
+ // 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
+
+ // //TEST
+ // /*if ( i == 228 )
+ // {
+ // std::cout << std::fixed << x << ", " << y << "\n";
+ // boost::geometry::index::detail::rtree::visitors::detail::print_indexable(std::cout, b);
+ // }*/
+
+ // t.insert(std::make_pair(b, i));
+
+ // //TEST
+ // /*if ( !boost::geometry::index::are_boxes_ok(t) )
+ // {
+ // 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 << "loading tree structure...\n";
+ std::ifstream is("save.txt");
+ t.load(is);
+ std::cout << "done.\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";
+
+ std::cin.get();
+
+ //TEST
+ glutInit(&argc, argv);
+ glutInitDisplayMode(GLUT_DEPTH | GLUT_SINGLE | GLUT_RGBA);
+ glutInitWindowPosition(100,100);
+ glutInitWindowSize(800, 600);
+ glutCreateWindow("Mouse click to insert new value");
+
+ glutDisplayFunc(render_scene);
+ glutReshapeFunc(resize);
+
+ glutMainLoop();
+
+ return 0;
+}
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-30 16:53:59 EDT (Sat, 30 Apr 2011)
@@ -6,6 +6,8 @@
#include <boost/timer.hpp>
#include <boost/foreach.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/save.hpp>
+
int main()
{
boost::timer tim;
@@ -13,34 +15,34 @@
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 = 1000000;
- //const size_t n = 300;
- const size_t ns = 100000;
-
std::ifstream file_cfg("config.txt");
- std::ifstream file("test_coords.txt");
+ size_t max_elems = 4;
+ size_t min_elems = 2;
+ size_t values_count = 0;
+ size_t queries_count = 0;
+ char save_ch = 'n';
+ file_cfg >> max_elems;
+ file_cfg >> min_elems;
+ file_cfg >> values_count;
+ file_cfg >> queries_count;
+ file_cfg >> save_ch;
+ std::cout << "max: " << max_elems << ", min: " << min_elems << "\n";
+ std::cout << "v: " << values_count << ", q: " << queries_count << "\n";
+ 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 )
+ std::vector< std::pair<float, float> > coords(values_count);
+ for ( size_t i = 0 ; i < values_count ; ++i )
{
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 )
+ for (size_t i = 0 ; i < values_count ; ++i )
{
float x = coords[i].first;
float y = coords[i].second;
@@ -71,10 +73,25 @@
}
std::cout << "time: " << tim.elapsed() << "s\n";
+ if ( save_ch == 's' )
+ {
+ std::cout << "saving...\n";
+ std::ofstream file("save_new.txt", std::ofstream::trunc);
+ file << std::fixed;
+ boost::geometry::index::detail::rtree::visitors::save<
+ boost::geometry::index::rtree< std::pair<B, size_t> >::value_type,
+ boost::geometry::index::rtree< std::pair<B, size_t> >::translator_type,
+ boost::geometry::index::rtree< std::pair<B, size_t> >::box_type,
+ boost::geometry::index::rtree< std::pair<B, size_t> >::tag_type
+ > saving_v(file, t.get_translator());
+ t.apply_visitor(saving_v);
+ std::cout << "saved...\n";
+ }
+
std::cout << "searching time test...\n";
tim.restart();
size_t temp = 0;
- for (size_t i = 0 ; i < ns ; ++i )
+ for (size_t i = 0 ; i < queries_count ; ++i )
{
float x = coords[i].first;
float y = coords[i].second;
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