-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
David Luff schrieb:
> 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 implemented
> 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 potential
> 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 links 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?
OK, this comes up once in a while (writing the WeatherCM code ages ago I
also had that problem). Perhaps it's time to solve generally.
The basic and ugly algorithm is to iterate through all points. This
takes at least O(n) and can be as bad as O(n^2) when I need e.g. the
distances between all points.
1) The usual solution is to create the delauney triangulation. It will
take O(n log n) to generate it and look ups can be quite fast as we know
the topology of the points.
This was my approach with the WeatherCM code. The used library should
still be somewhere in the FGFS codebase. (It's an extended version of
the triangulator to work on a sphere)
2) The sugested Quad-Tree (or Octtree) approach also might work with the
algorithm you've described (actually the buckets are a sort of quad tree
with only one level)
3) Interesting would be the use of a space filling curve ;)
There you can easily compute (O(log p) which we can assume to be O(1) in
our case) a index number out of the coordinates and then store all
points in the order of the index number. When you are now searching for
points that are close to a given one you just have to look upwards and
downwards from the index of the point you are interested in (this point
can be anywhere). As the usual space filling curves are Hölder
Continuous(*) this works quite good.
The most simplistic way to solve the problem is IMHO the use of a space
filling curve together with an STL map. This will result in only very
few lines of code and give us an quite fast and universal lookup scheme.
CU,
Christian
(*) Hölder Continuous to the exponent r basicly says that there's a C>0
that fullfills:
||f(x) - f(y)|| <= C * |x - y|^r
In the case of the n-D Hilbert curve (a very simple space filling
curve) r = 1/n, so in the 2D case:
||f(x) - f(y)|| <= C * sqrt( |x - y| )
Or more graphic: the distance between two indices limits the distance
that the two points in space can have.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.0 (MingW32)
iD8DBQFD9d7flhWtxOxWNFcRAj3jAJ4l0lLJqnwKY/bTnFd8cwK/kwIA1gCfSt/n
vo9XIlH/9KfOvLhyBfQHXJY=
=6x/z
-----END PGP SIGNATURE-----
-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems? Stop! Download the new AJAX search engine that makes
searching your log files as easy as surfing the web. DOWNLOAD SPLUNK!
http://sel.as-us.falkag.net/sel?cmd=lnk&kid3432&bid#0486&dat1642
_______________________________________________
Flightgear-devel mailing list
Flightgear-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/flightgear-devel
