Algorithmus zur spiralförmiger Anordnung

[hdi]

Hey, ich habe eine Liste von Elementen, deren Länge erst zur Laufzeit bekannt ist.
Ich möchte die Elemente spiralförmig anordnen, heisst:



Das ganze auf einem 2d-array, also nicht mal "echt" spiral mit diagonal usw.
Hat sich erstmal recht leicht angehört... Doch weit geirrt, ich empfinde die Lösung des Problems
als recht schwierig, weil ich eben die Anzahl der Elemente nur zur Laufzeit weiss.

Ich meine, ich habe eine Lösung, aber sie gefällt mir wie sooft nicht. Wäre super wenn ihr da mal nen
Blick drüberwerfen könntet.

// Anzahl der Felder, bei der die Richtung beibehalten werden soll
			int distance = 1;
			// Anzal der Felder bis zum nächsten Richtungswechsel
			int untilRedirect = 1;
			// Index des Feldes, bei dem der Wechsel passieren soll
			int redirectIndex = 1;
			// Momentane Richtung des Zelldurchlaufs
			int direction = 'w';
			int[] nextDir = { -1, 0 };
			// Zur Vereinfachung sagen wir mal das Zentrum der Spiral ist bei [0][0],
			// heisst es ist jetz auch egal wenn die Indizes negativ werden, das kann 
			// man ja einfach verschieben. Das erste Element (Index 0) muss ausserhalb
			// der Schleife gesetzt werden damit das hinhaut:
			int x = 0;
			int y = 0;
			zellen[0][0].insertStuff(0);
			x += nextDir[0];
			y += nextDir[1];
			// restlichen Elemente verteilen
			for (int i = 1; i< listLength; i++) {
				zellen[x][y].insertStuff(i);
				// Richtung updaten; Bei jedem zweiten Richtungswechsel
				// wächst die Distanz bis zum nächsten Wechsel um 1
				if (i == redirectIndex) {
					redirectIndex += distance;
					if (--untilRedirect == 0) {
						distance++;
						untilRedirect = 2;
					}
					switch (direction) {
					case 'w':
						nextDir = new int[] { 0, -1 };
						direction = 'n';
						break;
					case 'n':
						nextDir = new int[] { 1, 0 };
						direction = 'e';
						break;
					case 'e':
						nextDir = new int[] { 0, 1 };
						direction = 's';
						break;
					case 's':
						nextDir = new int[] { -1, 0 };
						direction = 'w';
						break;
					}
				}
				// Zelle für das nächste Element festlegen:
				x += nextDir[0];
				y += nextDir[1];
			}

Mir gefallen vorallem zwei Dinge nicht: Das updaten der Richtung immer, vllt ist das ja total schlecht
gelöst mit diesem 2-elementigen 2d-int array. Das is einfach so hässlicher Code, der alles optisch so in die Länge zieht.
Zum zweiten verwende ich für meinen Geschmack zuviele Variablen: redirectIndex, untilRedirect, distance, blaaa 😉
Leider hab ich keine mathematische Gleichmässigkeit entdecken können, die leichter auszudrücken ist...

Danke für eure Hilfe!

 

[Marco13]

Es gibt sicher 1000 mögliche Lösungen dafür. Effizienter ist vermutlich sowas

import java.util.*;

class TheDownwardSpiral
{
    public static void main(String args[])
    {
        compute(18);
    }


    private static void compute(int len)
    {
        int x = 0;
        int y = 0;
        int steps = 1;
        int step = 0;
        int deltas[][] =
        {
            { -1,  0 },
            {  0,  1 },
            {  1,  0 },
            {  0, -1 },
        };
        int counter = 0;
        for (int i=0; i<len; i++)
        {
            System.out.println("At "+x+" "+y+" step "+step+" of "+steps+" counter "+counter+" dir "+Arrays.toString(deltas[counter%4]));
            x += deltas[counter%4][0];
            y += deltas[counter%4][1];
            if (++step==steps)
            {
                if (++counter % 2 == 0)
                {
                    steps++;
                }
                step = 0;
            }
        }
    }
}

 

[0x7F800000]

Hm, das einzige was mir zu dieser anordnung spontan einfällt, wäre ulam's tischdecke.
Wenn es dir nur darum geht, das so zu zeichnen dann würde ich sehr empfehlen, diese anordnung nicht in irgendeinem array anzulegen, sondern den benötigten platz schätzen, und gleich loszeichnen. Denn beim zeichnen brauchst du nur eine schätzung, das geht ganz leicht, du berechnest einfach die quadratwurzel aus der zahl der elemente, rundest es auf, und hast die breite der annähernd quadratischen anordnung.

Sollte es sich wirklich um die ulams spirale handeln, so würde ich sogar empfehlen, schnell eine schöne formel für eine echte runde lineare spirale nachzurechnen, und die zahlen auf dieser spirale in gleichen abständen zu verteilen, da kommen tolle sachen raus 😉