Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

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

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

From: Mahdi Roozbahani

Date: 8 Nov, 2012 10:43:09

Message: 1 of 3

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.

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

From: Bruno Luong

Date: 8 Nov, 2012 12:36:09

Message: 2 of 3

"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

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

From: Mahdi Roozbahani

Date: 8 Nov, 2012 16:21:08

Message: 3 of 3

"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 ?

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us