Pertanyaan Butuh bantuan menggabungkan beberapa persegi panjang


Screenshot of what I have (on the left) and what I'm trying to accomplish (on the right)

Hai, saya memiliki kekacauan berantakan di sebelah kiri, itu cukup banyak susunan persegi panjang dengan beberapa lubang (ditandai dengan warna merah). Saya mencari cara untuk menggabungkannya dengan cara yang saya akan berakhir dengan beberapa persegi panjang mungkin dan sebaiknya memiliki sebagian besar dari mereka akan sedekat mungkin dengan kotak. Lihatlah gambar di sebelah kanan, itulah jenis yang ingin saya capai, hanya sedikit lebih cantik dan lebih disukai sedikit lebih otomatis.

Saya membutuhkan ini untuk permainan dan itu tidak akan dilakukan pada saat runtime sehingga kecepatan tidak benar-benar menjadi perhatian (kecuali itu sangat lambat, karena saya harus melakukannya di area yang cukup besar) tetapi saya tidak pernah melakukan sesuatu seperti ini sebelumnya dan saya benar-benar tidak tahu di mana untuk memulai.

Saya sudah mencoba brute menempa jalan saya melalui array, mulai dari alun-alun kiri atas dan jenis penggabungan sampai tidak ada yang tersisa untuk digabungkan tetapi sebenarnya tidak begitu efisien karena tidak bisa mempertimbangkan penggabungan persegi panjang 3x2, 4x3, dll.

Jika Anda bisa mengarahkan saya ke algoritme apa pun yang dapat menangani hal semacam ini atau memiliki gagasan tentang bagaimana hal ini dapat diselesaikan, itu akan sangat dihargai. Terima kasih!


6
2017-09-04 18:36


asal


Jawaban:


Anda dapat mencoba algoritma serakah. Tentu saja itu tidak akan optimal (baik, Anda tidak mendefinisikan kriteria optimalitas secara ketat). Tapi mungkin itu akan berfungsi cukup baik untuk kebutuhan Anda.

Jadi Anda dapat mencoba:

  • Temukan sepasang persegi panjang yang dapat digabung dengan luas total maksimum
  • Ganti dengan yang baru - hasil operasi penggabungan
  • Ulangi hingga Anda tidak dapat menemukan pasangan yang cocok

Jika Anda juga peduli untuk menghasilkan persegi panjang yang mendekati persegi Anda dapat mencoba untuk memaksimalkan sesuatu seperti a * totalArea + (1 - a) * (min_resulting_side/max_resulting_side) dengan nilai yang cocok untuk 0 <a <1.


2
2017-09-04 21:07