8x8 Matrix um jeweils 90 Grad drehen

rotalosi · Hält's aus hier Beiträge: 12 Erhaltene Danke: 1

Hallo,

ich habe eine Matrix mit 8 Spalten und 8 Zeilen. Diese Matrix ist in einem Array aus 8 Bytes gespeichert. Jedes Byte repräsentiert eine Zeile und jedes Bit darin eine Spalte. Nun zu meinem Problem:
Ich möchte die Matrix um jeweils 90 Grad in die ein oder andere Richtung drehen. Hat jemand eine Idee wie ich das ganze Umsetzen kann? Wichtig ist, das der Code möglichst schnell ausgeführt wird.

Wäre schön wenn jemand eine Idee hätte.

Gruß Frank

Moderiert von Martok: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Mi 16.12.2015 um 15:17

Fiete · Beiträge: 601 Erhaltene Danke: 339 W7 Delphi 6 pro

Moin rotalosi,
habe in meinem Archiv etwas gefunden, das Dir helfen könnte,
Stichwort Koordinatentransformation, Mathematik kann so schön sein!

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

procedure TSchablonenCode.RechtsDrehen(var Neu:TFeld;Alt:TFeld;BG:Integer);
  var X,Y:Integer;
  begin
   SetLength(Neu,BG+1,BG+1);
   for X:=1 to BG do
    for Y:=1 to BG do Neu[BG+1-Y,X]:=Alt[X,Y]
  end;

 procedure TSchablonenCode.LinksDrehen(var Neu:TFeld;Alt:TFeld;BG:Integer);
  var X,Y:Integer;
  begin
   SetLength(Neu,BG+1,BG+1);
   for X:=1 to BG do
    for Y:=1 to BG do Neu[Y,BG+1-X]:=Alt[X,Y]
  end;
Warum soll der Code möglichst schnell ausgeführt werden?

Gib doch mal die Aufgabenstellung und Deine Lösungsansätze hier an, könnte ja von allgemeinem Interesse sein.
Gruß Fiete

_________________
Fietes Gesetz: use your brain (THINK)

C# · Verfasst: Mi 16.12.15 18:53

Nabend,

da mich das Problem interessiert habe ich mich gleich selbst mal dran gesetzt und einen kleinen Algorithmus geschrieben (kann leider kein Delphi, daher in C#), der sowohl im als auch gegen den Uhrzeigersinn drehen kann. Im Prinzip funktioniert er für alle ganzzahligen Datentypen (sprich byte, short, int, long), die Matrix muss nur quadratisch sein. Den Code habe ich noch ein wenig kommentiert, ich hoffe dass es dir hilft.

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:

        static void Main(string[] args)
        {
            byte[] matrix = {14, 125, 127, 204, 232, 136, 56, 200};

            Console.WriteLine("Initial Matrix:");
            PrintMatrix(matrix);

            Console.WriteLine("\nRotate 90° clockwise:");
            matrix = RotateMatrix(matrix);
            PrintMatrix(matrix);

            Console.WriteLine("\nRotate 90° clockwise:");
            matrix = RotateMatrix(matrix);
            PrintMatrix(matrix);

            Console.WriteLine("\nRotate 90° counter-clockwise:");
            matrix = RotateMatrix(matrix, false);
            PrintMatrix(matrix);

            Console.WriteLine("\nRotate 90° counter-clockwise:");
            matrix = RotateMatrix(matrix, false);
            PrintMatrix(matrix);

            Console.ReadLine();
        }

        static void PrintMatrix(byte[] matrix)
        {
            foreach (byte b in matrix)
                Console.WriteLine(Convert.ToString(b, 2).PadLeft(8, '0').Aggregate("", (t, s) => t + s + " "));
        }
        

        static byte[] RotateMatrix(byte[] matrix, bool clockwise = true)
        {
            // columnSize kann für verschiedene Spaltenlängen (z.B. integer) angepasst werden
            int columnSize = sizeof (byte) * 8;

            // Rotation muss in neuem Array gespeichert werden, 
            // damit während der Rotation keine Werte verfälscht werden
            byte[] buffer = new byte[matrix.Length];

            // Iteration durch die Zeilen
            for (int i = 0; i < matrix.Length; i++)
            {
                // Iteration durch die Spalten
                for (int j = 0; j < columnSize; j++)
                {
                    // Check, ob das betreffende Bit den Wert 1 hat
                    if (((1 << j) & matrix[i]) != 0)
                    {
                        if (clockwise) buffer[columnSize - j - 1] |= (byte) (1 << i);
                        else buffer[j] |= (byte)(1 << (columnSize - i - 1));
                    }
                }
            }

            return buffer;
        }

Die Ausgabe davon ist:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:

Initial Matrix:
0 0 0 0 1 1 1 0
0 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1
1 1 0 0 1 1 0 0
1 1 1 0 1 0 0 0
1 0 0 0 1 0 0 0
0 0 1 1 1 0 0 0
1 1 0 0 1 0 0 0

Rotate 90° clockwise:
1 0 1 1 1 0 0 0
1 0 0 1 1 1 1 0
0 1 0 1 0 1 1 0
0 1 0 0 0 1 1 0
1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 0

Rotate 90° clockwise:
0 0 0 1 0 0 1 1
0 0 0 1 1 1 0 0
0 0 0 1 0 0 0 1
0 0 0 1 0 1 1 1
0 0 1 1 0 0 1 1
1 1 1 1 1 1 1 0
1 0 1 1 1 1 1 0
0 1 1 1 0 0 0 0

Rotate 90° counter-clockwise:
1 0 1 1 1 0 0 0
1 0 0 1 1 1 1 0
0 1 0 1 0 1 1 0
0 1 0 0 0 1 1 0
1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 0

Rotate 90° counter-clockwise:
0 0 0 0 1 1 1 0
0 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1
1 1 0 0 1 1 0 0
1 1 1 0 1 0 0 0
1 0 0 0 1 0 0 0
0 0 1 1 1 0 0 0
1 1 0 0 1 0 0 0

Hier mal noch ein Bild wie der Algorithmus funktioniert, wenn er im Uhrzeigersinn dreht. Reihenfolge: rot, blau, grün, pink
Bit_Matrix_Algo

Einloggen, um Attachments anzusehen!

_________________
Der längste Typ-Name im .NET-Framework ist: ListViewVirtualItemsSelectionRangeChangedEventHandler

Ralf Jansen · Verfasst: Mi 16.12.15 20:21

Mal quer gedacht. Ist es überhaupt notwendig die Matrix tatsächlich im Speicher zu rotieren (Nebenbei soll das Ergebnis im gleichen Array liegen oder in einem neuen rotierten)? Man könnte doch einfach den Zugriff auf das Array umrechnen. Ist ja letztlich nicht viel mehr als Spalten, Zeilen tauschen bei der Zelladressierung.

Nersgatt · Verfasst: Mi 16.12.15 22:24

Das würde ich davon abhängig machen, wie oft auf das gedrehte Array zugegriffen werden muss. Wenn es eine einmalige Sache ist, könnte man das beim Zugriff umrechnen.
Bei mehrfachem Zugriff ist es sicher effektiver, einmal das Array zu drehen und damit ist dann beim Zugriff keine Umrechnung mehr nötig.

_________________
Gruß, Jens
Zuerst ignorieren sie dich, dann lachen sie über dich, dann bekämpfen sie dich und dann gewinnst du. (Mahatma Gandhi)

jfheins · Beiträge: 918 Erhaltene Danke: 158 Win 10 VS 2013, VS2015

rotalosi hat folgendes geschrieben :

Wichtig ist, das der Code möglichst schnell ausgeführt wird.

Es wäre etwas praktischer, wenn du da eine konkrete Vorstellung hättest. in Stackoverflow gibt eine ähnliche Frage der Code muss aber evtl. angepast werden.

Falls es sehr schnell sein muss, würde ich C oder Assembler empfehlen; die SSE-Anweisung movemask sollte deinem Problem sehr gelegen kommen: mischasan.wordpress....posing-a-bit-matrix/

Aber vielleicht lässt sich da auch was mit shifts und Multiplikationen zusammenbasteln ... ich schaue mal

Sooo ... etwas müde, aber diese Version ist 3-4 Mal so schnell wie die aus Beitrag 3 auf meiner 64bit CPU. Zugegeben, auch etwas spezialisierter und kryptischer. Die Schleife könnte man sicher noch ausschreiben. (Ich hoffe jedoch, der compiler macht das bereits)

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

    static byte[] RotateMatrix2(byte[] matrix)
    {
      unchecked
      {
        ulong input1 = BitConverter.ToUInt32(matrix, 0); // Cast in einen uint32, geht noch schneller mit pointern
        ulong input2 = BitConverter.ToUInt32(matrix, 4); // Cast in einen uint32, geht noch schneller mit pointern

        for (int bit = 0; bit < 8; bit++)
        {
          uint mask = 0x80808080u >> bit;
          uint factor = (1u << (0 + bit)) | (1u << (7 + bit)) | (1u << (14 + bit)) | (1u << (21 + bit));

          uint tmp1 = (uint)(((input1 & mask) * factor) >> 28) & 0xFF;
          uint tmp2 = (uint)(((input2 & mask) * factor) >> 24) & 0xFF;
          matrix[bit] = (byte)(tmp1 | tmp2);
        }

        return matrix;
      }
    }

Idee ist von hier: wm.ite.pl/articles/scalar-sse-movmask.html

rotalosi · Hält's aus hier Beiträge: 12 Erhaltene Danke: 1

Hallo,

vielen Dank für eure Hilfe. Das bringt mich schon mal deutlich weiter. Selbst die erste c# Variante ist für meine Anwendung schnell genug. Ich denke bei Geschwindigkeit immer in den Dimensionen eines µC. In diesem Fall an einem Mega324A mit 8 Mhz Takt.

Zum Hintergrund falls es jemanden interessiert. Ich habe für unseren Verein vor einiger Zeit eine kleine Matrixanzeige gebaut. Die besteht aus 3 x 5 (8x8) Matrixelementen. Alle Module sind per SPI miteinander verbunden. Bisher wurde nur Text angezeigt. Das hat der kleine Atmel problemlos geschafft. Nun möchte ich aber auch animierte Grafiken anzeigen. Das schafft der kleine nur wenn er die Grafiken vorausberechnet serviert bekommt, sonnst flimmert es.

Da ich mich hauptsächlich mit Mikrocontrollern beschäftige, vergesse ich manchmal um wie viel schneller ein PC rechnet. Selbst die langsamste Variante auf jeden Fall schneller als ich die Daten an dem Atmel überragen kann. Vielen Dank für eure Hilfe. Ich melde mich nochmal ob es geklappt hat.

Gruß Frank

Horst_H · Verfasst: Do 17.12.15 12:16

Hallo,

Warum sollte das nicht auf dem AVR passieren? BItschubsen kann der auch schnell.
auf www.mikrocontroller.net/ wird die Frage schon seit Jahren beantwortet ;-)

www.mikrocontroller.net/topic/278392
In Assembler für AVR GCC unter Ausnutzung der vielen Register, die AVR bietet.
www.mikrocontroller....topic/278392#2935823 und folgende

Gruß Horst

OlafSt · Verfasst: Do 17.12.15 12:38

Außerdem kann man sicher einfach den Quarz gegen einen 16MHz-Typen austauschen und so die Rechenleistung des kleinen Atmel um 100% steigern

_________________
Lies, was da steht. Denk dann drüber nach. Dann erst fragen.

Nersgatt · Verfasst: Do 17.12.15 12:40

Der AVR wird ja noch andere Aufgaben haben, als Arrays zu rotieren. Wenn die Möglichkeit da ist, würde ich dem AVR die Daten soweit wie möglich auf dem PC vorkauen, um ihn nicht mehr arbeiten zu lassen als irgend nötig.

_________________
Gruß, Jens
Zuerst ignorieren sie dich, dann lachen sie über dich, dann bekämpfen sie dich und dann gewinnst du. (Mahatma Gandhi)

Horst_H · Verfasst: Do 17.12.15 13:14

Hallo,

wenn der AVR das in etwa 25 µs ~ 200 Takten rotiert, ist doch die Frage, ob das Versenden von 8 Byte vom PC nicht etwas länger dauert.
Bei 115200 Bd etwa 700 µs.OK, könnte Interupt gesteuert sein., aber das dauert wohl auch um >10 Takte pro Byte.
Man kann ja auch vorberechnete Muster im Flash oder Eeprom haben oder eine Externe Eeprom per SPI nutzen.
Meist quält man die AVR mit Däumchendrehen...

Gruß Horst

GuaAck · Verfasst: Do 17.12.15 23:35

Hallo alle,

wenn man von einer externen Bearbeitung absieht, dann laufen alle Algorithmen auf eine geschachtelte Schleife 0..7 hinaus, also 64 Schritte. Da gibt es drei Ansatzpunkte:

a) Jeden Schritt optimieren: "Bit lesen, Bit in einem anderen Byte an bestimmter Stelle setzen". Da könnte auch die Einführung eines Zwischenschrittes helfen. Beispiel: Man legt das Ergebnis zunächt in einem Array 1..256 ab, nutzt aber nur nur 1,2,4,8,..., 256, dann wäre die Shiftmaske zur Abfrage des Bits im Byte gleich dem Index im Ausgabefeld. Zum Abschluss muss man noch 7 Bytes umkopieren. Könnte Vorteile bringen.

b) Schleifenverwaltung minimieren, ideal den Code 64 x hintereinander im Quelltext, man spart die if-Abfragen und das Inkrementieren des Zählers und die Feldadressen müssen auch nicht zur Laufzeit berechnet werden; schon für die innere Schleife hilft das, weil der eigentliche Schritt ja kurz ist, ein paar ORs, ANDs und SHIFTs o.ä.

c) Statistik: Wenn das Array typisch nur wenige "1" enthält, dann muss man nicht jedes der 64 Bits setzen, sondern man initialisiert das Ausgangsfeld mit 0 und muss dann nur die seltene "1" setzen. (umgekehrt bei wenigen "0" entsprechend.)

Also:
a) Das muss man probieren, es hängt sehr vom Prozessor und vom Compiler ab, was geht. Und evtl. auch vom RAM oder anderen Resourcen.

b) Der Vorteil ist unstrittig. Nachteil: Man braucht Programmspeicher und es ist extrem änderungsunfreundlich. (Ich würde unbedingt ein kleines Programm (Delphi, C o.ä.) machen, das mir die 64 Dinger automatisch als Textdatei zum Einfügen in den Quellcode erzeugt.)

c) Der Vorteil ist unstrittig, hängt von der Anwendung ab.

Nun bin ich gespannt auf die schnellste Version,

Gruß´GuaAck

rotalosi · Hält's aus hier Beiträge: 12 Erhaltene Danke: 1

Hallo,

vielen Dank an alle. Besonders C#. Ich habe das Ganze nun in Delphi umgesetzt und es funktioniert nun einwandfrei.

Ich gehe hier nochmal kurz auf andere Antworten ein. Der Atmel läuft nicht mit einem externen Quarz sondern mit seinem internen RC Generator. Einfach den Quarz tauschen funktioniert also nicht. (Es gibt aber auch noch andere Gründe warum man nicht einfach die Frequenz ändern kann)

Der Atmel in meiner Anwendung ist quasi bis zum Anschlag ausgelastet. Die Anzeige ist nicht statisch, sondern in Zonen aufgeteilt. Während eine nur den Punktestand anzeigt, werden in den anderen Laufschriften mit Informationen angezeigt. Was angezeigt werden soll, holt sich der Atmel an seinem Port A ab (Interrupt). Dort werden die Daten von der PC-Anwendung über ein USB Interface bereitgestellt. Es ist natürlich kein Problem die Matrix im Atmel zu drehen oder gar im EEProm zu speichern. Aber es sollen ja Animationen übertragen werden, die vom Anwender des Programms beliebig erzeugt werden können.

Vielen Dank nochmal und allen ein schönes Weihnachtsfest und einen guten Rutsch.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme