Linear Quadtrees

["Carter T Shock" <ctso#umiacs,umd.edu>]

Please forgive the awful image attached... I is a code monkey, not a
artist.

Top figure is the space divided up by the quadtree in the bottom figure.
Bottom figure shows the classic pointer-based quadtree implementation.
Lotsa overhead here. Every node in the tree has four (possibly null)
pointers. It doesn't adapt well to disk based operations etc. The question
is how to get rid of all of those pointers. This is just an overview, not a
hard-core implementation.

The top figure is 256 pixels square, so the entire space indexes nicely
with a pair of 8 bit values. Take a peek at the 1's and 0's next to the
upper figure. We already know that we can come up with a morton code for
any point in 2-d space.  Consider the morton codes for the upper-left
corners of any block in the tree.

The green block's (at least I hope it's green) upper left coordinate is
[0,0], so the
morton code is trivially 0000000000000000. The blue block has upper left
coordinate [0,128] yielding 0100000000000000. The yellow block is [0,192],
0101000000000000. Why do we care?

'Scuse the pseudo-code here, but...
Find all points in the green block:

for each point's morton code, P
   if( (P & 1100000000000000) == 0)
       return true.

Where '&' is bitwise AND.

The blue block presents a bit of a problem because its upper left corner is
the same point as the square that contains it (i.e. the square that is the
same size as the green one... blue's parent). The difference is the block's
level in the tree. Just use more bits.

for each P (as above)
   if((P & 1111000000000000) == 0100000000000000) return true.

Same trick with the yellow block...

for each P
   if((P & 1111110000000000) == 0101000000000000) return true.

Look Ma! No pointers.

The trick is called (go figure..) Morton Blocks.
There are fancier tricks you can do, but for those you'll have to buy the
book :)
	-Todd

qt (GIF Image)