Eg.
Let x = 1;
Given (0,0), (0,1), (1, 2), (4,6);
Return 1 -> (0,0), (0,1)
Build the kd tree, iteratively find the neighbors for the node where the distance is less than 1
http://en.wikipedia.org/wiki/Kd-tree#Nearest_neighbor_search
foo(tree* root, tree* node, stack
{
if(!root) return;
if(DIS(root,node)<(-1*len))
foo(root->left,node,s,len);
else if(DIS(root,node)>len))
foo(root->right,node,s,len);
else
{ if(!root->left&&!root->right)//left node is the point node
{
s.push(root);
return;
}
foo(root->left,node,s,len);
foo(root->right,node,s,len);
}
}
No comments:
Post a Comment