Subject: [Boost-commit] svn:boost r70607 - in sandbox-branches/geometry/index_080_new: boost/geometry/extensions/index/rtree boost/geometry/extensions/index/rtree/rstar boost/geometry/extensions/index/rtree/visitors tests
From: adam.wulkiewicz_at_[hidden]
Date: 2011-03-26 22:21:46
Author: awulkiew
Date: 2011-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
New Revision: 70607
URL: http://svn.boost.org/trac/boost/changeset/70607
Log:
other version of split algorithm + a lot of minor changes
Added:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp (contents, props changed)
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_are_boxes_ok.hpp (contents, props changed)
Text files modified:
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rtree_insert.hpp | 645 ---------------------------------------
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree.hpp | 15
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp | 18 +
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp | 30
sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp | 29
sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp | 29 +
sandbox-branches/geometry/index_080_new/tests/additional_sizes_and_times.cpp | 8
sandbox-branches/geometry/index_080_new/tests/main.cpp | 13
sandbox-branches/geometry/index_080_new/tests/rtree_native.hpp | 19 +
9 files changed, 118 insertions(+), 688 deletions(-)
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp 2011-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -0,0 +1,186 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R*-tree ChooseNextNode algorithm
+//
+// 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_RSTAR_CHOOSE_NEXT_NODE_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP
+
+#include <algorithm>
+
+#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/rtree_node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/rtree_is_leaf.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+struct rtree_rstar_chnn_min_overlap_cost {};
+struct rtree_rstar_chnn_nearly_min_overlap_cost {};
+
+// TODO: awulkiew - it's possible that goodness values may be used to choose next node
+// on this step some of the goodness values would be calculated (not all)
+// and only for some nodes (goodness values should be calculated only if there is an overflow)
+
+template <typename Value, typename Box, typename Tag>
+class rtree_rstar_choose_next_node
+{};
+
+// TODO: awulkiew finish this version
+// use min_element instead of searching by myself
+
+//template <typename Value, typename Box>
+//class rtree_rstar_choose_next_node<Value, Box, rtree_rstar_chnn_nearly_min_overlap_cost>
+//{
+// typedef typename index::detail::rtree_node<Value, Box, rtree_rstar_tag>::type node;
+// typedef typename index::detail::rtree_internal_node<Value, Box, rtree_rstar_tag>::type internal_node;
+// typedef typename index::detail::rtree_leaf<Value, Box, rtree_rstar_tag>::type leaf;
+//
+// typedef typename internal_node::children_type children_type;
+//
+//public:
+// template <typename Indexable>
+// static inline size_t apply(internal_node & n, Indexable const& indexable)
+// {
+// assert(!n.children.empty());
+//
+// bool has_leaves = boost::apply_visitor(
+// visitors::rtree_is_leaf<Value, Box, rtree_rstar_tag>(),
+// *n.children.front().second);
+//
+// if ( !has_leaves )
+// return impl<internal_node_areas>(n, indexable);
+// else
+// return impl<branch_areas>(n, indexable);
+// }
+//
+//private:
+// template <typename Areas, typename Indexable>
+// static inline size_t impl(internal_node & n, Indexable const& indexable)
+// {
+// }
+//
+//};
+
+// TODO: awulkiew - wrong algorithm? Should branch check be applied to Leafs?
+// TODO: awulkiew - further optimization: don't calculate area with the overlap, calculate it only if
+// overlap < smallest_overlap (and current area must be stored) OR
+// overlap == smallest_overlap (and area must be compared)
+
+template <typename Value, typename Box>
+class rtree_rstar_choose_next_node<Value, Box, rtree_rstar_chnn_min_overlap_cost>
+{
+ typedef typename index::detail::rtree_node<Value, Box, rtree_rstar_tag>::type node;
+ typedef typename index::detail::rtree_internal_node<Value, Box, rtree_rstar_tag>::type internal_node;
+ typedef typename index::detail::rtree_leaf<Value, Box, rtree_rstar_tag>::type leaf;
+
+ typedef typename internal_node::children_type children_type;
+
+public:
+ template <typename Indexable>
+ static inline size_t apply(internal_node & n, Indexable const& indexable)
+ {
+ assert(!n.children.empty());
+
+ bool has_leaves = boost::apply_visitor(
+ visitors::rtree_is_leaf<Value, Box, rtree_rstar_tag>(),
+ *n.children.front().second);
+
+ if ( !has_leaves )
+ return impl<internal_node_areas>(n, indexable);
+ else
+ return impl<branch_areas>(n, indexable);
+ }
+
+private:
+ template <typename Areas, typename Indexable>
+ static inline size_t impl(internal_node & n, Indexable const& indexable)
+ {
+ typedef typename children_type::iterator children_iterator;
+
+ //assert(!n.children.empty());
+
+ children_iterator temp_it = n.children.begin();
+ children_iterator child_it = temp_it;
+ Areas min_areas(n.children, child_it, indexable);
+
+ for (children_iterator it = ++temp_it;
+ it != n.children.end(); ++it)
+ {
+ Areas areas(n.children, it, indexable);
+
+ if ( areas < min_areas )
+ {
+ child_it = it;
+ min_areas = areas;
+ }
+ }
+
+ // TODO: awulkiew - switch to indexes in the whole class?
+ return child_it - n.children.begin();
+ }
+
+ struct branch_areas
+ {
+ typedef typename area_result<Box>::type area_type;
+
+ template <typename Indexable>
+ inline branch_areas(children_type const& ch, typename children_type::iterator const& k_it, Indexable const& indexable)
+ {
+ overlap_area = 0;
+ for (typename children_type::const_iterator it = ch.begin(); it != ch.end(); ++it)
+ if ( it != k_it )
+ overlap_area += index::overlap(k_it->first, it->first);
+
+ area = index::area(k_it->first);
+
+ diff_area = index::union_area(k_it->first, indexable) - area;
+ }
+
+ inline bool operator<(branch_areas &a) const
+ {
+ return overlap_area < a.overlap_area ||
+ ( overlap_area == a.overlap_area && diff_area < a.diff_area ) ||
+ ( diff_area == a.diff_area && area < a.area );
+ }
+
+ area_type overlap_area;
+ area_type diff_area;
+ area_type area;
+ };
+
+ struct internal_node_areas
+ {
+ typedef typename area_result<Box>::type area_type;
+
+ template <typename Indexable>
+ inline internal_node_areas(children_type const&, typename children_type::iterator const& k_it, Indexable const& indexable)
+ {
+ area = index::area(k_it->first);
+ diff_area = index::union_area(k_it->first, indexable) - area;
+ }
+
+ inline bool operator<(internal_node_areas &a) const
+ {
+ return diff_area < a.diff_area ||
+ ( diff_area == a.diff_area && area < a.area );
+ }
+
+ area_type diff_area;
+ area_type area;
+ };
+};
+
+} // namespace visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_CHOOSE_NEXT_NODE_HPP
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rtree_insert.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rtree_insert.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/rtree_insert.hpp 2011-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -23,578 +23,13 @@
#include <boost/geometry/extensions/index/rtree/visitors/rtree_insert.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/rtree_is_leaf.hpp>
+#include <boost/geometry/extensions/index/rtree/rstar/choose_next_node.hpp>
+#include <boost/geometry/extensions/index/rtree/rstar/split.hpp>
+
namespace boost { namespace geometry { namespace index {
namespace visitors {
-// ----------------------------------------------------------------------------- //
-// rstar/choose_next_node
-// ----------------------------------------------------------------------------- //
-
-// TODO: awulkiew - it's possible that goodness values may be used to choose next node
-
-// rtree choose_next_node algorithm for rstar variant
-
-template <typename Value, typename Box>
-class rtree_rstar_choose_next_node
-{
- typedef typename index::detail::rtree_node<Value, Box, rtree_rstar_tag>::type node;
- typedef typename index::detail::rtree_internal_node<Value, Box, rtree_rstar_tag>::type internal_node;
- typedef typename index::detail::rtree_leaf<Value, Box, rtree_rstar_tag>::type leaf;
-
- typedef typename internal_node::children_type children_type;
-
-public:
- // TODO: awulkiew - alternative lower-cost version of overlap calculation may be used (branch_areas)
- // TODO: awulkiew - further optimization: don't calculate area with the overlap, calculate it only if
- // overlap < smallest_overlap (and current area must be stored) OR
- // overlap == smallest_overlap (and area must be compared)
- template <typename Indexable>
- static inline size_t apply(internal_node & n, Indexable const& indexable)
- {
- assert(!n.children.empty());
-
- bool has_leaves = boost::apply_visitor(
- visitors::rtree_is_leaf<Value, Box, rtree_rstar_tag>(),
- *n.children.front().second);
-
- if ( !has_leaves )
- return impl<internal_node_areas>(n, indexable);
- else
- return impl<branch_areas>(n, indexable);
- }
-
-private:
- template <typename Areas, typename Indexable>
- static inline size_t impl(internal_node & n, Indexable const& indexable)
- {
- typedef typename children_type::iterator children_iterator;
-
- //assert(!n.children.empty());
-
- children_iterator temp_it = n.children.begin();
- children_iterator child_it = temp_it;
- Areas min_areas(n.children, child_it, indexable);
-
- for (children_iterator it = ++temp_it;
- it != n.children.end(); ++it)
- {
- Areas areas(n.children, it, indexable);
-
- if ( areas < min_areas )
- {
- child_it = it;
- min_areas = areas;
- }
- }
-
- // TODO: awulkiew - switch to indexes in the whole class?
- return child_it - n.children.begin();
- }
-
- struct branch_areas
- {
- typedef typename area_result<Box>::type area_type;
-
- template <typename Indexable>
- inline branch_areas(children_type const& ch, typename children_type::iterator const& k_it, Indexable const& indexable)
- {
- overlap_area = 0;
- for (typename children_type::const_iterator it = ch.begin(); it != ch.end(); ++it)
- if ( it != k_it )
- overlap_area += index::overlap(k_it->first, it->first);
-
- area = index::area(k_it->first);
-
- diff_area = index::union_area(k_it->first, indexable) - area;
- }
-
- inline bool operator<(branch_areas &a) const
- {
- return overlap_area < a.overlap_area ||
- ( overlap_area == a.overlap_area && diff_area < a.diff_area ) ||
- ( diff_area == a.diff_area && area < a.area );
- }
-
- area_type overlap_area;
- area_type diff_area;
- area_type area;
- };
-
- struct internal_node_areas
- {
- typedef typename area_result<Box>::type area_type;
-
- template <typename Indexable>
- inline internal_node_areas(children_type const&, typename children_type::iterator const& k_it, Indexable const& indexable)
- {
- area = index::area(k_it->first);
- diff_area = index::union_area(k_it->first, indexable) - area;
- }
-
- inline bool operator<(internal_node_areas &a) const
- {
- return diff_area < a.diff_area ||
- ( diff_area == a.diff_area && area < a.area );
- }
-
- area_type diff_area;
- area_type area;
- };
-};
-
-// ----------------------------------------------------------------------------- //
-// rstar/sorts
-// ----------------------------------------------------------------------------- //
-
-// elements ids less comparator
-
-template <typename Elements, typename Translator, size_t Corner, size_t AxisIndex>
-class rtree_rstar_elements_indexes_less
-{
-public:
- rtree_rstar_elements_indexes_less(Elements const& elements, Translator const& tr)
- : m_elements(elements), m_tr(tr)
- {}
-
- bool operator()(size_t e1_index, size_t e2_index)
- {
- return
- index::detail::get<Corner, AxisIndex>(
- index::detail::rtree_element_indexable(m_elements[e1_index], m_tr)
- )
- <
- index::detail::get<Corner, AxisIndex>(
- index::detail::rtree_element_indexable(m_elements[e2_index], m_tr)
- );
- }
-
-private:
- Elements const& m_elements;
- Translator const& m_tr;
-};
-
-template <typename T, size_t Dimension>
-class rtree_rstar_vectors
-{
-public:
- inline rtree_rstar_vectors(size_t count)
- : m_count(count), m_ids(Dimension * 2 * count)
- {}
-
- template <size_t AxisIndex, size_t Corner>
- inline typename std::vector<T>::iterator begin()
- {
- BOOST_STATIC_ASSERT(AxisIndex < Dimension);
- BOOST_STATIC_ASSERT(Corner < 2);
- return m_ids.begin() + ( AxisIndex * 2 + Corner ) * m_count;
- }
-
- template <size_t AxisIndex, size_t Corner>
- inline typename std::vector<T>::iterator end()
- {
- BOOST_STATIC_ASSERT(AxisIndex < Dimension);
- BOOST_STATIC_ASSERT(Corner < 2);
- return m_ids.begin() + ( AxisIndex * 2 + Corner + 1) * m_count;
- }
-
- template <size_t AxisIndex, size_t Corner>
- inline T const& get(size_t index) const
- {
- BOOST_STATIC_ASSERT(AxisIndex < Dimension);
- BOOST_STATIC_ASSERT(Corner < 2);
- assert(index < m_count);
- return m_ids[( AxisIndex * 2 + Corner ) * m_count + index];
- }
-
- template <size_t AxisIndex, size_t Corner>
- inline void set(size_t index, T const& v)
- {
- BOOST_STATIC_ASSERT(AxisIndex < Dimension);
- BOOST_STATIC_ASSERT(Corner < 2);
- assert(index < m_count);
- m_ids[( AxisIndex * 2 + Corner ) * m_count + index] = v;
- }
-
- inline T const& get(size_t axis, size_t corner, size_t index) const
- {
- assert(axis < Dimension);
- assert(corner < 2);
- assert(index < m_count);
- return m_ids[( axis * 2 + corner ) * m_count + index];
- }
-
- inline size_t vector_size() const
- {
- return m_count;
- }
-
-private:
- size_t m_count;
- std::vector<T> m_ids;
-};
-
-// init indexes of elements and sort them
-
-template <typename Elements, typename Translator, size_t Dimension>
-class rtree_rstar_sorts_fill_ids
-{
- BOOST_STATIC_ASSERT(0 < Dimension);
-
-public:
- template <size_t D>
- static inline void apply(rtree_rstar_vectors<size_t, D> & ids, Elements const& elements, Translator const& tr)
- {
- rtree_rstar_sorts_fill_ids<Elements, Translator, Dimension - 1>::apply(ids, elements, tr);
-
- fill<min_corner>(ids, elements, tr);
- fill<max_corner>(ids, elements, tr);
- }
-
-private:
- template <size_t Corner, size_t D>
- static inline void fill(rtree_rstar_vectors<size_t, D> & ids, Elements const& elements, Translator const& tr)
- {
- for ( size_t i = 0 ; i < elements.size() ; ++i )
- ids.set<Dimension - 1, Corner>(i, i);
-
- rtree_rstar_elements_indexes_less<Elements, Translator, Corner, Dimension - 1> less(elements, tr);
- std::sort(ids.begin<Dimension - 1, Corner>(), ids.end<Dimension - 1, Corner>(), less);
- }
-};
-
-template <typename Elements, typename Translator>
-class rtree_rstar_sorts_fill_ids<Elements, Translator, 1>
-{
-public:
- template <size_t D>
- static inline void apply(rtree_rstar_vectors<size_t, D> & ids, Elements const& elements, Translator const& tr)
- {
- fill<min_corner>(ids, elements, tr);
- fill<max_corner>(ids, elements, tr);
- }
-
-private:
- template <size_t Corner, size_t D>
- static inline void fill(rtree_rstar_vectors<size_t, D> & ids, Elements const& elements, Translator const& tr)
- {
- for ( size_t i = 0 ; i < elements.size() ; ++i )
- ids.set<0, Corner>(i, i);
-
- rtree_rstar_elements_indexes_less<Elements, Translator, Corner, 0> less(elements, tr);
- std::sort(ids.begin<0, Corner>(), ids.end<0, Corner>(), less);
- }
-};
-
-// sorts for each axis for min and max
-
-template <typename Elements, typename Translator, size_t Dimension>
-class rtree_rstar_sorts
-{
-public:
- inline rtree_rstar_sorts(Elements const& elements, Translator const& tr)
- : m_elems(elements), m_tr(tr), m_ids(m_elems.size())
- {
- rtree_rstar_sorts_fill_ids<Elements, Translator, Dimension>::apply(m_ids, elements, tr);
- }
-
- // TODO: awulkiew - should those methods be here? Just leave get_element?
-
- template <size_t AxisIndex, size_t Corner>
- inline typename index::detail::rtree_element_indexable_type<typename Elements::value_type, Translator>::type const&
- get_indexable(size_t index) const
- {
- size_t id = m_ids.get<AxisIndex, Corner>(index);
- return index::detail::rtree_element_indexable(m_elems[id], m_tr);
- }
-
- inline typename index::detail::rtree_element_indexable_type<typename Elements::value_type, Translator>::type const&
- get_indexable(size_t axis, size_t corner, size_t index) const
- {
- size_t id = m_ids.get(axis, corner, index);
- return index::detail::rtree_element_indexable(m_elems[id], m_tr);
- }
-
- template <size_t AxisIndex, size_t Corner>
- inline typename Elements::value_type const& get_element(size_t index) const
- {
- size_t id = m_ids.get<AxisIndex, Corner>(index);
- return m_elems[id];
- }
-
- inline typename Elements::value_type const& get_element(size_t axis, size_t corner, size_t index) const
- {
- size_t id = m_ids.get(axis, corner, index);
- return m_elems[id];
- }
-
- inline size_t sort_size() const
- {
- return m_ids.vector_size();
- }
-
-private:
- Elements const& m_elems;
- Translator const& m_tr;
-
- rtree_rstar_vectors<size_t, Dimension> m_ids;
-};
-
-// ----------------------------------------------------------------------------- //
-// rstar/goodness_values
-// ----------------------------------------------------------------------------- //
-
-// calculate margins, areas and overlaps
-
-template <typename Box, size_t AxisIndex, size_t Corner>
-class rtree_rstar_calculate_goodness_values_for_axis
-{
- typedef typename geometry::traits::coordinate_type<
- typename geometry::traits::point_type<Box>::type
- >::type coordinate_type;
-
- static const size_t dimension = geometry::traits::dimension<
- typename geometry::traits::point_type<Box>::type
- >::value;
-
- typedef typename area_result<Box>::type area_type;
- typedef typename margin_result<Box>::type margin_type;
- typedef typename overlap_result<Box>::type overlap_type;
- typedef boost::tuple<Box, Box, margin_type, overlap_type, area_type> goodness_type;
-
-public:
- template <typename Elements, typename Translator>
- static inline void apply(
- rtree_rstar_vectors<goodness_type, dimension> & goodness_vectors,
- rtree_rstar_sorts<Elements, Translator, dimension> const& sorts,
- size_t min_elems,
- size_t max_elems)
- {
- assert(sorts.sort_size() == max_elems + 1);
- assert(goodness_vectors.vector_size() == max_elems - 2 * min_elems + 2);
-
- size_t median_index_last = max_elems - min_elems + 2;
- size_t i = 0;
- for ( size_t median_index = min_elems ; median_index < median_index_last ; ++median_index, ++i )
- {
- Box left_box = calculate_box(sorts, 0, median_index);
- Box right_box = calculate_box(sorts, median_index, sorts.sort_size());
-
- margin_type margin = index::margin(left_box) + index::margin(right_box);
- area_type area = index::area(left_box) + index::area(right_box);
- overlap_type overlap = index::overlap(left_box, right_box);
-
- goodness_vectors.set<AxisIndex, Corner>(
- i,
- boost::make_tuple(left_box, right_box, margin, overlap, area));
- }
- }
-private:
- template <typename Elements, typename Translator>
- static inline Box calculate_box(
- rtree_rstar_sorts<Elements, Translator, dimension> const& sorts,
- size_t index_first,
- size_t index_last)
- {
- assert(index_first < index_last);
-
- Box result;
- geometry::convert(sorts.template get_indexable<AxisIndex, Corner>(index_first), result);
- ++index_first;
- for ( ; index_first < index_last ; ++index_first )
- geometry::expand(result, sorts.template get_indexable<AxisIndex, Corner>(index_first));
- return result;
- }
-};
-
-// calculate goodness values for all axis
-
-template <typename Box, size_t Dimension>
-struct rtree_rstar_calculate_goodness_values
-{
- BOOST_STATIC_ASSERT(0 < Dimension);
-
- typedef typename area_result<Box>::type area_type;
- typedef typename margin_result<Box>::type margin_type;
- typedef typename overlap_result<Box>::type overlap_type;
- typedef boost::tuple<Box, Box, margin_type, overlap_type, area_type> goodness_type;
-
- template <typename Elements, typename Translator, size_t D>
- static inline void apply(
- rtree_rstar_vectors<goodness_type, D> & goodness_vectors,
- rtree_rstar_sorts<Elements, Translator, D> const& sorts,
- size_t min_elems,
- size_t max_elems)
- {
- rtree_rstar_calculate_goodness_values<Box, Dimension - 1>
- ::apply(goodness_vectors, sorts, min_elems, max_elems);
-
- rtree_rstar_calculate_goodness_values_for_axis<Box, Dimension - 1, min_corner>
- ::apply(goodness_vectors, sorts, min_elems, max_elems);
- rtree_rstar_calculate_goodness_values_for_axis<Box, Dimension - 1, max_corner>
- ::apply(goodness_vectors, sorts, min_elems, max_elems);
- }
-};
-
-template <typename Box>
-struct rtree_rstar_calculate_goodness_values<Box, 1>
-{
- typedef typename area_result<Box>::type area_type;
- typedef typename margin_result<Box>::type margin_type;
- typedef typename overlap_result<Box>::type overlap_type;
- typedef boost::tuple<Box, Box, margin_type, overlap_type, area_type> goodness_type;
-
- template <typename Elements, typename Translator, size_t D>
- static inline void apply(
- rtree_rstar_vectors<goodness_type, D> & goodness_vectors,
- rtree_rstar_sorts<Elements, Translator, D> const& sorts,
- size_t min_elems,
- size_t max_elems)
- {
- rtree_rstar_calculate_goodness_values_for_axis<Box, 0, min_corner>
- ::apply(goodness_vectors, sorts, min_elems, max_elems);
- rtree_rstar_calculate_goodness_values_for_axis<Box, 0, max_corner>
- ::apply(goodness_vectors, sorts, min_elems, max_elems);
- }
-};
-
-// goodness values
-
-template <typename Elements, typename Translator, typename Box>
-class rtree_rstar_goodness_values
-{
- typedef typename geometry::traits::coordinate_type<
- typename geometry::traits::point_type<Box>::type
- >::type coordinate_type;
-
- static const size_t dimension = geometry::traits::dimension<
- typename geometry::traits::point_type<Box>::type
- >::value;
-
- typedef typename area_result<Box>::type area_type;
- typedef typename margin_result<Box>::type margin_type;
- typedef typename overlap_result<Box>::type overlap_type;
- typedef boost::tuple<Box, Box, margin_type, overlap_type, area_type> goodness_type;
-
-public:
- inline rtree_rstar_goodness_values(
- Elements const& elements,
- Translator const& tr,
- size_t min_elems,
- size_t max_elems)
- : m_sorts(elements, tr)
- , m_goodness_vectors(max_elems - 2 * min_elems + 2)
- {
- rtree_rstar_calculate_goodness_values<Box, dimension>::apply(
- m_goodness_vectors, m_sorts, min_elems, max_elems);
- }
-
- inline size_t elements_size() const
- {
- return m_sorts.sort_size();
- }
-
- inline size_t goodnesses_size() const
- {
- return m_goodness_vectors.vector_size();
- }
-
- inline goodness_type const& get_goodness(size_t axis, size_t corner, size_t index) const
- {
- return m_goodness_vectors.get(axis, corner, index);
- }
-
- inline typename Elements::value_type const& get_element(size_t axis, size_t corner, size_t index) const
- {
- return m_sorts.get_element(axis, corner, index);
- }
-
-private:
- rtree_rstar_sorts<Elements, Translator, dimension> m_sorts;
- rtree_rstar_vectors<goodness_type, dimension> m_goodness_vectors;
-};
-
-template <typename Elements, typename Translator, typename Box>
-class rtree_rstar_choose_split_axis
-{
- typedef typename margin_result<Box>::type margin_type;
-public:
- static inline std::pair<size_t, size_t> apply(rtree_rstar_goodness_values<Elements, Translator, Box> const& gv)
- {
- std::pair<size_t, size_t> smallest_distr = std::make_pair(0, 0);
- margin_type smallest_margins_sum = calculate_margins_sum(0, 0, gv);
-
- margin_type margins_sum = calculate_margins_sum(0, 1, gv);
- if ( margins_sum < smallest_margins_sum )
- {
- smallest_distr.second = 1;
- smallest_margins_sum = margins_sum;
- }
-
- for ( size_t a = 1 ; a < traits::dimension<Box>::value ; ++a )
- {
- for ( size_t c = 0 ; c < 2 ; ++c )
- {
- margins_sum = calculate_margins_sum(a, c, gv);
- if ( margins_sum < smallest_margins_sum )
- {
- smallest_distr.first = a;
- smallest_distr.second = c;
- smallest_margins_sum = margins_sum;
- }
- }
- }
- return smallest_distr;
- }
-private:
- static inline typename margin_result<Box>::type
- calculate_margins_sum(size_t axis, size_t corner, rtree_rstar_goodness_values<Elements, Translator, Box> const& gv)
- {
- typename margin_result<Box>::type margins_sum = 0;
- for ( size_t i = 0 ; i < gv.goodnesses_size() ; ++i )
- margins_sum += boost::get<2>(gv.get_goodness(axis, corner, i));
- return margins_sum;
- }
-};
-
-template <typename Elements, typename Translator, typename Box>
-class rtree_rstar_choose_split_index
-{
- typedef typename area_result<Box>::type area_type;
- typedef typename overlap_result<Box>::type overlap_type;
-public:
- static inline size_t apply(rtree_rstar_goodness_values<Elements, Translator, Box> const& gv, size_t axis, size_t corner)
- {
- size_t smallest_index = 0;
- overlap_type smallest_overlap = boost::get<3>(gv.get_goodness(axis, corner, 0));
- overlap_type smallest_area = boost::get<4>(gv.get_goodness(axis, corner, 0));
-
- for ( size_t i = 1 ; i < gv.goodnesses_size() ; ++i )
- {
- overlap_type overlap = boost::get<3>(gv.get_goodness(axis, corner, i));
- if ( overlap < smallest_overlap )
- {
- smallest_overlap = overlap;
- smallest_area = boost::get<4>(gv.get_goodness(axis, corner, i));
- smallest_index = i;
- }
- else if ( overlap == smallest_overlap )
- {
- area_type area = boost::get<4>(gv.get_goodness(axis, corner, i));
- if ( area < smallest_area )
- {
- smallest_area = area;
- smallest_index = i;
- }
- }
- }
-
- return smallest_index;
- }
-};
-
-// rtree insert routine for rstar variant
-
template <typename Value, typename Translator, typename Box>
class rtree_insert<Value, Translator, Box, rtree_rstar_tag> : public boost::static_visitor<>
{
@@ -617,7 +52,9 @@
size_t current_child_index_bckup = m_current_child_index;
// choose next node, where value insert traversing should go
- m_current_child_index = rtree_rstar_choose_next_node<Value, Box>::apply(n, m_tr(m_value));
+ m_current_child_index =
+ rtree_rstar_choose_next_node<Value, Box, rtree_rstar_chnn_min_overlap_cost>::
+ apply(n, m_tr(m_value));
// TODO: awulkiew - if reinsert is implemented this must be changed
geometry::expand(n.children[m_current_child_index].first, m_tr(m_value));
@@ -631,7 +68,8 @@
if ( m_max_elems_per_node < n.children.size() )
{
- split(n);
+ rtree_rstar_split<Value, Translator, Box>::
+ apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
}
}
@@ -641,75 +79,12 @@
if ( m_max_elems_per_node < n.values.size() )
{
- split(n);
+ rtree_rstar_split<Value, Translator, Box>::
+ apply(n, m_parent, m_current_child_index, m_root_node, m_min_elems_per_node, m_max_elems_per_node, m_tr);
}
}
private:
- template <typename Node>
- inline void split(Node & n)
- {
- typedef typename index::detail::rtree_elements_type<Node>::type elements_type;
- typedef typename elements_type::value_type element_type;
-
- elements_type & elems = index::detail::get_elements(n);
-
- rtree_rstar_goodness_values<elements_type, Translator, Box> gv(elems, m_tr, m_min_elems_per_node, m_max_elems_per_node);
-
- std::pair<size_t, size_t> axis_and_corner =
- rtree_rstar_choose_split_axis<elements_type, Translator, Box>::apply(gv);
- size_t axis = axis_and_corner.first;
- size_t corner = axis_and_corner.second;
-
- size_t choosen_index =
- rtree_rstar_choose_split_index<elements_type, Translator, Box>::apply(gv, axis, corner);
-
- size_t median_index = m_min_elems_per_node + choosen_index;
- assert(median_index <= m_max_elems_per_node + 1 - m_min_elems_per_node);
-
- // create new node
- node * right_node = rtree_create_node(Node());
- elements_type & new_elems = index::detail::get_elements(boost::get<Node>(*right_node));
-
- // update new node's elements
- new_elems.reserve(m_max_elems_per_node + 1 - median_index);
- for ( size_t i = median_index ; i < m_max_elems_per_node + 1 ; ++i)
- new_elems.push_back(gv.get_element(axis, corner, i));
-
- // fill temporary container with left node's elements
- elements_type left_elems;
- left_elems.reserve(median_index);
- for ( size_t i = 0 ; i < median_index ; ++i )
- left_elems.push_back(gv.get_element(axis, corner, i));
- // update old node's elements
- elems = left_elems;
-
- if ( m_parent != 0 )
- {
- // update old node's box
- m_parent->children[m_current_child_index].first = boost::get<0>(gv.get_goodness(axis, corner, choosen_index));
- // add new node to the parent's children
- m_parent->children.push_back( std::make_pair(
- boost::get<1>(gv.get_goodness(axis, corner, choosen_index)), right_node ) );
- }
- else
- {
- assert(&n == boost::get<Node>(m_root_node));
-
- // 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(boost::get<0>(gv.get_goodness(axis, corner, choosen_index)), m_root_node)
- );
- boost::get<internal_node>(*new_root).children.push_back(
- std::make_pair(boost::get<1>(gv.get_goodness(axis, corner, choosen_index)), right_node)
- );
-
- m_root_node = new_root;
- }
- }
-
Value const& m_value;
Translator const& m_tr;
size_t m_min_elems_per_node;
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rstar/split.hpp 2011-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -0,0 +1,338 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R*-tree split 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_RSTAR_SPLIT_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_SPLIT_HPP
+
+#include <algorithm>
+
+#include <boost/tuple/tuple.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/rtree_node.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/rtree_insert.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/rtree_is_leaf.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+// elements less
+
+template <typename Elements, typename Translator, size_t AxisIndex, size_t Corner>
+class rtree_rstar_elements_less
+{
+ typedef typename Elements::value_type element_type;
+public:
+ inline rtree_rstar_elements_less(Translator const& tr)
+ : m_tr(tr)
+ {}
+
+ inline bool operator()(element_type const& e1, element_type const e2) const
+ {
+ return
+ index::detail::get<Corner, AxisIndex>(
+ index::detail::rtree_element_indexable(e1, m_tr)
+ )
+ <
+ index::detail::get<Corner, AxisIndex>(
+ index::detail::rtree_element_indexable(e2, m_tr)
+ );
+ }
+
+private:
+ Translator const& m_tr;
+};
+
+// rstar split axis data
+
+template <typename Box>
+struct rtree_rstar_split_axis_data
+{
+ typedef typename margin_result<Box>::type margin_type;
+ typedef typename overlap_result<Box>::type overlap_type;
+ typedef typename area_result<Box>::type area_type;
+
+ inline rtree_rstar_split_axis_data()
+ : margins_sum(0)
+ , smallest_overlap(std::numeric_limits<overlap_type>::max())
+ , smallest_area(std::numeric_limits<area_type>::max())
+ {}
+
+ inline void update(
+ size_t corner,
+ size_t median_index,
+ Box const& left_box,
+ Box const& right_box,
+ margin_type const& margin,
+ overlap_type const& overlap,
+ area_type const& area)
+ {
+ margins_sum += margin;
+
+ if ( overlap < smallest_overlap ||
+ ( overlap == smallest_overlap && area < smallest_area ) )
+ {
+ choosen_corner = corner;
+ choosen_median_index = median_index;
+ choosen_left_box = left_box;
+ choosen_right_box = right_box;
+ smallest_overlap = overlap;
+ smallest_area = area;
+ }
+ }
+
+ size_t choosen_corner;
+ size_t choosen_median_index;
+ Box choosen_left_box;
+ Box choosen_right_box;
+ margin_type margins_sum;
+ overlap_type smallest_overlap;
+ area_type smallest_area;
+};
+
+// update axis data for given axis and corner
+
+template <typename Value, typename Translator, typename Box, size_t Corner>
+class rtree_rstar_split_update_axis_data_for_corner
+{
+ typedef typename rtree_rstar_split_axis_data<Box>::margin_type margin_type;
+ typedef typename rtree_rstar_split_axis_data<Box>::overlap_type overlap_type;
+ typedef typename rtree_rstar_split_axis_data<Box>::area_type area_type;
+
+ BOOST_STATIC_ASSERT(Corner < 2);
+
+public:
+ template <typename Elements>
+ static inline void apply(
+ rtree_rstar_split_axis_data<Box> & split_axis_data,
+ Elements const& sorted_elements,
+ size_t min_elems,
+ size_t max_elems,
+ Translator const& tr)
+ {
+ size_t median_index_last = max_elems - min_elems + 2;
+ for ( size_t median_index = min_elems ; median_index < median_index_last ; ++median_index )
+ {
+ Box left_box = index::detail::elements_box<Box>(sorted_elements.begin(), sorted_elements.begin() + median_index, tr);
+ Box right_box = index::detail::elements_box<Box>(sorted_elements.begin() + median_index, sorted_elements.end(), tr);
+
+ margin_type margin = index::margin(left_box) + index::margin(right_box);
+ overlap_type overlap = index::overlap(left_box, right_box);
+ area_type area = index::area(left_box) + index::area(right_box);
+
+ split_axis_data.update(Corner, median_index, left_box, right_box, margin, overlap, area);
+ }
+ }
+};
+
+// split data
+
+template <typename Elements, typename Box>
+struct rtree_rstar_split_data
+{
+ typedef typename margin_result<Box>::type margin_type;
+ typedef typename overlap_result<Box>::type overlap_type;
+ typedef typename area_result<Box>::type area_type;
+
+ inline rtree_rstar_split_data()
+ : smallest_margins_sum(std::numeric_limits<margin_type>::max())
+ {}
+
+ inline void update(
+ size_t axis,
+ size_t corner,
+ size_t median_index,
+ Box const& left_box,
+ Box const& right_box,
+ margin_type const& margins_sum,
+ Elements const& distribution)
+ {
+ if ( margins_sum < smallest_margins_sum )
+ {
+ choosen_axis = axis;
+ choosen_corner = corner;
+ choosen_median_index = median_index;
+ choosen_left_box = left_box;
+ choosen_right_box = right_box;
+ smallest_margins_sum = margins_sum;
+ choosen_distribution = distribution;
+ }
+ }
+
+ size_t choosen_axis;
+ size_t choosen_corner;
+ size_t choosen_median_index;
+ Box choosen_left_box;
+ Box choosen_right_box;
+ margin_type smallest_margins_sum;
+ Elements choosen_distribution;
+};
+
+// update split data for given axis and corner
+
+template <typename Value, typename Translator, typename Box, size_t AxisIndex, size_t Corner>
+class rtree_rstar_split_update_data_for_axis_and_corner
+{
+ typedef typename rtree_rstar_split_axis_data<Box>::margin_type margin_type;
+ typedef typename rtree_rstar_split_axis_data<Box>::overlap_type overlap_type;
+ typedef typename rtree_rstar_split_axis_data<Box>::area_type area_type;
+
+public:
+ template <typename Elements>
+ static inline void apply(
+ rtree_rstar_split_data<Elements, Box> & split_data,
+ Elements & elements,
+ size_t min_elems,
+ size_t max_elems,
+ Translator const& tr)
+ {
+ rtree_rstar_split_axis_data<Box> split_axis_data;
+
+ rtree_rstar_elements_less<Elements, Translator, AxisIndex, Corner> less_min(tr);
+ std::sort(elements.begin(), elements.end(), less_min);
+
+ rtree_rstar_split_update_axis_data_for_corner<Value, Translator, Box, Corner>::
+ apply(split_axis_data, elements, min_elems, max_elems, tr);
+
+ split_data.update(
+ AxisIndex,
+ split_axis_data.choosen_corner,
+ split_axis_data.choosen_median_index,
+ split_axis_data.choosen_left_box,
+ split_axis_data.choosen_right_box,
+ split_axis_data.margins_sum,
+ elements);
+ }
+};
+
+// for each dimension and corner update split data
+
+template <typename Value, typename Translator, typename Box, size_t Dimension>
+struct rtree_rstar_split_update_data
+{
+ BOOST_STATIC_ASSERT(0 < Dimension);
+
+ template <typename Elements>
+ static inline void apply(
+ rtree_rstar_split_data<Elements, Box> & split_data,
+ Elements & elements,
+ size_t min_elems,
+ size_t max_elems,
+ Translator const& tr)
+ {
+ rtree_rstar_split_update_data<Value, Translator, Box, Dimension - 1>::
+ apply(split_data, elements, min_elems, max_elems, tr);
+
+ rtree_rstar_split_update_data_for_axis_and_corner<Value, Translator, Box, Dimension - 1, min_corner>::
+ apply(split_data, elements, min_elems, max_elems, tr);
+ rtree_rstar_split_update_data_for_axis_and_corner<Value, Translator, Box, Dimension - 1, max_corner>::
+ apply(split_data, elements, min_elems, max_elems, tr);
+ }
+};
+
+template <typename Value, typename Translator, typename Box>
+struct rtree_rstar_split_update_data<Value, Translator, Box, 1>
+{
+ template <typename Elements>
+ static inline void apply(
+ rtree_rstar_split_data<Elements, Box> & split_data,
+ Elements & elements,
+ size_t min_elems,
+ size_t max_elems,
+ Translator const& tr)
+ {
+ rtree_rstar_split_update_data_for_axis_and_corner<Value, Translator, Box, 0, min_corner>::
+ apply(split_data, elements, min_elems, max_elems, tr);
+ rtree_rstar_split_update_data_for_axis_and_corner<Value, Translator, Box, 0, max_corner>::
+ apply(split_data, elements, min_elems, max_elems, tr);
+ }
+};
+
+// split
+
+template <typename Value, typename Translator, typename Box>
+class rtree_rstar_split
+{
+ typedef typename index::detail::rtree_node<Value, Box, rtree_rstar_tag>::type node;
+ typedef typename index::detail::rtree_internal_node<Value, Box, rtree_rstar_tag>::type internal_node;
+ typedef typename index::detail::rtree_leaf<Value, Box, rtree_rstar_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)
+ {
+ typedef typename index::detail::rtree_elements_type<Node>::type elements_type;
+ typedef typename elements_type::value_type element_type;
+
+ elements_type & elements = index::detail::get_elements(n);
+
+ // get split data
+ rtree_rstar_split_data<elements_type, Box> split_data;
+ rtree_rstar_split_update_data<Value, Translator, Box, dimension>::
+ apply(split_data, elements, min_elems, max_elems, tr);
+
+ // create new node
+ node * right_node = rtree_create_node(Node());
+ elements_type & new_elems = index::detail::get_elements(boost::get<Node>(*right_node));
+
+ // update new node's elements
+ new_elems.resize(max_elems + 1 - split_data.choosen_median_index);
+ std::copy(
+ split_data.choosen_distribution.begin() + split_data.choosen_median_index,
+ split_data.choosen_distribution.end(),
+ new_elems.begin());
+
+ // update elements of the current node
+ elements.resize(split_data.choosen_median_index);
+ std::copy(
+ split_data.choosen_distribution.begin(),
+ split_data.choosen_distribution.begin() + split_data.choosen_median_index,
+ elements.begin());
+
+ if ( parent != 0 )
+ {
+ // update old node's box
+ parent->children[current_child_index].first = split_data.choosen_left_box;
+ // add new node to the parent's children
+ parent->children.push_back(std::make_pair(split_data.choosen_right_box, right_node));
+ }
+ 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(split_data.choosen_left_box, root));
+ boost::get<internal_node>(*new_root).children.push_back(std::make_pair(split_data.choosen_right_box, right_node));
+
+ root = new_root;
+ }
+ }
+};
+
+} // namespace visitors
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_RSTAR_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-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -41,18 +41,17 @@
typedef typename detail::rtree_internal_node<Value, box_type, rtree_rstar_tag>::type internal_node;
typedef typename detail::rtree_leaf<Value, box_type, rtree_rstar_tag>::type leaf;
- inline explicit rtree(size_t max_elems_per_node = 4, size_t min_elems_per_node = 2, translator_type const& translator = translator_type())
+ inline explicit rtree(size_t max_elems_per_node = 2, size_t min_elems_per_node = 1, translator_type const& translator = translator_type())
: m_values_count(0)
, m_max_elems_per_node(max_elems_per_node)
, m_min_elems_per_node(min_elems_per_node)
, m_root(0)
, m_translator(translator)
{
- if ( min_elems_per_node < 2 )
- min_elems_per_node = 2;
-
- // TODO: awulkiew - reconsider following assert
- assert(2 * m_min_elems_per_node <= m_max_elems_per_node);
+ if ( m_min_elems_per_node < 1 )
+ m_min_elems_per_node = 1;
+ if ( m_max_elems_per_node < 2 )
+ m_max_elems_per_node = 2;
m_root = detail::rtree_create_node(leaf());
}
@@ -82,9 +81,9 @@
}
template <typename Visitor>
- void apply_visitor(Visitor & visitor) const
+ typename Visitor::result_type apply_visitor(Visitor & visitor) const
{
- boost::apply_visitor(visitor, *m_root);
+ return boost::apply_visitor(visitor, *m_root);
}
translator_type const& get_translator() const
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/rtree_node.hpp 2011-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -153,6 +153,24 @@
return tr(el);
};
+// elements box
+
+template <typename Box, typename FwdIter, typename Translator>
+inline Box elements_box(FwdIter first, FwdIter last, Translator const& tr)
+{
+ assert(first != last);
+
+ Box result;
+
+ geometry::convert(index::detail::rtree_element_indexable(*first, tr), result);
+ ++first;
+
+ for ( ; first != last ; ++first )
+ geometry::expand(result, index::detail::rtree_element_indexable(*first, tr));
+
+ return result;
+}
+
// create leaf node
template <typename Value, typename Box, typename Tag>
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-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -27,10 +27,10 @@
template <typename Point>
struct rtree_gl_draw_point<Point, 2>
{
- static inline void apply(Point const& p)
+ static inline void apply(Point const& p, size_t level)
{
glBegin(GL_POINT);
- glVertex2f(geometry::get<0>(p), geometry::get<1>(p));
+ glVertex2f(geometry::get<0>(p), geometry::get<1>(p), level);
glEnd();
}
};
@@ -42,13 +42,13 @@
template <typename Box>
struct rtree_gl_draw_box<Box, 2>
{
- static inline void apply(Box const& b)
+ static inline void apply(Box const& b, size_t level)
{
glBegin(GL_LINE_LOOP);
- glVertex2f(geometry::get<min_corner, 0>(b), geometry::get<min_corner, 1>(b));
- glVertex2f(geometry::get<max_corner, 0>(b), geometry::get<min_corner, 1>(b));
- glVertex2f(geometry::get<max_corner, 0>(b), geometry::get<max_corner, 1>(b));
- glVertex2f(geometry::get<min_corner, 0>(b), geometry::get<max_corner, 1>(b));
+ 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);
glEnd();
}
};
@@ -64,9 +64,9 @@
typedef typename geometry::traits::point_type<Indexable>::type point_type;
static const size_t dimension = geometry::traits::dimension<point_type>::value;
- static inline void apply(Indexable const& i)
+ static inline void apply(Indexable const& i, size_t level)
{
- rtree_gl_draw_box<Indexable, dimension>::apply(i);
+ rtree_gl_draw_box<Indexable, dimension>::apply(i, level);
}
};
@@ -75,9 +75,9 @@
{
static const size_t dimension = geometry::traits::dimension<Indexable>::value;
- static inline void apply(std::ostream &os, Indexable const& i)
+ static inline void apply(Indexable const& i, size_t level)
{
- rtree_gl_draw_point<Indexable, dimension>::apply(i);
+ rtree_gl_draw_point<Indexable, dimension>::apply(i, level);
}
};
@@ -86,12 +86,12 @@
namespace detail {
template <typename Indexable>
-inline void rtree_gl_draw_indexable(Indexable const& i)
+inline void rtree_gl_draw_indexable(Indexable const& i, size_t level)
{
dispatch::rtree_gl_draw_indexable<
Indexable,
typename geometry::traits::tag<Indexable>::type
- >::apply(i);
+ >::apply(i, level);
}
} // namespace detail
@@ -128,7 +128,7 @@
for (typename children_type::const_iterator it = n.children.begin();
it != n.children.end(); ++it)
{
- detail::rtree_gl_draw_indexable(it->first);
+ detail::rtree_gl_draw_indexable(it->first, level);
}
size_t level_backup = level;
@@ -152,7 +152,7 @@
for (typename values_type::const_iterator it = n.values.begin();
it != n.values.end(); ++it)
{
- detail::rtree_gl_draw_indexable(tr(*it));
+ detail::rtree_gl_draw_indexable(tr(*it), level);
}
}
Modified: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp (original)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/print.hpp 2011-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -128,22 +128,15 @@
{
typedef typename internal_node::children_type children_type;
- os << " --> Node --------" << std::endl;
- os << " Address: " << this << std::endl;
- os << " Level: " << level << std::endl;
- os << " Children: " << n.children.size() << std::endl;
- os << " | ";
-
+ spaces(level) << "INTERNAL NODE - L:" << level << " Ch:" << n.children.size() << " @:" << &n << '\n';
+
for (typename children_type::const_iterator it = n.children.begin();
it != n.children.end(); ++it)
{
+ spaces(level);
detail::rtree_print_indexable(os, it->first);
- os << " | ";
+ os << " ->" << it->second << '\n';
}
- os << std::endl;
- os << " --< Node --------" << std::endl;
-
- os << " Children: " << std::endl;
size_t level_backup = level;
++level;
@@ -161,17 +154,21 @@
{
typedef typename leaf::values_type values_type;
- os << "\t" << " --> Leaf --------" << std::endl;
- os << "\t" << " Values: " << n.values.size() << std::endl;
+ spaces(level) << "LEAF - L:" << level << " V:" << n.values.size() << " @:" << &n << '\n';
for (typename values_type::const_iterator it = n.values.begin();
it != n.values.end(); ++it)
{
- os << "\t" << " | ";
+ spaces(level);
detail::rtree_print_indexable(os, tr(*it));
- os << " | " << std::endl;;
+ os << '\n';
}
- os << "\t" << " --< Leaf --------" << std::endl;
+ }
+ inline std::ostream & spaces(size_t level)
+ {
+ for ( size_t i = 0 ; i < 2 * level ; ++i )
+ os << ' ';
+ return os;
}
std::ostream & os;
Added: sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_are_boxes_ok.hpp
==============================================================================
--- (empty file)
+++ sandbox-branches/geometry/index_080_new/boost/geometry/extensions/index/rtree/visitors/rtree_are_boxes_ok.hpp 2011-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -0,0 +1,103 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Boost.Index - R-tree boxes checking 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_RTREE_ARE_BOXES_OK_HPP
+#define BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_ARE_BOXES_OK_HPP
+
+#include <boost/geometry/algorithms//equals.hpp>
+#include <boost/geometry/extensions/index/rtree/rtree_node.hpp>
+
+namespace boost { namespace geometry { namespace index {
+
+namespace visitors {
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+class rtree_are_boxes_ok : public boost::static_visitor<bool>
+{
+ typedef typename index::detail::rtree_internal_node<Value, Box, Tag>::type internal_node;
+ typedef typename index::detail::rtree_leaf<Value, Box, Tag>::type leaf;
+
+public:
+ inline rtree_are_boxes_ok(Translator const& tr)
+ : m_tr(tr), m_is_root(true)
+ {}
+
+ inline bool operator()(internal_node const& n)
+ {
+ if (n.children.empty())
+ return false;
+
+ Box box_bckup = m_box;
+ bool is_root_bckup = m_is_root;
+
+ m_is_root = false;
+
+ for ( internal_node::children_type::const_iterator it = n.children.begin();
+ it != n.children.end() ; ++it)
+ {
+ m_box = it->first;
+
+ if ( false == boost::apply_visitor(*this, *it->second) )
+ return false;
+ }
+
+ m_box = box_bckup;
+ m_is_root = is_root_bckup;
+
+ Box result;
+ geometry::convert(n.children.front().first, result);
+ for(internal_node::children_type::const_iterator it = n.children.begin() + 1;
+ it != n.children.end() ; ++it)
+ {
+ geometry::expand(result, it->first);
+ }
+
+ return m_is_root || geometry::equals(result, m_box);
+ }
+
+ inline bool operator()(leaf const& n)
+ {
+ if (n.values.empty())
+ return false;
+
+ Box result;
+ geometry::convert(m_tr(n.values.front()), result);
+ for(leaf::values_type::const_iterator it = n.values.begin() + 1;
+ it != n.values.end() ; ++it)
+ {
+ geometry::expand(result, m_tr(*it));
+ }
+
+ return m_is_root || geometry::equals(result, m_box);
+ }
+
+private:
+ Translator const& m_tr;
+ Box m_box;
+ bool m_is_root;
+};
+
+} // namespace visitors
+
+template <typename Value, typename Translator, typename Box, typename Tag>
+bool rtree_are_boxes_ok(rtree<Value, Translator, Box, Tag> const& tree)
+{
+ typedef rtree<Value, Translator, Box, Tag> rt;
+ visitors::rtree_are_boxes_ok<
+ typename rt::value_type,
+ typename rt::translator_type,
+ typename rt::box_type,
+ Tag> v(tree.get_translator());
+
+ return tree.apply_visitor(v);
+}
+
+}}} // namespace boost::geometry::index
+
+#endif // BOOST_GEOMETRY_EXTENSIONS_INDEX_RTREE_VISITORS_RTREE_ARE_BOXES_OK_HPP
Modified: sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp
==============================================================================
--- sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp (original)
+++ sandbox-branches/geometry/index_080_new/tests/additional_glut_vis.cpp 2011-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -4,10 +4,12 @@
#include <boost/geometry/extensions/index/rtree/rtree.hpp>
#include <boost/geometry/extensions/index/rtree/visitors/gl_draw.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/print.hpp>
+#include <boost/geometry/extensions/index/rtree/visitors/rtree_are_boxes_ok.hpp>
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;
+boost::geometry::index::rtree<B> t(2, 1);
void render_scene(void)
{
@@ -30,8 +32,8 @@
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
gluLookAt(
- 5.0f, 5.0f, 15.0f,
- 5.0f, 5.0f, -1.0f,
+ 150.0f, 150.0f, 150.0f,
+ 50.0f, 50.0f, -1.0f,
0.0f, 1.0f, 0.0f);
}
@@ -39,12 +41,21 @@
{
if ( state == GLUT_DOWN )
{
- float x = ( rand() % 10000 ) / 1000.0f;
- float y = ( rand() % 10000 ) / 1000.0f;
- float w = ( rand() % 10000 ) / 100000.0f;
- float h = ( rand() % 10000 ) / 100000.0f;
-
- boost::geometry::index::insert(t, B(P(x - w, y - h),P(x + w, y + h)));
+ float x = ( rand() % 100 );
+ float y = ( rand() % 100 );
+ float w = ( rand() % 2 ) + 1;
+ float h = ( rand() % 2 ) + 1;
+
+ B b(P(x - w, y - h),P(x + w, y + h));
+
+ boost::geometry::index::insert(t, b);
+
+ std::cout << "\n\n\n" << t << "\n\n";
+
+ std::cout << "inserted: ";
+ boost::geometry::index::visitors::detail::rtree_print_indexable(std::cout, b);
+ std::cout << '\n';
+ std::cout << ( boost::geometry::index::rtree_are_boxes_ok(t) ? "boxes OK" : "WRONG BOXES!" );
glutPostRedisplay();
}
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-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -29,10 +29,10 @@
std::vector<B> v(n);
for ( size_t i = 0 ; i < n ; ++i )
{
- float x = ( rand() % 10000 ) / 1000.0f;
- float y = ( rand() % 10000 ) / 1000.0f;
- float w = ( rand() % 10000 ) / 100000.0f;
- float h = ( rand() % 10000 ) / 100000.0f;
+ float x = float( rand() % 1000 );
+ float y = float( rand() % 1000 );
+ float w = float( rand() % 10 ) / 10.0f;
+ float h = float( rand() % 10 ) / 10.0f;
v[i] = B(P(x - w, y - h),P(x + w, y + h));
}
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-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -8,6 +8,19 @@
tests_rtree_native_hpp();
tests_rtree_filters_hpp();
+ /*namespace g = boost::geometry;
+ typedef g::model::point<float, 2, g::cs::cartesian> P;
+ typedef g::model::box<P> B;
+
+ g::index::rtree<B> tree(4, 2);
+ g::index::insert(tree, B(P(1, 6),P(6, 19)));
+ g::index::insert(tree, B(P(10, 1),P(18, 18)));
+ g::index::insert(tree, B(P(22, 6),P(27, 20)));
+ g::index::insert(tree, B(P(29, 2),P(34, 18)));
+ g::index::insert(tree, B(P(35, 3),P(39, 19)));
+
+ std::cout << tree;*/
+
#ifdef _MSC_VER
std::cin.get();
#endif
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-03-26 22:21:45 EDT (Sat, 26 Mar 2011)
@@ -17,7 +17,24 @@
{
std::cout << "tests/rtree_native.hpp\n";
- std::cout << "Boxes\n";
+ std::cout << "Boxes3d\n";
+ {
+ 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::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)));
+ boost::geometry::index::insert(t, B(P(6, 6, 6), P(7, 7, 7)));
+ boost::geometry::index::insert(t, B(P(8, 8, 8), P(9, 9, 9)));
+ std::cerr << t;
+ }
+
+ std::cout << "-------------------------------------------------\n";
+ std::cout << "-------------------------------------------------\n";
+
+ std::cout << "Boxes2d\n";
{
typedef boost::geometry::model::point<float, 2, boost::geometry::cs::cartesian> P;
typedef boost::geometry::model::box<P> B;