Re: [boost] Fixed point arithmetic - any interest?

From: Hervé Brönnimann (hervebronnimann_at_[hidden])
Date: 2007-04-23 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 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