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)<br><br>// Use appropriate values rather than 0.5 if world is not scaled<br>long convert(double x, double y)

<br>{<br>    long result = 0;<br>    for(int i=0;i<32;i++)<br>    {<br>        result *= 4; // shift<br>        x -= Math.floor(x);<br>        y -= Math.floor(y);<br>        result += (x > 0.5?1:0) + (y > 0.5 ? 2 : 0);

<br>        x *=2;<br>        y *= 2;<br>    }<br>    return result;<br>}<br><br>And you are proposing something like<br>long convert(double x, double y)<br>{<br>    long result = 0;<br>    long longX = (long)(x * 10000000); // FCONV

<br>    long longY = (long)(y * 10000000);<br>    for(int i=0;i<32;i++)<br>

    {<br>

        result *= 2; // shift up<br>        // add to bottom<br>        result += (longX & 0x80000000 ?1:0) + (longY & 0x80000000  ? 2 : 0); <br>        longX = longX * 2;  // Shift so top bits most sig.<br>        longY = longY * 2;

<br>

    }<br>

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

<br><br><br><div><span class="gmail_quote">On 18/09/06, <b class="gmail_sendername">Nick Hill</b> <<a href="mailto:nick@nickhill.co.uk">nick@nickhill.co.uk</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">

<br><br>Nigel Magnay wrote:<br>> The disadvantage is though that you have a bit of work to do in areas<br>> which overlap (the +/-180 line), which you wouldn't have if the grid fit<br>> the globe exactly - this is going to be a bit of a pain for things like

<br>> coastlines.<br><br>This is a good point, we would need to use a specific wrap algorithm,<br>where the platform based binary calculation may provide a suitable wrap<br>function. However, the borders would be at the pacific date line, mostly

<br>down the pacific ocean, and at the poles.<br><br><br>><br>>   The only thing that I think is bothering me is the "then interleave"<br>> step. To perform this function don't you need to recurse around the 1E7

<br>> lon and lat figures shifting bits off, and isn't that exactly the same<br>> as my inner loop ? And if that's the case, the fact that it's a 1E7<br>> multiplication a bit unimportant, because that's not the "hard bit"? Or

<br>> is there some fancier way of interleaving bits I haven't thought of?<br>><br>No recursion is necessary. Only bit-shifting is necessary for the<br>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.

<br><br><br>_______________________________________________<br>dev mailing list<br><a href="mailto:dev@openstreetmap.org">dev@openstreetmap.org</a><br><a href="http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev">

http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev</a><br></blockquote></div><br>