Fortran - Re: Fortran to find nearest point from set in 3-D

Author

Re: Fortran to find nearest point from set in 3-D

David.Paterson@csiro.au

2006-04-19, 4:03 am

> Btw a similar question was asked recently in comp.lang.fortran -- one
can Google "kd tree" there.

Thanks from David Paterson. I've come to the conclusion that a "kd
tree" is excellent if I want to find the approximate nearest neighbour
(which is good enough for me) but not if I want the exact nerarest
neighbour.

Have you seen a Fortran implementation of a "kd tree"?

Gordon Sande

2006-04-19, 8:03 am

On 2006-04-19 03:19:14 -0300, David.Paterson@csiro.au said:

> can Google "kd tree" there.
>
> Thanks from David Paterson. I've come to the conclusion that a "kd
> tree" is excellent if I want to find the approximate nearest neighbour
> (which is good enough for me) but not if I want the exact nerarest
> neighbour.

Having used kd-trees for a couple distinct applications I would said
that they do (exact) nearest neigbour nicely and if you just want
approximate nearest neighbour then there are there are some other
variants for that. Ask google and it will tell you about some
folks with a package called ANN.

> Have you seen a Fortran implementation of a "kd tree"?

By the time you wade throught the overhead of someone else's code
you will find that rolling your own is about as simple. Reading the
other stuff helps for the first time.

One of the folks (Watson) who does this lives just down the street from
you in Perth. (That's a joke as Perth is one the other end of Oz and
about a 6 hour flight away. Like asking someone from New York if they
know your friend in Los Angeles because both cities are in the USA.)
His variant goes by the name natural neighbours.

Paul Van Delst

2006-04-19, 8:03 am

Gordon Sande wrote:
> On 2006-04-19 03:19:14 -0300, David.Paterson@csiro.au said:
>
>
>
> Having used kd-trees for a couple distinct applications I would said
> that they do (exact) nearest neigbour nicely and if you just want
> approximate nearest neighbour then there are there are some other
> variants for that. Ask google and it will tell you about some
> folks with a package called ANN.
>
>
>
> By the time you wade throught the overhead of someone else's code
> you will find that rolling your own is about as simple. Reading the
> other stuff helps for the first time.
>
> One of the folks (Watson) who does this lives just down the street from
> you in Perth. (That's a joke as Perth is one the other end of Oz and
> about a 6 hour flight away. Like asking someone from New York if they
> know your friend in Los Angeles because both cities are in the USA.)

Warning: Totally OT. It's not always a joke..... I was asked that once when I was on a
field trip in the boonies of Oklahoma. Some farmer moved to Oz outside of Sydney and the
local RV LPG refiller guy asked me if I knew him after I told him I was from Perth. I
thought he was joking, but my nudge nudge wink wink "good one" head nod was greeted with a
vacant stare.

cheers,

paulv

--
Paul van Delst
CIMSS @ NOAA/NCEP/EMC

Brooks Moses

2006-04-19, 10:01 pm

David.Paterson@csiro.au wrote:
>
> can Google "kd tree" there.
>
> Thanks from David Paterson. I've come to the conclusion that a "kd
> tree" is excellent if I want to find the approximate nearest neighbour
> (which is good enough for me) but not if I want the exact nerarest
> neighbour.

Huh. My impression was that a kd-tree was used to locate a (small) set
of candidate nearest-neighbor points, which one would then test to find
the exact nearest neighbor.

- Brooks

--
The "bmoses-nospam" address is valid; no unmunging needed.

Gordon Sande

2006-04-19, 10:01 pm

On 2006-04-19 16:15:41 -0300, Brooks Moses
<bmoses-nospam@cits1.stanford.edu> said:

> David.Paterson@csiro.au wrote:
>
> Huh. My impression was that a kd-tree was used to locate a (small) set
> of candidate nearest-neighbor points, which one would then test to find
> the exact nearest neighbor.
>
> - Brooks

I would have said that the kd-tree offers up an exapanding collection of
highly plausible neigbourhoods, with contents, that have to be inspected
more closely because it does not know exactly where the contents are inside
those neighbourhoods. The kd neigbourhoods may not match the precise form
of the metric you are using. Its neighbourhoods are rectalinear while metrics
like L_2 have spherical neighbourhoods.

There are enough variations on kd-trees that it depends on which version
one is looking at. Are the queries for the best or a range? Are the kd-trees
buckets taken all the way to single points or do they stop early? It shows
that the basic scheme is both powerful and versatile.

Christer Ericson

2006-04-20, 4:03 am

In article <1145427554.720375.287540@g10g2000cwb.googlegroups.com>,
David.Paterson@csiro.au says...
> Thanks from David Paterson. I've come to the conclusion that a "kd
> tree" is excellent if I want to find the approximate nearest neighbour
> (which is good enough for me) but not if I want the exact nerarest
> neighbour.

Not so. The k-d tree is the canonical data structure for exact
nearest neighbor queries (in low dimensions I should probably
add). The original reference is:

Friedman, Jerome. Jon Bentley. Raphael Finkel. =3FAn Algorithm for
Finding Best Matches in Logarithmic Expected Time.=3F ACM Transactions
on Mathematical Software, vol. 3, no. 3, pp. 209-226, September 1977.

You can find the technical report version of this paper here:

ftp://reports.stanford.edu/pub/cstr...5/482/CS-TR-75-
482.pdf

Their description leaves a bit to be desired, but the bottom line
is that, given a k-d tree implementation, the nearest neighbor
query can be implemented in about 10-15 lines of C/C++ code
(and probably not much more in Fortran).

I give an almost complete implementation in Section 7.3.7 of my
book; to be turned into an exact nearest neighbor query the code
just needs to be completed by shrinking the query sphere as
points are encountered (i.e. 1-2 lines of code).

--
Christer Ericson
http://realtimecollisiondetection.net/

Sponsored Links