[vtk-developers] KdTree FindPointsWithinRadius

[David Doria]

An operation that I perform extremely frequently is to build a tree on a set
of points and then query for all neighbors within a radius of a point that
is in the tree. Currently the procedure is to get the coordinates of the
point, then query the tree, then remember to ignore the point that was the
query point:

    double queryPoint[3];
    input->GetPoint(pointID, queryPoint);

    //find all the points around the query point
    vtkSmartPointer<vtkIdList> neighbors =
      vtkSmartPointer<vtkIdList>::New();
    kdTree->FindPointsWithinRadius(eRadius, queryPoint, neighbors);

    // Do something with the neighbors
    for(vtkIdType n = 0; n < neighbors->GetNumberOfIds(); n++)
      {
      if(neighbors->GetId(n) == pointID) //we have found exactly the same
point we queried for!
        {
        continue;
        }

I would like to propose adding a function to query by a pointID already in
the tree.

  // Description:
  // Find all points within a specified radius R of point n.
  // The result does not include point n.
  virtual void FindPointsWithinRadius(double R, const vtkIdType n,
                                      vtkIdList *result);

void vtkKdTreePointLocator::FindPointsWithinRadius(double R, const vtkIdType
n,
                                      vtkIdList *result)
{
  double queryPoint[3];
  vtkPointSet::SafeDownCast(this->GetDataSet())->GetPoint(n, queryPoint);
  this->BuildLocator();
  this->KdTree->FindPointsWithinRadius(R, queryPoint, result);
  result->DeleteId(n);
}

I have also added a test for both the new and old method.

I have created a branch here:
repo: git at github.com:daviddoria/daviddoria-vtk.git
branch: VTK-KdTree

Any comments?

Thanks,

David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20100820/27fc2d23/attachment.html>