Hitung jumlah sisi pada poligon
Robot penghitung sisi poligon telah memutuskan untuk melakukan perjalanan dunia tanpa memberitahu siapa pun sebelumnya, tetapi sangat penting bahwa proses penghitungan poligon tidak dihentikan terlalu lama. Jadi, Anda memiliki tugas berikut: Diberikan gambar hitam dan putih poligon, program / functoin Anda harus mengembalikan jumlah sisi.
Program ini akan diumpankan ke komputer kartu punch lama, dan karena kartu punch sangat mahal saat ini, Anda sebaiknya mencoba membuat program Anda sesingkat mungkin.
Tepi setidaknya 10 piksel, dan sudut yang dibentuk oleh dua tepi adjecent setidaknya 10 ° tetapi tidak lebih dari 170 ° (atau lebih besar dari 190 °). Poligon benar-benar terkandung di dalam gambar, dan poligon serta komplemennya terhubung (tidak ada pulau terisolasi) sehingga input ini tidak valid:
Mencetak gol
Ini codegolf, artinya pengiriman terpendek dalam byte menang, kiriman Anda harus menemukan jumlah tepi yang benar untuk setiap kasus uji. (Dan pengajuan harus bekerja untuk kasus-kasus lain juga, optimisasi hanya untuk kasus-kasus uji tidak diperbolehkan.)
Jika Anda ingin mengirimkan solusi yang tidak menemukan nomor yang benar setiap kali, Anda dapat mengirimkannya juga, tetapi itu akan diperingkat di belakang semua pengiriman yang berkinerja lebih baik.
Harap sertakan jumlah total dalam judul kiriman Anda. (Kesalahan total jumlah perbedaan mutlak antara jumlah sisi yang nyata dan setiap output).
Uji kasus
n = 10
n = 36
n = 7
n = 5
Ini bukan ujian, hanya karena penasaran: Berapa banyak tepi yang Anda dapatkan untuk input ini?
sumber
Jawaban:
Python 2 + PIL, tidak ada kesalahan,
313307 byteMengambil nama file gambar pada baris perintah, dan mencetak hasilnya ke STDOUT.
Memberikan hasil yang benar untuk semua tes, dan n = 28 untuk lingkaran.
Penjelasan
Algoritma ini bekerja dengan berjalan di sepanjang perimeter poligon, dan menghitung jumlah simpul yang ditemui (terdeteksi sebagai perubahan arah). Kita mulai pada piksel yang paling jauh dari asalnya,,
o
yang dijamin sebagai titik, dan oleh karena itu, berdekatan dengan tepi (yaitu, batas antara piksel latar depan dan piksel latar belakang). Kami melacak posisi kami,,p
titik terbaruv
, dan "pos pemeriksaan" terbaruq
, yang semuanya awalnya sama dengano
. Kami juga melacak arah tepid
,, relatif terhadap piksel saat ini;d
awalnya menunjuk ke timur, yang merupakan arah yang aman, karena kita tahu ada ujung ke timuro
, atau yang tidak akan terjauh dari asalnya. Kami bergerak di sepanjang tepi, dalam arah yang tegak lurusd
, sehinggad
mengarah ke kiri, yaitu, dalam arah searah jarum jam. Setiap kali kita "jatuh dari tepi", yaitu, dalam situasi apa pun dip
luar poligon, atau di mana piksel di sebelah kiri kita (yaitu, ke arahd
) ada di dalam poligon, kami menyesuaikanp
dand
sesuai sebelum melanjutkan.Setiap kali jarak antara
p
dan pos pemeriksaan terakhirq
,, menjadi lebih besar dari 5, kami mencoba menentukan apakah kami melewati titik di antaraq
danp
: Kami membandingkan sudut antaravq
(yaitu, vektor dariv
keq
), yang merupakan arah umum dari sisi poligon kami berjalan bersama ketika kami mencapai pos pemeriksaan terakhir, danqp
, perpindahan antara pos pemeriksaan terakhir dan posisi saat ini. Jika sudut lebih besar dari sekitar 10 °, kami menyimpulkan bahwa kami berjalan di sisi yang berbeda dari poligon, menambah jumlah titik, dan mengaturv
, titik saat ini, untukp
. Di setiap pos pemeriksaan, terlepas dari apakah kami mendeteksi titik atau tidak, kami memperbaruiq
, pos pemeriksaan terakhir, kep
. Kami melanjutkan dengan cara ini sampai kami tiba kembali dio
, titik awal, dan mengembalikan jumlah simpul yang ditemukan (perhatikan bahwa jumlah titik awalnya 1, karena titik awalo
, itu sendiri merupakan titik.)Gambar di bawah ini menunjukkan simpul yang terdeteksi. Perhatikan bahwa pengambilan
p
, posisi saat ini di setiap pos pemeriksaan, karena posisi titik baru tidak optimal, karena titik sebenarnya mungkin berada di antara titik pemeriksaan terakhirq
,, danp
, di sepanjang perimeter. Seperti yang Anda lihat, semua simpul selain yang pertama (umumnya, simpul kanan-bawah) sedikit tidak aktif. Memperbaiki ini akan membutuhkan lebih banyak byte, tetapi ini tampaknya bekerja dengan cukup baik. Meski begitu, agak sulit untuk tidak berpakaian dengan hanya empat test case.sumber
o
, bukankah ujung lainnya akan lebih jauh dari asalnya?o
adalah piksel latar depan terjauh dari asalnya, jadi piksel di sebelah timurnya harus merupakan piksel latar belakang, maka kami mengatakan bahwa ada tepi di sebelah timuro
.