Prev: About behavior of KeyPressFcn
Next: mcc generating .exe
From: Kyle on 7 Jul 2010 16:45
So I have a data set of point coordinates in x, y, z format.

Given any one of the points, I was wondering if there is a matlab function out there that can return the closest point in the data set to the given point in 3d space. If something like this doesnt exist here a couple of ideas I had to solve the problem myself:

Create a series of for loops that iterates through every point and compares its distance from every other point but it seems like this would take a rather long time since the data sets I am working with have approximately 3000 points.

I also had an idea of creating a theoretical sphere that originates from the given point and grows larger until another point is enclosed by the sphere. Is this feasible and could it be faster?
From: Peter Perkins on 7 Jul 2010 17:02
On 7/7/2010 4:45 PM, Kyle wrote:
> So I have a data set of point coordinates in x, y, z format.
>
> Given any one of the points, I was wondering if there is a matlab
> function out there that can return the closest point in the data set to
> the given point in 3d space.

Kyle, if you have access to the Statistics Toolbox, see KNNSEARCH.
From: Walter Roberson on 7 Jul 2010 17:26
Kyle wrote:
> So I have a data set of point coordinates in x, y, z format.
>
> Given any one of the points, I was wondering if there is a matlab
> function out there that can return the closest point in the data set to
> the given point in 3d space. If something like this doesnt exist here a
> couple of ideas I had to solve the problem myself:
>
> Create a series of for loops that iterates through every point and
> compares its distance from every other point but it seems like this
> would take a rather long time since the data sets I am working with have
> approximately 3000 points.
>
> I also had an idea of creating a theoretical sphere that originates from
> the given point and grows larger until another point is enclosed by the
> sphere. Is this feasible and could it be faster?

Your question of the second paragraph has to do with returning the nearest
dataset neighbour of a _particular_ point, which is a problem that is linear
in the number of points in the dataset: compute the 3000 distances and find
the minimum.

Your proposed algorithm of the third paragraph has to do with comparing every
point to every other point, involving N*(N-1)/2 distances and which doesn't
seem to take into account the original 3-space point. It is not clear why you
are considering such an approach.

With respect to the theoretical-sphere algorithm: yes, such algorithms are
possible and searches are possibly practical in N^(1/3) time once the data
structure is set up, if you were to use something like an octree
representation. There is non-negligible overhead for setting up the octree
representation so this kind of approach would not be feasible for single point
probes, but would become more practical as the number of searches over the
same dataset increase (amortizing the cost of building the structure over the
number of searches.) There may well be algorithms even better than searching
within an octree, as it seems likely the problem has been studied before.
From: Matt J on 7 Jul 2010 17:35
D=bsxfun(@minus,Points,GivenPoint);
[~,idx]=min(sum(D.^2));

ClosestPoint=Points(:,idx)
From: Bruno Luong on 7 Jul 2010 18:23
"Kyle " <kandrews(a)andrew.cmu.edu> wrote in message <i12p0j$dp6$1(a)fred.mathworks.com>...
> So I have a data set of point coordinates in x, y, z format.
>
> Given any one of the points, I was wondering if there is a matlab function out there that can return the closest point in the data set to the given point in 3d space. If something like this doesnt exist here a couple of ideas I had to solve the problem myself:
>
> Create a series of for loops that iterates through every point and compares its distance from every other point but it seems like this would take a rather long time since the data sets I am working with have approximately 3000 points.
>
> I also had an idea of creating a theoretical sphere that originates from the given point and grows larger until another point is enclosed by the sphere. Is this feasible and could it be faster?

Check out the Voironoi diagram (voronoin or TriDelaunay class for newer Matlab version), it splits the 3D in polytopes that contains points closer to a seed of that cell than any other.

The dsearchn() function and nearestNeighbor method of TriDelaunay class use the voronoi diagram to find nearest points, and are the canned functions that you might be interested in.

Bruno
 |  Next  |  Last
Pages: 1 2
Prev: About behavior of KeyPressFcn
Next: mcc generating .exe