Bagaimana menemukan persegi panjang area maksimum di dalam poligon cembung?

21

Dalam posting ini kami sedang mencari algoritma / ide tentang bagaimana menemukan maksimum-area-persegi panjang di dalam poligon cembung .

Pada gambar berikut, angka adalah area persegi panjang yang dipasang. Seperti yang ditunjukkan persegi panjang yang diinginkan dapat bervariasi di setiap dimensi dan dapat di sudut mana pun.

Edit:

Kami tidak memiliki gagasan yang jelas bagaimana menangani masalah yang disebutkan karena itu kami bertanya di sini. Namun demikian, kami menduga bahwa luas-luas-persegi panjang mungkin salah satu dari mereka yang memiliki satu sisi sejajar (tentu saja tidak dengan panjang sisi yang sama, tentu saja) tepi poligon.

masukkan deskripsi gambar di sini

Pengembang
sumber
1
Bisakah Anda menentukan perangkat lunak apa yang Anda gunakan? Juga, posting pekerjaan Anda sejauh ini, atau pendekatan umum yang telah Anda lakukan untuk menyelesaikannya. Mungkin seseorang dapat meningkatkan apa yang telah Anda lakukan. Dalam pengalaman saya, itu akan menghasilkan jawaban yang jauh lebih berguna daripada hanya memposting pertanyaan "tiba-tiba".
Martin
@Martin Software: Pemrograman di Pythonkemudian akan masuk Fortranjika diperlukan. Kami memiliki dugaan bahwa berdasarkan posting kami sebelumnya di sini juga disebutkan di atas oleh whuberbahwa mungkin persegi panjang dengan tepi yang sama dengan poligon akan menjadi jawaban.
Pengembang
1
Masalah Anda sangat menarik, dan saya pikir saya berhasil menemukan algoritma penyelesaian di sini dan di sini .
nickves
1
@nickves Terima kasih atas tautannya. Apakah Anda mau memberikan info ini sebagai jawaban dengan sedikit penjelasan tentang algoritma? Ini akan berpotensi jawaban yang baik untuk diterima.
Pengembang

Jawaban:

4

Beberapa catatan terlalu besar untuk dimasukkan ke dalam komentar (meskipun ini tidak menyarankan algoritma yang jelas):

The punch line (EDITED) : Setidaknya dua simpul dari persegi panjang area maksimum harus terletak pada batas poligon (yaitu di sepanjang tepi, atau di puncak). Dan jika persegi panjang area maksimum bukan persegi, maka setidaknya tiga simpul harus terletak pada batas poligon.

Saya membuktikannya pada diri saya dalam empat langkah:

Catatan # 1 : Setidaknya satu simpul dari persegi panjang area maksimum akan selalu terletak pada batas poligon. Ini cukup jelas, tetapi buktinya bisa seperti ini (dengan kontradiksi): Misalkan Anda memiliki persegi panjang "maksimal" tanpa simpul pada batas poligon. Itu berarti akan ada setidaknya sedikit ruang di sekitar masing-masing simpulnya. Jadi Anda bisa memperluas persegi panjang Anda sedikit, bertentangan dengan maksimalnya.

Catatan # 2 : Setidaknya dua simpul dari persegi panjang area maksimum akan selalu terletak pada batas poligon. Buktinya bisa seperti ini (sekali lagi dengan kontradiksi): Misalkan Anda memiliki persegi panjang "maksimal" dengan hanya satu simpul pada batas (dijamin oleh Catatan # 1). Pertimbangkan dua sisi yang tidak berdekatan dengan simpul itu. Karena titik akhir mereka BUKAN pada batas, ada sedikit ruang di sekitar masing-masing. Jadi salah satu dari tepi itu bisa "diekstrusi" sedikit, memperluas area poligon dan bertentangan dengan maksimalnya.

Catatan # 3 : Ada dua simpul yang berlawanan secara diagonal dari luas area maksimum yang terletak pada batas poligon. (Kita tahu dari Catatan # 2 bahwa paling tidak ada dua, tetapi tidak harus saling berhadapan satu sama lain.) Tetapi sekali lagi dengan kontradiksi, jika hanya dua simpul batas yang bersebelahan, maka tepi yang berseberangan (tak satu pun dari simpul yang memiliki simpul berada di batas) dapat diekstrusi sedikit, meningkatkan luas persegi panjang dan bertentangan dengan maksimalitasnya.

Catatan # 4 : (DIedit) Jika persegi panjang area maksimum bukan persegi, maka tiga simpulnya akan terletak pada batas poligon.

Untuk membuktikan, anggap itu tidak terjadi, yaitu bahwa persegi panjang area maksimum bukan persegi, tetapi hanya dua dari simpulnya berada pada batas poligon. Saya akan menunjukkan bagaimana membangun persegi panjang yang lebih besar, yang bertentangan dengan maksimalitas.

Panggil simpul dari persegi panjang A, B, C, dan D. Tanpa kehilangan sifat umum, asumsikan itu Bdan Dkeduanya adalah yang berada pada batas poligon. Karena Adan Cberada di bagian dalam poligon, ada beberapa ruang gerak di sekitar mereka (diwakili dengan lingkaran di sekitar Adan Cpada gambar di bawah). Sekarang gambar sebuah lingkaran di sekitar persegi panjang, dan geser poin Adan Csedikit di sekitar lingkaran dengan jumlah yang sama (untuk membuat A'dan C', digambarkan di bawah) sehingga persegi panjang baruA'BC'Dlebih persegi dari persegi panjang asli. Proses ini menciptakan persegi panjang baru yang juga dalam poligon asli dan memiliki area yang lebih besar. Ini adalah kontradiksi, jadi buktinya dilakukan.

Membangun persegi panjang baru

Untuk mempercayai bukti itu, Anda harus meyakinkan diri sendiri bahwa luas persegi panjang yang tertulis dalam lingkaran bertambah ketika menjadi "lebih persegi" (yaitu perbedaan antara panjang tepi semakin kecil). Anda juga perlu poligon menjadi cembung sehingga garis-garis baru ada di dalamnya. Dan mungkin ada detail kecil lainnya tersapu di bawah karpet, tapi saya cukup yakin mereka semua berhasil.

csd
sumber
Catatan # 4 mencurigakan, karena "menggeliat" dua simpul lainnya akan membuat non-persegi panjang.
whuber
Benar. Namun, visualisasi Anda pada contoh ke-4 kurang tepat (jika 2 simpul berada pada batas poligon, Anda tidak dapat merentangkannya lebih jauh). Saya tidak dapat menemukan persis bagaimana menjelaskannya (mencoba menulis komentar tetapi terlalu berantakan), tapi saya percaya Anda benar.
Saryk
Saya percaya ada contoh tandingan untuk dicatat # 4. Yang saya temukan mengambil beberapa perhitungan yang terlibat untuk ditampilkan, meskipun; yang paling sederhana adalah gangguan dari segi enam tidak teratur (kotak dengan dua sudut yang berlawanan sedikit terpotong).
whuber
Setuju bahwa Note # 4 mencurigakan. Saya akan melihat lebih dekat malam ini dan memperbaikinya atau menghapusnya.
csd
+1 Itu adalah resolusi kesulitan yang bagus. Terima kasih untuk hasil editnya!
whuber
3

Saya telah membuat sketsa yang sangat cepat dan mengerikan tentang catatan hijau Anda dalam pertanyaan. Saya tidak dapat mempostingnya sebagai komentar jadi saya harus menulis jawaban, walaupun itu bukan jawaban.
Saya percaya bahwa pada gambar di bawah ini kami memiliki luas persegi panjang maksimum (tidak sempurna, itu hanya sketsa yang dibuat pada Paint untuk memberikan ide), dan saya tidak berpikir Anda dapat menemukan yang lebih besar yang akan memiliki kesamaan dengan perbatasan plygon hitam ...
Namun saya bisa salah, dalam hal ini Anda memiliki semua permintaan maaf saya.
Sketsa Cepat yang saya buat di Paint

Saryk
sumber
3
Poin bagus (+1). Namun, ada contoh tandingan yang jauh lebih sederhana: pertimbangkan masalah menuliskan persegi panjang area maksimal dalam segi delapan biasa. Sangat mudah dilihat (dan mudah dibuktikan dengan pertama-tama menemukan kotak maksimal dalam lingkaran oktagon) bahwa sudut-sudut larutan bertepatan dengan simpul bolak-balik dari segi delapan dan bahwa solusi ini secara substansial lebih besar daripada persegi panjang bertuliskan edge-aligned.
whuber
Sebenarnya (saya hanya punya keraguan besar sekarang), persegi panjang terkecil eksternal (yang dari posting ini ) dari poligon ini tidak memiliki orientasi yang sama dengan salah satu sisi, bukan? (Saya akan melihatnya dengan orientasi yang sama dengan persegi panjang merah saya)
Saryk
3
Omong-omong, poligon itu bukan cembung. Pertanyaan aslinya tidak membatasi poligon cembung.
csd
2
@csd Itu poin bagus, tapi Saryk masih benar, seperti yang ditunjukkan oleh counterexample saya. Saryk, tidak ada masalah dengan persegi panjang pembatas area minimum: mudah untuk membuktikan (secara ketat) bahwa itu harus mencakup sisi lambung cembung. Saya percaya area maksimum bertuliskan segi empat (dari poligon cembung) hanya perlu memiliki dua simpul menyentuh batas, tidak lebih.
whuber
2

Sebagian besar algoritma lainnya menemukan luas maksimum bujur sangkar persegi panjang tertulis dalam poligon cembung, dan memiliki kompleksitas O(log n). Saya tidak berpikir tebakan Anda bahwa area max poligon disejajarkan dengan salah satu sisi benar, karena semua yang perlu Anda lakukan adalah memutar nkali poligon , menghasilkan kompleksitas O(n log n), dan dalam penelitian singkat saya, saya tidak bisa menemukan sesuatu yang mengatakan itu mudah.

Namun, kertas Rectangular Tertulis Tertulis di Cembung Poligon oleh Knauer, et. al., menjelaskan algoritma perkiraan yang akan membuat Anda mendekati jawaban yang tepat.

Sebaik yang saya mengerti algoritme, itu dibangun di atas salah satu dari poligon area max sejajar sumbu yang diketahui, dan kemudian sampel secara acak poin di dalam ruang polon, menghasilkan beberapa sumbu dari sampel acak, mengulangi sumbu tersebut dan menerapkan sumbu Algoritma -dignign untuk masing-masing, dan kemudian mengembalikan persegi panjang terbesar di set itu.

lreeder
sumber
Apakah mungkin ada kesalahan ketik pada kalimat pertama? Tidak mungkin ada algoritma O (log (n)) karena hanya membaca dalam koordinat adalah operasi O (n)!
whuber
Tautannya sudah mati
berbahaya,
1
@dangerousdave - Menemukan tautan pengganti untuk waktu yang lama ...
lreeder