Terinspirasi oleh vi.sualize.us
Tujuan
Input adalah gambar skala abu-abu dan outputnya adalah gambar hitam putih. Gambar output hanya terdiri dari satu kurva tertutup (loop) yang tidak diizinkan untuk bersinggungan dengan dirinya sendiri atau menyentuh sendiri. Lebar garis harus konstan di seluruh gambar. Tantangannya di sini adalah menemukan algoritma untuk melakukannya. Output hanya harus mewakili gambar input, tetapi dengan kebebasan artistik. Resolusi tidak begitu penting tetapi rasio aspek harus tetap hampir sama.
Contoh
Lebih banyak gambar uji
The width of the line shall be constant throughout the whole image.
Tapi masih petunjuk yang bergunaJawaban:
Java: Gaya dot matrix
Karena tidak ada yang menjawab pertanyaan, namun saya akan mencobanya. Pertama saya ingin mengisi kanvas dengan kurva Hilbert, tetapi pada akhirnya saya memilih pendekatan yang lebih sederhana:
Ini kodenya:
Pembaruan : Sekarang ia menciptakan siklus, bukan hanya satu baris
sumber
Python: Hilbert curve (
373361)Saya memutuskan untuk menggambar kurva Hilbert dengan variabel granularitas tergantung pada intensitas gambar:
Sebenarnya saya berencana untuk membuat keputusan pada tingkat detail yang berbeda, seperti "Tempat ini sangat cerah, saya akan menghentikan rekursi dan pindah ke blok berikutnya!". Tetapi mengevaluasi intensitas gambar secara lokal yang mengarah ke gerakan besar sangat tidak akurat dan terlihat jelek. Jadi saya berakhir dengan hanya memutuskan apakah akan melewati level 1 atau menggambar lingkaran Hilbert yang lain.
Ini adalah hasil gambar uji pertama:
Berkat @githubphagocy renderingnya cukup cepat (menggunakan
turtle.tracer
). Jadi saya tidak perlu menunggu sepanjang malam untuk hasilnya dan bisa pergi ke tempat tidur saya yang memang layak. :)Beberapa kode golf
@ flawr: "program singkat"? Anda belum melihat versi golfnya! ;)
Jadi hanya untuk bersenang-senang:
(
373361 karakter. Tapi itu akan selamanya karena saya menghapusturte.tracer(...)
perintah!)Animasi oleh flawr
flawr: Algoritme saya sedikit dimodifikasi dengan apa yang dikatakan @DenDenDo kepada saya: Saya harus menghapus beberapa poin di setiap iterasi karena konvergensi akan melambat secara drastis. Itu sebabnya kurva akan memotong sendiri.
sumber
screen.tracer(0)
bukanturtle.speed(0)
. Anda mungkin perlu membuat instance layar di awal, tetapi jika itu adalah satu-satunya contoh layar semua kura-kura Anda akan secara otomatis ditugaskan untuk itu. Kemudian hanyascreen.update()
di bagian akhir untuk menampilkan hasilnya. Saya kagum dengan perbedaan kecepatan ketika saya pertama kali menemukan ini ...Python 3.4 - Masalah Salesman Bepergian
Program ini membuat gambar bingung dari aslinya:
Untuk setiap piksel hitam, sebuah titik dihasilkan secara acak di dekat pusat piksel dan titik-titik ini diperlakukan sebagai masalah salesman keliling . Program ini menyimpan file html yang berisi gambar SVG secara berkala ketika mencoba mengurangi panjang lintasan. Jalan mulai berpotongan sendiri dan secara bertahap menjadi kurang dari beberapa jam. Akhirnya jalan tidak lagi berpotongan:
Program ini menggunakan 3 pendekatan berbeda untuk meningkatkan solusi, dan mengukur kinerja per detik untuk masing-masing. Waktu yang dialokasikan untuk masing-masing pendekatan disesuaikan untuk memberikan sebagian besar waktu untuk pendekatan apa pun yang berkinerja terbaik pada waktu itu.
Awalnya saya mencoba menebak berapa proporsi waktu yang dialokasikan untuk masing-masing pendekatan, tetapi ternyata pendekatan mana yang paling efektif sangat bervariasi selama proses berlangsung, sehingga membuat perbedaan besar untuk tetap menyesuaikan secara otomatis.
Tiga pendekatan sederhana adalah:
Untuk pendekatan 3 digunakan kisi, mendaftar semua garis yang melewati sel tertentu. Daripada harus memeriksa setiap baris pada halaman untuk persimpangan, hanya mereka yang memiliki sel grid yang sama diperiksa.
Saya mendapat ide untuk menggunakan masalah salesman keliling dari posting blog yang saya lihat sebelum tantangan ini diposting, tetapi saya tidak bisa melacaknya ketika saya memposting jawaban ini. Saya percaya gambar dalam tantangan diproduksi menggunakan pendekatan salesman keliling juga, dikombinasikan dengan semacam jalur smoothing untuk menghilangkan tikungan tajam.
Saya masih tidak dapat menemukan posting blog tertentu tetapi saya sekarang telah menemukan referensi ke makalah asli di mana Mona Lisa digunakan untuk menunjukkan masalah salesman keliling .
Implementasi TSP di sini adalah pendekatan hybrid yang saya coba untuk bersenang-senang untuk tantangan ini. Saya belum membaca makalah terkait saat saya memposting ini. Pendekatan saya sangat lambat dibandingkan. Perhatikan bahwa gambar saya di sini menggunakan kurang dari 10.000 poin, dan membutuhkan waktu berjam-jam untuk cukup konvergen sehingga tidak ada garis silang. Contoh gambar di tautan ke makalah menggunakan 100.000 poin ...
Sayangnya sebagian besar tautan tampaknya sudah mati sekarang, tetapi makalah "TSP Art" oleh Craig S Kaplan & Robert Bosch 2005 masih berfungsi dan memberikan gambaran menarik tentang berbagai pendekatan.
sumber
Java - Osilasi
Program ini menggambar jalur tertutup dan menambahkan osilasi yang amplitudo dan frekuensinya didasarkan pada kecerahan gambar. "Sudut" jalur tidak memiliki osilasi untuk memastikan jalur tidak berpotongan dengan sendirinya.
Di bawah ini algoritma yang sebanding yang didasarkan pada spiral. ( Saya tahu jalannya tidak menutup dan itu pasti berpotongan , saya hanya mempostingnya demi seni :-)
sumber
Java - Jalur Rekursif
Saya mulai dari jalur tertutup 2x3. Saya memindai setiap sel jalur dan membaginya menjadi sub-jalur 3x3 baru. Saya mencoba setiap kali untuk memilih sub-path 3x3 yang "mirip" gambar aslinya. Saya ulangi proses di atas 4 kali.
Ini kodenya:
sumber