Re: [Flightgear-devel] Global data positional lookup

[Frederic B. <fre...@fr...>]

Selon David Luff :

> I'm considering the problem of looking up global data at the moment (eg=
. how
> many navaids are within x miles of point p).  So far I've only implemen=
ted
> this in a very crude manner, by indexing a map of navaid pointers using=
 FG
> bucket number, and then traversing all the navaids in the user's bucket=
 and
> concentric rings of buckets out from the user to the required distance.=
  This
> works, but is somewhat ugly, and requires more navaids / buckets to be
> checked than may be necessary due to the non-square bucket size and pot=
ential
> for non-centered position of the user within a bucket.
>
> I'm sure there must be a better way, and I'm sure Norman has posted lin=
ks on
> this subject to the list before, but I can't find them, and can't seem =
to
> find a good method.  Anyone got any ideas?

You can use a Kd-Tree. At the link below, there is a demo and a link to t=
he java
source code of the demo applet:
http://www.diku.dk/hjemmesider/studerende/zrock/KDTree/

-Fred