rotating_calipers
Rotating calipers 1.0
Kaliper putar adalah modul Python yang menerapkan algoritma dengan nama yang sama.
Algoritma pertama kali ditemukan oleh Michalel Shamos pada tahun 1978 dan mendapatkan namanya "Calipers Rotating" berkat Godfried Toussant yang menampilkannya di korannya pada tahun 1983.
Metode ini dinamai demikian karena idenya analog dengan memutar caliper vernier pegas di sekitar bagian luar poligon cembung. Setiap kali satu bilah kaliper terletak datar di tepi poligon, ia membentuk pasangan antipodal dengan titik atau tepi menyentuh bilah yang berlawanan. "Rotasi" lengkap dari kaliper di sekitar poligon mendeteksi semua pasangan antipodal; Set semua pasangan, dipandang sebagai grafik, membentuk trackle. Metode kaliper berputar dapat ditafsirkan sebagai dual proyektif dari algoritma garis sapuan di mana sapuan melintasi lereng garis daripada melintasi koordinat titik X atau y.
Deskripsi di atas diadaptasi dari halaman Wikipedia: https://en.wikipedia.org/wiki/rotating_calipers
Algoritma "Calipers Rotating" diimplementasikan oleh saya untuk proyek universitas. Secara mengejutkan saya mengalami banyak kesulitan menemukan solusi yang efisien di Python. Itulah sebabnya saya ingin membagikannya dengan semua orang yang membutuhkan implementasi "caliper rotating" dengan cepat di Python.
Karena kaliper berputar berjalan dalam waktu linier, ia membutuhkan lambung cembung pada input WIHCH dihitung di sini menggunakan algoritma Graham yang berjalan di O (nlogn). Semua dalam semua kompleksitas waktu algorihm (algoritma graham + rotating caliper) adalah O (nlogn) + O (n) = O (nlogn)
Linux:
Contoh penggunaan dapat ditemukan di sini
