C-Programmierung

Maximum Distance Search

← Nearest Neighbor Search | ● | kd-Tree Template →

Given: A set of n given items at specific points in 3D space inserted in a kd-tree.
Wanted: All items within a particular circle (maximum distance)!

Strategy: Visit all half-spaces that overlap with the search circle and gather points that are inside the search circle:

  • While traversing the kd-tree, append nodes that are within the search radius to a node list
  • if the search circle overlaps with a half space descend recursively into the corresponding half space
    • meaning that the signed distance of the center of the search circle to the separating plane plus the radius needs to be greater than zero.
typedef Node *node_pointer;
typedef std::vector<node_pointer> result_list;

result_list search(Vector3D point, double radius, node_pointer node)
{
   result list = empty

   if (node != null)
   {
      if node is within radius
         result list += node

      if search circle overlaps left half space
      {
         left result list = search in the left half space of node
         result list += left result list
      }

      if search circle overlaps right half space
      {
         right result list = search in the right half space of node
         result list += right result list
      }
   }

   return(result list);
}
[Get Code]

Hint: a circle with center point $\vec{p}$ and radius $r$ overlaps with 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, if and only if the signed distance $d=\vec{n}\cdot(\vec{p}-\vec{o})$ of $\vec{p}$ to the plane is greater than or equal to $-r$:

$\displaystyle{ \vec{n}\cdot(\vec{p}-\vec{o}) \ge -r }$


← Nearest Neighbor Search | ● | kd-Tree Template →

Options: