User Tools

Site Tools


pftrails:discontinuous_traversals

Plane-filling trails for discontinuous traversals

On this page we see plane-filling trails visualizing the jumping Lebesgue/Z/Morton, U, Gray-code, Double-Gray-code, Inside-Out, Burstedde-Holke, and Hill-Z traversals. The Lebesgue curve is one of the classical plane-filling curves; the others have appeared in the computer science literature1). All of them have jumps, that is, they must be described as plane-filling curves that contain sections that do not cover any area, or they must be described as maps that are not continuous and not one-to-one. For this reason, we call these maps traversals rather than plane-filling curves.

Z traversal / Lebesgue curve / Morton indexing

Definition: (1,1,1,1)(0,-1,0,0)(1,1,1,1)(-2,0,0,0)(1,1,1,1)(0,-1,0,0)(1,1,1,1)

In this rendering, the squares that are filled are moved slightly apart to make space for drawing the jumps as horizontal corridors.

z-traversal.jpg

Schrack and Liu's U traversal

Definition: (1,0,1,1)(-1,1,0,0)(1,0,1,1)(1,0,1,1)(-1,-1,0,0)(1,0,1,1)

In this drawing, the diagonal jumps of the traversal are drawn as paths that follow a slide detour along the “mountain” side, from which they are suspended or cut out.

u-traversal.jpg

Gray-code traversal

Definition: (1,0,1,1)(0,2,0,0)(-1,0,-1,-1)(2,0,0,0)(1,0,1,1)(0,-2,0,0)(-1,0,-1,-1)

The jumps of this traversal appear as bridges and tunnels.

gray-code.jpg

Faloutsos's Double-Gray-code traversal

Definition: (1,0,1,1)(0,2,0,0)(-1,0,-1,1)(2,0,0,0)(-1,0,1,1)(0,-2,0,0)(1,0,-1,1)

The jumps of this traversal appear as bridges and tunnels.

double-gray-code.jpg

Inside-Out traversal

Definition: (-1,0,1,1)(0,2,0,0)(1,0,-1,1)(2,0,0,0)(1,0,1,1)(0,-2,0,0)(-1,0,-1,1)

The jumps of this traversal appear as bridges and tunnels.

inside-out.jpg

Burstedde-Holke traversal

Definition: (1,1,1,1)(-1,0,0,0)(1,1,1,1)(-1,-1,0,0)(1,1,-1,-1)(0,-1,0,0)(1,1,1,1)

The visualization shows the middle two of the four sections of the traversal.

burstedde-holke.jpg

Hill-Z traversal

Definition: (1,1,1,1)(-1,0,0,0)(1,1,1,1)(-1,-1,0,0)(1,1,1,-1)(0,-1,0,0)(1,1,1,1)

The visualization shows the middle two of the four sections of the traversal.

hill-z.jpg


1) For alternative descriptions and for precise references, check out my paper Sixteen space-filling curves and traversals for d-dimensional cubes and simplices
pftrails/discontinuous_traversals.txt · Last modified: 2020/04/04 07:24 by administrator