Traversing the Triangle Elements of an Icosahedral Spherical Representation in Constant-Time

摘要

Techniques are presented for moving between adjaceent triangles of equal size in a hierarchical representation for spherical data that is projected onto the faces of an icosahedron. The faces of the icosahedron are represented by a triangular quadtree. The operations are analogous to those used for a quadtree representation of data on the two-dimensional plane where the underlying space is tessellated into squares. A new technique is presented for labeling the triangular faces as well as the smaller triangles within each of the triangular faces of the icosahedron. The labeling enables the implementation of the quadtress corresponding to the individual triangle faces of the icosahedron as linear quadtrees (i.e., pointer-less quadtrees). Outlines of algorithms are given for traversing adjacenet triangles of equal size in constant time. The labeling and algorithms can also be used with minor modification (and no change from a computational complexity standpoint) with a hierarchical representation for spherical data that is projected onto the faces of an octahedron.