Thread Subject: distance between nearest neighbors

I am trying to calculate the distance between certain nearest neighbor points that are elements of a larger branched structure. I think that the best way to describe this is by an analogy.....

....imagine a branch of a tree (the type that grows in the ground). It has a main "parent" branch and then potentially multiple smaller branches of this as you follow it to the tips of the branch. On this branch are leaves at random places. I want to calculate the distance (along the branch - not euclidean distance) between each leaf and its nearest neighbor. Naturally, the nearest neighbor leaf could be on the same branch-let or could be many branch-points away.

Sorry for the long-winded analogy, but I was struggling to describe the problem.

The data itself is presently stored as multiple xyz coordinates that each define the spatial position of each point of the overall structure (as well as the leaves).

Does anyone have any ideas as to how to approach this problem?

For example,
Could a KDTree approach work?
Do I need to travel in all possible directions from each leaf until I reach the next one and take the shortest of those distances?

Many thanks for any help.

Mike

Hi Michael,

A kd-tree will not address the problem that you have outlined. I believe you
are trying to compute the shortest path, if so take a look at Kruskal's
algorithm. This is not available in MATLAB, but it may be on the file
exchange. If you have a discrete set of points that are not connected to
form a graph then you could use the delaunay function to construct a
Delaunay triangulation and you could then run Kruskal's on that.

I hope this provides a useful lead.

Damian

"Michael Ashby" <ashbymc{removethis}@gmail.com> wrote in message
news:go12av$lmb$1@fred.mathworks.com...
>I am trying to calculate the distance between certain nearest neighbor
>points that are elements of a larger branched structure. I think that the
>best way to describe this is by an analogy.....
>
> ....imagine a branch of a tree (the type that grows in the ground). It has
> a main "parent" branch and then potentially multiple smaller branches of
> this as you follow it to the tips of the branch. On this branch are leaves
> at random places. I want to calculate the distance (along the branch - not
> euclidean distance) between each leaf and its nearest neighbor. Naturally,
> the nearest neighbor leaf could be on the same branch-let or could be many
> branch-points away.
>
> Sorry for the long-winded analogy, but I was struggling to describe the
> problem.
>
> The data itself is presently stored as multiple xyz coordinates that each
> define the spatial position of each point of the overall structure (as
> well as the leaves).
>
> Does anyone have any ideas as to how to approach this problem?
>
> For example,
> Could a KDTree approach work?
> Do I need to travel in all possible directions from each leaf until I
> reach the next one and take the shortest of those distances?
>
> Many thanks for any help.
>
> Mike