2
\$\begingroup\$

This is our first attempt at building an unbalanced k-dimensional tree with nearest neighbor (1NN) lookup to process multi-dimensional data. In particular, the "suspect region" in the NN() function is where we are having the most questions:

  • Is a distance calculation (distCheck) necessary on every element in the subtree to assure the nearest candidate point? Is there a more elegant way to do this given the \$O(log n)\$ nature of kdtrees?
  • While we could readily find code for "search" (exact match) implementations, we struggled to find examples of 1NN implementations. From what we've gathered, search is very similar to sort with an added parameter of comparing radii:

    • Compare the given point's current working dimension to the root node's corresponding dimension; if < recursively search the left sub tree, if >= recursively search the right sub tree.
    • After recursion, if the radius from the given point's current dimension to the opposing subtree's corresponding dimension is <= the radius to the root node, recurse the opposing subtree as well.

Is this properly implemented? It seems unnecessarily verbose, given the nature of the data-structure. Clearly this could benefit from templatization and variable truncation, but are there more elegant approaches to this functionality?

The node struct:

#include<iostream>
#include<cmath>

struct kdNode {
    kdNode(unsigned int k) {
        point = new float[k];
        left = NULL;
        right = NULL;
        dim = k;
    }
    float *point;   // The point in k-space
    kdNode *left;   // less-than node
    kdNode *right;   // greater-than-or-equal node
    unsigned int dim;   // k

    friend std::ostream &operator<<(std::ostream &outStream, kdNode &node){
        outStream << "(";
        for (int i = 0; i < (node.dim - 1); i++) {
            outStream << node.point[i];
            outStream << ",";
        }
    return outStream << node.point[node.dim - 1] << ")";
    }
};

And functions:

kdNode *insert(kdNode *parentNode, float point[], unsigned int currDepth, unsigned int dim)
{
// Inserts a node (sorted, but unbalanced)
    if (parentNode == NULL){
        kdNode *temp = new kdNode(dim);
        for (int i = 0; i < dim; i++)
            temp->point[i] = point[i];
        return temp;
    }

    unsigned workingDepth = currDepth % dim;

    if (point[workingDepth] < (parentNode->point[workingDepth]))
        parentNode->left  = insert(parentNode->left, point, currDepth + 1, dim);
    else
        parentNode->right = insert(parentNode->right, point, currDepth + 1, dim);

    return parentNode;
}

void distCheck(kdNode *currNode, float point[], kdNode *&candidateNode){
// Checks distance and manipulates the nearest candidate node

    float currNodeDist = 0;
    float candidateNodeDist = 0;

    for(int i = 0; i < currNode->dim; i++)
    {
        float norm1 = point[i] - currNode->point[i];
        float norm2 = point[i] - candidateNode->point[i];
        currNodeDist += norm1 * norm1;
        candidateNodeDist += norm2 * norm2;
    }
    candidateNode = (candidateNodeDist < currNodeDist)?candidateNode:currNode;
    return;
}

void NN(kdNode *currNode, float point[], kdNode *&candidateNode, unsigned int currDepth)
{
// Finds nearest neighbor
    if (currNode == NULL)
    return;

    unsigned workingDepth = currDepth % currNode->dim;

//Suspect region
    distCheck(currNode, point, candidateNode);

    if (point[workingDepth] < currNode->point[workingDepth]) {
        NN(currNode->left, point, candidateNode, currDepth + 1);
        if((currNode->right != NULL) && std::abs(point[workingDepth] - currNode->point[workingDepth]) >= std::abs(point[workingDepth] - currNode->right->point[workingDepth]))
            NN(currNode->right, point, candidateNode, currDepth + 1);
    }
    else {
        NN(currNode->right, point, candidateNode, currDepth + 1);
        if ((currNode->left != NULL) && std::abs(point[workingDepth] - currNode->point[workingDepth]) >= std::abs(point[workingDepth] - currNode->left->point[workingDepth]))
            NN(currNode->left, point, candidateNode, currDepth + 1);
    }
// End suspect region
    return;
}

Some sample use:

int main()
{
    // This will eventually be a linked-list
    float points[][2] = {{1.9,1}, {1,2}, {2.1,3.1}, {0.9,0.9}, {1.5,3.5}, {2.9,2.1}, {3,4}, {0,0}, {1.7,2.7}, {4,3}, {2,5}};
    unsigned int dim = 2;
    unsigned int numOfPts = sizeof(points)/sizeof(points[0]);

    kdNode *kdtree = NULL;

    for (int i = 0; i < numOfPts; i++)
        kdtree = insert(kdtree, points[i], 0, dim);

    float point1[] = {3,3};

    std::cout << "\n(" << point1[0] << "," <<  point1[1] << ") ";
    kdNode *near = kdtree;
    NN(kdtree, point2, near, 0);
    std::cout << "Nearest node ";
    std::cout << *near;
        return 0;
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.