Question for kdtree nearest neighbour search
Page 1 of 1

Author:  hemi86 [ Thu Nov 22, 2012 5:08 pm ]
Post subject:  Question for kdtree nearest neighbour search

Hi there,

im working on a school project where i have to use a nearest neighbour search (Programming language is c#).

now i have the following problem:

im searching for the nearest neighbour from the x-/y- position (A). Then i get the nearest neighbour to it (B). now i have to search for the nearest neigbour from (B) but then i get the x- and y- position from (A) again. Is is possible to delete points from the kd tree, that the nearest neighbour will always be a new value of the kd tree? Or is there any other solution?

i hope you understand what i mean ;)

looking forward to your answers

Author:  Sergey.Bochkanov [ Thu Nov 22, 2012 7:26 pm ]
Post subject:  Re: Question for kdtree nearest neighbour search


Current version of ALGLIB does not allow to modify kd-tree - delete items or add new ones. I think that you can have try working with additional array which stores "is_deleted" flag and to perform k-NN queries for k>1 in case nearest neighbor was deleted. It should be slower than deleting elements from tree, but still it should work.

BTW, can you describe problem which required ability to remove elements from tree?

Author:  hemi86 [ Fri Nov 23, 2012 9:00 am ]
Post subject:  Re: Question for kdtree nearest neighbour search

Yes i can, and thanks for your fast reply :)

I want to track a person via the microsoft kinect and want to project the silhouette of the user with a laser projector. I am searching for the points of the edges from the depth-frame of the kinect. Now i get an unsortet pointlist of the tracked points. for example: if im searching for the edges of one line inside the frame, i get 2 points (for example: one point at the right side of the head and the next point on the same line at the left side of the head). But with this i cant project the silhouette of the user with the laser projector beacause the scanning system inside the laser projector will move from point to point in that list of points while the laser source in the projector is on. So if i use this unsortet list of points i will get a wrong projection.

so i have to sort this pointlist point for point, that i always get the nearest neighbour of an actual point to create a sorted pointlist which can be projected by the laser projector. if i found a point and inserted it in the sorted point list, this point is useless and there is no need to compare it again with the following points. I attached a picture of the problem. I hope you understand what i want to do :)


Maybe there is a better solution than the nearest neighbour search which i dont know.

Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group