Я разрабатываю структуру, которая похожа на двоичное дерево, но обобщена по размерам, поэтому вы можете установить, является ли это двоичным деревом, quadtree, octree и т. Д., Установив параметр измерения во время инициализации.Поиск соседних узлов в дереве
Вот определение этого:
template <uint Dimension, typename StateType>
class NDTree {
public:
std::array<NDTree*, cexp::pow(2, Dimension)> * nodes;
NDTree * parent;
StateType state;
char position; //position in parents node list
bool leaf;
NDTree const &operator[](const int i) const
{
return (*(*nodes)[i]);
}
NDTree &operator[](const int i)
{
return (*(*nodes)[i]);
}
}
Таким образом, для инициализации это- я установить размер, а затем разделить. Я иду на квадрадерево глубины 2 для иллюстрации здесь:
const uint Dimension = 2;
NDTree<Dimension, char> tree;
tree.subdivide();
for(int i=0; i<tree.size(); i++)
tree[i].subdivide();
for(int y=0; y<cexp::pow(2, Dimension); y++) {
for(int x=0; x<cexp::pow(2, Dimension); x++) {
tree[y][x].state = ((y)*10)+(x);
}
}
std::cout << tree << std::endl;
Это приведет к квадрадерево, состояние каждого из значений инициализируются [0-4] [0-4].
([{0}{1}{2}{3}][{10}{11}{12}{13}][{20}{21}{22}{23}][{30}{31}{32}{33}])
У меня возникли проблемы с поиском соседних узлов из любой части. То, что ему нужно сделать, это принять направление, а затем (при необходимости) пересечь дерево, если направление уходит с края родительского узла (например, если бы мы были в правом нижнем углу квадрата квадрата, и нам нужно было получить часть справа от него). Мой алгоритм возвращает фиктивные значения.
Вот как массивы раскладывают:
А вот структуры необходимо знать для этого:
Это просто держит направление для элементов.
Это держит направление и должно ли оно идти глубже.
template <uint Dimension>
struct TraversalHelper {
std::array<orientation, Dimension> way;
bool deeper;
};
node_orientation_table содержит ориентации в структуре. Таким образом, в 2d, 0 0 относится к верхнему левому квадрату (или к левому квадрату). [[LEFT, LEFT], [RIGHT, LEFT], [влево, вправо], [RIGHT, RIGHT]]
И функция getPositionFromOrientation бы влево, влево и вернуть 0. Это только в основном противоположна node_orientation_table выше.
TraversalHelper<Dimension> traverse(const std::array<orientation, Dimension> dir, const std::array<orientation, Dimension> cmp) const
{
TraversalHelper<Dimension> depth;
for(uint d=0; d < Dimension; ++d) {
switch(dir[d]) {
case CENTER:
depth.way[d] = CENTER;
goto cont;
case LEFT:
if(cmp[d] == RIGHT) {
depth.way[d] = LEFT;
} else {
depth.way[d] = RIGHT;
depth.deeper = true;
}
break;
case RIGHT:
if(cmp[d] == LEFT) {
depth.way[d] = RIGHT;
} else {
depth.way[d] = LEFT;
depth.deeper = true;
}
break;
}
cont:
continue;
}
return depth;
}
std::array<orientation, Dimension> uncenter(const std::array<orientation, Dimension> dir, const std::array<orientation, Dimension> cmp) const
{
std::array<orientation, Dimension> way;
for(uint d=0; d < Dimension; ++d)
way[d] = (dir[d] == CENTER) ? cmp[d] : dir[d];
return way;
}
NDTree * getAdjacentNode(const std::array<orientation, Dimension> direction) const
{
//our first traversal pass
TraversalHelper<Dimension> pass = traverse(direction, node_orientation_table[position]);
//if we are lucky the direction results in one of our siblings
if(!pass.deeper)
return (*(*parent).nodes)[getPositionFromOrientation<Dimension>(pass.way)];
std::vector<std::array<orientation, Dimension>> up; //holds our directions for going up the tree
std::vector<std::array<orientation, Dimension>> down; //holds our directions for going down
NDTree<Dimension, StateType> * tp = parent; //tp is our tree pointer
up.push_back(pass.way); //initialize with our first pass we did above
while(true) {
//continue going up as long as it takes, baby
pass = traverse(up.back(), node_orientation_table[tp->position]);
std::cout << pass.way << " :: " << uncenter(pass.way, node_orientation_table[tp->position]) << std::endl;
if(!pass.deeper) //we've reached necessary top
break;
up.push_back(pass.way);
//if we don't have any parent we must explode upwards
if(tp->parent == nullptr)
tp->reverseBirth(tp->position);
tp = tp->parent;
}
//line break ups and downs
std::cout << std::endl;
//traverse upwards combining the matrices to get our actual position in cube
tp = const_cast<NDTree *>(this);
for(int i=1; i<up.size(); i++) {
std::cout << up[i] << " :: " << uncenter(up[i], node_orientation_table[tp->position]) << std::endl;
down.push_back(uncenter(up[i], node_orientation_table[tp->parent->position]));
tp = tp->parent;
}
//make our way back down (tp is still set to upmost parent from above)
for(const auto & i : down) {
int pos = 0; //we need to get the position from an orientation list
for(int d=0; d<i.size(); d++)
if(i[d] == RIGHT)
pos += cexp::pow(2, d); //consider left as 0 and right as 1 << dimension
//grab the child of treepointer via position we just calculated
tp = (*(*tp).nodes)[pos];
}
return tp;
}
В качестве примера этого:
std::array<orientation, Dimension> direction;
direction[0] = LEFT; //x
direction[1] = CENTER; //y
NDTree<Dimension> * result = tree[3][0]->getAdjacentNode(direction);
Это должно захватить верхний правый квадрат внутри нижнего левого квадрата, например, tree[2][1], который будет иметь значение 21, если мы прочитаем его состояние. Что работает с моего последнего редактирования (алгоритм изменен). Тем не менее, однако, многие запросы не возвращают правильные результаты.
//Should return tree[3][1], instead it gives back tree[2][3]
NDTree<Dimension, char> * result = tree[1][2].getAdjacentNode({ RIGHT, RIGHT });
//Should return tree[1][3], instead it gives back tree[0][3]
NDTree<Dimension, char> * result = tree[3][0].getAdjacentNode({ RIGHT, LEFT });
Есть несколько примеров неправильного поведения, таких как дерево [0] [0] (влево, влево), но и многие другие правильно работать.
Here - это папка git repo, с которой я работаю. Просто запустите g++ -std=c++11 main.cpp из этого каталога, если это необходимо.
Я не могу скомпилировать. Он ищет 'gmp.h'. Можете ли вы сказать все библиотеки, которые используете? – Gene
Зайдите в папку test/treet и скомпилируйте ее оттуда. Корневая папка использует другой код вне вопроса. – jett
Спасибо. Он компилируется здесь просто отлично. Это довольно барочная реализация. Много избыточной информации. Вы уверены, что не хотите быть более консервативным? Пространство обычно является проблемой в реалистичных приложениях 2^n-дерева. – Gene