[vtk-developers] KdTree FindPointsWithinRadius

[Arnaud GELAS]

  Hi David,

That would be indeed really useful !!!

Arnaud

On 08/20/2010 03:16 PM, David Doria wrote:
> 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