от рекурсии по дереву до итеративной по массиву (kd-tree Nearest Neighbor) - PullRequest
Новая
       48

от рекурсии по дереву до итеративной по массиву (kd-tree Nearest Neighbor)

3 голосов
/ 29 марта 2011

У меня есть рекурсивная функция (для дерева), и мне нужно, чтобы она работала без рекурсии и представляла дерево как неявную структуру данных (массив).

Вот функция: 

kdnode* kdSearchNN(kdnode* here, punto point, kdnode* best=NULL, int depth=0)
{   
if(here == NULL)
    return best;

if(best == NULL)
    best = here;

if(distance(here, point) < distance(best, point))
    best = here;

int axis = depth % 3;

kdnode* near_child = here->left;
kdnode* away_child = here->right;

if(point.xyz[axis] > here->xyz[axis])
{
    near_child = here->right;
    away_child = here->left;
}

best = kdSearchNN(near_child, point, best, depth + 1);

if(distance(here, point) < distance(best, point))
{
    best = kdSearchNN(away_child, point, best, depth + 1);
}

return best;
}

Я использую эти свойства для представления дерева в виде массива: 

root: 0
left: index*2+1
right: index*2+2

enter image description here

Вот что я сделал: 

punto* kdSearchNN_array(punto *tree_array, int here, punto point, punto* best=NULL, int depth=0, float dim=0)
{
if (here > dim) {
    return best;
}

if(best == NULL)
    best = &tree_array[here];

if(distance(&tree_array[here], point) < distance(best, point))
    best = &tree_array[here];

int axis = depth % 3;

int near_child = (here*2)+1;
int away_child = (here*2)+2;

if(point.xyz[axis] > tree_array[here].xyz[axis])
{
    near_child = (here*2)+2;
    away_child = (here*2)+1;
}

best = kdSearchNN_array(tree_array, near_child, point, best, depth + 1, dim);

if(distance(&tree_array[here], point) < distance(best, point))
{
    best = kdSearchNN_array(tree_array, away_child, point, best, depth + 1, dim);
}

return best;
}

Теперь последний шаг - избавиться от рекурсии, но я не могу найти какой-либо намек?Спасибо

1 Ответ

0 голосов
/ 30 марта 2011

Вы всегда самостоятельно повторяетесь, поэтому вы можете просто обернуть все тело своей функции в цикл, а в тех местах, где вы хотите продолжить поиск, просто установить новые параметры и продолжить цикл?

...