Menentukan apakah satu set ubin di kotak membentuk bentuk tertutup

Diberikan satu set ubin di kotak, saya ingin menentukan:

• Jika ubin membuat gambar terlampir
• Jika ubin membuat gambar terlampir ketika Anda menghitung sisi papan sebagai tepi gambar
• Jika salah satu dari dua pernyataan sebelumnya benar, ubin tambahan mana yang berada di dalam gambar terlampir di formulir ubin awal.

Pemain akan mulai dengan menekan satu ubin, lalu menyeret jari mereka ke ubin lain untuk membuat rantai ubin berwarna sama. Saya akan memeriksa ketika saya pergi untuk melihat apakah ubin berikutnya valid. Ex. Jika pemain dimulai pada ubin merah, mereka hanya valid bergerak selanjutnya adalah ubin merah yang berdekatan (diagonal melakukan count). Ketika pengguna mengangkat jari mereka, saya harus dapat memeriksa 3 item di atas.

Jadi pemikiran awal saya adalah bahwa, karena saya memeriksa validitas rantai setiap kali saya pergi, ketika pemain mengangkat jari mereka, saya bisa memeriksa apakah ubin pertama dan terakhir berdekatan. (Saya sudah tahu warnanya sama.) Jika mereka berdekatan, saya punya firasat bahwa saya akan membuat figur tertutup, dan saya akan datang ke sini untuk mencoba dan melihat apakah saya kehilangan sesuatu yang besar, dan untuk mendapatkan semacam bukti logis / matematis bahwa dugaan saya benar (atau contoh membuktikannya salah.)

Tetapi saat itulah saya memikirkan item nomor 2: Saya juga harus memperhitungkan rantai yang menggunakan tepi papan sebagai sisi dari gambar terlampir. Dalam hal itu, item pertama dan terakhir dalam rantai tidak akan berdekatan, tetapi saya masih memiliki sosok terlampir. Jadi sekarang saya kembali ke titik awal, sedikit.

Apa yang bisa saya lakukan dengan rantai koordinat kotak ini untuk mencari tahu apakah mereka membuat angka terlampir atau tidak? Dan setelah saya lakukan tahu aku memiliki angka tertutup, apa cara terbaik untuk mendapatkan daftar tambahan dari semua ubin yang jatuh di dalam batas-batas nya?

Di atas saya telah menggambar gambar dari apa yang saya harapkan 4 hasil yang mungkin dari tes ini dapat.

1. Rantai tidak membuat gambar terlampir.

2. Rantai memang membuat sosok terlampir.

3. Jika Anda menghitung sisi papan sebagai bagian tepi (atau lebih dari satu sisi) gambar, rantai membuat gambar terlampir.

4. Rantai memang membuat angka terlampir, tetapi ada titik data tambahan (dipilih secara sah oleh pengguna sebagai bagian dari rantai) yang bukan merupakan bagian dari angka yang dibuat.

Kasus 4 adalah yang paling sulit, karena Anda harus mengekstrak tautan rantai "ekstra" untuk menemukan gambar terlampir dan potongan-potongan yang berada di dalamnya (tetapi tidak di sekitar area "tanpa tutup").

Jadi ... Ada yang punya ide tentang cara yang baik untuk menyelesaikan ini, atau hanya titik awal bagi saya? Saya agak berputar-putar pada titik ini dan bisa menggunakan mata yang lain.

1. Mendeteksi satu lingkaran ubin

Masalahnya tampaknya mirip dengan mendeteksi siklus (loop) dalam grafik, lihat di sini atau di sini .

• Himpunan node Vdari grafik itu G=(V, E)adalah ubin,
• e = (v1, v2)ada tepi antara dua node yang berbeda, jika ubin langsung atau diagonal tetangga

2. Menangani kasing layar

Perbatasan layar terdiri dari ubin imajiner yang akan membentuk tepi lebar satu ubin di sekitar layar ubin yang terlihat.

Menurut spesifikasi Anda bagian dari perbatasan layar akan membentuk bagian implisit dari loop tertutup. Hanya untuk mendeteksi loop tertutup, itu akan cukup untuk memperluas grafik Gke grafik G'dengan menghormati koneksi melalui aturan ini:

• tepi lain ada di antara dua node yang berbeda, jika dua ubin masing-masing diposisikan tepat di dekat batas layar

Jadi ubin di (0,0) dan (1,0) akan menjadi bagian dari loop tertutup, bersama dengan "ubin batas" (-1,0), (-1, -1), (0, -1) , (1, -1).

3. Bagian dalam area melingkar

Saya akan pergi ke arah yang serupa dengan apa yang disarankan oleh pengguna Arthur Wulf White :

Membatasi kumpulan ubin yang harus kita periksa dengan kotak pembatas ubin lingkaran.

Kemudian menggunakan mengisi banjir untuk memilih semua ubin dalam kotak pembatas yang baik eksterior atau interior ke loop tertutup. Itu hanya salah satu dari dua kasus itu. Yang mana yang harus kita cari tahu sesudahnya.

Memperluas kotak pembatas dengan satu ubin di setiap arah akan menjadi ide yang baik juga, menghasilkan extbb, jadi kita hanya berakhir dengan satu set titik eksterior yang terhubung, jika kita mulai mengisi banjir dengan ubin eksterior.

Setelah kami memiliki area genangan banjir, kami akan menghitung kotak pembatasnya, yaitu ffbb. Jika kita mulai dengan ubin eksterior, itu harus identik dengan kotak pembatas loop diperpanjang.

ffbb == extbb

Jika kita mulai dengan ubin interior, itu harus menghasilkan kotak pembatas yang jelas lebih kecil, karena ubin lingkaran harus diapit di antara kedua kotak pembatas.

ffbb < extbb

Ubin awal awal untuk isi banjir dapat berupa ubin apa pun di dalamnya extbbyang merupakan ubin gratis. Mungkin memilih satu secara acak adalah pendekatan terbaik.

Jika saya tahu sebelumnya bahwa interior lebih kecil dari eksterior, saya akan mulai di sekitar pusat massa titik loop yang ada di interior untuk banyak area (contoh konter: area berbentuk C), jika tidak di perbatasan extbb. Tapi saya tidak tahu bagaimana memperkirakan ini.

Komentar akhir

Secara normal saya akan mengatakan berjalan sederhana mulai dari beberapa ubin dan menyimpan daftar ubin yang dikunjungi akan cukup untuk mendeteksi siklus, tetapi kondisi batas layar mungkin menghasilkan grafik yang lebih rumit, jadi Anda harus berada di sisi yang aman dengan algoritma grafik .

Di bawah ini adalah contoh di mana interior tidak terhubung, di sisi lain deteksi siklus harus menemukan dua loop dalam kasus itu, satu harus dibuang.

Anda dapat menyelesaikan ini dengan:

1. Menemukan kotak pembatas bentuk itu.
2. Meningkatkan ukurannya dengan 1 di setiap arah.
3. Iterasi pada bingkai kotak pembatas yang sedikit diperbesar dan aplikasikan pengisian banjir.
4. Jika ada ubin yang tidak Anda tandai dengan genangan-banjir yang tidak ada di rantai itu, maka ubin itu tertutup. Saya kira itu menurut definisi Anda jika ada ubin tertutup daripada bentuknya adalah sosok tertutup.

Untuk melakukan satu, iterate atas semua ubin pada rantai dan menemukan mereka minX, minY, maxXdan maxYdan itu adalah kotak berlari atau aabb.

Dua itu sepele.

Iterasi pada bingkai sederhana, pastikan untuk tidak mengisi banjir di luar grid. Anda dapat mempelajari cara mengisi banjir di Wikipedia .

Untuk nomor empat Anda bisa mulai dengan hanya memeriksa ubin yang berdekatan dengan rantai. Anda dapat mengisi dari ubin mana pun yang Anda temukan yang tidak ditandai untuk menemukan lebih banyak ubin.

Intuisi Anda benar, dengan anggapan bahwa rantai berakhir segera setelah pengguna mencoba memilih ubin yang telah mereka pilih. Dalam hal ini, bentuknya secara umum terlihat seperti laso, dalam gambar Anda (4). Jika mereka dapat terus menggesek, maka mereka dapat menarik banyak loop, dan segalanya menjadi lebih rumit. Yang ingin Anda lakukan adalah menjawab pertanyaan point-in-polygon .

Pertama, kita perlu mendefinisikan masalahnya. Saya akan berasumsi bahwa situasinya seperti (2), yaitu setiap ekor telah dilepas, dan akhirnya menghubungkan kembali ke awal, sehingga setiap ubin memiliki tepat satu "pendahulu" dan tepat satu "penerus" dalam rantai (di mana pendahulu penerus ubin X selalu ubin X). Selanjutnya, jika Anda mengikuti "penerus" cukup lama, Anda akhirnya kembali ke tempat Anda mulai. Anda dapat menggunakan saran Gurgadurgen untuk mendeteksi apakah loop benar-benar melintasi kembali pada titik mana pun. Dengan asumsi Anda mengakhiri input pengguna ketika itu, itu akan terlihat seperti beberapa seri node dalam satu baris, diikuti oleh satu loop. Anda dapat menghapus garis dari mendapatkan loop.

Sekarang kita, untuk setiap baris lakukan hal berikut:

1. Mulai dari tepi kiri, dan pantau boolean untuk setiap ubin yang memberi tahu apakah kita DI DALAM atau KELUAR. Memulai.
2. Jika ubin saat ini adalah bagian dari rantai, lihat baik penerus dan pendahulunya (yang harus berdekatan). Jika salah satunya benar-benar di atas (yaitu utara, timur laut, atau barat laut ubin saat ini), atur keadaan ubin saat ini ke kebalikan dari ubin di sebelah kiri. Kalau tidak, atur sama dengan ubin di sebelah kiri. Goto 4.
3. Jika ubin saat ini bukan bagian dari rantai, atur ubin ke status judul di sebelah kirinya. Goto 4.
4. Ubin di sebelah kanan sekarang menjadi ubin saat ini. Goto 2.

Sekarang ambil semua ubin yang IN, tambahkan ubin di perbatasan (termasuk ekor jika Anda melepasnya sebelumnya atau tidak, pilihan Anda), dan menyebutnya wilayah.

Jika Anda ingin mengizinkan pengguna untuk menggunakan batas, ingat bahwa ini tidak mendefinisikan dan IN / OUT di papan tulis, tetapi hanya membaginya menjadi dua bagian. Anda dapat memilih wilayah yang lebih kecil, misalnya, atau meminta pengguna untuk menggunakan dua sisi yang bersebelahan (yaitu, kiri dan bawah, tetapi tidak atas / bawah atau kiri / kanan).

Optimasi adalah Anda hanya perlu melakukan baris yang memiliki batas di dalamnya (jika Anda tidak dapat menggunakan sisi). Saya berasumsi bahwa papan Anda cukup kecil sehingga bisa diulang di setiap ubin dan melakukan perhitungan yang sangat sederhana bukanlah masalah, bahkan pada sistem seluler terlemah. (Lagi pula, Anda harus membuat mereka, yang jauh lebih kompleks dari tugas).