Subject: [Boost-commit] svn:boost r71658 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/linear boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-05-01 19:51:46
Author: awulkiew
Date: 2011-05-01 19:51:45 EDT (Sun, 01 May 2011)
New Revision: 71658
URL: http://svn.boost.org/trac/boost/changeset/71658
Log:
insert algorithm divided to tag dispatched parts
Added:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp (contents, props changed)
Removed:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/choose_next_node.hpp
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/insert.hpp
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/linear.hpp | 2
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 25 ----
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/find.hpp | 73 ++++++++++++
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp | 217 +++++++++++++++++++++++++++++++++++++++
sandbox-branches/geometry/index_080_new/tests/main.cpp | 3
sandbox-branches/geometry/index_080_new/tests/rtree_native.hpp | 15 +-
6 files changed, 296 insertions(+), 39 deletions(-)
Deleted: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/choose_next_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/choose_next_node.hpp 2011-05-01 19:51:45 EDT (Sun, 01 May 2011)
+++ (empty file)
@@ -1,80 +0,0 @@
-// 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
Deleted: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/insert.hpp 2011-05-01 19:51:45 EDT (Sun, 01 May 2011)
+++ (empty file)
@@ -1,112 +0,0 @@
-// 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
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/linear.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/linear.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/linear.hpp 2011-05-01 19:51:45 EDT (Sun, 01 May 2011)
@@ -16,6 +16,6 @@
}}} // namespace boost::geometry::index
-#include <boost/geometry/extensions/index/rtree/linear/insert.hpp>
+#include <boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp>
#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_LINEAR_HPP
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/redistribute_elements.hpp 2011-05-01 19:51:45 EDT (Sun, 01 May 2011)
@@ -0,0 +1,325 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree linear 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_REDISTRIBUTE_ELEMENTS_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_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 visitors {
+
+namespace detail {
+
+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 = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[0], tr));
+ coordinate_type highest_high = index::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 = index::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;
+ }
+};
+
+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);
+
+ // in the old implementation different operator was used: <=
+ 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;
+ }
+};
+
+// 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;
+ choose_axis_impl<Elements, Translator, dimension>::apply(elements, tr, axis, separation, seed1, seed2);
+ return axis;
+ }
+};
+
+} // namespace linear
+
+// 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<Value, Translator, Box, linear_tag>
+{
+ 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;
+
+ 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;
+ linear::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;
+ }
+ }
+ }
+ }
+ }
+ }
+};
+
+} // namespace detail
+
+}}} // namespace detail::rtree::visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_LINEAR_REDISTRIBUTE_ELEMENTS_HPP
Deleted: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/linear/split.hpp 2011-05-01 19:51:45 EDT (Sun, 01 May 2011)
+++ (empty file)
@@ -1,374 +0,0 @@
-// 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 = index::get<min_corner, DimensionIndex>(rtree::element_indexable(elements[0], tr));
- coordinate_type highest_high = index::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 = index::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/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-05-01 19:51:45 EDT (Sun, 01 May 2011)
@@ -18,11 +18,8 @@
#include <boost/geometry/extensions/index/rtree/visitors/find.hpp>
#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>
+#include <boost/geometry/extensions/index/rtree/rstar/rstar.hpp>
namespace boost { namespace geometry { namespace index {
@@ -105,26 +102,6 @@
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/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-05-01 19:51:45 EDT (Sun, 01 May 2011)
@@ -20,6 +20,74 @@
namespace detail { namespace rtree { namespace visitors {
+//template <size_t N, typename Cont>
+//class array_semi_dynamic
+//{
+//public:
+// typedef typename Cont::value_type value_type;
+//
+// array_semi_dynamic()
+// : arr_elements(0)
+// {}
+//
+// void push_back(value_type const& v)
+// {
+// if ( arr_elements < N )
+// arr[arr_elements++] = v;
+// else
+// cont.push_back(v);
+// }
+//
+// void pop_back()
+// {
+// if ( !cont.empty() )
+// cont.pop_back();
+// else
+// {
+// assert(0 < arr_elements);
+// --arr_elements;
+// }
+// }
+//
+// value_type & back()
+// {
+// if ( !cont.empty() )
+// return cont.back();
+// else
+// {
+// assert(0 < arr_elements);
+// return arr[arr_elements - 1];
+// }
+// }
+//
+// value_type const& back() const
+// {
+// if ( !cont.empty() )
+// return cont.back();
+// else
+// {
+// assert(0 < arr_elements);
+// return arr[arr_elements - 1];
+// }
+// }
+//
+// bool empty() const
+// {
+// assert(cont.empty());
+// return 0 == arr_elements;
+// }
+//
+// size_t size() const
+// {
+// return arr_elements + cont.size();
+// }
+//
+//private:
+// boost::array<value_type, N> arr;
+// size_t arr_elements;
+// Cont cont;
+//};
+
// rtree spatial query visitor
template <typename Value, typename Translator, typename Box, typename Tag, typename Geometry, typename OutIter>
@@ -37,7 +105,7 @@
{
/*typedef typename internal_node::children_type children_type;
- std::deque<node*> nodes;
+ array_semi_dynamic<512, std::deque<node*> > nodes;
for (typename children_type::const_iterator it = n.children.begin();
it != n.children.end(); ++it)
@@ -70,8 +138,7 @@
{
operator()(boost::get<leaf>(*n));
}
- }
- */
+ }*/
typedef typename internal_node::children_type children_type;
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/insert.hpp 2011-05-01 19:51:45 EDT (Sun, 01 May 2011)
@@ -1,6 +1,6 @@
// Boost.Geometry (aka GGL, Generic Geometry Library)
//
-// Boost.Index - R-tree details
+// Boost.Index - R-tree insert details
//
// Copyright 2011 Adam Wulkiewicz.
// Use, modification and distribution is subject to the Boost Software License,
@@ -16,10 +16,221 @@
namespace detail { namespace rtree { namespace visitors {
+namespace detail {
+
+// Default choose_next_node
+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;
+ }
+};
+
+// Not implemented here
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct redistribute_elements;
+
+// Default split algorithm
+template <typename Value, typename Translator, typename Box, typename Tag>
+class split
+{
+ 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;
+
+ 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;
+ redistribute_elements<Value, Translator, Box, Tag>::
+ 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;
+ }
+ }
+};
+
+// Default overflow treatment algorithm
+template <typename Value, typename Translator, typename Box, typename Tag>
+struct overflow_treatment
+{
+ 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;
+
+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)
+ {
+ split<Value, Translator, Box, Tag>::apply(n, parent, current_child_index, root, min_elems, max_elems, tr);
+ }
+};
+
+} // namespace detail
+
+// Default insert algorithm
template <typename Value, typename Translator, typename Box, typename Tag>
-struct insert
+class insert : public boost::static_visitor<>
{
- // not implemented here
+ 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;
+
+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 = detail::choose_next_node<Value, Box, 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() )
+ {
+ detail::overflow_treatment<Value, Translator, Box, Tag>::
+ 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() )
+ {
+ detail::overflow_treatment<Value, Translator, Box, Tag>::
+ 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
Modified: sandbox-branches/geometry/index_080_new/tests/main.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/main.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/main.cpp 2011-05-01 19:51:45 EDT (Sun, 01 May 2011)
@@ -5,7 +5,8 @@
int main()
{
tests_translators_hpp();
- tests_rtree_native_hpp();
+ tests_rtree_native_hpp<boost::geometry::index::linear_tag>();
+ tests_rtree_native_hpp<boost::geometry::index::rstar_tag>();
tests_rtree_filters_hpp();
/*namespace g = boost::geometry;
Modified: sandbox-branches/geometry/index_080_new/tests/rtree_native.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/rtree_native.hpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/rtree_native.hpp 2011-05-01 19:51:45 EDT (Sun, 01 May 2011)
@@ -13,6 +13,7 @@
#include <map>
+template <typename Tag>
void tests_rtree_native_hpp()
{
std::cout << "tests/rtree_native.hpp\n";
@@ -22,7 +23,7 @@
typedef boost::geometry::model::point<float, 3, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
- boost::geometry::index::rtree<B> t(4, 2);
+ boost::geometry::index::rtree<B, boost::geometry::index::default_parameter, Tag> t(4, 2);
boost::geometry::index::insert(t, B(P(0, 0, 0), P(1, 1, 1)));
boost::geometry::index::insert(t, B(P(2, 2, 2), P(3, 3, 3)));
boost::geometry::index::insert(t, B(P(4, 4, 4), P(5, 5, 5)));
@@ -39,7 +40,7 @@
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
- boost::geometry::index::rtree<B> t(4, 2);
+ boost::geometry::index::rtree<B, boost::geometry::index::default_parameter, Tag> t(4, 2);
boost::geometry::index::insert(t, B(P(0, 0), P(1, 1)));
boost::geometry::index::insert(t, B(P(2, 2), P(3, 3)));
boost::geometry::index::insert(t, B(P(4, 4), P(5, 5)));
@@ -56,7 +57,7 @@
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;
- boost::geometry::index::rtree<P> t(4, 2);
+ boost::geometry::index::rtree<P, boost::geometry::index::default_parameter, Tag> t(4, 2);
boost::geometry::index::insert(t, P(0, 0));
boost::geometry::index::insert(t, P(2, 2));
boost::geometry::index::insert(t, P(4, 4));
@@ -74,7 +75,7 @@
typedef boost::geometry::model::box<P> B;
typedef std::pair<B, int> V;
- boost::geometry::index::rtree<V> t(4, 2);
+ boost::geometry::index::rtree<V, boost::geometry::index::default_parameter, Tag> t(4, 2);
boost::geometry::index::insert(t, V(B(P(0, 0), P(1, 1)), 0));
boost::geometry::index::insert(t, V(B(P(2, 2), P(3, 3)), 1));
boost::geometry::index::insert(t, V(B(P(4, 4), P(5, 5)), 2));
@@ -99,7 +100,7 @@
V v4( new std::pair<B, int>(B(P(6, 6), P(7, 7)), 3) );
V v5( new std::pair<B, int>(B(P(8, 8), P(9, 9)), 4) );
- boost::geometry::index::rtree<V> t(4, 2);
+ boost::geometry::index::rtree<V, boost::geometry::index::default_parameter, Tag> t(4, 2);
boost::geometry::index::insert(t, v1);
boost::geometry::index::insert(t, v2);
boost::geometry::index::insert(t, v3);
@@ -125,7 +126,7 @@
m.insert(std::pair<int, B>(3, B(P(6, 6), P(7, 7))));
m.insert(std::pair<int, B>(4, B(P(8, 8), P(9, 9))));
- boost::geometry::index::rtree<V> t(4, 2);
+ boost::geometry::index::rtree<V, boost::geometry::index::default_parameter, Tag> t(4, 2);
V vit = m.begin();
boost::geometry::index::insert(t, vit++);
boost::geometry::index::insert(t, vit++);
@@ -153,7 +154,7 @@
v.push_back(B(P(6, 6), P(7, 7)));
v.push_back(B(P(8, 8), P(9, 9)));
- boost::geometry::index::rtree<V, T> t(4, 2, T(v));
+ boost::geometry::index::rtree<V, T, Tag> t(4, 2, T(v));
boost::geometry::index::insert(t, 0u);
boost::geometry::index::insert(t, 1u);