Rotate Y-Axis of a 2D Vector
— By Yasin
So you want to rotate a vector, huh?
The solution I'm going to describe works well with both two-dimensional and multidimensional vectors if applied correctly. It is originally based on John Bentley's Reverse Rotate algorithm but with a teeny tiny twist. So, if you want to understand how this algorithm works, you have to read that article first.
All I did was invert the indices for
down shift operations to
achieve complement sub-vectors and . This makes the algorithm more
efficient and agile for dynamic programming.
Note that I have utilized generics in both functions to accept different types.
[T any] allows multiple types as the argument (you may change this to any
concrete type you desire). Additionally, we use an enumeration called
Direction to improve the clarity of the code.
Suppose you want to shift up all the 2D vector columns by
Suppose you want to shift down all the 2D vector columns by
Y-Axis Column Rotation
If you want to rotate specific columns with variable shifts. We need a bit
reverseRotate. In such a case, the problem is a bit hard because
when we think of it as columns, each element index is located in a different
array. I devised a 3-step solution, which works for me right now (I want to
keep it super simple).
For example, let's say we have a
3 x 3 matrix.
Here, the challenge is to shift columns
3 up by 1 and 2 consecutively
instead of rotating the entire facet. Let's take a more complex input
to understand how we can do it.
Suppose you have a
6 x 6 matrix.
And then, each column of the matrix has to be shifted up a variable amount of
We could do this in three easy steps. First, copying the target column to a temporary
vector, then rotating it using
reverseRotate, and finally reassigning the values
for the source vector. However, this takes time and uses space to hold
the temporary vector while iterating each column.
Here's the code for it: -
Also, note that
ReduceShifts is a small optimization I've implemented for the algorithm.
For example, if we receive the delta array
[ 4,5,6,6,4,3 ], we can find the minimum
delta and rotate the entire facet times. Here, the minimum is . So we
rotate the whole facet times. Once rotated, we can reduce the shifts of each
delta by the minimum rotations we did, and we are left with new changes
[1, 2, 3, 3, 1, 0].
Effectively reducing several iterations of the algorithm.
How to use this function, so? Simple!
Bonus: Shift Left & Right
If you want to shift in the
x-axis, then you have to iterate through each sub-vector
2D vector to achieve the outcome. For example, you could do the following: -
Left and right shifts yields a running time of with space in-place shifting. But why run sequentially, when you can parallelize 😎 *? Reverse Rotate algorithm is an absolute gem ✨💎.
That's it folks!