Pertimbangkan poligon yang berpotongan-sendiri yang berpotensi, yang ditentukan oleh daftar simpul dalam ruang 2D. Misalnya
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
Ada beberapa cara untuk mendefinisikan bidang poligon seperti itu, tetapi yang paling menarik adalah aturan genap. Mengambil titik mana pun di pesawat, menggambar garis dari titik keluar hingga tak terbatas (ke segala arah). Jika garis itu melintasi poligon beberapa kali ganjil, titik tersebut merupakan bagian dari area poligon, jika garis itu melintasi poligon beberapa kali, titik tersebut bukan bagian dari poligon. Untuk contoh poligon di atas, berikut adalah garis besarnya dan juga area genapnya:
Poligon pada umumnya tidak ortogonal. Saya hanya memilih contoh sederhana untuk memudahkan menghitung area.
Area dari contoh ini adalah 17
(tidak 24
atau 33
sebagai definisi atau area lain mungkin menghasilkan).
Perhatikan bahwa di bawah definisi ini area poligon tidak tergantung pada urutan belitannya.
Tantangan
Diberikan daftar simpul dengan koordinat bilangan bulat yang mendefinisikan poligon, tentukan luasnya di bawah aturan genap.
Anda dapat menulis suatu fungsi atau program, mengambil input melalui STDIN atau alternatif terdekat, argumen baris perintah atau argumen fungsi dan mengembalikan hasilnya atau mencetaknya ke STDOUT atau alternatif terdekat.
Anda dapat mengambil input dalam format string atau daftar yang mudah digunakan, selama itu tidak diproses sebelumnya.
Hasilnya harus berupa angka floating point, akurat hingga 6 digit signifikan (desimal), atau hasil rasional yang representasi floating point-nya akurat hingga 6 digit signifikan. (Jika Anda menghasilkan hasil yang rasional, kemungkinan besar akan tepat, tetapi saya tidak dapat meminta ini, karena saya tidak memiliki hasil yang tepat untuk referensi.)
Anda harus dapat menyelesaikan setiap kasus uji di bawah ini dalam waktu 10 detik pada mesin desktop yang masuk akal. (Ada beberapa kelonggaran dalam aturan ini, jadi gunakan penilaian terbaik Anda. Jika butuh 20 detik pada laptop saya, saya akan memberi Anda manfaat dari keraguan, jika butuh satu menit, saya tidak akan.) Saya pikir batas ini harus sangat murah hati tetapi seharusnya mengesampingkan pendekatan di mana Anda hanya mendiskreditkan poligon pada kisi dan jumlah yang cukup baik, atau menggunakan pendekatan probabilistik seperti Monte Carlo. Jadilah olahragawan yang baik dan jangan mencoba mengoptimalkan pendekatan ini sehingga Anda tetap dapat memenuhi batas waktu. ;)
Anda tidak boleh menggunakan fungsi apa pun yang ada yang terkait langsung dengan poligon.
Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang.
Asumsi
- Semua koordinat bilangan bulat dalam kisaran
0 ≤ x ≤ 100
,0 ≤ y ≤ 100
. - Setidaknya akan ada
3
dan paling banyak50
simpul. - Tidak akan ada simpul berulang. Tidak ada simpul terletak di tepi yang lain. (Namun, mungkin ada titik collinear dalam daftar.)
Uji Kasus
{{0, 0}, {5, 0}, {5, 4}, {1, 4}, {1, 2}, {3, 2}, {3, 3}, {2, 3}, {2, 1}, {4, 1}, {4, 5}, {0, 5}}
17.0000
{{22, 87}, {6, 3}, {98, 77}, {20, 56}, {96, 52}, {79, 34}, {46, 78}, {52, 73}, {81, 85}, {90, 43}}
2788.39
{{90, 43}, {81, 85}, {52, 73}, {46, 78}, {79, 34}, {96, 52}, {20, 56}, {98, 77}, {6, 3}, {22, 87}}
2788.39
{{70, 33}, {53, 89}, {76, 35}, {14, 56}, {14, 47}, {59, 49}, {12, 32}, {22, 66}, {85, 2}, {2, 81},
{61, 39}, {1, 49}, {91, 62}, {67, 7}, {19, 55}, {47, 44}, {8, 24}, {46, 18}, {63, 64}, {23, 30}}
2037.98
{{42, 65}, {14, 59}, {97, 10}, {13, 1}, {2, 8}, {88, 80}, {24, 36}, {95, 94}, {18, 9}, {66, 64},
{91, 5}, {99, 25}, {6, 66}, {48, 55}, {83, 54}, {15, 65}, {10, 60}, {35, 86}, {44, 19}, {48, 43},
{47, 86}, {29, 5}, {15, 45}, {75, 41}, {9, 9}, {23, 100}, {22, 82}, {34, 21}, {7, 34}, {54, 83}}
3382.46
{{68, 35}, {43, 63}, {66, 98}, {60, 56}, {57, 44}, {90, 52}, {36, 26}, {23, 55}, {66, 1}, {25, 6},
{84, 65}, {38, 16}, {47, 31}, {44, 90}, {2, 30}, {87, 40}, {19, 51}, {75, 5}, {31, 94}, {85, 56},
{95, 81}, {79, 80}, {82, 45}, {95, 10}, {27, 15}, {18, 70}, {24, 6}, {12, 73}, {10, 31}, {4, 29},
{79, 93}, {45, 85}, {12, 10}, {89, 70}, {46, 5}, {56, 67}, {58, 59}, {92, 19}, {83, 49}, {22,77}}
3337.62
{{15, 22}, {71, 65}, {12, 35}, {30, 92}, {12, 92}, {97, 31}, {4, 32}, {39, 43}, {11, 40},
{20, 15}, {71, 100}, {84, 76}, {51, 98}, {35, 94}, {46, 54}, {89, 49}, {28, 35}, {65, 42},
{31, 41}, {48, 34}, {57, 46}, {14, 20}, {45, 28}, {82, 65}, {88, 78}, {55, 30}, {30, 27},
{26, 47}, {51, 93}, {9, 95}, {56, 82}, {86, 56}, {46, 28}, {62, 70}, {98, 10}, {3, 39},
{11, 34}, {17, 64}, {36, 42}, {52, 100}, {38, 11}, {83, 14}, {5, 17}, {72, 70}, {3, 97},
{8, 94}, {64, 60}, {47, 25}, {99, 26}, {99, 69}}
3514.46
sumber
upath
operator. (Ini sebenarnya adalah konversi 1: 1 yang sangat sederhana antara pemisah.}, {
Hanya menjadilineto
, dan koma antara x dan y dihapus, dan kawat gigi pembuka dan penutup diganti dengan header dan footer statis ...)upath
danlineto
terdengar seperti Anda benar-benar memproses input. Yaitu Anda tidak mengambil daftar koordinat tetapi poligon yang sebenarnya.CrossingPolygon
.Jawaban:
Mathematica,
247225222Pertama-tama tambahkan titik persimpangan ke poligon, lalu balikkan beberapa tepinya, kemudian luasnya dapat dihitung seperti poligon sederhana.
Contoh:
sumber
{1,2},{4,4},{4,2},{2,4},{2,1},{5,3}
? Anda harus keluar dengan 3.433333333333309. Saya melihat menggunakan logika yang sama.103/30
, dan nilai numeriknya3.43333
.Python 2,
323319 byteMengambil daftar simpul melalui STDIN sebagai bilangan kompleks, dalam bentuk berikut
, dan menulis hasilnya ke STDOUT.
Kode yang sama setelah penggantian string dan beberapa spasi:
Penjelasan
Untuk setiap titik perpotongan dua sisi poligon input (termasuk simpul), lewati garis vertikal melewati titik itu.
(Faktanya, karena bermain golf, program melewati beberapa baris lagi; itu tidak terlalu penting, selama kita melewati setidaknya baris-baris ini.) Tubuh poligon antara dua garis berurutan terdiri dari trapesium vertikal ( dan segitiga, dan segmen garis, sebagai kasus khusus dari mereka). Itu harus menjadi kasus, karena jika salah satu dari bentuk-bentuk ini memiliki simpul tambahan antara dua pangkalan, akan ada garis vertikal lain melalui titik itu, antara dua garis tersebut. Jumlah area dari semua trapesium tersebut adalah area poligon.
Inilah cara kami menemukan trapesium ini: Untuk setiap pasang garis vertikal berturut-turut, kami menemukan segmen dari setiap sisi poligon yang (dengan benar) terletak di antara kedua garis ini (yang mungkin tidak ada untuk beberapa sisi). Dalam ilustrasi di atas, ini adalah enam segmen merah, ketika mempertimbangkan dua garis vertikal merah. Perhatikan bahwa segmen ini tidak saling berpotongan dengan benar (yaitu, mereka hanya dapat bertemu pada titik akhir, benar-benar bertepatan atau tidak berpotongan sama sekali, karena, sekali lagi, jika berpotongan dengan benar akan ada garis vertikal lain di antaranya;) dan jadi masuk akal untuk berbicara tentang memesannya dari atas ke bawah, yang kami lakukan. Menurut aturan genap, begitu kita melewati segmen pertama, kita berada di dalam poligon; begitu kita melewati yang kedua, kita keluar; yang ketiga, lagi; yang keempat, keluar; dan seterusnya...
Secara keseluruhan, ini adalah algoritma O ( n 3 log n ).
sumber
Haskell, 549
Sepertinya saya tidak bisa bermain golf yang satu ini cukup jauh, tetapi konsepnya berbeda dari dua jawaban lainnya, jadi saya pikir saya akan membagikannya. Ia melakukan operasi rasional O (N ^ 2) untuk menghitung area.
Contoh:
Idenya adalah untuk memasang kembali poligon di setiap persimpangan, menghasilkan penyatuan poligon tanpa tepi yang bersilangan. Kami kemudian dapat menghitung area (yang ditandatangani) dari masing-masing poligon menggunakan rumus tali sepatu Gauss ( http://en.wikipedia.org/wiki/Shoelace_formula ). Aturan genap bahkan menuntut bahwa ketika persimpangan dikonversi, luas poligon baru dihitung secara relatif relatif terhadap poligon lama.
Sebagai contoh, perhatikan poligon dalam pertanyaan awal. Persimpangan di kiri atas dikonversi menjadi dua jalur yang hanya bertemu pada satu titik; kedua jalur keduanya berorientasi searah jarum jam, sehingga area masing-masing akan positif kecuali kita menyatakan bahwa jalur dalam dibobot oleh -1 relatif terhadap jalur luar. Ini setara dengan pembalikan jalur alphaalpha.
Sebagai contoh lain, perhatikan poligon dari komentar MickyT:
Di sini, beberapa poligon berorientasi searah jarum jam dan beberapa berlawanan arah jarum jam. Aturan sign-flip-on-crossing memastikan bahwa wilayah yang berorientasi searah jarum jam mengambil faktor tambahan -1, menyebabkan mereka berkontribusi jumlah positif ke area tersebut.
Begini cara program bekerja:
sumber