Quadtrees?

[Carter T Shock]

> do you know of any good books that I can read up on some of those
algorithms
> specifically the Peano, Hilbert or Morton curves you mentioned?
> 

"The Design and Analysis of Spatial Data Structures" by Samet (Addison
Wesley) is a great primer on this stuff and spatial data structures in
general. However, save 30 bux...

Peano and Morton are two names for the same thing. A space filling curve is
one that can cover all the points in a grid without ever crossing over
itself. Hilbert is kinda odd and computationally a bit nasty to work with,
but Morton is easy.

In a nutshell: interleave the bits.

Given a coordinate [3,5] represented with 4 bits each you have:
X = 0011
Y = 0101
Morton is: 00011011 or 00100111

0 0 1 1
 0 1 0 1
00011011

Your choice as to whether to start with the X or Y bit as most significant.
Here's the sweet part... because the most significant bits of the code
represent the most significant bits of the two coordinates you can use it
as a sorting key. Codes that are numerically close are also spatially
close. There's also a direct correspondence between the code and
quadrants/depth in quadtrees but I'm not swift enough with ASCII graphics
to draw it here. I can do a picture and send it via MIME if ya want. Also
as mentioned, you can do algebra on them. Need to offset the coordinates by
an X,Y? make a code for the offset and add/subtract it in.
You can also do range searching by masking off low-order bits. Finally,
this is why using B-Tree type stuff works.. the keys in the tree are just
the interleaved codes. It's one of those things that once discovered you
bonk yourself on the head and say "why didn't I think of that?"
	-Todd