Hierarchical Triangular Mesh

http://www.sdss.jhu.edu/htm/

Everyone knows how to subdivide Euclidean space with quad-trees or 
space-filling curves, but what about subdividing the sphere?
Projections abound for mapping the sphere to the plane, but these 
projections create singularities, introduce discontinuities, and 
suffer from anisotropy, nonuniformity or both. Hierarchical Triangular 
Mesh (HTM) is a uniform way to recursively decompose the sphere into 
labelled spherical triangles and to convert spatial queries into sets 
of these triangles. HTM was designed for indexing astronomical data, 
but should work just as well for geographical data or anything else
associated with a sphere. C++ and Java libraries are included.
(Submitted by Ico Doornekamp.)

See also HEALPix <http://www.eso.org/science/healpix/> (a quadrilateral
subdivision with FORTRAN code) and Clive Page's survey article 
"Indexing the Sky" <http://www.star.le.ac.uk/~cgp/ag/skyindex.html>.
_______________________________________________
sweetcode mailing list
http://lists.ofb.net/listinfo/sweetcode
http://sweetcode.org/