
Boost : 
From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 20070423 22:28:38
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 nearestneighbour would
> become useful.
I see. For range searching, kdtrees would be the best in linear
storage.
> Some sort of tree (RTree, 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 kdtrees: 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/ilyathesis/index.html
(http://photon.poly.edu/~hbr/publi/ilyathesis/doc/geometry/
static__kd__tree_8hpp.html)
(http://photon.poly.edu/~hbr/publi/ilyathesis/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/ilyathesis/thesis.pdf
>> You must be aware of Timothy Chan's
>> paper "Closestpoint problems simplified on the RAM", in Proc. 13th
>> ACMSIAM Symposium on Discrete Algorithms (SODA), pages 472473,
>> 2002.
>
> I have not found a freelydownloadable 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 twopage long which could easily fit
eight. But all the code is given in pseudocode 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 32bit fixedpoint value and a 32bit
> floatingpoint 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk