forum.alglib.net

ALGLIB forum
It is currently Thu Mar 28, 2024 11:25 pm

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Question for kdtree nearest neighbour search
PostPosted: Thu Nov 22, 2012 5:08 pm 
Offline

Joined: Thu Nov 22, 2012 4:57 pm
Posts: 2
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


Top
 Profile  
 
 Post subject: Re: Question for kdtree nearest neighbour search
PostPosted: Thu Nov 22, 2012 7:26 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
Hello!

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?


Top
 Profile  
 
 Post subject: Re: Question for kdtree nearest neighbour search
PostPosted: Fri Nov 23, 2012 9:00 am 
Offline

Joined: Thu Nov 22, 2012 4:57 pm
Posts: 2
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 :)

Image

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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 45 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group