[inline]<br><br><div><span class="gmail_quote">On 16/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>Nick Hill wrote:<br>> Hello Nigel<br>> You could, for example, use the two most significant bits to represent<br>> each quadrant, then the two next most significant bits to select  the<br>> next level quadrant and so on. With a 32 bit int, you can do this 16

> times, dividing the planet into 4Bn portions, much like the tiles I > suggested. > I haven't yet considered your quadtree proposal in enough depth to fully > compare the two approaches, but there are many similarities.

<br><br>If we use a quadtree form, and make all represented values fit to base-2<br>(to avoid ugly floats) we end up with<br><br>Bit number<br>1 Latitude sign  (MSB)<br>2 longitude sign<br>3 1073741824 units LAT<br>4 1073741824 units LON

5 536870912 LAT 6 536870912 LON 7 268435456 8 268435456 continuing in the binary series for as much precision as required. To extract a latitude value, we'd  need to use bits 3,5,7,9,11,13,15 etc. Shift the number then apply 2's compliment if bit 1 is set.

<br><br>To extract longitude, bits 4,6,8,10,12,14 etc, shift, then apply 2's<br>complement if bit 2 is set.<br><br>So the quadtree form is very similar to my suggestion. The difference is<br>that bits 1-16 are lat for my form but for quadtree form, bits

<br>1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31 are lat.</blockquote><div><br>This is required though, otherwise fetching supertiles (e.g. 'D' from my example) can't be done with a range lookup. <br><br>e.g: As quadtiles<br>

AA AB BA BB

<br>AC AD BC BD<br>CA CB DA DB<br>CC CD DC DD<br><br>== as bits<br><br>0000 0001 0100 0101<br>0010 0011 0110 0111<br>1000 1001 1100 1101<br>1010 1011 1110 1111<br><br>== as numbers<br><br>0 1 4 5<br>2 3 6 5<br>8 9 12 13<br>

10 11 14 15<br><br>Fetch the bottom-right quadrant of the map is either ' like D%' or 'where val >= 12 and <= 15).<br><br>This is very important if you ever want tiles that are > than the minimum size. If you're doing,say, tiles that are composed of some size greater than the maximum resolution. For example, you have a tile address

AAAB and a 'tile invalidated' message arrives, for tile AAABABFB, you know, trivially, that your tile is now invalid. The same can be done with pairs of numbers, (e.g tile 9 invalidated, my tile is >=0,<=15) but it's a bit uglier.

<br><br><br><br><br></div><br></div><br>