[OSM-dev] Proposal: Database accelerator and dirty tile marker based on simple algorithm.

[Nigel Magnay]

Iterative or recursive, you still have to traverse the bits. So, if I
understand correctly, I'm proposing (for, say, a 64-bit output format)

// Use appropriate values rather than 0.5 if world is not scaled
long convert(double x, double y)
{
    long result = 0;
    for(int i=0;i<32;i++)
    {
        result *= 4; // shift
        x -= Math.floor(x);
        y -= Math.floor(y);
        result += (x > 0.5?1:0) + (y > 0.5 ? 2 : 0);
        x *=2;
        y *= 2;
    }
    return result;
}

And you are proposing something like
long convert(double x, double y)
{
    long result = 0;
    long longX = (long)(x * 10000000); // FCONV
    long longY = (long)(y * 10000000);
    for(int i=0;i<32;i++)
    {
        result *= 2; // shift up
        // add to bottom
        result += (longX & 0x80000000 ?1:0) + (longY & 0x80000000 ? 2 : 0);
        longX = longX * 2;  // Shift so top bits most sig.
        longY = longY * 2;
    }
    return result;
}

There may be a better implementation, but we can't talk about clock cycles
because OSM is written in Ruby, and who cares about the odd clock cycle here
and there?. Unless I've missed something (which is entirely possible), those
two routines look remarkably similar; I could benchmark them in a HLL and
compare but I doubt we'll see any significant difference - but - the cost of
the latter one is that you loose a bit of precision, and need a set of
'special case' processing around the latitude wrap to cope with the fact
that the tiles won't evenly match up. That doesn't seem to me to be a
worthwhile tradeoff...


On 18/09/06, Nick Hill <nick at nickhill.co.uk> wrote:
>
>
>
> Nigel Magnay wrote:
> > The disadvantage is though that you have a bit of work to do in areas
> > which overlap (the +/-180 line), which you wouldn't have if the grid fit
> > the globe exactly - this is going to be a bit of a pain for things like
> > coastlines.
>
> This is a good point, we would need to use a specific wrap algorithm,
> where the platform based binary calculation may provide a suitable wrap
> function. However, the borders would be at the pacific date line, mostly
> down the pacific ocean, and at the poles.
>
>
> >
> >   The only thing that I think is bothering me is the "then interleave"
> > step. To perform this function don't you need to recurse around the 1E7
> > lon and lat figures shifting bits off, and isn't that exactly the same
> > as my inner loop ? And if that's the case, the fact that it's a 1E7
> > multiplication a bit unimportant, because that's not the "hard bit"? Or
> > is there some fancier way of interleaving bits I haven't thought of?
> >
> No recursion is necessary. Only bit-shifting is necessary for the
> conversion. There are potentially single math operations to perform the
> function, although any function I can currently think of needs a CPU
> cycle per bit. But then again, I can think of a function which wold
> convert your recursive division tiles using the 11930464.711111111
> coefficient then bit-shifting.
>
>
> _______________________________________________
> dev mailing list
> dev at openstreetmap.org
> http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20060918/74c202c6/attachment.html>