A háromdimenziós buborék rendezési algoritmus

Original article:http://www.tropicalcoder.com/3dBubbleSort.htm

Image produced by a sort

Művészet vagy tudomány?

1999 őszén fedeztem fel ezt a kíváncsi, de valószínűleg teljesen haszontalan algoritmust. Még egy feljegyzést is elküldtem erről Dr. Dobb’s Journal-nak, és nagyon meglepődtem, amikor néhány hónappal később visszaírtak, és azt javasolták, készítsek egy cikket nekik. Akkoriban túl elfoglalt voltam, és a világ elvesztette a lehetőséget a haszontalan tudás fokozatos növekedésére. Ezt most bemutatom; ajándékom a világnak és talán egyetlen örökségem. Ki tudja, lehet, hogy valamelyik poros irodában dolgozó matematikus kulcsfontosságúnak találhatja valami homályos elmélet megoldását.

A koncepció…

Az ötlet nagyon egyszerű. Kezdje egy színes pixelekkel feltöltött képernyőn, véletlenszerűen elosztva. A lehetséges színek száma nem számít, de végül sokkal érdekesebb képet készít, ha kevesebb színt használnak. Ezután megkezdjük a pixelek rendezését a következő algoritmus szerint:

LOOP
W, H méretû képernyõn
Válasszon egy pixelt véletlenszerű koordinátákban x, y ahol x = {0 thru (W – 1)}, y = {0 thru (H – 2)}
Ha az alábbi pixelben lévő piros mennyisége (x, y + 1-nél) nagyobb, mint a jelenlegi pixelben a piros, cserélje ki a pixeleket
Válasszon egy másik pixelt véletlenszerű x, y koordinátákon, ahol x = {0 thru (W – 2)}, y = {0 thru (H – 2)}
Ha a zöld képpontja a jobb alsó sarokban (x + 1, y + 1 értéknél) kisebb, mint a jelenlegi pixelben lévő zöld, akkor cserélje ki a képpontokat
Válasszon egy másik pixelt véletlenszerű koordinátákon x, y ahol x = {1 thru (W – 1)}, y = {0 thru (H – 2)}
Ha a kék képpontja a bal alsó sarokban (x-1, y + 1 értéknél) kisebb, mint a kék az aktuális pixelben, akkor cserélje a képpontokat
if(!done)goto LOOP

Több milliószor folytatjuk így a hurkolást, amíg létre nem jön az egyensúly, amelyben a színek medencékbe vannak rendezve. A tiszta színű pixelek a medencékben mozdulatlanná válnak, és az egyetlen művelet, amely ezután folytatódik, a színkészletek interfészei mentén zajlik.

E jelenség vizsgálatának általános módjaként képzeljen el egy adott pixelt meghatározott mennyiségű vörös, zöld és kék színnel. Piros tartalmától függően olyan erőt tapasztal, amely felfelé vagy lefelé mozgatja a képernyőt, és a másik két szín mennyiségétől függően átlósan balra és jobbra mozgatja azokat. A végső nyugalmi helyzet ennek a három erőnek a vektor összege, a képernyőn lévő összes többi pixelhez viszonyítva. Ez a rendezési algoritmus még nagyobb dimenziókba is felvehető, és a tulajdonságok bármilyen kombinációjára alkalmazható, nemcsak a pixelek színeire. Bármilyen elképzelhető forgatókönyv szerint a hagyományos válogatási technikák sokkal egyszerűbbek és gyorsabbak. Ha a pszichedelikus képek készítésén túl talál valamilyen hasznot ennek az algoritmusnak, kérem, tudassa velem, és kérem, legalább vegyen jóvá az ötletért.

3DSort.exe PC-hez – A WinZipped (26,6 Kb) a legújabb Windows GDI-verzióm (2004. február 16.), amely különféle felületformákon (négyzet, kör, tórusz stb.) <2 perc alatt rendezi a területet 512 pixel négyzet, és csak másodperc egy 256 pixel négyzet alakú területre. Az assemblerben optimalizálva valószínűleg nem lesz ennél gyorsabb – legalábbis egy P4 – 2 Ghz platformon. Íme néhány általa készített kép: Circle.gif, Triangle.gif, Torus.gif.

További képek …

  1. rendezés RGB alapján,
  2. rendezés RGB alapján,
  3. rendezés YcrCb alapján,
  4. rendezés YcrCb alapján.

Frissítve 2016. augusztus

Az alábbiakban 1024 külön kép létrehozásával és összesített átlagolásával generált kép található. Összesen 123 színt használtunk fel, amelyeket úgy állítottunk elő, hogy az egyes r, g, & b értékeket 64-re léptettük, és a fekete-fehér színeket megszüntettük. 1024 x 632 képméretet választottak, mert a szélesség és a magasság aránya megegyezik az aranyaránnyal egy szép prezentáció érdekében.

Ez a kód áll a hatalmas válogatási munka középpontjában Mindegyik kép elkészítése alig több mint két percet vett igénybe, a végső kép elkészítéséhez pedig körülbelül 34,5 óra feldolgozási időre volt szükség Intel i5 processzorral és sok RAM-mal. A kivizsgálás lényege a “tökéletes fajta” megtalálása volt a platoni értelemben, mivel a kép létrehozása teljesen véletlenszerű folyamatoktól függ. Érdekes megjegyezni, hogy még az összes véletlenszerűen generált kép összevonása után is az eredményül kapott képnek éles vonásai vannak, mintha a pixeleket “előre meghatározták”, hogy utat találjanak a végső pihenőhelyükhöz. Nos, talán csak túl sok idő volt a kezemen 🙂

 

Image produced by averaging 1024 3D sorted images

 

Frissítve 2018. január

A következő alábbi képet ugyanúgy készítettük el, de 6 színből egy másik paletta származik. A különböző színek használata teljesen más mintát hoz létre. 17,5 órás feldolgozást igényelt Intel i7-7700 processzorral a rendereléshez.

A következő alábbi kép ugyanúgy készült, de 12 különböző színű, különböző palettáról származó szín.

Image produced by averaging 1024 3D sorted images

 

Az alábbi 3 alábbi képet ugyanúgy készítettük. A jobb oldali első kép 24 színt használt, a következő csak 6, az utolsó pedig 60 színt használt. A középső kép más palettát használt, mint a többi.

 

Images produced by averaging 1024 3D sorted images

Négydimenziós színrendezés

Mint fent említettük, a rendezés tetszőleges számú dimenzióban elvégezhető. A rendezés egy 256 pixel méretű kockán történt, véletlenszerűen elosztott színes pixelekkel feltöltve. Összesen 123 szín volt. A pixeleket a következő alogoritmus szerint rendeztük …

LOOP

W (szélesség), H (magasság), D (mélység) méretű kockákhoz

Válasszon egy pixelt véletlenszerű x, y, z koordinátán, ahol x = {0 thru (W-1)}, y = {0 thru (H-2), z = {0 thru (D-1)}
Ha az alábbi pixelben a piros mennyisége (x, y + 1, z értéknél) nagyobb, mint a jelenlegi pixelben a piros, cserélje ki a képpontokat

 

Válasszon másik pixelt véletlenszerű koordinátákon x, y, z ahol x = {0 thru (W-2)}, y = {0 thru (H-2)}, z = {0 thru (D-1)}
Ha a zöld képpontja a jobb alsó sarokban (x + 1, y + 1, z értéknél) kisebb, mint a jelenlegi pixelben lévő zöld, akkor cserélje a képpontokat

Válasszon másik pixelt véletlenszerű koordinátákon x, y, z ahol x = {1 thru (W-1)}, y = {0 thru (H-2)}, z = {0 thru (D-1)}
Ha a kék képpontja a bal alsó sarokban (x-1, y + 1, z értéknél) kisebb, mint a kék az aktuális pixelben, akkor cserélje a képpontokat

Végül válasszon egy pixelt véletlenszerű koordinátákon x, y, z, ahol x = {0 thru (W-1)}, y = {0 thru (H-1)}, z = {0 thru (D-2)}
Ha a (x, y, z + 1-nél) mögött lévő pixel fényértéke nagyobb, mint az aktuális pixel fényértéke, cserélje ki a képpontokat.
(A fényerő vagy az „Y” értéke: (0,299 * piros) + (0,587 * zöld) + (0,114 * kék))

if(!done)goto LOOP

Folyamatosan folytassa a ciklusokat így több milliárdszor, amíg létre nem jön az egyensúly, amelyben a színek foltokba vannak rendezve. A tiszta színű pixelek a foltokban mozdulatlanná válnak, és az egyetlen művelet, amely ezután folytatódik, az egyes színes foltok interfészei mentén hat egymással.

Most utazzon keresztül egy kockán, amelynek oldala 256 pixel, véletlenszerűen 123 színnel hozzárendelve, ezen algoritmuson keresztül rendezve.

Az alábbiakban egy grafikon szemlélteti a rendezés során elért haladást különböző színszámok mellett, az oldalon lévő négyzet alakú 512 képponton. Csaknem 200 millió ismétlésre lehet szükség az egyensúlyi állapot eléréséhez. Az évekkel ezelőtti első verzióim több mint két órát vettek igénybe. Csak a mai P4 processzorokkal és kézzel optimalizált assembler kóddal lehet a rendezést órák helyett néhány perc alatt elvégezni. Látható, hogy a színek száma nem sok különbséget jelent abban, hogy az algoritmus mikor ér el állandó állapotot, ahol a színek a lehető legnagyobb mértékben vannak rendezve. Az egyetlen drámai különbség az, hogy több színnel több pixel marad örökre az interfészek mentén, anélkül, hogy otthont kellene hívniuk.

A színeket úgy kaptuk meg, hogy minden egyes piros, zöld és kék színkomponentust 128, 64, 32, 16 vagy 8-ra léptettünk, majd pusztán esztétikai okokból eltávolítottuk a fekete, fehér és szürkéket a kapott színekből. Ez 25, 123, 727, 4911 és 35 935 színt eredményez.

Az alábbiakban egy grafikon szemlélteti a rendezés során elért haladást különböző színszámok mellett, az oldalon lévő négyzet alakú 512 képponton. Csaknem 200 millió ismétlésre lehet szükség az egyensúlyi állapot eléréséhez. Az évekkel ezelőtti első verzióim több mint két órát vettek igénybe. Csak a mai P4 processzorokkal és kézzel optimalizált assembler kóddal lehet a rendezést órák helyett néhány perc alatt elvégezni. Látható, hogy a színek száma nem sok különbséget jelent abban, hogy az algoritmus mikor ér el állandó állapotot, ahol a színek a lehető legnagyobb mértékben vannak rendezve. Az egyetlen drámai különbség az, hogy több színnel több pixel marad örökre az interfészek mentén, anélkül, hogy otthont kellene hívniuk.

A színeket úgy kaptuk meg, hogy minden egyes piros, zöld és kék színkomponentust 128, 64, 32, 16 vagy 8-ra léptettünk, majd pusztán esztétikai okokból eltávolítottuk a fekete, fehér és szürkéket a kapott színekből. Ez 25, 123, 727, 4911 és 35 935 színt eredményez.

Graph of sort progress

 

Leave a Reply

Your email address will not be published. Required fields are marked *