Thread Subject:

How to find the nearest neighbors of a point in space quickly?

I have the matrix A, where the columns represents (x,y,z) coordinates of the points having a length about 1000000.

I want to find the nearest points (for example 1000 points) from a particular point of q in the matrix A. Noted that A is defined in a for loop and q is changed in every iteration.

I used "Knnsearch" method, but it is too slow for high iterations in a for loop.

Other method, I employed "histc" (as a binary search method) to find a cubical grid surrounding a portion of points in the matrix A around the point q. Afterwards, I did not use the "knnsearch", just found the Euclidian distance of the points in the specified cubical grid from the point q. This method made the code to be implemented faster but not very strikingly.

I need your help to speed up this process.

"Mahdi Roozbahani" <m.m.roozbahani@gmail.com> wrote in message <k7g2bs$79d$1@newscl01ah.mathworks.com>...
> I have the matrix A, where the columns represents (x,y,z) coordinates of the points having a length about 1000000.
>
> I want to find the nearest points (for example 1000 points) from a particular point of q in the matrix A. Noted that A is defined in a for loop and q is changed in every iteration.
>
> I used "Knnsearch" method, but it is too slow for high iterations in a for loop.
>
> Other method, I employed "histc" (as a binary search method) to find a cubical grid surrounding a portion of points in the matrix A around the point q. Afterwards, I did not use the "knnsearch", just found the Euclidian distance of the points in the specified cubical grid from the point q. This method made the code to be implemented faster but not very strikingly.
>
> I need your help to speed up this process.

Hint: Use methods based on Delaunay's triangulation.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <k7g8vp$s0q$1@newscl01ah.mathworks.com>...
> "Mahdi Roozbahani" <m.m.roozbahani@gmail.com> wrote in message <k7g2bs$79d$1@newscl01ah.mathworks.com>...
> > I have the matrix A, where the columns represents (x,y,z) coordinates of the points having a length about 1000000.
> >
> > I want to find the nearest points (for example 1000 points) from a particular point of q in the matrix A. Noted that A is defined in a for loop and q is changed in every iteration.
> >
> > I used "Knnsearch" method, but it is too slow for high iterations in a for loop.
> >
> > Other method, I employed "histc" (as a binary search method) to find a cubical grid surrounding a portion of points in the matrix A around the point q. Afterwards, I did not use the "knnsearch", just found the Euclidian distance of the points in the specified cubical grid from the point q. This method made the code to be implemented faster but not very strikingly.
> >
> > I need your help to speed up this process.
>
> Hint: Use methods based on Delaunay's triangulation.
>
> Bruno
------------------------
You know, the size of matrix A increases in each iteration. So, Delaunay tessellation should be applied in each iteration. This can affect code speed again. What do you think ?