Bagaimana cara menghitung rotasi angka secara efisien?

13

Gambar 1 Gambar 2

Saya memiliki Gambar diwakili melalui matriks byte (bitmap-like matrix). Contoh Gambar ditunjukkan pada Picture 1.

Tujuannya adalah untuk menemukan sudut rotasi terbaik dari beberapa Gambar yang diberikan . Ketika Gambar diputar oleh sudut terbaik, persegi panjang yang sejajar dengan sumbu X dan Y dan menuliskan Gambar memiliki area terkecil.

Persegi panjang yang menuliskan gambar ditampilkan sebagai abu-abu terang pada gambar. Dalam Picture 2, Anda dapat melihat bahwa rotasi Gambar yang ideal adalah sekitar 30 derajat searah jarum jam.

Sekarang, saya tahu algoritma bagaimana menemukan sudut ini, tetapi menurut saya itu sangat tidak efisien. Bunyinya seperti ini:

  1. Loop melalui sudut dari 0 hingga 45.
  2. Untuk sudut saat ini, untuk setiap titik angka hitung lokasi baru, diputar,
  3. Temukan batas-batas persegi panjang yang berisi gambar (minimum dan maksimum x, y) dan daftarkan jika itu adalah yang paling cocok sejauh ini
  4. Sudut selanjutnya

Ini adalah semacam metode brute-force dan bekerja dengan baik dan cukup cepat untuk angka-angka kecil. Namun, saya perlu bekerja dengan angka yang berisi hingga 10 juta poin, dan algoritma saya menjadi lambat.

Algoritma apa yang bagus untuk masalah ini?

c# algorithms geometry Dusan
sumber

Jawaban:

20

Sepertinya Anda dapat menemukan kotak batas minimum yang disejajarkan secara sewenang - wenang menggunakan algoritma kaliper berputar waktu linear .

Setelah Anda memiliki kotak pembatas, Anda hanya perlu menentukan sudut rotasi dengan menghitung kemiringan salah satu sisi.

Dan Pichelman
sumber
Ini adalah solusi hebat, sangat bagus.
InformedA
Hebat, karena saya sudah mengurutkan poin dengan x dan y, saya dapat menemukan convex hull dengan en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/… dan menggunakan algoritma yang ada dengan poin hull.
Dusan
12

Langkah pertama dari pendekatan Anda cacat - ada jumlah tak terhingga dari nilai nyata antara 0 dan 45, jadi tidak masuk akal untuk "mengulanginya". Namun, algoritme Anda dapat diperbaiki:

  • temukan cembung lambung poligon

  • lingkaran melalui jumlah terbatas (!) sudut yang diberikan oleh tepi luar cembung cembung

  • sekarang terapkan langkah 2 hingga 4 menggunakan sudut ini.

Ini berfungsi karena dapat ditunjukkan bahwa persegi panjang penutup minimum harus menyentuh salah satu tepi luar lambung cembung.

Doc Brown
sumber
Ya, itulah yang akan saya lakukan, sudah menemukan sedikit bantuan dari jawaban Dan. Terima kasih.
Dusan
@ Susan: Saya tidak yakin jawaban yang lain menjelaskan pendekatan yang sama, jadi saya mencoba menggambarkan solusinya dengan cara yang lebih sederhana, semoga sedikit lebih jelas. Temukan
Doc Brown
Ya, Anda benar, pendekatan Anda jauh lebih konkret dan lebih sederhana dan lebih jelas, tetapi saya sendiri telah menyimpulkan pendekatan yang sama dengan petunjuk yang diberikan dalam jawaban Dan, jadi saya memberinya tanda terima. Semoga jawaban Anda mendapatkan lebih banyak suara. Tidak ada perasaan keras. Bersulang!
Dusan