February 1997
- Its nice to be back Nathan Yospe
- Its nice to be back coder@ibm.net
- Its nice to be back Nathan Yospe
- Testing coder@ibm.net
- Invitation to MUD Design Mailing List Chris Gray
- Invitation to MUD Design Mailing List coder@ibm.net
- Invitation to MUD Design Mailing List coder@ibm.net
- Invitation to MUD Design Mailing List coder@ibm.net
- Invitation to MUD Design Mailing List coder@ibm.net
- Wout's mailing list and old digests coder@ibm.net
- Wout's mailing list and old digests Wout Mertens
- Wout's mailing list and old digests coder@ibm.net
- Just a bit of musing Nathan Yospe
- Just a bit of musing Adam Wiggins
- Just a bit of musing coder@ibm.net
- Just a bit of musing Chris Gray
- Just a bit of musing Carter T Shock
- Just a bit of musing Chris Gray
- Just a bit of musing S001GMU@nova.wright.edu
- Just a bit of musing Dmitri Kondratiev
- Just a bit of musing Chris Gray
- Just a bit of musing Dmitri Kondratiev
- Just a bit of musing coder@ibm.net
- Just a bit of musing Jon A. Lambert
- Just a bit of musing coder@ibm.net
- Just a bit of musing coder@ibm.net
- Just a bit of musing clawrenc@cup.hp.com
- Just a bit of musing coder@ibm.net
- Just a bit of musing Carter T Shock
- Just a bit of musing Alex Oren
- Just a bit of musing Wout Mertens
- Just a bit of musing coder@ibm.net
- Just a bit of musing coder@ibm.net
- Just a bit of musing Wout Mertens
- Just a bit of musing Carter T Shock
- Just a bit of musing S001GMU@nova.wright.edu
- Just a bit of musing Chris Gray
- Just a bit of musing coder@ibm.net
- Just a bit of musing Nathan Yospe
- Just a bit of musing coder@ibm.net
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Adam Wiggins
- Just a bit of musing coder@ibm.net
- Just a bit of musing GnomesHome@aol.com
- Just a bit of musing Carter T Shock
- Just a bit of musing Chris Gray
- Just a bit of musing coder@ibm.net
- Just a bit of musing Adam Wiggins
- Just a bit of musing Chris Gray
- Just a bit of musing Adam Wiggins
- Just a bit of musing claw@null.net
- Just a bit of musing Chris Gray
- Just a bit of musing claw@null.net
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Chris Gray
- Just a bit of musing Carter T. Shock
- Just a bit of musing claw@null.net
- Just a bit of musing Wout Mertens
- Just a bit of musing coder@ibm.net
- Just a bit of musing Adam Wiggins
- Just a bit of musing coder@ibm.net
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Chris Gray
- Just a bit of musing Jon A. Lambert
- Just a bit of musing Travis Casey
- Just a bit of musing Jon A. Lambert
- Just a bit of musing clawrenc@cup.hp.com
- Just a bit of musing Nathan Yospe
- Just a bit of musing clawrenc@cup.hp.com
- Quadtrees? Wout Mertens
- Quadtrees? coder@ibm.net
- Quadtrees? Greg Munt
- Quadtrees? Ola Fosheim Grøstad
- Quadtrees? Ling
- Quadtrees? Miroslav Silovic
- Quadtrees? Chris Gray
- Quadtrees? Carter T Shock
- Quadtrees? S001GMU@nova.wright.edu
- 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 - Quadtrees? S001GMU@nova.wright.edu
- Quadtrees? Carter T Shock
- Quadtrees? coder@ibm.net
- Quadtrees? Chris Gray
- Quadtrees? Carter T Shock
- Quadtrees? coder@ibm.net
- Quadtrees? claw@kanga.nu