Does anyone have or know of an algorithm to rotate a square 2D array clockwise 90, 180 or 270 degrees? I bet there’s a mathematical way to do this easily with matrix transpositions but it was a long time since I touched those subjects at school!
For example, given the array myArray(2,2):
1 2 3
4 5 6
7 8 9
How can I rotate this to:
7 4 1
8 5 2
9 6 3
Looking for the most efficient way to do this (as the array could be up to 100 x 100 in size. If possible, can this be done without creating a new array? Any thoughts?
Garry,
I would think that you just do some variation of the shuffle algorithm that Xojo has in their user guide:
Dim myArray(5, 5) As Text
For i As Integer = 0 To 5
For j As Integer = 0 To 5
myArray(i, j) = i.ToText + j.ToText
Next
Next
myArray.Shuffle
This came straight out of the Xojo users guide under Arrays. There is probably some uber hacker that can make this more efficient, but given the scope of what you want to do, I don’t know that this won’t work reasonably well. As to doing it in the same array, I’m kind of fond of leaving the original as is and creating a new one when manipulating data, it’s a lot easier to debug. But that’s just me.
You dont need to move anything about, as long as the retrieval time isnt important.
All you need to do is wrap the ‘get’ function up to look at a computed position.
Lets add an extra row before rotating
1 2 3
4 5 6
7 8 9
A B C
becomes
A 7 4 1
B 8 5 2
C 9 6 3
The 5 should be at 2,1 after rotation
[code]msgbox rotatedvalue(2,1)
private function rotatedvalue(x,y) as string
const arwidth = 2
const arheight = 3 //vary these for your array
return myArray( arheight-x, arwidth -y)
end function
[/code]
gets 3-2 = 2, 2-1 =1
and myArray(1,1) = 5
The Shuffle method randomly rearranges the array. I need to control the order, by rotating it 90 degrees as described above.
Garry,
Yes, the shuffle method randomly rearranges the array, which is why I said it needed to be a variation of that method. The concept is pretty much the same, a nested loop where the outer loop iterates across the x axis and the internal loop iterating down the y axis and having it create the pivoted array row by row.
However; maybe Jeff has a better solution for you.
Look up this elaborate discussion for Java:link text. There are several solutions posted. Shouldn’t be too hard to port this to Xojo.
Garry,
This one intrigued me and I had to take a shot at it. This is what I came up with:
PivotArry(xSize as Integer, ySize As Integer)
dim c As integer
dim r As Integer
for y as integer = 0 to ySize
c = 0
for x as integer = xsize to 0 step -1
pivotArr(r,c) = matrixArr(x,y)
c = c+1
next x
r = r +1
next y
I created a console application that created a 2 dimensional array setup like your example and this method pivoted the data 90 degrees just like you requested. As I said, it’s a variation of the shuffle example, but it works. For my test I made matrixArr and pivotArr both properties dimensioned to 100,100. I only did you test of a 2,2 so I’m not sure of the performance.
Now that I have that out of my head, I can get back to work. 
Hope this helps.
I should add that my method handles non- square arrays too. Garry: have you had a chance to try these?
Assuming a square array as was originally specified, the array can be rotated without having to make a separate copy as follows:
'rotate array a in place
n=ubound(a)
m=n\\2
m1=(n-1)\\2
for r=0 to m
for c=0 to m1
temp=a(r,c)
a(r,c)=a(n-c,r)
a(n-c,r)=a(n-r,n-c)
a(n-r,n-c)=a(c,n-r)
a(c,n-r)=temp
next
next
Sorry for the delay guys. I’m on holiday in rural France and it would seem that internet is a precious commodity here, as is permission to code from the wife!
First, thanks for all the responses.
I like Jeff’s approach of simply changing the index to use rather than rotating the array - very clever. I came up with the following function to “rotate” a 2D array either 0, 90, 180 or 270 degrees based on this approach. This only works on square arrays however (I don’t think yours works correctly on non-square arrays Jeff).
[code]function RotateArray(ByRef theArray() as Auto, x as Integer, y as Integer, rotation as RotateBy) as Auto
’ RotateBy is an enumeration specifying the rotation
dim temp as Integer
select case rotation
case RotateBy.None
return myArray(x, y)
case RotateBy.NinetyDegrees
temp = x
x = y
y = Ubound(myArray, 1) - temp - 1
case RotateBy.OneEightyDegrees
y = Ubound(myArray, 1) - y - 1
x = Ubound(myArray, 1) - x - 1
case RotateBy.TwoSeventyDegrees
temp = y
y = x
x = Ubound(myArray, 1) - temp - 1
end select
end function[/code]
I am going to try to find a little bit of time today to try Stewart and Rob’s attempts to see if they also validate. As a little bit of background, this is for rotating an isometric tile map in a game so I may end up altering how I draw the map rather than how I store the tiles in memory (in this array we are trying to rotate).
If your drawing code assembles the tiles as Object2d primitives, and you Group them, then you can rotate the entire group with a line of code.
Similarly, to draw them, you just draw the group, and it can be offset x or y to scroll, and rotated if you want.
(Although that would make a tile that looks like ^ become one that looks like > unless you rotated the primitives too)