Четкая и эффективная реализация 3D Range Tree
Я работаю над этим проектом, где мне нужно искать объекты в трехмерном пространстве, и эффективность - огромная проблема, я думаю, что Range Tree идеально подходит для того, что я пытаюсь сделать, Interval Tree также будет работать, но я не Я собираюсь удалить что-нибудь из дерева, как только я добавлю каждый объект в трехмерное пространство, я буду использовать структуру только для поиска.
Вот как я собираюсь использовать структуру:
Допустим, у меня есть массив (назовем это queryArr) объектов (~ 10000 объектов), у каждого объекта есть 3 параметра (x,y,z). У меня есть еще один очень большой массив (назовем его totalArr) объектов ( > 5 000000 объектов).).
Здесь я пытаюсь сделать заданный элемент queryArr, найти наиболее похожий (или тот же элемент в totalArr). В некоторых случаях в totalArr будет объект с такими же параметрами, но в большинстве случаев не будет быть объектом с такими же параметрами.
Итак, я буду искать все значения между (x+10,y+10,z+10) а также (x-10,y-10,z-10), Если это не даст никакого результата, я умножу x, y, z на 2 и попробую еще раз, пока не получу некоторые результаты.
Самый простой способ сделать это - наивный метод поиска, который будет иметь сложность O(N*M) (N = size of queryArr, M = sie of totalArr) но этот метод невероятно медленный и тупой.
Я думаю, что Range Tree - это путь, но я никогда не реализовывал его сам, и я не совсем понимаю, как дерево диапазонов работает на измерениях больше 2. Так кто-нибудь знает хорошую реализацию деревьев диапазонов? Я верю, что если у меня будет исходный код, я смогу понять, как они на самом деле работают.
Кстати, если вы думаете, что для этой задачи есть лучшая структура, чем Range Tree, дайте мне знать, что я открыт для предложений. (Я уже рассмотрел kd-деревья и интервальные деревья)
Спасибо,
1 ответ
Я только что прочитал статью в Википедии. Посмотрим, смогу ли я написать дерево n-мерного диапазона. Потому что все, что стоит делать в трех измерениях, стоит делать на русском.
Таким образом, основная часть n-мерного дерева диапазонов состоит в том, что оно может быть рекурсивно определено в терминах деревьев более низких измерений.
Некоторые классы свойств для работы с относительно общими типами значений. специализироваться element_properties<T> установить скалярный тип любого вашего n-мерного значения и специализировать get<i>(T const&) чтобы получить iй размер вашего n-мерного значения.
#include <memory>
#include <cstddef>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
void Assert(bool test) {
if (!test)
{
std::cout << "Assert failed" << std::endl;
exit(-1);
}
}
template<typename... Args>
struct Print {
static void Do(Args... args) {}
};
template<typename Arg, typename... Tail>
struct Print<Arg, Tail...> {
static void Do(Arg arg, Tail... args) {
std::cout << arg;
Print<Tail...>::Do(args...);
}
};
template<typename... Args>
void Debug(Args... args) {
std::cout << "DEBUG:[";
Print<Args...>::Do(args...);
std::cout << "]\n";
}
template<typename T>
struct element_properties {
typedef typename T::value_type value_type;
};
template<>
struct element_properties<int> {
typedef int value_type;
};
template<size_t d, typename T>
typename element_properties<T>::value_type get( T const & t );
template<size_t d>
typename element_properties<int>::value_type get( int i ) { return i; }
template<size_t d, typename U, typename A>
typename element_properties<std::vector<U,A>>::value_type get( std::vector<U,A> const& v) {
return v[d];
}
template<typename T, size_t dim, typename Order = std::less< typename element_properties<T>::value_type> >
struct range_tree {
typedef typename element_properties<T>::value_type value_type;
struct sorter {
bool operator()( T const& left, T const& right ) const {
return Order()( get<dim-1>(left), get<dim-1>(right) );
}
};
struct printer {
std::string operator()( T const& t ) const {
std::string retval = "[ ";
retval += print_elements( t );
retval += "]";
return retval;
}
std::string print_elements( T const& t ) const {
std::stringstream ss;
typedef typename range_tree<T, dim-1, Order>::printer next_printer;
ss << next_printer().print_elements(t);
ss << get<dim-1>(t) << " ";
return ss.str();
}
};
template<typename Iterator>
range_tree( Iterator begin, Iterator end ) {
std::sort( begin, end, sorter() );
root.reset( new tree_node( begin, end ) );
}
template<size_t n, typename Func>
void walk(Func f) const {
if (root) root->walk<n>(f);
}
template<size_t n, typename Func>
void walk(Func f) {
if (root) root->walk<n>(f);
}
struct tree_node {
std::unique_ptr< range_tree<T, dim-1, Order> > subtree;
T value;
template<size_t n, typename Func>
void walk(Func f) const {
if (n==dim && !left && !right)
f(value);
if (left)
left->walk<n>(f);
if (right)
right->walk<n>(f);
if (subtree)
subtree->walk<n>(f);
}
template<size_t n, typename Func>
void walk(Func f) {
if (n==dim && !left && !right)
f(value);
if (left)
left->walk<n>(f);
if (right)
right->walk<n>(f);
if (subtree)
subtree->walk<n>(f);
}
void find_path( T const& t, std::vector< tree_node const* >& vec ) {
vec.push_back(this);
if ( sorter()(t, value) ) {
if (left)
left->find_path(t, vec);
} else if (sorter()(value, t)) {
if (right)
right->find_path(t, vec);
} else {
// found it!
return;
}
}
std::vector< tree_node const* > range_search( T const& left, T const& right )
{
std::vector<tree_node const*> left_path;
std::vector<tree_node const*> right_path;
find_path( left, left_path );
find_path( right, right_path );
// erase common path:
{
auto it1 = left_path.begin();
auto it2 = right_path.begin();
for( ; it1 != left_path.end() && it2 != right_path.end(); ++it1, ++it2) {
if (*it1 != *it2)
{
Debug( "Different: ", printer()( (*it1)->value ), ", ", printer()( (*it2)->value ) );
break;
}
Debug( "Identical: ", printer()( (*it1)->value ), ", ", printer()( (*it2)->value ) );
}
// remove identical prefixes:
if (it2 == right_path.end() && it2 != right_path.begin())
--it2;
if (it1 == left_path.end() && it1 != left_path.begin())
--it1;
right_path.erase( right_path.begin(), it2 );
left_path.erase( left_path.begin(), it1 );
}
for (auto it = left_path.begin(); it != left_path.end(); ++it) {
if (*it && (*it)->right) {
Debug( "Has right child: ", printer()( (*it)->value ) );
*it = (*it)->right.get();
Debug( "It is: ", printer()( (*it)->value ) );
} else {
Debug( "Has no right child: ", printer()( (*it)->value ) );
if ( sorter()( (*it)->value, left) || sorter()( right, (*it)->value) ) {
Debug( printer()( (*it)->value ), "<", printer()( left ), " so erased" );
*it = 0;
}
}
}
for (auto it = right_path.begin(); it != right_path.end(); ++it) {
if (*it && (*it)->left) {
Debug( "Has left child: ", printer()( (*it)->value ) );
*it = (*it)->left.get();
Debug( "It is: ", printer()( (*it)->value ) );
} else {
Debug( "Has no left child: ", printer()( (*it)->value ) );
if ( sorter()( (*it)->value, left) || sorter()( right, (*it)->value) ) {
Debug( printer()( right ), "<", printer()( (*it)->value ), " so erased" );
*it = 0;
}
}
}
left_path.insert( left_path.end(), right_path.begin(), right_path.end() );
// remove duds and duplicates:
auto highwater = std::remove_if( left_path.begin(), left_path.end(), []( tree_node const* n) { return n==0; } );
std::sort( left_path.begin(), highwater );
left_path.erase( std::unique( left_path.begin(), highwater ), left_path.end() );
return left_path;
}
std::unique_ptr<tree_node> left;
std::unique_ptr<tree_node> right;
// rounds down:
template<typename Iterator>
static Iterator middle( Iterator begin, Iterator end ) {
return (end-begin-1)/2 + begin ;
}
template<typename Iterator>
tree_node( Iterator begin, Iterator end ):value(*middle(begin,end)) {
Debug( "Inserted ", get<dim-1>(value), " at level ", dim );
Iterator mid = middle(begin,end);
Assert( begin != end );
if (begin +1 != end) { // not a leaf
Debug( "Not a leaf at level ", dim );
++mid; // so *mid was the last element in the left sub tree
Assert(mid!=begin);
Assert(mid!=end);
left.reset( new tree_node( begin, mid ) );
right.reset( new tree_node( mid, end ) );
} else {
Debug( "Leaf at level ", dim );
}
if (dim > 0) {
subtree.reset( new range_tree<T, dim-1, Order>( begin, end ) );
}
}
};
std::unique_ptr<tree_node> root;
};
// makes the code above a tad easier:
template<typename T, typename Order >
struct range_tree< T, 0, Order > {
typedef typename element_properties<T>::value_type value_type;
struct printer { template<typename Unused>std::string print_elements(Unused const&) {return std::string();} };
range_tree(...) {};
struct tree_node {}; // maybe some stub functions in here
template<size_t n, typename Func>
void walk(Func f) {}
};
int main() {
typedef std::vector<int> vector_type;
std::vector<vector_type> test;
test.push_back( vector_type{5,2} );
test.push_back( vector_type{2,3} );
range_tree< vector_type, 2 > tree( test.begin(), test.end() );
std::cout << "Walking dim 2:";
auto print_node = [](vector_type const& v){ std::cout << "(" << v[0] << "," << v[1] << ")"; };
tree.walk<2>( print_node );
std::cout << "\nWalking dim 1:";
tree.walk<1>( print_node );
std::cout << "\n";
std::cout << "Range search from {3,3} to {10,10}\n";
auto nodes = tree.root->range_search( vector_type{3,3}, vector_type{10,10} );
for (auto it = nodes.begin(); it != nodes.end(); ++it)
{
(*it)->walk<2>( print_node );
}
}
что чертовски близко к n-мерному дереву диапазонов. Дерево 0 измерений естественно не содержит ничего.
Основные возможности для поиска (в одном измерении за один раз) были добавлены сейчас. Вы можете вручную выполнить рекурсии в более низкие измерения или сделать так, чтобы range_search всегда возвращает уровень 1 tree_node*s.