On Apr 22, 2007, at 5:47 PM, Phil Endecott wrote:
This is highly interesting to me. I suppose you're doing this for nearest neighbors of some kind.
Actually I'm currently just using it to find the subset of a set of points that lie within a rectangle. At some point in the future I may need to do clustering, at which point nearest-neighbour would become useful.
I see. For range searching, kd-trees would be the best in linear storage.
Some sort of tree (R-Tree, whatever) might sound like a more obvious solution to my current problem. I decided to try space filling curves instead because they let me exploit the standard containers (e.g. std::map); I almost "adapt" the standard 1D container to 2D (or potentially higher dimensions).
I had a student do inplace static and dynamic kd-trees: stored inside a vector, the ordering is key to the organisation of the kd- tree. The code and documentation are available along with the rest at: http://photon.poly.edu/~hbr/publi/ilya-thesis/index.html (http://photon.poly.edu/~hbr/publi/ilya-thesis/doc/geometry/ static__kd__tree_8hpp.html) (http://photon.poly.edu/~hbr/publi/ilya-thesis/doc/geometry/ dynamic__kd__tree_8hpp.html) It's unfinished, as I've come to believe that all Theses are (*sigh*). The thesis itself is accessible at http://photon.poly.edu/~hbr/publi/ilya-thesis/thesis.pdf
You must be aware of Timothy Chan's paper "Closest-point problems simplified on the RAM", in Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 472-473, 2002.
I have not found a freely-downloadable version of that.
On Timothy's web page: http://www.cs.uwaterloo.ca/~tmchan/pub.html#ram I must warn you: Timothy's one of the smartest people around, and the paper is a deceptively two-page long which could easily fit eight. But all the code is given in pseudo-code and you don't even need to understand to program it (although it's nicer to understand, of course). I've not tried to code it myself, but
One difference between a 32-bit fixed-point value and a 32-bit floating-point value is that in the latter case you "waste" 8 bits for the exponent. So for latitude/longitude GPS data you get 256 (or maybe 128) times better precision in the same memory space by using fixed point. IIRC the difference is between centimetres and metres of resolution. In my application, having found the set of points that are currently visible, their positions are converted to integer screen positions for display; at this point it is certainly more efficient to not convert to and from floating point again.
Excellent point. Thanks. -- HB