Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

1. Overview

In this tutorial, we’ll study an algorithm for traversing the elements of a matrix in a square spiral.

2. What Is a Spiral?

A spiral is a curve that originates from a point called the center and progressively gets farther as it winds around it. In a polar plane, a spiral has the form of a continuous monotonic function f that relates the angle \theta to the radius r, as r = f(\theta). This is the graph of one of the most common spirals, the spiral of Archimedes:

spiral continuous

Generalized algorithms for computing spirals that extend over surfaces with arbitrary shapes also exist. For looping over matrices, however, a slightly different definition is needed.

3. Spirals and Matrices

In relation to matrices, the spiral that loops over its elements is called a square spiral. A square spiral has this shape:

square spiral

Because we can’t define it as a continuous function, we can instead define it procedurally. It’s intuitive to understand how it functions, if we imagine traversing a matrix in a spiral fashion starting from one of its elements. Let’s use this sample matrix:

\begin{bmatrix} e_{1,1} & e_{1,2}  & e_{1,3} \\ e_{2,1} & e_{2,2}  & e_{2,3} \\ e_{3,1} & e_{3,2}  & e_{3,3} \\ \end{bmatrix}

We can indicate with numbers the order in which the elements have to be traversed, starting from 1, to produce a square spiral. Traversing the matrix in spiral then corresponds to vectorizing it by starting from one corner and looping over all elements, and then terminating in the center:

\begin{matrix} \text{Clockwise} & \text{Counter-clockwise} \\ \text{traversal} & \text{traversal} \\ \begin{bmatrix} 1 & 2  & 3 \\ 8 & 9 & 4 \\ 7 & 6  & 5 \\ \end{bmatrix} & \begin{bmatrix} 1 & 8 & 7 \\ 2 & 9 & 6 \\ 3 & 4  & 5 \\ \end{bmatrix} \end{matrix}

Or, alternatively, by starting from the center and then terminating in one of the corners:

\begin{matrix} \text{Clockwise} & \text{Counter-clockwise} \\ \text{traversal} & \text{traversal} \\ \begin{bmatrix} 9 & 2  & 3 \\ 8 & 1 & 4 \\ 7 & 6  & 5 \\ \end{bmatrix} & \begin{bmatrix} 9 & 8 & 7 \\ 2 & 1 & 6 \\ 3 & 4  & 5 \\ \end{bmatrix} \end{matrix}

The traversal occurs by moving in one direction by i steps, then rotating, then moving i more steps, then rotating, then incrementing the counter i:= i+1 and repeating. Notice also how the traversal from the center to the corner is simply a reversal of the traversal, and that this is valid for both clockwise and counter-clockwise spirals.

4. Non-Square Matrix

If the matrix is non-square, and has N rows and M columns, such that N>M \vee M>N, then we’ll need some extra steps. We’ll first extend it to the square matrix A of size A_{P, P}: P ={max}(N, M), and then skip all elements that are present in the square but not in the rectangular matrix:

\begin{matrix} \text{3 by 5 Spiral} \\ \begin{pmatrix}\O & \O & \O & \O & \O \end{pmatrix}\\ \begin{bmatrix} 15 & 9 & 2  & 3 & 10\\ 14 & 8 & 1 & 4 & 11\\ 13 & 7 & 6  & 5 & 12\\ \end{bmatrix}\\ \begin{pmatrix}\O & \O & \O & \O & \O \end{pmatrix} \end{matrix}

We’re now going to study the algorithm that performs this traversal. One last note before that: instead of using rows and columns as a coordinate system, it’s more practical to shift the origin to the center of the matrix. This means that, if N and M are odd, we place the origin (0; 0) to ( \frac{N+1}{2}; \frac{M+1}{2} ):

grid

4. Traversing From Center to Corner

We can now study an algorithm that traverses the matrix from the origin (0; 0), up to the corner (-\frac{N+1}{2}; -\frac{M+1}{2}), in a square spiral. To build one, we need to define two pointers x, y that store the coordinates of the current element relative to the center, and two direction vectors dx, dy = \pm 1. The algorithm is this:

Rendered by QuickLaTeX.com

When executed on a 3 by 5 matrix, as in the example above, the algorithm produces the traversal in the expected order:

output MiLSsl

We can also define a counter-clockwise rotation, by simply modifying slightly the second if statement:

Rendered by QuickLaTeX.com

And as expected, this is the output with a 3 by 7 matrix:

output fw6osf1

5. Traversing from Corner to Center

If we want instead to traverse the matrix from a corner to the center, we can refer to the consideration we made above. All that we need to do is to store in a list the order of traversal and then reverse it.

For example, this is the reverse spiral traversal of a 5 by 7 matrix:

reverse1

6. Conclusion

In this article, we studied how to loop over the elements of a matrix in a square spiral pattern.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!