Re: [Flightgear-devel] Global data positional lookup
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Norman Vine schrieb: IIRC I have been mentioning http://www.sdss.jhu.edu/htm/index.html every time these kind of questions arise for years now :-) :) I know. Perhaps it's time that we implement it this time :) CU, Christian -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.0 (MingW32) iD8DBQFD+bGllhWtxOxWNFcRAsmOAJwN7588r8urrhI45GQiMF2NHfdnZQCfWkVS k4HTSioG7ihmqZ0sTgQSTiM= =S7Eb -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=lnkkid=103432bid=230486dat=121642 ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] Global data positional lookup
Thanks for all the suggestions guys. I'm ashamed to say that I'd never heard of the kd tree or the quad-tree before. Yes, the current bucket approach works, and yes I'll probably use it this time (Special User Airspace records for display on the kln89 map page), but the possibility of a more elegant approach is something that's been bugging me for a while. Cheers - Dave --- 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=lnkkid=103432bid=230486dat=121642 ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] Global data positional lookup
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 As my last post to this topic was probably a bit cryptic for some I've looked in the net a bit and have found: http://taltos.pha.jhu.edu/htm/ Probably we can use their software directly - or use their algorithm to partition the earth in such a way that we can cheaply query points (like navaids, METAR stations, ...) on the earth. CU, Christian -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.0 (MingW32) iD8DBQFD+LyClhWtxOxWNFcRAh8OAJ9LQpj1DTEveyWQFcL979s+CpREgwCgg3ag fMgUFkC2FAjicnPkbVZ+tT0= =vxNS -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=lnkkid=103432bid=230486dat=121642 ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] Global data positional lookup
On Sunday 19 February 2006 19:44, Christian Mayer wrote: As my last post to this topic was probably a bit cryptic for some I've looked in the net a bit and have found: Hehe, not really cryptic. Rather interresting! http://taltos.pha.jhu.edu/htm/ Probably we can use their software directly - or use their algorithm to partition the earth in such a way that we can cheaply query points (like navaids, METAR stations, ...) on the earth. Ok, a 'triangular quadtree' :) Should not be too hard to implement. I have some time during the next days ... Your note was that well done that it appeared that you will come up with an apprioriate solution in a few minutes ... :) At least it made me believe that you already have something more or less ready to share ... Greetings Mathias -- Mathias Fröhlich, email: [EMAIL PROTECTED] --- 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=lnkkid3432bid#0486dat1642 ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] Global data positional lookup
-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 C0 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=lnkkid3432bid#0486dat1642 ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
[Flightgear-devel] Global data positional lookup
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? Cheers - Dave --- 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=lnkkid=103432bid=230486dat=121642 ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] Global data positional lookup
Hi, On Friday 17 February 2006 01:51, David Luff wrote: 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? Hierarchical bounding boxes or octrees or something like that. Having that would be beneficial for the groundcache too. Ok, thinking loud: May be it is possible to build a quadtree for the earths surface. No clue if you *really* gain something vs the 3d approach appart from having fun thinking about that problem :) Other question: With the available tools the bucket indexed map is a good choice for that thing. Does it really hurt to use your current approach? How often are these navid lookups required per frame and how long does this take? Greetings Mathias -- Mathias Fröhlich, email: [EMAIL PROTECTED] --- 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=lnkkid3432bid#0486dat1642 ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
Re: [Flightgear-devel] Global data positional lookup
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 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? You can use a Kd-Tree. At the link below, there is a demo and a link to the java source code of the demo applet: http://www.diku.dk/hjemmesider/studerende/zrock/KDTree/ -Fred --- 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=lnkkid3432bid#0486dat1642 ___ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
