c++ - How to convert the following Nearest Neighbor recursive function to an iterative function

Question

I'm currently trying to optimize the following nearest neighbor algorithm by converting it to an iterative function.

Note: d0, d1, d2, d, shortest, shortest_node is defined outside of the function to reduce memory usage shortest is initialized to a large number, everything else to 0

void NearestNeighbor(Node * node, float vector[3], unsigned short depth)
{
    if (node == nullptr)
        return;

    d0 = node->vector[0] - vector[0];
    d1 = node->vector[1] - vector[1];
    d2 = node->vector[2] - vector[2];

    // distance without sqrt
    d = d0 * d0 + d1 * d1 + d2 * d2;

    // if d is less than the distance to the current closest node
    if (d < shortest)
    {
        shortest = d;
        shortest_node = node;
        // if [shortest] is equal to 0, we've found the nearest possible neighbor
        if (shortest == 0)
            return;
    }
    // % 3 is because the vector is 3 dimensional
    short diff = node->vector[depth % 3] - vector[depth % 3];

    // can't wrap my head around converting this to an iterative algorithm
    Nearest(diff > 0 ? node->l : node->r, vector, depth + 1);
    if (diff * diff < shortest)
        Nearest(diff > 0 ? node->r : node->l, vector, depth + 1);
}

I've tried by starting from an iterative tree traversal algorithm (https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/) and modifying it to fit my algorithm, but I can't seem to figure out how to work around the conditional recursion.

After quite some time trying, I currently have a non working function: (Just blindly trying btw, I can't figure out how to approach the problem)

void NearestNeighbor_Iterative(Node * root, float vector[3])
{
    std::stack<Node *> s;
    Node * cur = root;
    bool e = false;
    unsigned short depth = 0;
    while (cur != NULL || s.empty() == false)
    {
        if(cur != NULL)
            e = true;

        while (cur != NULL)
        {
            d0 = cur->vector[0] - vector[0];
            d1 = cur->vector[1] - vector[1];
            d2 = cur->vector[2] - vector[2];

            d = d0 * d0 + d1 * d1 + d2 * d2;

            if (d < shortest)
            {
                shortest = d;
                shortest_node = root;

                if (shortest == 0)
                    break;
            }
        
            diff[depth] = cur->vector[depth % 3] - vector[depth % 3];

            s.push(cur);
            cur = diff[depth] > 0 ? cur->l : cur->r;
            depth++;
        }
        if (e)
            depth--;
        else
            depth -= 2;
        cur = s.top();
        s.pop();
        if (diff[depth] * diff[depth] < shortest)
        {
            e = false;
            cur = diff[depth] > 0 ? cur->r : cur->l;
            depth++;
        }
        else
        {
            cur = nullptr;
        }
    }
}

Any help would be much appreciated!

Answer 1

等待大神答复