清晰有效的3D范围树实现 [英] Clear And Efficient 3D Range Tree Implementation
问题描述
我将如何使用以下结构：
让我们说一个数组（让我们称之为 queryArr ）对象（〜10,000个对象）每个对象有3个参数（x，y，z）我有另一个非常大的数组（让我们称之为 totalArr ）的对象（> 5,000,000个对象）。
我想在这里做的是给定 queryArr 的元素，找到最相似的（或相同的元素在 totalArr ）在某些情况下，在 totalArr 中将有一个具有相同参数的对象，但在大多数情况下，不会有一个对象相同的参数。
所以，我将搜索（x + 10，y + 10，z + 10）之间的所有值。和（x-10，y-10，z-10）。如果它不产生任何结果，我将x，y，z乘以2，然后重试，直到产生一些结果。
最简单的方法是一个天真的搜索方法，它将具有 O（N * M）的复杂度（N = queryArr的大小，M = sie of totalArr）但是这种方法是非常缓慢而笨拙的。
我认为范围树是要走的路，但是我从来没有实现过我自己，我不太明白范围树如何在大于2的维度上工作。任何人都知道范围树的良好实现？我相信如果我可以有一个源代码，我将能够了解他们如何真正的工作。
顺便说一句，如果你认为，有一个更好的结构范围树的这个任务，让我知道我是开放的建议。 （我已经考虑过kd-Trees和Interval树）
谢谢，
我刚读了维基百科的文章。让我看看我是否可以编写一个n维范围的树。因为在三维中值得做的任何事情都值得在n中进行。
因此，n维范围树的基本部分是它可以递归地定义为较低的一些属性类可以使用相对通用的值类型进行处理。
专门设计 element_properties< T> 以设置任何n维值的标量类型，并专门为 get< i>（T const& / code>以获得n维值的 i 维度。
#include< memory>
#include< cstddef>
#include< vector>
#include< iostream>
#include< algorithm>
#include< string>
#include< sstream>
void Assert（bool test）{
if（！test）
{
std :: cout<<< 断言失败< std :: endl;
exit（-1）;
}
}
template< typename ... Args>
struct打印{
static void Do（Args ... args）{}
};
template< typename Arg，typename ... Tail>
struct Print< Arg，Tail ...> {
static void Do（Arg arg，Tail ... args）{
std :: cout<<<参考
打印< Tail ...> :: Do（args ...）;
}
};
template< typename ... Args>
void Debug（Args ... args）{
std :: cout<<< DEBUG：[;
打印< Args ...> :: Do（args ...）;
std :: cout<<< ] \\\
;
}
模板< 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）;
模板< 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（右））;
}
};
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<<得到< 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））;
}
模板< 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> >子树
T值;
template< size_t n，typename Func>
void walk（Func f）const {
if（n == dim&&！left&&right; 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; $ 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 {
//发现它！
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 *>正确的道路;
find_path（left，left_path）;
find_path（right，right_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）
{
调试（different：，printer（）（（* it1） - > value），，，printer（）（（* it2） - > value））;
break;
}
调试（相同，printer（）（（* it1） - >值），，，printer（）（（* it2） - > ））;
}
//删除相同的前缀：
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（）;
调试（It is：，printer（）（（* it） - > value））;
} else {
调试（没有权利的孩子，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（）;
调试（It is：，printer（）（（* it） - > value））;
} else {
调试（没有左边的孩子：，printer（）（（* it） - > value））;
if（sorter（）（（* it） - > value，left）|| sorter（）（right，（* it） - > value））{
Debug（printer右），<，printer（）（（* it） - > value），so erased）;
* it = 0;
}
}
}
left_path.insert（left_path.end（），right_path.begin（），right_path.end（））;
//删除duds和重复：
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>剩下;
std :: unique_ptr< tree_node>对;
// 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） ）;
迭代器mid = middle（begin，end）;
Assert（begin！= end）;
如果（开始+1！=结束）{//不是一个叶子
调试（不是叶子的水平，dim）;
++ mid; // so * mid是左子树中的最后一个元素
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>根;
};
//使代码更容易：
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 {}; //这里可能有一些stub函数
template< size_t n，typename Func>
void walk（func f）{}
};
int main（）{
typedef std :: vector< int> vector_type;
std :: vector< vector_type>测试;
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<<< 走淡淡2：;
auto print_node = []（vector_type const& v）{std :: cout < （< v [0]<，< v [1]<）; };
tree.walk< 2>（print_node）;
std :: cout<<< \\\
Walking dim 1：;
tree.walk< 1>（print_node）;
std :: cout<<< \\\
;
std :: cout<<< 范围搜索从{3,3}到{10,10} \\\
;
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& ）;
}
}
这是非常接近于一个n维范围树。 0维树自然不含任何东西。
现在已经添加了要搜索的基本功能（一次一个维度）。您可以手动将递归更改为较低的维度，或者将其递减，以便 range_search 始终返回1级 tree_node * s 。
I'm working on this project where I have to search for objects in 3d space, and efficiency is a huge concern, I think Range Tree is perfect for what I'm trying to do, Interval Tree would also work but I'm not going to delete anything from the tree, once I add every object in 3D space, I'll only use the structure to do a search.
Here's how I'm going to use the structure:
Let say that I have an array(let's call it queryArr) of objects (~ 10,000 objects) each objects have 3 parameter (x,y,z) I have another very large array(let's call it totalArr) of objects ( > 5,000,000 objects).
What I'm trying to do here is given element of queryArr, find the most similar(or the same element in totalArr) In some cases there will be an object with the same parameters in totalArr, but in most cases, there won't be an object with same parameters.
So, I'll search all the values in between (x+10,y+10,z+10) and (x-10,y-10,z-10). If it doesn't yield any result, I'll multiply x,y,z by 2 and try again until it yields some results.
The simplest way of doing this is a naive search method, which will have complexity of O(N*M) (N = size of queryArr, M = sie of totalArr) but this method is incredibly slow and dumb.
I think Range Tree's is the way to go, but I have never implemented one myself and I don't quite understand how the range tree works on dimensions bigger than 2. So does anyone know a good implementation of the range trees? I believe if I can have a source code, I'll be able to understand how they really work.
By the way if you think, there is a better structure than Range Tree for this task, let me know I'm open to suggestions. (I have already considered kd-Trees and Interval trees)
Thanks,
I just read the wikipedia article. Lets see if I can write an n dimensional range tree. Because anything worth doing in 3 dimensions is worth doing in n.
So the basic part of an n-dimensional range tree is that it can be recursively defined in terms of lower dimensional range trees.
Some property classes to work with relatively generic value types. Specialize element_properties<T> to set the scalar type of whatever your n-dimensional value is, and specialize get<i>(T const&) to get the ith dimension of your n-dimensional value.
#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 );
}
}
which is pretty damn close to an n-dimensional range tree. The 0 dimension tree naturally contains nothing.
Basic facilities to search (in one dimension at a time) have been added now. You can manually do the recursions into lower dimensions, or it up so that the range_search always returns level 1 tree_node*s.
这篇关于清晰有效的3D范围树实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
