CODEWITHSUNDEEP
pythonalgorithmvtkkdtree
zhongshu
zhongshu

Reputation: 7878

Nearest neighbour(closest point) search using vtkKdTree

I am using vtk's kdtree to search closest point, here is a simple example that, to my surprise, returned a value that was not what I was expecting

import vtk

points = vtk.vtkPoints()
points.InsertNextPoint(1, 0, 0)
points.InsertNextPoint(0, 1, 0)
points.InsertNextPoint(0, 0, 1)

kdtree = vtk.vtkKdTree()
kdtree.BuildLocatorFromPoints(points)

dist=vtk.reference(0.0)
p = kdtree.FindClosestPoint(0,0,10,dist)

print(p,dist)

the printed result is 0 4.0 and the value I expect is 2 81 (The return dist is a square of real distance)

Upvotes: 1

Views: 473

Answers (1)

Aditya
Aditya

Reputation: 1

I checked out the source code of vtkKdTree, and it seems this is because of the MaxWidth variable which is set based on the min & max values of the points in the point set.

For the above point set, the bounds look like this:

Bounds: 
    Xmin,Xmax: (0, 1)
    Ymin,Ymax: (0, 1)
    Zmin,Zmax: (0, 1)

Hence, the MaxWidth stays 1. Thus, any point having a distance larger than 4 * MaxWidth * MaxWidth (see this) = 4 in this case, will be capped to this value of 4 - which is what we see.

That's why for points like (0,0,0), (0,0,0.5), (0,0,1), (0,0,2), (0,0,2.9) etc, it is working as expected, but (0,0,3) onwards it breaks.

The fact is that setting the MaxWidth to incorporate the range of all points (in the point set and the queries) should solve the problem. A workaround that I found for that was to set a significant valued point in the original set (to denote infinity), such as (0,0,100) in the original point set. With that:

import vtk

points = vtk.vtkPoints()
points.InsertNextPoint(1, 0, 0)
points.InsertNextPoint(0, 1, 0)
points.InsertNextPoint(0, 0, 1)
points.InsertNextPoint(0, 0, 100) # denotes infinity

kdtree = vtk.vtkKdTree()
kdtree.BuildLocatorFromPoints(points)

dist=vtk.reference(0.0)
p = kdtree.FindClosestPoint(0,0,10,dist)

print(p,dist)

This results in the expected output: 2 81.0

However, I guess there should be a more elegant manner in which one can update the MaxWidth parameter. I looked at SetNewBounds() followed by ForceBuildLocator() to update the bounds and hence the width but that didn't seem to do the job at hand.

Upvotes: 0

Related Questions