User Tools

Site Tools


Notation for plane-filling curves

To be able to verify what can be seen in the plane-filling trails on this website, one needs a notation system to define a plane-filling curve.

A surjective mapping from 1D to 2D

Mathematically, a plane-filling curve is a continuous, surjective mapping f from the unit interval (all numbers t ∈ [0,1]) to an image (a set of points) Ut ∈ [0,1] f(t) in the plane that has non-zero area1). The image may be a simple shape such as a square or a triangle, but it could also be something more adventurous. We can trace the curve by going through the points f(t) as t increases from 0 to 1. The mapping is usually chosen such that it is measure-preserving, that is, if we let t go from 0 to 1 at constant speed, then we fill the plane at constant speed. More precisely: for any interval [a,z] ⊂ [0,1], its image Ut ∈ [a,z] f(t) has measure (area) z - a, where we take the area of the complete image of the curve as the unit of area. Thus, f(t) is the point where the curve has arrived after filling a fraction t of the complete image.

Capturing the self-similar structure

Plane-filling curves usually have a self-similar structure: the curve consists of a finite number of parts f1,… , fn, each of which are similar to the curve as a whole. Each part covers a part of the pre-image and the image of the curve, such that together, the parts cover, that is, tessellate, the complete pre-image [0,1] and the complete image. To define a particular plane-filling curve, one has to specify, for each part fi of the curve, what similarity transformation maps the whole curve to the part fi. We can express this concisely with matrix multiplications, as follows. We regard a point f(t) = (x,y) of the curve as a four elements' column vector (x,y,t,1). For a part fi of the curve, we specify the corresponding similarity transformation as a 4 × 4 matrix M(i), such that if and only if v = (x,y,t,1) is a point of the curve, then M(i) v is a point of the curve. The matrix M(i) is of a restricted type: it scales down and possibly rotates, reflects and translates the x and y components of v to map the image of f to that of fi, and it scales down and possibly reflects and translates the t-component of v to map the pre-image of f to that of fi. Since each M(i) induces scaling down, any product of an infinite sequence of matrices M(i1), M(i2), M(i3), … with v converges to a vector that is independent of v. In the end, the curve consists of the relations f(t) = (x,y) that are described by the vectors of convergence for all infinite sequences of matrices chosen from M(1),…,M(n).

For example, if we place Pólya's curve for an isosceles right triangle such that it starts at the point with coordinates (0,0) and ends at (2,0), then it is described by the following matrices:

If we take, for example, i1, i2, i3, i4, i5, … = 1, 2, 1, 2, 1, …, then we find that the product M(i1) M(i2) M(i3) … converges to a matrix whose last column is (4/5, 2/5, 1/3, 1) and all other entries are zero; thus, f(1/3) = (4/5, 2/5) is a point of the curve.

Concise notation

Any notation system for plane-filling curves specifies the matrices M(i) in one way or another. Actually writing out 16-element matrices would, usually, be unnecessarily cumbersome. Ventrella2) uses a more compact notation system: for part i, we specify four numbers xi, yi, di, oi; the last two must be -1 or 1. That is it. These numbers are to be interpreted as follows: the curve starts at the origin of the coordinate system, and part i ends at the point (xi,yi) relative to the endpoint the previous part, where oi specifies the orientation (reflected or not), and di specifies the direction (forward or backward, that is, without or with reflection in the pre-image). For i ∈ {0,… , n}, we may now define Xi := ∑ji xi, Yi := ∑ji yi, and Ti := ∑ji ||(xi,yi)||2 / ||(Xn,Yn)||2. The transformation matrix M(i) is now derived as the unique transformation matrix that satisfies the following conditions: (1) if di = 1, then f(0) is mapped to (Xi-1, Yi-1) and f(1) is mapped to (Xi, Yi), whereas if di = -1, then f(1) is mapped to (Xi-1, Yi-1) while f(0) is mapped to (Xi, Yi); and (2) the transformation induces a reflection if and only if oi = -1.

This essentially describes Ventrella's notation for “square” grids, that is, when the x and y coordinates are to be interpreted as standard Cartesian coordinates. With Ventrella's notation, we can format the numbers for, for example, Pólya's curve as follows:

Square grid
2 segments

segment values:
1: 1, 1, 1,-1
2: 1,-1, 1,-1

On this web page, we will write this more compactly as (1,1,1,-1)(1,-1,1,-1).

Triangular-grid coordinates

Many plane-filling curves are more naturally described using coordinates on a triangular grid. Points and vectors in the plane are then specified by three coordinates x, y, z, where the x-axis points east, the y-axis points 30 degrees west of south, and z-axis points 30 degrees west of north. Two points are the same if their coordinates differ by (α,α,α), for any α. Segments of a plane-filling curve are now described by five numbers: xi, yi, zi, di, and oi. For clarity, we will prefix the curve definition with the symbol Δ if we use triangular-grid coordinates. Our notation differs from Ventrella's notation for triangular grids, but conversion is easy3).

Plane-filling curves with jumps

Database literature and applications commonly include plane-filling “curves” that contain discontinuities, that is, places where the curve jumps from one point to another 4)5). In that case, there will be values of t that are associated with two different points (x,y): the point before the jump and the point after the jump. Note that this poses no problem for our matrix-based approach to specifying plane-filling curves. It would also be easy to insert discontinuities in Ventrella-style specifications: to this end, we would simply allow segments that have di = oi = 0 and whose norms do not count towards Ti, Ti+1, …, Tn.

1) Technically, we will measure the area by Jordan content.
2) J. Ventrella. Brainfilling curves: a fractal bestiary. Self-published / Eyebrain Books, 2012.
3) A vector (x,y) in Ventrella's triangular-grid notation corresponds to a vector (x+α,-y+α,α) in our notation, for any real number α.
5) H. Samet. Foundations of multidimensional and metric data structures, section “Ordering Space”, p 199. Morgan Kaufmann, 2006.
pftrails/notation_for_plane-filling_curves.txt · Last modified: 2020/02/16 22:28 by administrator