Яркая и эффективная реализация дерева 3D-диапазона

Question

Я работаю над этим проектом, где мне нужно искать объекты в 3d-пространстве, а эффективность - огромная проблема, я думаю Range Tree идеально подходит для того, что я пытаюсь do, Interval Tree также будет работать, но я не собираюсь ничего удалять из дерева, как только я добавлю каждый объект в 3D-пространство, я буду использовать эту структуру только для выполнения поиска.

Вот как я буду использовать структуру:

Пусть говорят, что у меня есть массив (назовем его queryArr) объектов (~ 10000 объектов) каждый объекты имеют 3 параметра (х, у , 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 = size of queryArr, M = sie of totalArr), но этот метод невероятно медленный и немой.

Я думаю, что Range Tree - это путь, но я никогда не реализовал его сам, и я не совсем понимаю, как дерево диапазона работает с размерами больше 2. Так кто-нибудь знает хорошую реализацию деревьев диапазона ? Я считаю, что если у меня есть исходный код, я смогу понять, как они действительно работают.

Кстати, если вы считаете, что для этой задачи есть лучшая структура, чем Дерево древостоев, дайте мне знать, что я открыт для предложений. (Я уже рассмотрел К.Д.-деревья и деревья Interval)

Спасибо,

Answer 1

Я только что прочитал статью Википедии. Давайте посмотрим, могу ли я написать n-мерное дерево размеров. Потому что все, что стоит делать в 3 измерениях, стоит делать в 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.