Mengisi ruang antara garis 2D acak

Pertimbangkan suatu wilayah (2D) yang diisi dengan garis-garis secara acak (Gambar berikut). Kami tertarik untuk mengisi ruang kosong di antara garis termasuk empat tepi batas dengan cara:

0- memaksimalkan ukuran parsel;
1- bentuk paket mengisi persegi selaras secara horizontal atau vertikal;
2 - bentuk parsel isian berbentuk bujur sangkar, yaitu keselarasan yang rileks ;
3 - bentuk mengisi paket adalah segala segi empat. pertanyaan awal kami

Jadi untuk saat ini ada tiga skenario berbeda.
Perhatikan bahwa garis-garis adalah [x1,y1,x2,y2]set titik bentuk , bilangan real.

[* * *] Gagasan kemungkinan solusi / algoritme / cuplikan kode / dll lebih dari diterima.

Pembaruan 1: Kami dapat mengelola solusi untuk kasus pertama:

Langkah-langkahnya adalah:
1- baris
2- rasterisasi baris ke dalam bitmap
3- mencari sel terdekat untuk setiap sel warna yang diinginkan (yaitu, warna yang sama) dengan fungsi tujuan untuk memaksimalkan yaitu daerah, jumlah sel.

Ini bekerja dengan baik namun hanya mencakup skenario pertama dan juga lambat.

Pembaruan 2:
Kami berasumsi bahwa pembaca akrab dengan konsep penataan ruang-mengisi. Anda dapat mengikuti tautan untuk inspirasi. Namun perhatikan bahwa masalah kita berbeda. Karena kami tidak mengisi ruang kosong secara acak dan kami tidak memilih ukuran secara acak. Solusinya harus berulang. Untuk semua kasus, tidak ada batasan jumlah paket yang dipasang. Memang, itu tergantung pada pengguna untuk membatasi nomor iterasi, dengan memilih area minimum untuk paket, misalnya. Ini jelas dalam contoh yang diberikan di atas di mana kami memisahkan garis menjadi piksel dengan ukuran yang ditentukan. Artinya, prosedur harus berjalan sampai seluruh area kosong dipenuhi dengan kriteria misalnya, area maksimum paket.

Pembaruan 3:
ringkasan:
Satu aplikasi adalah untuk mengetahui distribusi blok 'batu' utuh yang dapat diekstraksi dalam 'tambang' yang sangat retak. Ini bisa sangat membantu untuk banyak aspek termasuk desain pengeboran, evaluasi keuangan dll
deskripsi:
Untuk tambang batu hias (batu) produk yang merupakan blok dari batu utuh dipotong sebagai kubus persegi panjang, harga sangat tergantung pada ukuran blok. Ekstraksi blok dari area yang sesuai yaitu, tanpa fraktur utama akan diinginkan jika jumlah bagian yang tersisa sekecil mungkin. Biasanya, potongan-potongan kecil batu tidak memiliki nilai ekonomi yang relatif dan dianggap sebagai limbah.
Pertanyaan dalam posting ini menyelidiki solusi untuk masalah seperti ini.

Pandangan matematis untuk masalah ini dapat dinyatakan sebagai berikut:
2D: Temukan semua persegi panjang yang dapat diekstraksi dari wilayah 2D tertentu dengan beberapa garis yang dioptimalkan untuk ukuran persegi yang lebih besar mungkin.
3D: Temukan semua kubus persegi panjang yang dapat diekstraksi dari wilayah 3D tertentu dengan beberapa sub-bidang (lebih baik: poligon) yang dioptimalkan untuk ukuran blok yang lebih besar.

Karena ini adalah bagian dari penelitian yang sedang berlangsung, beberapa pertanyaan yang diajukan dalam komentar di bawah tidak memiliki jawaban tertentu yang dapat kami berikan. Kami percaya bahwa informasi yang diberikan di sini sejauh ini memang cukup untuk mendapatkan gambaran keseluruhan masalah. Namun demikian, kami memberikan beberapa detail yang kami bisa untuk manfaat masyarakat.
Anda dapat memberikan beberapa batasan pada solusi untuk pertanyaan pamungkas, meskipun, kami yakin selalu mungkin untuk menambahkan lebih banyak nanti. Sebagai contoh, ikuti ini: {2D case}
Ukuran terbaik dari sebuah blok (segi empat optimum ekonomis) untuk diekstraksi di bawah kondisi yang disebutkan di atas, 1x1 mdiberikan 10x10 muntuk wilayah dalam contoh. Ini adalah salah satu kendala yang ditentukan berdasarkan nilai ekonomis. Ukuran minimum yang bisa diterapkan untuk memotong dll0.15x0.15 m; jadi ini batas ukuran kedua.

Gambar di atas menunjukkan fungsi nilai ekonomi tergantung pada ukuran blok. Jadi untuk kasus khusus ini setiap potongan batu yang lebih kecil dari 0.15x0.15 msekadar limbah. Tidak akan ada ukuran blok yang lebih besar dari 1.7x1.7 mbatas operasi.

Saya punya ide bagaimana Anda bekerja secara iteratif dari blok besar ke blok kecil menggunakan FME (oleh Safe Software.) Sebagai catatan saya tidak bekerja untuk mereka tetapi tampaknya memuji alat mereka cukup ...

1. Gunakan "BoundingBoxReplacer" di area yang diinginkan.
2. Proyeksi ulang ke sistem koordinat lokal (untuk nanti ketika Anda perlu "memasang" dalam satuan kaki / meter.)
3. Buffer garis dengan transformator "Bufferer". Anda hanya perlu ukuran acak, katakan 0,01 kaki / meter. Apa yang kita cari di sini adalah poligon garis untuk langkah selanjutnya.
4. Tambahkan Transformer "Tiler". Tentukan Ukuran Ubin yang besar (diperkirakan atau sebaliknya) dalam Kaki atau Meter. Apa yang kami lakukan di sini adalah memasang bidang yang diminati menjadi balok persegi. Tergantung pada dataset mulai besar untuk benar-benar mendapatkan outlier besar.
5. Tambahkan trafo "Clipper". Apa yang kami lakukan di sini pada dasarnya adalah mengiris dataset untuk melihat ubin mana yang baik / buruk. Pada output, ubin yang "Di dalam" terlalu besar. Namun, ubin yang "Luar" cukup besar dan siap untuk memotong ...
6. Di sinilah kompleksnya, tetapi tidak sulit ... Kita akan memutarkan transformator sehingga kita menggunakan kembali BoundingBox yang asli, tetapi memotong area yang sudah siap untuk dipotong. Jadi, tambahkan clipper dan rutekan Clipper sebagai ubin "Output" pada output clipper sebelumnya. Sekarang kami memiliki satu poligon yang siap untuk bekerja lagi.
7. Gunakan tiler lagi, kali ini menentukan ubin yang lebih kecil. Misalnya jika Anda menggunakan ubin 100 meter sebelumnya, coba 90 meter.
8. Tambahkan clipper lain, dengan clipper input menjadi garis buffered, dan clippee input menjadi ubin yang lebih kecil sebagai input.

Bilas dan ulangi sebanyak yang diperlukan dengan menggunakan ubin yang lebih kecil setiap kali. Saya telah memasang awal meja kerja yang akan saya gunakan sebagai satu pendekatan.

Berdasarkan uraian (terperinci dengan baik) Anda, itu hanya akan berfungsi dengan opsi 1 Anda untuk saat ini. Tanpa menghabiskan banyak waktu dulu.

Bagaimanapun, ini hanyalah satu pendekatan yang akan saya mulai dengan setidaknya menyaring gandum dari sekam.