Algoritma untuk "menyembuhkan" beberapa persegi panjang menjadi lebih sedikit persegi panjang?

13

masukkan deskripsi gambar di sini

Katakanlah saya memiliki kotak persegi panjang dengan berbagai bentuk dan warna dan saya ingin mengurangi (cukup dekat dengan optimal baik-baik saja, optimal tidak perlu) jumlah persegi panjang untuk mewakili tata letak warna yang sama.

Gambar di atas adalah kasus yang sangat disederhanakan dan spasi putih antara persegi panjang hanya untuk visualisasi - mereka benar-benar akan penuh sesak.

Apa itu nama pendekatan atau algoritma (senang Google) yang dapat membantu saya melakukan ini?

algorithm geometry space-partitioning xaxxon
sumber
3
Bisakah Anda ceritakan sedikit tentang dari mana persegi panjang ini berasal? Apakah mereka cenderung (secara kasar) sejajar dengan kisi-kisi yang mendasarinya, atau berbagi beberapa blok bangunan yang sama, atau persegi panjang "atom" terkecil? Bisakah mereka diputar? Ini terlihat seperti jenis masalah yang bisa sangat sulit dalam kasus yang paling umum, tetapi mungkin akan jauh lebih mudah jika kita dapat mengeksploitasi beberapa kendala atau kesamaan dalam skenario khusus Anda.
DMGregory
Ada kotak kotak yang mendasarinya (seperti kotak-kotak) dan setiap kotak berbagi batas dengan kotak yang mendasarinya. yaitu Anda dapat menggunakan integer untuk menggambarkan atas / bawah / kiri / kanan setiap kotak. Karenanya mereka tidak dapat diputar dalam sudut yang tidak bisa dibagi 90 derajat. Grid NxM juga terisi penuh dengan persegi panjang - tidak ada posisi grid terbuka.
xaxxon
Saya hanya mencoba menghindari kasing yang terlihat seperti contoh di atas (dari perspektif pewarnaan), tetapi terdiri dari satu ton persegi panjang 1x1 dan saya sedang memproses masing-masing ketika saya dapat menangani ruang di banyak lebih sedikit panggilan.
xaxxon
Saya kira semacam "mulai saja di suatu tempat dan terus mencoba persegi panjang yang lebih besar dan lebih besar dalam satu dimensi (katakanlah secara vertikal) sampai Anda mencapai batas warna, lalu tumbuhkan dimensi lainnya (secara horizontal) sampai Anda mencapai batas. Kemudian coba secara horizontal terlebih dahulu . Kemudian mungkin mencoba hanya kotak (tumbuh secara diagonal) Tapi tidak yakin jika hanya memilih yang terbesar di atas 3 kemungkinan adalah pendekatan yang tepat..
xaxxon
Apakah dapat diterima untuk membagi persegi panjang yang ada, jika hasilnya lebih sedikit persegi panjang pada akhirnya? Atau haruskah algoritme hanya pernah bergabung? Juga, apakah jumlah total merupakan satu-satunya kriteria, atau apakah Anda lebih suka bentuk squarer daripada sliver kurus panjang / persegi panjang yang lebih besar daripada yang lebih kecil?
DMGregory

Jawaban:

15

Pertama, kami dapat mengonversi persegi panjang sumber Anda menjadi sel di kisi yang mendasarinya, untuk membuat input lebih seragam. (Secara efektif merasterisasi masalah)

Ini akan memungkinkan kami menemukan optimisasi yang mungkin tidak jelas ketika bekerja secara langsung dengan persegi panjang sumber - terutama ketika itu melibatkan pemisahan beberapa sumber persegi panjang untuk menggabungkannya secara berbeda.

Contoh mengubah persegi panjang menjadi sel-sel kotak dan kembali

Selanjutnya kita dapat menemukan daerah yang terhubung dengan warna yang sama, menggunakan algoritma pencarian kedalaman atau pencarian banjir. Kita dapat mempertimbangkan masing-masing daerah yang terhubung ( polyomino ) secara terpisah - tidak ada yang kita lakukan untuk wilayah yang berbeda yang perlu memengaruhi yang ini.

Secara efektif kami ingin menemukan cara untuk membedah polyomino ini menjadi persegi panjang (sayangnya sebagian besar literatur yang saya dapat temukan adalah tentang masalah yang berlawanan: membedah persegi panjang menjadi polyomino! Ini membuatnya sulit untuk mencari petunjuk ...)

Salah satu metode langsung adalah menggabungkan run horisontal dari kotak yang berdekatan menjadi persegi panjang kurus. Kemudian kita dapat membandingkan dengan baris di atas dan menggabungkan jika proses kita mulai & berakhir cocok - baik saat kita menyelesaikan setiap proses / baris, atau karena kita menganggap setiap sel untuk menambah proses saat ini.

Mengurai polyomino menjadi run horisontal, kemudian menggabungkan secara vertikal

Saya belum tahu seberapa dekat metode ini menjadi optimal. Tampaknya ia dapat mengalami sedikit masalah ketika suatu baris yang belum dianggapnya menunjukkan perpecahan yang berbeda dari baris yang terlihat sejauh ini:

Contoh kasus dengan solusi 3-persegi panjang, di mana metode di atas menemukan 4

Mendeteksi ketika menjalankan / persegi panjang persis ditutupi oleh berjalan di atas & di bawah, kemudian membaginya dan menggabungkan mereka akan menyelesaikan kasus khusus ini, tapi saya belum menjelajahi seberapa umum masalahnya.

Saya juga telah melihat metode di mana kita berjalan di sekeliling polyomino, dan memotong kapan saja kita menemukan sudut cekung, tetapi pendekatan ini terlihat lebih rentan kesalahan bagi saya. Mendapatkan hasil yang optimal tampaknya memerlukan pemotongan prioritas yang menggabungkan dua sudut cekung, dan bentuk yang mengandung lubang perlu penanganan khusus, sehingga metode pemindaian baris tampaknya memiliki keunggulan kesederhanaan.

Satu lagi metode yang saya lihat adalah untuk mengambil run pertama yang ditemukan di baris atas & memperpanjang sejauh yang Anda bisa. Kemudian jalankan pertama di baris atas dari apa yang tersisa ... Ini tersandung pada bentuk T terbalik, jadi itu juga tidak optimal.

Saya merasa mungkin ada cara untuk menggunakan pemrograman dinamis untuk menemukan pemisahan optimal, tetapi saya belum menemukannya.

DMGregory
sumber
Terima kasih atas jawaban yang luar biasa! solusi itu terlihat cukup cepat sehingga saya bisa menjalankannya dengan beberapa arah berbeda dan memilih yang mana yang terbaik - kiri kanan> kanan, kanan horisontal> kiri, dan kemudian vertikal setiap jalan juga.
xaxxon
2
Masalahnya adalah kita dapat membuat bentuk yang akan menyesatkan algoritma dari setiap arah sweep. Itu mungkin tidak akan muncul dalam penggunaan nyata, tetapi masih mengganggu saya. Saya pikir ada perbaikan sederhana belum ... Sesuatu seperti mencatat di setiap run, apakah ada sudut cekung di atasnya mid-run. Kemudian jika lari berikutnya berakhir pada titik yang persis seperti itu, kami mundur melalui berjalan di atas membelahnya secara vertikal. Saya belum menyelesaikan detail lengkapnya.
DMGregory
1
Juga, saya tidak yakin mengapa langkah mengisi banjir diperlukan. Saat beralih dari positino kisi ke persegi panjang kurus, Anda cukup berjalan di baris atau kolom penuh kisi (ke mana pun Anda pergi) untuk membuat 1xN persegi panjang itu. Tidak perlu tahu polomino, kan?
xaxxon
Anda benar, mengisi banjir bukanlah langkah yang perlu. Saya memasukkannya untuk membenarkan fokus hanya pada satu wilayah berwarna pada satu waktu dalam langkah-langkah berikutnya, tetapi Anda dapat dengan mudah menerapkan metode pemindaian baris ke beberapa wilayah berwarna yang disisipkan. Metode berbasis perimeter perlu bekerja pada perimeter satu bentuk sekaligus.
DMGregory