Mortan Scan Order

Windalf

hat zufällig jemand ne Formel auf ner Pfanne die mir den x und den y wert (Position) vom n_ten Schritt von einem beliebigen 2d feld der grösse x_dim und y_dim liefert...

um mal ein beispiel zu machen... für eine matrix der grösse 16*16

würde x (von links nach recht und oben nach unten lesen) so laufen
0 1 0 1 2 3 2 3 0 1 0 1 2 3 2 3
4 5 4 5 6 7 6 7 4 5 4 5 6 7 6 7
0 1 0 1 2 3 2 3 0 1 0 1 2 3 2 3
4 5 4 5 6 7 6 7 4 5 4 5 6 7 6 7

8 9 8 9 10 11 10 11 8 9 8 9 10 11 10 11
12 13 12 13 14 15 14 15 12 13 12 13 14 15 14 15
8 9 8 9 10 11 10 11 8 9 8 9 10 11 10 11
12 13 12 13 14 15 14 15 12 13 12 13 14 15 14 15

0 1 0 1 2 3 2 3 0 1 0 1 2 3 2 3
4 5 4 5 6 7 6 7 4 5 4 5 6 7 6 7
0 1 0 1 2 3 2 3 0 1 0 1 2 3 2 3
4 5 4 5 6 7 6 7 4 5 4 5 6 7 6 7

8 9 8 9 10 11 10 11 8 9 8 9 10 11 10 11
12 13 12 13 14 15 14 15 12 13 12 13 14 15 14 15
8 9 8 9 10 11 10 11 8 9 8 9 10 11 10 11
12 13 12 13 14 15 14 15 12 13 12 13 14 15 14 15

0 1 0 1 2 3 2 3 0 1 0 1 2 3 2 3
4 5 4 5 6 7 6 7 4 5 4 5 6 7 6 7
0 1 0 1 2 3 2 3 0 1 0 1 2 3 2 3
4 5 4 5 6 7 6 7 4 5 4 5 6 7 6 7

8 9 8 9 10 11 10 11 8 9 8 9 10 11 10 11
12 13 12 13 14 15 14 15 12 13 12 13 14 15 14 15
8 9 8 9 10 11 10 11 8 9 8 9 10 11 10 11
12 13 12 13 14 15 14 15 12 13 12 13 14 15 14 15

0 1 0 1 2 3 2 3 0 1 0 1 2 3 2 3
4 5 4 5 6 7 6 7 4 5 4 5 6 7 6 7
0 1 0 1 2 3 2 3 0 1 0 1 2 3 2 3
4 5 4 5 6 7 6 7 4 5 4 5 6 7 6 7

8 9 8 9 10 11 10 11 8 9 8 9 10 11 10 11
12 13 12 13 14 15 14 15 12 13 12 13 14 15 14 15
8 9 8 9 10 11 10 11 8 9 8 9 10 11 10 11
12 13 12 13 14 15 14 15 12 13 12 13 14 15 14 15

--------
16 17 16 17......

hoffe ich habs deutlich formuliert wenns unklar ist bitte nochmal nachfragen

Jester

häh?

Was meinst Du mit dem n_ten Schritt eines Feldes?

Windalf

also ok ich versuchs nochmal zu erklären...

also nehmen wir mal ne 2x2 matrix...

da werden die felder in der reihenfolge (0/0),(1/0),(0/1) und (1,1) durchlaufen...

die funktion die ich in diesem fall bräuchte wäre dann

xwert(0) =0;
xwert(1) =1;
xwert(2) =0;
xwert(3) =1;

soweit noch recht einfach jetzt mal für 4*4;

der anfang ist wieder gleich
(0/0),(1/0),(0/1) und (1,1)
dann kommen
(2/0),(3/0),(2/1) und (3,1)
(0/2),(1/2),(0/3) und (1,3)
(2/2),(3/2),(2/3) und (3,3)

in dem fall wäre also xwert(n)...

xwert(0) =0;
xwert(1) =1;
xwert(2) =0;
xwert(3) =1;
xwert(4) =2;
xwert(5) =3;
xwert(6) =2;
xwert(7) =3;
xwert(8) =0;
xwert(9) =1;
xwert(10) =0;
xwert(11) =1;
xwert(12) =2;
xwert(13) =3;
xwert(14) =2;
xwert(15) =3;

und die zahlen aus meinem vorigen post sollten darstellen wie die xwerte verlaufen bei ner 16*16 matrix... und das ganze bräuchte ich jetzt für ne belibige x_dim * y_dim matrix (das mit dem rändern soll jetzt mal keine rolle spielen, annahme die matrix ist immer "wohl dimensioniert") also immer quadratisch und eine potzenz von 2

und ich brauch x_wert(n)... wenn ich das zusammengereimt bekommt bekomme sollte ja y_wert(n) analog gehen...

hoffentlich ist es jetzt klar was ich meine und ich hab nicht noch mehr verwirrung gestiftet

Windalf

so hat vermutlich immer noch keiner verstanden gehabt weil ichs so beschissen erklärt habe

aber zum glück habe ich in den tiefen des internets ne Lösung für mein Problem gefunden (ich glaub es war auf der 10. ergebnisseite von google wo ich schon nicht mehr dran geglaubt hab das da noch was kommt)

erstaunlich einfach die sache.... allerdings hab ichs nicht wirklich tiefgründig verstanden aber ist mir auch egal hopsa funzt

http://www.ncgia.ucsb.edu/giscc/units/u057/u057.html

die oben von mir gepostet folge kann man dann z.b. wie folgt erhalten

size_t qtree2x(size_t pos){
	size_t i,rv=0;
	for(i=0;i<8*sizeof(size_t);i+=2)	
		rv|=(pos&(1<<i))>>i/2;
	return rv;
}

@Jester
Sorry wenn du dir jetzt umsonst das hirn für mich verrenkt haben solltest...