Hilbert Curves [was: "Re: [DGD] Rooms with Views" and "Re: [Mud-Dev] Physics"]

[Christopher Allen]

Recently on the Mud-Dev list <http://www.kanga.nu/lists/listinfo/mud-dev> there
has been some discussion of Physics, including properties of physical spaces,
and on the DGD-List <http://list.imaginary.com/mailman/listinfo/dgd> the
discussion recently is on how to have rooms with a view.

There is an excellent article in July 1999 issue of Dr. Dobbs 'Space-Filling
Curves in Geospatial Applications' by Ron Gutman on page 115, with the summary
"B-Tree databases are very efficient with one-dimensional data. Ron shows how
Hilbert curves can be used to efficiently manage multidimensional data, with no
changes to the underlying database".

Regrettably, it is not one of the free articles on their website, but you can
buy it for $4 at <http://www.ddj.com/articles/1999/9907/9907toc.htm>. More
importantly, though, there is free source code available at
<http://www.ddj.com/ftp/1999/1999_07/aa799.txt>.

The problem that Hilbert curves solve are when you have a number of items in a
2D space, and you want to find all the other items that are nearby. In mud
terms, these problems include how far you a shout can be heard, determine if the
tower in the distance is visible, etc. Using a *-tree index to answer these 2-D
space problems is very inefficient.

Instead, the 2D space is stretched out into a one dimensional list where every
2D cell is mapped to an ordered list. Items in 2D space are mapped to where on
that 1D string the item exists. Then a standard *-tree index can be used to
quickly find the items.

The trick is how to turn the 2D space into a 1D list that is efficient for
finding the items. There are several techniques, in particular Morton keys, that
have been used to do this as they offer a quad hierarchy. However, Hilbert
curves (which look similar to fractal curves) are even more efficient, in
particular for square 2D source regions, and square search regions. There is an
excellent primer on Hilbert curves at
<http://www.dcs.napier.ac.uk/~andrew/hilbert.html>, and some other Hilbert
source code in the Numerical Math Class Library at
<http://www.kanga.nu/mirrors/www.lh.com/%257Eoleg/ftp/LinAlg.README.txt>.

The article also hints at the end that Hilbert curves can also be used for 3D
cubic spaces and as an efficient (but non-optimal) solution to the traveling
salesman problem. The author Ron Gutman also claims but does not describe a
variant called "Hilbert R-Tree" that combines both Hilbert and R-Tree
techniques.

I searched the Mud-Dev list <http://www.kanga.nu/search.php3> on the topic of
Hilbert curve. There are some discussions of merits of Morton curves on Mud-Dev
already <http://www.kanga.nu/archives/MUD-Dev-L/1997Q1/msg00025.html>, but I
have not seen any discussion of Hilbert curves for spatial keys other then that
they are "kinda odd and computationally a bit nasty to work with" -- I hope that
people find them useful.

If anyone implements anything interesting with Hilbert curves, I'd be pleased to
find out about it.

------------------------------------------------------------------------
.. Christopher Allen                                 Skotos Tech Inc. ..
..                           1512 Walnut St., Berkeley, CA 94709-1513 ..
.. <http://www.Skotos.net>               o510/649-4030  f510/649-4034 ..




_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev