Array-Inhalt drehen

Servus,

Ich würde gerne auf den Inhalt eines Arrays gedreht zugreifen. Sprich:
[9][1]
[2][6]
[0][4]
Und wenn ich per getValue( x, y ) darauf zugreife, den Wert zurückbekommen, als wäre das Array um den 0-Punkt (unten-links) gedreht.
Klar kann man das Array nur in 4 Stufen drehen, 0°, 90°, 180°, 270°.

Sprich wenn ich folgendes Aufrufe get( 1, 1, 90° ); soll “2” ausgegeben werden - statt 6 - wie als wenn das Array intern so aussehen würde:
[0][2][9]
[4][6][1]

Irgendwie stehe ich dabei auf dem Schlauch, und zwar mächtig.
Ich habe zwar Rotationsmatrizen erstellt (hier für 90° im Uhrzeigersinn)
[0][-1]
[1][0]
aber ich komme trotzdem nicht auf ein richtiges Ergebnis (für 0|0 soll 1|0):
[ 0][-1] - 00+0-1 = 0
[ 1][ 0] - 01+00 = 0
Irgendwie muss ich, denke ich, noch die Gesamtlänge W und H des Arrays mit in die Rechnung verwursten.

Eigentlich habe ich lange mit Matrizen seitens OpenGL gearbeitet, aber irgendwie steh ich hier auf dem Schlauch.

Danke schon einmal.

Nimm mal ein einfacher Beispiel, einen einfachen Spaltenvektor (A)

[6]
[5]
[4]

Drehe diesen um 90 Grad, so wird daraus ein Zeilenvektor (B)

[4][5][6]

(0,2) von A = 6

(2,0) von B = 6, also wird der y-Wert bei der Drehung zum x-Wert.

Dreht man jetzt B um weiter 90 Grad, erhält man einen Umgekehrten Spaltenvektor ©

[4]
[5]
[6]

(0,0) von C = 6, aus dem x-Wert bei B, wird ein y-Wert von 0 bei C.

Das könnte man durch die Länge von B, (also den höchsten Index hier 2) Minus des x Wertes bekommen.

folglich entspricht

get(x,y,90) einem get(y, maxIndexVonX-x, 0)

Das kommt daher, da das Array wenn es gedreht würde ansonsten ja einen negativen Index bräuchte und der y-Achse entlang um den maxIndex nach oben geschoben wird um positive Indizes zu bekommen.

1 „Gefällt mir“

Vorneweg: Das mit den Matrizen ist ziemlich gewagt. Jeder „Normale Mensch ®“ würde das mit einem switch(rotationSteps) machen und händisch aufdröseln. Und damit wäre das ziemlich trivial. Aber so es ist zumindest interessant :smiley:


(Irgendwann ist mir mal aufgefallen, dass die Veränderungen der Einträge (!) von (3D) Rotationsmatrizen für die Anwendung auf verschiedene Achsen wieder durch Lineare Transformationen abbildbar sind: Rotation matrix - Wikipedia : Von x nach z ist es eine Translation um (-1,-1). Von x nach y ist es eine Skalierung um Faktor 1.5 und eine Spiegelung an der Hauptdiagonalen. Aber das nur nebenbei :nerd: )


Vielleicht würde es schon helfen, in die Arrays die Koordinaten für die Addressierung reinzuschreiben…

      [2,0][2,1]
      [1,0][1,1]
      [0,0][0,1]

Wenn der nun um 90° CW gedreht wird, dann vermutlich um (0,0). Was da rauskäme wäre

      [0,0][1,0][2,0]
      [0,1][1,1][2,1]

Aber wenn der nach dem gleichen Muster (von unten nach oben, und in jeder Zeile von links nach rechts) durchnumeriert werden sollte, wäre das ja

      [1,0][1,1][1,2]
      [0,0][0,1][0,2]

Der Ursprung ist ja woanders. Oder auf dein Beispiel bezogen: Einmal ist der Ursprung bei [0], und einmal ist er bei [4].

Ich glaube, dass nicht der array gedreht wird, sondern die Addressierung (in OpenGL: Man dreht nicht das Objekt, sondern die Kamera :smiley: ). Deswegen gehe ich davon aus, dass man den Adressierungspunkt nicht mit der Matrix transformieren darf, die man auf den Array anwenden würde, sondern mit der inversen davon. Außerdem gehe ich davon aus, dass man das nicht nur mit Rotationsmatrizen (und ohne händische Verschiebungen) abbilden kann - da kommen ja ein paar Minusse vor, und Arrays mögen Minusse gar nicht :smiley: Ich denke also, dass man den Zugriff immer noch „zurechtbiegen“ muss, damit man nur auf positive indizes zugreift - und auf die richtigen. Man muss also dafür sorgen, dass die Adressierung (zusätzlich zur Drehung) noch in der richtigen Ecke anfängt.

In jedem Fall erscheint das ziemlich kompliziert. Oder ich stehe auch auf dem Schlauch, und zwar mächtig (das ist gut möglich (übermüdet)). Ich hab’ zwar mit viel Rumprobiererei etwas hingefrickelt…

// For https://forum.byte-welt.net/t/array-inhalt-drehen/19341
package bytewelt;

import java.awt.Point;
import java.awt.geom.AffineTransform;

public class RotatedArrayAccess
{
    public static void main(String[] args)
    {
        int array[][] = {
            { 0, 1 },
            { 2, 3 },
            { 4, 5 }
        };
        
        for (int i = 0; i < 4; i++)
        {
            System.out.println("Rotated " + i + " steps");
            int rows = getRows(array, i);
            int cols = getCols(array, i);
            System.out.println("    rows " + rows);
            System.out.println("    cols " + cols);
            for (int r = rows-1; r >= 0; r--)
            {
                for (int c = 0; c < cols; c++)
                {
                    System.out.printf("%3d", get(array, r, c, i));
                }
                System.out.println();
            }

        }
    }
    
    private static int get(int[][] array, int r, int c, int rotationSteps)
    {
        Point p = new Point(c, r);
        int rows = array.length;
        int cols = array[0].length;
        int rMax = rows - 1;
        int cMax = cols - 1;
        Point rotatedMax = rotate(cMax, rMax, rotationSteps);
        int cMinMax = Math.min(0, rotatedMax.x);
        int rMinMax = Math.min(0, rotatedMax.y);
        Point rotatedMin = rotate(cMinMax, rMinMax, -rotationSteps);
        int rMin = rotatedMin.y;
        int cMin = rotatedMin.x;
        AffineTransform at = new AffineTransform();
        at.concatenate(rotation(-rotationSteps));
        at.transform(p, p);
        int ar = (rMin+p.y);
        int ac = (cMin+p.x);
        return array[ar][ac];
    }
    
    private static AffineTransform rotation(int rotationSteps)
    {
        int steps = rotationSteps % 4;
        if (steps < 0)
        {
            steps += 4;
        }
        return AffineTransform.getQuadrantRotateInstance(-steps); 
    }

    private static Point rotate(int x, int y, int rotationSteps)
    {
        Point p = new Point(x, y);
        rotation(rotationSteps).transform(p, p);
        return p;
    }
    
    private static int getRows(int array[][], int rotationSteps)
    {
        return Math.abs(rotate(array.length, array[0].length, rotationSteps).x);
    }
    
    private static int getCols(int array[][], int rotationSteps)
    {
        return Math.abs(rotate(array.length, array[0].length, rotationSteps).y);
    }
}

aber wie man sieht: „Schön“ ist das nicht. Mach’ einfach ein switch :wink:


Schön, eine Frage zu sehen, bei der man sich beim Titel denkt: „Joa, worum geht’s? Quadratischer 2D-Array mit umkopieren, oder diese [0,1,2,3]->[3,0,1,2]-Operation (die auch „Rotation“ heißt)?“, und dann beim Autor schon stutzt, beim Durchlesen merkt, dass es nicht um eine Trivialität geht, und beim genaueren Überlegen+Implementieren dann denkt: "Sh!t, bin ich jetzt blöd?! :dizzy_face: " :smiley:

1 „Gefällt mir“

Sehr gut, danke euch beiden, ich bin der Lösung jetzt ganz nahe, es fehlt nur noch das letzte Puzzleteil, dann kann ich die Lösung hier ausführlich beschreiben!
Und zwar suche ich eine Gleichung für die gilt f(1)=0, f(0)=0 und f(-1)=1
Bin schon am rumprobieren, irgendwie müsste sich die 1 selber nullen, aber bei -1 dürfte das nicht mehr passieren.
Irgendwie in dem man *-1 oder *1 berechnet und dadurch sich das Ergebnis verändert.

Ich frage mich ob das mit Wolfram irgendwie ginge. Ist doch sonst so schlau…


*Edit
Die Zwischenlösung sieht im Moment so aus:

x2 = r1 * (x1 + w/2 * (r1-1)) + r2 * (y2 + h/2 * (r2 - 1)) y2 = r1 * (y1 + h/2 * (r1-1)) - r2 * (x1 - w/2 * (r2 - 1))
Wobei

w = array.length - 1
h = array[0].length -1

und r1 und r2 respektive für die 4 rotation steps

000° [1][0]
090° [0][1]
180° [-1][0]
270° [0][-1]

Hergeleitet mit der Schlüsselgleichung f(z) bei der gilt f(1)=0, f(0)=0 und f(-1)=1

f(z)=(z²-z)/2

Damit bin ich aber noch nicht ganz zufrieden, ich frage mich ob es eine noch bessere Gleichung damit die End-Gleichung (oben) nicht so kompliziert wird.

DIe ganzen Arrays und ihre “(r,c)”-Addressen aufzuschreiben und als großen Haufen von Gleichungssystemen anzusehen, kam mir auch in den Sinn. Aber da man auch eine Translation braucht, müsste man da ja mit einer 3x3-Matrix rechnen, was auch wieder un-intuitiv wirkt.

Die Zwischenlösung habe ich jetzt noch nicht nachvollzogen, aber … für die gesuchte Funktion gäbe es ja einen Haufen möglicher Lösungen. Irgendwas mit Math.sign oder Math.abs wäre vermutlich wieder zu sperrig. Vielleicht

f(x) = (1-x) / 2

(mit int, natürlich) ? Da wäre

f( 0) = (1-  0)  / 2 = 0
f( 1) = (1-  1)  / 2 = 0
f(-1) = (1-(-1)) / 2 = 1
1 „Gefällt mir“

WolframAlpha gibt mir neben meiner bereits gefundenen Gleichung noch diese Annäherung hier
0.000720776 * e^(-7.23508 x)
Auch ganz witzig, wenn auch uninteressant.

Interessante Idee sich das integer-Verhalten zunutze zu machen.
Das funktioniert auch, gut sogar.
Rein zu Auswahlzwecken habe ich beide Formeln durch einen Profiler laufen lassen und deine ist fast doppelt so schnell. Selbst wenn ich versuche zu schummeln und meiner Gleichung mit if-Anweisungen auf die Sprünge helfe ist die benötigte Zeit für 100Milliarden Berechnungen größer gleich.
Einen guten Tick schneller geht es nur wenn ich deine Gleichung mit if-Anweisungen ausschmücke, wobei von der ursprünglichen Gleichung dann auch fast nichts mehr übrig bleibt. :smiley:

Und daraus habe ich schlussendlich durch logische Überlegung eine 12 Matrix gemacht.
Im Grunde logisch, bedenkt man dass wir nur 4 Rotationsmöglichkeiten haben, eine 3
3 Matrix aber einen viel höheren Informationsgehalt hat.

Ich mach jetzt erstmal eine deftige Pause. Schreibe eine richtige Klasse daraus und dann wie ich auf die Formel oben gekommen bin…

Ja, gut, wenn man mit if-Abfragen anfängt…

return x==-1 ? 1 : 0;

:wink:

hust ja schon, hatte gehofft dass durch die Beschreibung durch eine Gleichung sich die Endgleichung kürzen lässt. :disappointed_relieved:


Falls es jemanden interessieren sollte, noch die Herleitung und das Endergebnis. Es fängt langsam an und wird in der zweiten Hälfte interessanter.
Danke an @ionutbaiu und @Marco13 für die Mithilfe.

Durch @ionutbaiu habe ich die Sache erst durch einen 13 Spaltenvektor betrachtet, und gemerkt dass man die Rotation durch eine Rotationsmatrix gut berechnen kann
[xx][xy]
[yx][yy]
für 90° ist die Rotationsmatrix
[0][1]
[-1][0]
sprich der neue X-Wert ist 0
X+1Y und der Y-Wert ist -1X+0*Y, sprich X2=Y und Y2=-X.
Der Punkt (1|2) wäre - wenn man das Array um 90° drehen würde - dann an Position (2|-1).

Arrays mögen aber keine negativen Adressierungen, wie @Marco13 aber passend angemerkt hat.
Das ganze muss noch durch eine Translations-Matrix verrechnet werden, sprich damit sich der größte negative Wert wieder an Position 0|0 befindet.
Eine Translations-Matrix für 90° sieht dann so aus
[xw][xh] → [0][0]
[yw][yh] → [1][0]
Der Y2 Wert würde um Y2+(yw*Breite des Arrays) verschoben werden. Und der X2-Wert gar nicht; xw=0, xh=0.

Für jede Drehung kann man also 2x [2*2] Matrizen aufstellen (Rotation und Translation) und entsprechend die Gleichung für X und Y dazu.


Jetzt kommt der spannende Teil. Ich habe mir die Matrizen nebeneinander aufgeschrieben (links Rotation, rechts Translation) für die 4 Rotationssteps.


[+1][0] - [0][0]
[0][+1] - [0][0]
90°
[0][+1] - [0][0]
[-1][0] - [1][0]
180°
[-1][0] - [1][0]
[0][-1] - [0][1]
270°
[0][-1] - [0][1]
[+1][0] - [0][0]

Dann merkt man
XX und YY haben dabei immer den selben Wert → XX=YY.
XY und YX haben immer den selben invertierten Wert → XY=-YX.

Die Translationsmatrix hat zudem immer an der Stelle den Wert „1“, an der die Rotationsmatrix den Wert „-1“ hat, der Rest ist immer 0.
Die Beziehung der Werte zwischen der Rotationsmatrix und der Translationsmatrix lassen sich mathematisch so beschreiben
f(z)=(z^2-z)/2. Für f(1)=0, f(0)=0, f(-1)=1.
Oder entsprechend die alternative angewandte Informatik Methode von @Marco13.


Schlussendlich ergeben sich daraus die folgenden Gleichungen für X2 und Y2

X2 = X * xx + Y * xy + w * (xx^2-xx)/2 + h * (xy^2-xy)/2
Y2 = X * -xy + Y * xx + w * (xy^2+xy)/2 + h * (xx^2-xx)/2
für yx=-xy; yy=xx; xw=(xx^2-xx)/2; xh=(xy^2-xy)/2

Das ganze etwas gekürzt gibt dann in Code-Form

	public int getX(int x, int y, int w, int h) {
		return rot1 * (2 * x + w * (rot1 - 1)) / 2 + rot2 * (2 * y + h * (rot2 - 1)) / 2;
	}

	public int getY(int x, int y, int w, int h) {
		return rot1 * (2 * y + h * (rot1 - 1)) / 2 - rot2 * (2 * x - w * (rot2 + 1)) / 2;
	}

bzw. in invertierter Form (weil wir nicht das Array drehen, sondern nur so tun als ob wir auf ein gedrehtes Array zugreifen, intern aber auf ein Array in Ursprungsposition zugreifen keuch)

	public int getInvX(int x, int y, int w, int h) {
		return rot1 * (2 * x - w * (rot1 + 1)) / 2 - rot2 * (2 * y - h * (rot2 + 1)) / 2;
	}

	public int getInvY(int x, int y, int w, int h) {
		return rot1 * (2 * y - h * (rot1 + 1)) / 2 + rot2 * (2 * x + w * (rot2 - 1)) / 2;
	}

Das ganze nochmal als verwendbares Codestück

public enum Rotation {
	NORTH(0, 1, 0), EAST(1, 0, 1), SOUTH(2, -1, 0), WEST(3, 0, -1);

	public final int rot, rot1, rot2;

	Rotation(int rot, int rot1, int rot2) {
		this.rot = rot;
		this.rot1 = rot1;
		this.rot2 = rot2;
	}

	public int getX(int x, int y, int w, int h) {
		return rot1 * (2 * x + w * (rot1 - 1)) / 2 + rot2 * (2 * y + h * (rot2 - 1)) / 2;
	}

	public int getInvX(int x, int y, int w, int h) {
		return rot1 * (2 * x - w * (rot1 + 1)) / 2 - rot2 * (2 * y - h * (rot2 + 1)) / 2;
	}

	public int getY(int x, int y, int w, int h) {
		return rot1 * (2 * y + h * (rot1 - 1)) / 2 - rot2 * (2 * x - w * (rot2 + 1)) / 2;
	}

	public int getInvY(int x, int y, int w, int h) {
		return rot1 * (2 * y - h * (rot1 + 1)) / 2 + rot2 * (2 * x + w * (rot2 - 1)) / 2;
	}

	public int get2X(int x, int y, int w, int h) {
		return rot1 == 0 ? rot2 * y + (rot2 == -1 ? h : 0) : rot1 * x + (rot1 == -1 ? w : 0);
	}

	public int get2Y(int x, int y, int w, int h) {
		return rot1 == 0 ? -rot2 * x + (rot2 == 1 ? w : 0) : rot1 * y + (rot1 == -1 ? h : 0);
	}

	public int get2InvX(int x, int y, int w, int h) {
		return rot1 == 0 ? rot2 * y + (rot2 == 1 ? w : 0) : rot1 * x + (rot1 == -1 ? w : 0);
	}

	public int get2InvY(int x, int y, int w, int h) {
		return rot1 == 0 ? rot2 * x + (rot2 == -1 ? h : 0) : rot1 * y + (rot1 == -1 ? h : 0);
	}
}

Die unteren mit einer „2“ gelabelten Methoden sind zwar nicht mehr rein mathematische Formeln, aber in der Praxis schneller.

*Edit
Code-Fehler korrigiert

Ein langer, steiniger Weg im Vergleich zu einem

switch (steps) {
    case 0: return access0(x,y);
    case 1: return access90(x,y);
    case 2: return access180(x,y);
    case 3: return access270(x,y);
}

(und wenn es darum geht, vermutlich auch weniger performant), aber … :nerd:

Ein Punkt, der dort versteckt ist: Ich hatte bei meinem Rumprobieren (was, zugegeben, gar nicht systematisch war) mehrmals diesen „Ach Mist: X/Y/row/col-Moment“: Das ist ja schon „gedreht“ - Matrizen sind eigentlich (row,col), aber die Rotationen gehen meistens von (x,y) aus :dizzy_face: