Axis Aligned Spatial Division: Membagi ruang menjadi persegi panjang acak?

Saya perlu metode untuk membagi ruang 3d menjadi bentuk kotak sejajar sumbu acak. Untuk saat ini saya sedang membagi ruang 2d untuk tujuan pengujian. Pendekatan paling cepat yang saya lakukan adalah mendefinisikan persegi panjang ukuran (1, 1) dan kemudian secara rekursif membagi semua persegi panjang yang ada menjadi dua persegi panjang yang tidak rata bergantian antara sumbu X dan Y.

Masalahnya di sini sudah jelas. Pendekatan ini menghasilkan garis peregangan yang panjang (ditandai dengan warna merah)

Yang saya inginkan adalah sesuatu yang terlihat lebih organik (saya sertakan contoh)

Lihat, tidak ada garis lurus panjang dari atas ke bawah atau kiri ke kanan.

Satu-satunya kendala adalah bahwa saya mungkin ingin membatasi ukuran minimal dari persegi panjang tanpa mempengaruhi granularity ukuran. yaitu jika kotak terkecil adalah 1 cm persegi dari detik ruangan terkecil tidak harus 2 unit persegi.

Jadi idealnya algoritma harus memenuhi ketiga kendala berikut:

1. Persegi panjang tidak terlalu kecil.
2. Ukuran rect bukan perkalian diskrit dari ukuran rect terkecil. yaitu jika kotak terkecil adalah 3 unit persegi daripada rekt yang lebih besar tidak dibatasi menjadi 6, 9, 12 dan seterusnya unit persegi dan sebaliknya bisa menjadi 3,2 atau 4,7 dalam hal ini).
3. Algoritme berjalan dalam waktu polinomial (perlu menghitung cepat).

Pendekatan yang Anda buat sederhana dan bermanfaat, tetapi menderita artefak mengerikan seperti yang ditunjukkan. Hindari itu. Anda membutuhkan algoritma pertumbuhan paralel; untuk model single-threaded, pendekatan round-robin mengikuti:

1. Tempatkan berbagai titik secara acak di ruang peta Anda. Normalisasi distribusinya (hindari pengelompokan jelek) menggunakan distribusi Gaussian atau dengan menerapkan algoritma relaksasi berulang untuk memindahkan titik-titik yang ditempatkan secara acak satu sama lain, sesuai relaksasi Lloyd untuk Diagram Voronoi . Poin-poin ini mewakili centroid dari calon kamar Anda.
2. (Paralel / Ulangi round-robin untuk semua kamar) Dari setiap titik, tumbuhkan 4 simpul ke luar (ruang persegi panjang), bergerak dari titik pusat per iterasi global (Anda dapat menumbuhkan kamar yang berbeda dengan laju yang berbeda di setiap sumbu daripada yang sama untuk semua, dan lihat bagaimana hasilnya - mungkin untuk hasil yang lebih organik / bervariasi). Pada titik tertentu, beberapa persegi panjang Anda akan mulai menekan satu sama lain. Pada titik itu, batasi pertumbuhan sumbu itu, pastikan ujung-ujung yang berdekatan dari kedua ruangan benar-benar bersentuhan, dan lanjutkan.
3. Ulangi langkah 2, tumbuhkan setiap kamar secara bertahap, sampai semua pertumbuhan dibatasi oleh ruang yang berdekatan atau batas peta.
4. Ini masih akan meninggalkan beberapa ruang kosong. Masalahnya sekarang menjadi salah satu penempatan dan pembuatan kamar dari ruang yang tidak ditempati. Faktanya, jika ruang Anda yang mendasari adalah kisi (integer-indexed) (dan setiap iterasi pertumbuhan masuk ke kisi itu), maka ini jauh lebih mudah untuk ditangani, karena Anda dapat mempertahankan daftar sel kisi yang diduduki dan tidak dihuni: Sekali Anda Saya telah menempatkan dan menumbuhkan semua kamar Anda, mencari melalui daftar kosong untuk ruang diskrit yang terdiri dari kelompok sel yang berdekatan. Karena banyak ruang yang tidak digunakan akan memiliki bentuk non-persegi panjang, Anda harus memilih sel secara acak dari dalam ruang non-persegi panjang itu, dan menumbuhkannya ke ukuran maksimal seperti yang Anda lakukan dengan kamar di langkah 2. Ulangi dalam kata non -Ruang segi empat, sampai benar-benar terisi.
5. Ulangi langkah 4 hingga peta Anda terisi 100%.

Seperti yang Anda lihat, saya berhasil menyingkirkan dunia artefak ini. Idenya sangat mirip.

1. Bagilah ruang 2d menjadi kotak yang tidak seragam. Jika dua garis terlalu dekat, hapus satu.
2. Pilih persegi panjang secara acak, periksa apakah telah dimodifikasi di sumbu-y (tingginya) dan jika tetangga langsung dimodifikasi di sumbu-y. Saya sama-sama tidak dimodifikasi, minta mereka menegosiasikan ulang segmen di antara mereka (satu akan menyumbangkan beberapa ruang untuk yang lain).
3. Lakukan hal yang sama seperti pada langkah 2 hanya kali ini pada sumbu lainnya.
4. Ulangi proses ini sampai Anda memodifikasi sebanyak mungkin.

Kisi tidak seragam (1):

Bernegosiasi pada sumbu x (2):

Bernegosiasi pada sumbu y (3):

Hasil (4):