pftrails: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.

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) U_{t ∈ [0,1]} *f*(*t*) in the plane that has non-zero area^{1)}. 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 U_{t ∈ [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.

Plane-filling curves usually have a self-similar structure: the curve consists of a finite number of parts *f*_{1},… , *f*_{n}, 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 *f*_{i} of the curve, what similarity transformation maps the whole curve to the part *f*_{i}. 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 *f*_{i} 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 *f*_{i}, and it scales down and possibly reflects and translates the *t*-component of **v** to map the pre-image of *f* to that of *f*_{i}. Since each *M*(*i*) induces scaling down, any product of an infinite sequence of matrices *M*(*i*_{1}), *M*(*i*_{2}), *M*(*i*_{3}), … 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, *i*_{1}, *i*_{2}, *i*_{3}, *i*_{4}, *i*_{5}, … = 1, 2, 1, 2, 1, …, then we find that the product *M*(*i*_{1}) *M*(*i*_{2}) *M*(*i*_{3}) … 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.

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. Ventrella^{2)} uses a more compact notation system: for part *i*, we specify four numbers *x*_{i}, *y*_{i}, *d*_{i}, *o*_{i}; 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 (*x*_{i},*y*_{i}) relative to the endpoint the previous part, where *o*_{i} specifies the orientation (reflected or not), and *d*_{i} specifies the direction (forward or backward, that is, without or with reflection in the pre-image). For *i* ∈ {0,… , *n*}, we may now define *X*_{i} := ∑_{j≤i} *x*_{i}, *Y*_{i} := ∑_{j≤i} *y*_{i}, and *T*_{i} := ∑_{j≤i} ||(*x*_{i},*y*_{i})||^{2} / ||(*X*_{n},*Y*_{n})||^{2}. The transformation matrix *M*(*i*) is now derived as the unique transformation matrix that satisfies the following conditions: (1) if *d*_{i} = 1, then *f*(0) is mapped to (*X*_{i-1}, *Y*_{i-1}) and *f*(1) is mapped to (*X*_{i}, *Y*_{i}), whereas if *d*_{i} = -1, then *f*(1) is mapped to (*X*_{i-1}, *Y*_{i-1}) while *f*(0) is mapped to (*X*_{i}, *Y*_{i}); and (2) the transformation induces a reflection if and only if *o*_{i} = -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).

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: *x*_{i}, *y*_{i}, *z*_{i}, *d*_{i}, and *o*_{i}. 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 easy^{3)}.

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 *d*_{i} = *o*_{i} = 0 and whose norms do not count towards *T*_{i}, *T*_{i+1}, …, *T*_{n}.

pftrails/notation_for_plane-filling_curves.txt · Last modified: 2020/02/16 22:28 by administrator