Approximate rotations of the square lattice

Orbits of points under approximate rotation.

Rotation of the integer lattice

Rotation of a point \((x,y)\) by angle \(\phi\) is given by the following linear transformation:

$$\begin{align} x_1 &= \cos(\phi)x-\sin(\phi)y\\ y_1 &= \sin(\phi)x+\cos(\phi)y \end{align}$$

Consider square lattice \(\mathbb{Z}^2\): the set of plane points with integer coordinates. Square lattice is a natural model for raster images, where lattice points represent pixels. It is impossible to rotate such lattice \(\mathbb{Z}^2\) by an angle other than \(\pi k/2\, k \in \mathbb{N}\), because for any other angle coordinates of the rotated points will not be integer. It is, however, possible to make an approximate rotation.

The simplest approach is the nearest-point approximation: after transforming, use the nearest point with integer coordinates. However, such rotation with nearest-point approximation is not very elegant mathematically (well, it's just my impression), because it is not a bijection. This means that sometimes, 2 different points of the original are mapped the the same target point, and some target points don't have any original. This also means that such approximate rotation is not reversible: information is lost during the transform.

How to find a more elegant, bijective approximation? Here is a way.

Shear transform

There is an affine transform that is simpler than rotation: shear. Horizontal shear is defined as:

$$ \begin{align} x_1 &= x + ky\\ y_1 &= y \end{align}$$

Here \(k=\tan \phi\) is the shear coefficient and \(\phi\) is the shear angle. Similarly to rotation, shear is unitary: it preserves the area. Indeed, shear with non-integer coefficient will not map integer lattice to itself, and some approximation is needed. Let's take a nearest-point approximation again:

Approximate shear. Note that it is a bijective mapping.

Contrary to the rotation, this approximated transform is clearly a bijection! Each source point is unambiguously mapped to one target point, and vice versa.

Rotation by shears

In the previous post, it was shown that every rotation with angle \(\phi\) can be decomposed to 3 horizontal and vertical shears with coefficients \(\tan(\phi/2), -\sin\phi, \tan(\phi/2)\) correspondingly. Let's replace ideal shears with approximated:

Composition of 3 approximate shears gives approximate rotation.

Because the resulting transform is a composition of bijections, it is a bijection too. This gives a bijective approximation to rotation of integer lattice. The total transform is described by the equations: $$\begin{align} x'&= x + \lfloor \tan(\phi/2)y\rceil \\ y_1&= y - \lfloor \sin(\phi) x'\rceil \\ x_1&= x'+ \lfloor \tan(\phi/2)y_1\rceil \end{align} $$

Here, \(\phi\) is the rotation angle, (x, y) is the original point and (x₁, y₁) is the rotated one; "broken" braces denote nearest integer. The resulting transformation produces a bit more "noise" compared to the simple rotation with nearest-point approximation, but it gives one-to-one correspondence between the original and rotated image.

Approximate rotation compared to exact rotation.

If the rotation angle varies continuously, transformed image will move like below. Note that the number of pixels of each color never changes - it's a consequence of the bijective nature of the transform.

Animated approximate rotation. Number of cells of each color remains constant.

Orbits

Take some point and apply approximate rotation to it iteratively. If the rotation were exact, the point would move by circular orbit around the center of rotation. However, under the approximate rotation, the point would step away from the ideal circle.

Because the transform is bijective, all orbits will be either closed (cyclic) or infinite. No orbits will ever collide. Because integer rotation approximately preserves distance from point to the origin, cyclic orbit are more likely.

Orbits under the approximate rotation by \(\pi/5\).

The animation above demonstrates some orbits, obtained by iterating approximate rotation by \(\pi/5\). First part of this animation shows separate points of one of the orbits. Second part shows multiple orbits, each colored in a different color.

By painting different orbits with different colors, a colorful images resembling fractals can be generated. On these images, different orbits were painted with different colors. To make images more visually appealing, nearby orbits were colored with similar colors. The monochrome pictures are showing length of the orbit, by modulo 256. All these pictures share the invariance property: they are exactly preserved during corresponding integer rotations. In other words, they are the fixed point of the approximate rotation.

Source code to generate such images (C++).

Some additional examples (more in the gallery). Click to view full image. (Warning: big image files.)

2π/7 (2048 x 2048)

4π/9 (2048 x 2048)

5π/9 (2048 x 2048)

(2π/7)⁷: on each step, point was approximately rotated 7 times. (2048 x 2048)

(2π/5)⁵ (2048 x 2048)

2π/5, orbit length. (1024 x 1024)

π/3, orbit length (1024 x 1024)

Finite orbit conjecture

Numeric tests show that orbits are always closed, no orbit goes infinitely. Intuitively, it seems to be viable because approximate rotation nearly preserves distance from the point to the center. Thus, one can expect that some point will eventually hit its own trail. However, I don't see any way to prove it.