On 11 Dec 2009, at 19:32, Csaba Halász wrote: > Also, the whole positioned code seems to be ignorant of the fact that > buckets don't have the same size. Staying with the spatialGetClosest, > it assumes it can just use NxN boxes when in fact a different row > (latitude) could have half or double the bucket size. spatialFind() > even uses the width/height of the current bucket explicitly.
The code isn't 'aware' of it, but I was aware, when I wrote the code - I just opted to ignore the fact, on the basis that the results I got from testing seemed plausible. By the time you're at a latitude where it matters, you're running low on navaids/fixes anyway. > In light of this, not even the patch I proposed on IRC is halfway > correct, so James please don't commit that. In my opinion, such a > low-level and widely used piece of code must work correctly otherwise > a lot of things can break. Well, this might surprise you, but it's actually used quite rarely *at the moment* - mostly by the GPS code, and the marker beacon code. The GPS code uses it extensively, of course - and the usage will increase quite a bit more - but most positioned users currently find things by ident or frequency. > Thus I consider this a show-stopper for the > release and an attitude of "the issue of terminating with 'not > actually the closest', I know of, but don't really care about" isn't > acceptable. Fundamentally we need a better algorithm, and probably a new data-structure - Mathias has a potential solution using a hierarchical triangle map, though the code is a bit template-heavy for my liking. Before writing the current algorithm, I experimented with various linear hashes of the lat/lon, but effectively that's what the bucket number from SGBucket gives you - and it doesn't help with 'find me all the buckets within 'x' nm of this lat/lon'. I'll take another read over Mathias' code today, but I don't think I'll like it any more than I did the last few times I read over it. Other suggestions welcome, or proposals for a sufficiently accurate 'all the SGBuckets within a given radius of position P' - allowing for behaviour at the poles and in the Pacific. BTW, it would also be possible to spatially index FGPositioneds by their cartesian position, potentially even using a BSP or similar. (Or an oct-tree). This would avoid all the wrap-around problems at the poles and -180/180 longitude search. Again, this is something I made some algorithmic doodles for, but never developed into working code. Actually, the more I think on it, the more I think the cartesian approach may be a win - assuming you can find the bsp/octree/whatever node that contains your 'search sphere' (sphere of radius set by the cutoff, centred on search location), ordering all the contents by distance is just X^2 + Y^2 + Z^2 and a sort - no geodetic computations at all. I'll think on that some more now. (And it's fairly amenable to the filtering methodology too) James ------------------------------------------------------------------------------ Return on Information: Google Enterprise Search pays you back Get the facts. http://p.sf.net/sfu/google-dev2dev _______________________________________________ Flightgear-devel mailing list Flightgear-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/flightgear-devel
