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);
}
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);
}
Hint: a circle with center point →p and radius r overlaps with a half space defined by a implicit plane equation →n⋅(→x−→o)=0, where the plane normal →n points into the half space, if and only if the signed distance d=→n⋅(→p−→o) of →p to the plane is greater than or equal to −r:
→n⋅(→p−→o)≥−r
← Nearest Neighbor Search | ● | kd-Tree Template →