We show how to build a continuous, one-dimensional index of the points on a triangulated irregular network (TIN). The index is constructed by first finding an ordering of the triangles in which consecutive triangles share a vertex or an edge. Then, the space within each triangle is continuously indexed with a space-filling curve that begins at one vertex of the triangle and ends at another. The space-filling curve is oriented such that the first point in each triangle is a vertex shared with the previous triangle and the last point is a vertex shared with the next triangle. Furthermore, our index can be refined locally and, therefore, efficiently when the TIN is augmented by filling any face with another TIN (to make a hierarchical TIN). Such processes arise, for example, in the elaboration of detail on a graphical surface.

We describe how to create a continuous global index of the surface of the Earth. The index is based on a hierarchical subdivision of the surface into triangular regions in which each region is assigned a numerical label according to a spacefilling curve. Sequential labels are assigned to adjacent regions, so labels can be sorted to create a continuous one-dimensional index. Benefits of continuity include the implicit preservation of adjacency information, and the ability to vary resolution at different locations. Previously suggested schemes based on similar models produce indices that are discontinuous. Unfortunately, discontinuities degrade the usefulness of an index, as we show by comparing continuous and discontinuous schemes based on performance criteria such as the ability to preserve spatial adjacency. The best index appears to be the continuous one based on the Sierpinski spacefilling curve.

Abstract We describe a method, based on vertex‐labeling, to generate algorithms for manipulating the Hilbert spacefilling curve. The method leads to algorithms for: computing the image of a point in R1; computing a pre‐image of a point in R2; drawing a finite approximation of the curve; finding neighbor cells in a decomposition ordered according to the curve. The method is straightforward and flexible, resulting in short, intuitive procedures that are as efficient as specialized procedures found in the literature. Moreover, the same method can be applied to many other spacefilling curves. We demonstrate vertex‐labeling algorithms for the Sierpinski and Peano spacefilling curves, and variations. Copyright © 2001 John Wiley & Sons, Ltd.

To construct a short tour through points in the plane, the points are sequenced as they appear along a spacefilling curve. This heuristic consists essentially of sorting, so it is easily coded and requires only O ( N ) memory and O ( N log N ) operations. Its performance is competitive with that of other fast methods.