C-Programmierung

Nearest Neighbor Search

← Nearest Neighbor Strategy | ● | Maximum Distance Search →

Given: A set of n given items at specific points in 3D space.
Wanted: The item with the smallest geometric distance to a particular point (nearest neigbor)!

Assumed: n points inserted in a kd-tree.
Solution: As given by the following pseudocode for a recursive kd-tree search of the nearest neighbor, meaning that

  • we are looking for the nearest node
  • with respect to a specific point
  • recursively searching depth-first from the starting root node
typedef Node *node_pointer;

node_pointer search(Vector3D point, node_pointer node)
{
   result = null

   if (node != null)
   {
      result = node

      result2 = search in the half space that contains the search center
      if (result2 != null)
         if result2 is closer than result
            result = result2

      if (minimum distance of point to other half space is not farther away than result)
      {
         result2 = search in the other half space
         if (result2 != null)
            if result2 is closer than result
               result = result2
      }
   }

   return(result);
}
[Get Code]

Hint: the minimum distance $d$ of a point $\vec{p}$ to a half space defined by a implicit plane equation $\vec{n}\cdot(\vec{x}-\vec{o})=0$, where the plane normal $\vec{n}$ points into the half space, is

$\displaystyle{ d=max(-\vec{n}\cdot(\vec{p}-\vec{o}),0) }$


← Nearest Neighbor Strategy | ● | Maximum Distance Search →

Options: