Rumah dari ...
Tiga Dimensi Bubble Sort Algoritma
Seni atau ilmu?
Saya menemukan algoritma penasaran tapi mungkin sama sekali tidak berguna ini pada musim gugur 1999. Saya bahkan dikirim surat kepada Dr. Dobb Journal tentang hal itu, dan itu menyenangkan terkejut ketika mereka menulis kembali beberapa bulan kemudian dan menyarankan saya sebuah artikel untuk mereka. Saya terlalu sibuk pada saat itu, dan dunia kehilangan kesempatan untuk peningkatan inkremental dalam pengetahuan tidak berguna. Saya menyajikan ini sekarang; hadiah saya untuk dunia dan mungkin saya hanya warisan. Siapa tahu mungkin beberapa matematikawan bekerja jauh di beberapa kantor berdebu mungkin merasa keystone untuk memecahkan beberapa teori jelas.
Konsep...
Idenya sangat sederhana. Mulai dengan layar diisi dengan piksel berwarna, didistribusikan secara acak. Jumlah warna yang mungkin tidak masalah, tapi itu membuat gambar lebih menarik pada akhirnya jika warna lebih sedikit digunakan. Kemudian kita mulai memilah pixel sesuai dengan algoritma berikut:
LOOP
Untuk layar dimensi W, H
Pilih pixel pada koordinat acak x, y mana x = {0 thru (W - 1)}, y = {0 thru (H - 2)}
Jika jumlah warna merah pada pixel bawah ( di x, y + 1) lebih besar dari merah dalam pixel saat ini, pertukaran piksel
Pilih pixel lain pada koordinat x acak, y mana x = {0 thru (W - 2)}, y = {0 thru (H - 2)}
Jika jumlah warna hijau pada pixel ke kanan bawah (di x + 1, y + 1) kurang dari hijau dalam pixel saat ini, pertukaran piksel
Pilih pixel lain pada koordinat acak x, y mana x = {1 thru (W - 1) }, y = {0 thru (H - 2)}
Jika jumlah biru di pixel ke kiri bawah (di x-1, y + 1) kurang dari biru pixel saat ini, pertukaran piksel
jika (! dilakukan) LOOP goto
Kami terus perulangan seperti jutaan ini kali, sampai keseimbangan menjadi didirikan di mana warna diurutkan ke dalam kolam. Pixel warna murni dalam kolam menjadi tidak bergerak, dan satu-satunya tindakan yang berlanjut setelah itu beberapa interaksi sepanjang interface dari kolam renang warna.
Sebagai cara umum pemeriksaan fenomena ini, bayangkan sebuah pixel yang diberikan dengan jumlah yang ditentukan dari merah, hijau, dan biru. Tergantung pada itu konten merah, mengalami gaya bergerak ke atas atau bawah layar, dan tergantung pada jumlah masing-masing dua warna lain, itu mengalami pasukan bergerak diagonal kiri dan kanan. Ini posisi peristirahatan terakhir adalah jumlah vektor dari tiga kekuatan tersebut, dalam hubungannya dengan semua piksel lainnya pada layar. algoritma sorting ini dapat diambil untuk dimensi yang lebih tinggi, dan dapat diterapkan untuk setiap kombinasi sifat, bukan hanya warna piksel. Namun, dalam skenario apapun saya bisa membayangkan, teknik pemilahan konvensional jauh lebih sederhana dan lebih cepat. Jika Anda menemukan beberapa penggunaan untuk algoritma ini melampaui menciptakan gambar psychedelic, tolong beritahu saya dan silahkan setidaknya kredit saya untuk ide.
3DSort.exe untuk PC - WinZipped (26,6 Kb) adalah saya terbaru Windows 'GDI versi (16 Feb 2004), yang melakukan semacam pada berbagai bentuk permukaan (persegi, bulat, torus, dll) di <2 menit untuk daerah 512 pixel kuadrat, dan hanya detik untuk area 256 piksel kuadrat. Dioptimalkan dalam assembler, mungkin tidak mendapatkan lebih cepat dari ini - setidaknya pada P4 - 2 ghz Platform, bagaimanapun. Berikut adalah beberapa gambar yang dihasilkan oleh itu: Circle.gif ,Triangle.gif , Torus.gif .
Beberapa gambar yang lebih ...
...
Memperbarui Agustus 2016
Berikut adalah gambar yang dihasilkan dengan menciptakan 1.024 gambar yang terpisah dan rata-rata mereka semua bersama-sama. Sebanyak 123 warna yang digunakan, dihasilkan oleh melangkah setiap r, g, & nilai b sebesar 64 dan menghilangkan warna hitam dan putih. Ukuran gambar 1024 x 632 dipilih karena rasio lebar terhadap tinggi sama dengan Golden Ratio untuk presentasi yang bagus.
Berikut adalah kode di jantung pekerjaan pemilahan besar Setiap gambar mengambil lebih dari dua menit untuk membuat, dan gambar yang dihasilkan final diperlukan beberapa 34,5 jam waktu pengolahan dengan prosesor Intel i5 dan banyak RAM. Titik excersize adalah untuk menemukan "semacam sempurna" dalam arti Platonis, karena generasi gambar tergantung sepenuhnya pada proses acak. Sangat menarik untuk dicatat bahwa bahkan setelah averging bersama semua gambar secara acak, gambar yang dihasilkan masih memiliki fitur yang tajam, seakan piksel yang "ditakdirkan" untuk menemukan jalan mereka ke tempat peristirahatan terakhir mereka. Yah, mungkin aku hanya punya terlalu banyak waktu di tangan saya :)
...
A Urut Empat-dimensi Warna
Seperti disebutkan di atas, semacam itu dapat dilakukan dalam sejumlah dimensi. Semacam dilakukan pada kubus 256 pixles di sisi, diisi dengan piksel berwarna terdistribusi secara acak. Ada 123 warna dalam semua. Piksel diurutkan menurut alogorithm berikut ...
LOOP
Untuk sebuah kubus dimensi W (lebar), H (tinggi), D (kedalaman)
Pilih pixel pada koordinat acak x, y, z di mana x = {0 melalui ( W-1)}, y = {0 thru (H-2), z = {0 thru (D-1)}
Jika jumlah warna merah pada pixel bawah (di x, y + 1, z) lebih besar dari merah pixel saat ini, pertukaran piksel
Pilih pixel lain pada koordinat acak x, y, z di mana x = {0 thru (W-2)}, y = {0 thru (H-2)}, z = {0 thru (D-1 )}
Jika jumlah warna hijau pada pixel ke kanan bawah (di x + 1, y + 1, z) adalah kurang dari hijau dalam pixel saat ini, pertukaran piksel
Pilih pixel lain pada koordinat acak x, y, z di mana x = {1 thru (W-1)}, y = {0 thru (H-2)}, z = {0 thru (D-1)}
Jika jumlah biru di pixel ke kiri bawah (di x-1, y + 1 , z) adalah kurang dari biru pixel saat ini, pertukaran piksel
Akhirnya, memilih sebuah pixel pada koordinat x acak, y, z, di mana x = {0 thru (W-1)}, y = {0 thru (H-1) }, z = {0 thru (D-2)}
Jika nilai luminace dari pixel belakang di (at x, y, z + 1) lebih besar dari nilai luminace dari pixel saat ini, piksel swap.
(Luminance atau 'Y' dihitung sebagai (0,299 * Red) + (0,587 * Green) + (0,114 * Blue))
if (! Dilakukan) goto LOOP
Lanjutkan perulangan seperti miliaran ini kali, sampai keseimbangan menjadi didirikan di mana warna diurutkan ke dalam gumpalan. Pixel warna murni dalam gumpalan menjadi tidak bergerak, dan satu-satunya tindakan yang berlanjut setelah itu beberapa interaksi sepanjang interface dari beberapa gumpalan berwarna.
Sekarang perjalanan melalui sebuah kubus 256 piksel pada sisi, piksel acak dengan 123 warna, diurutkan melalui algoritma ini ...
https://youtu.be/fHl8HwrxqX4
...
Di bawah ini adalah grafik yang menggambarkan kemajuan selama semacam untuk berbagai jumlah warna pada persegi 512 piksel pada sisi. Hal ini dapat mengambil hampir 200 juta iterasi untuk mencapai keadaan stabil. Saya versi pertama tahun lalu mengambil lebih dari dua jam untuk melakukan hal semacam itu. Hanya dengan prosesor P4 saat ini dan kode assembler tangan-dioptimalkan dapat mengurutkan harus sekarang dilakukan dalam beberapa menit bukan jam. Hal ini dapat dilihat bahwa jumlah warna tidak membuat banyak perbedaan untuk ketika algoritma mencapai keadaan stabil, di mana warna diurutkan sebanyak yang mereka bisa. Satu-satunya perbedaan dramatis adalah bahwa dengan warna yang lebih, lebih banyak piksel yang tersisa untuk selamanya berjalan sepanjang antarmuka tanpa rumah untuk memanggil mereka sendiri.
Warna berasal dengan menginjak setiap komponen warna merah, hijau, dan biru dengan 128, 64, 32, 16, atau 8, lalu menghapus hitam, putih, dan abu-abu dari warna yang dihasilkan semata karena alasan estetika. Ini menghasilkan 25, 123, 727, 4911, dan 35.935 warna masing-masing.
