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

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2007-04-22 17:47:02

Herv? Br?nnimann wrote:
> On Apr 19, 2007, at 3:25 PM, Phil Endecott wrote:
>> I'd also like to mention that I have been using this type to implement
>> a 2D set<point> container using space filling curves.
>
> 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.

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).

> 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.

> I imagine (this was my first thought when reading Chan's  
> paper) that everything can be wrapped into a functor that computes  
> the order along the curve.  Is this the approach you're  
> implementing?

My current implementation uses the Z-curve, which simply interleaves 
the bits from each coordinate.  I have done this by writing an 
interleaved_pair<T> class which has some similarity to std::pair<T,T>.  
I can then implement point_map<point<COORD_T>,V> as 
std::map<interleaved_pair<COORD_T>,V>.  So no, there isn't a functor; 
it could be expanded in that way, but what benefit does the functor's 
state have?

Other curves are more expensive to compute but more efficient in use.  
I have done some quick experiments with a freely-available C 
implementation of the Hilbert curve, but I don't yet have a large 
enough test data set to quantify whether it is better overall than my 
simple Z-curve implementation.

> I'd be interested to hear your thoughts / experience /  
> esp. your setup (why you are interested in this in the first place).

I'm making a pan/zoom user interface to view GPS tracks superimposed on 
a base map.

> You can reply to the list if you think it's of general interest, or  
> to me directly.
>
> Re: the original topic of this thread, I really don't see the point  
> of fixed-point arithmetic for this, though, it seems to me point  
> coordinates could be computed in floating point, then rounded/scaled  
> to integers for inserting into the set<point>.  Iow, the fixed-point  
> coordinates are likely simply representational, not used in  
> computations.

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.

> Unless you're dealing with moving points, and even then...
>
> Btw, in Dr Dobb's I saw an article recently which I really didn't  
> understand.  Seemed like the author rediscovered quad-trees.

I have had a quick look and can't find it.

> Seems  
> like a functor for comparing along space-filling curves would also  
> make a great paper for Dr Dobb's / CUJ.  Cheers,
> --
> Herve Bronnimann

Regards

Phil.