Titik-titik sudut dari poligon dapat diurutkan baik dalam urutan Searah Jarum Jam (CW) atau Berlawanan Arah Jarum Jam (CCW). Dalam visualisasi ini, kami lebih memilih menggunakan urutan CCW (meskipun menggambar poligon dengan titik-titik sudut dalam urutan CW juga diperbolehkan). Di balik layar, kami juga mengatur titik pertama = titik terakhir untuk menyederhanakan implementasi.
Perhatikan bahwa kami membatasi poligon yang digambar menjadi poligon sederhana, yaitu, tidak ada perpotongan sisi.
Jumlah titik sudut poligon disimpan dalam variabel n. Karena poligon adalah sirkuit tertutup, jumlah sisi poligon juga n.
Semua operasi yang tersedia terdaftar di menu sisi kiri seperti biasa.
Dua yang pertama digunakan untuk memberikan poligon input sederhana, dan lima berikutnya adalah algoritma geometri komputasi yang dapat Anda jalankan pada poligon yang sedang digambar.
Dalam visualisasi ini, Anda dapat menggambar poligon sederhana apa pun (minimal 3 titik), tanpa titik yang kollinear (sebenarnya, mungkin untuk memodifikasi implementasi kami untuk memungkinkan titik kollinear, hanya saja itu akan memperumit beberapa operasi). Poligon terkecil yang memungkinkan adalah segitiga.
Poligon yang Anda gambar dapat berupa convex (garis yang menghubungkan dua titik di dalam poligon akan tetap berada di dalam poligon) atau concave.
Jika Anda tidak menutup loop (menggambar sisi dari titik terakhir kembali ke titik 0), kami akan melakukannya secara otomatis untuk Anda.
Kami menyediakan beberapa contoh poligon sebagai titik awal.
Setelah memuat halaman visualisasi ini, kami akan mengacak poligon contoh yang dipilih.
Keliling poligon adalah jumlah dari panjang (jarak Euclidean) dari segmen-segmen garis berturut-turut (sisi poligon).
Rutin ini berfungsi untuk poligon convex maupun concave dan berjalan dalam waktu O(n).
Tanpa berlama-lama, mari kita hitung dari poligon yang sedang digambar saat ini.
Ketika titik-titik dari sebuah poligon diberikan dalam urutan melingkar (searah jarum jam atau berlawanan arah jarum jam), kita dapat menghitung luasnya menggunakan Rumus Shoelace.
Rumus Shoelace ini mengembalikan luas, yaitu setengah dari hasil cross product vektor yang didefinisikan oleh titik akhir sisi-sisi poligon.
Rumus ini serbaguna karena dapat digunakan untuk poligon cembung maupun cekung. Perhitungannya dapat dilakukan dalam waktu O(n).
Tanpa basa-basi lagi, mari kita hitung dari poligon yang saat ini digambar.
Sebuah poligon disebut sebagai poligon Cembung (Convex) jika kita menggambar garis antara sembarang dua titik yang berbeda di dalam poligon dan garis tersebut selalu tetap berada di dalam poligon. Sebaliknya, poligon disebut Cekung (Concave).
Ada metode yang jauh lebih mudah untuk memeriksa apakah sebuah poligon (asumsi tidak ada tiga titik yang kolinear) cembung tanpa menggunakan definisi langsung di atas. Kita dapat memeriksa apakah semua tiga titik berturut-turut dari poligon membentuk jenis belokan yang sama (semua berlawanan arah jarum jam atau semua searah jarum jam). Pemeriksaan ini jelas O(n).
Tanpa basa-basi lagi, mari kita periksa apakah poligon yang saat ini digambar .
Ada beberapa algoritma untuk memeriksa apakah sebuah titik (pt1) berada di dalam poligon atau tidak. Kami menganggap algoritma yang paling kuat adalah Algoritma Winding Number yang menghitung jumlah sudut yang dibentuk oleh setiap sisi poligon dengan pt1 sebagai titik asal. Karena hanya ada n sudut tersebut, pemeriksaan ini juga berjalan dalam O(n).
Poligon sederhana yang dimasukkan bisa serumit kasus uji "MAZE" yang ditampilkan saat ini. Cobalah kasus uji dan .
Dalam Mode Eksplorasi, Anda akan diminta untuk memberikan titik yang diuji (pt1) sebagai input tambahan untuk operasi ini.
Kita dapat memotong poligon konveks dengan garis lurus yang ditentukan oleh dua titik (pt1, pt2). Hasil dari pemotongan adalah dua poligon yang lebih kecil namun juga konveks. Algoritma ini saat ini mengembalikan poligon yang lebih kecil di 'sisi kiri' dari garis pemotongan (pt1, pt2).
Perhatikan bahwa meskipun memungkinkan, memotong poligon cekung lebih rumit karena dapat menghasilkan lebih dari dua poligon (dan mungkin poligon degenerasi). Kami memungkinkan operasi semacam ini dalam visualisasi ini, tetapi perhatian ekstra harus diberikan dalam implementasi nyata.
Coba untuk melihat versi default dari rutinitas ini dan di mana kami menukar pt1 dan pt2 untuk mendapatkan sisi lainnya dari pemotongan.
Dalam Mode Eksplorasi, Anda akan diminta untuk menyediakan dua titik untuk mendefinisikan garis potong (pt1 dan pt2) sebagai input tambahan dari operasi ini (untuk menghindari kasus degenerasi, kedua titik ini harus diletakkan di lokasi yang berbeda).
Rutinitas ini juga berjalan dalam O(n).
Terdapat satu visualisasi geometri komputasi dalam VisuAlgo: Convex Hull.
Anda dapat menggunakan beberapa algoritma pada poligon untuk menyelesaikan beberapa latihan pemrograman: UVa 11265 - The Sultan's Problem and Kattis - robotprotection.
Anda dapat menggunakan/memodifikasi kode implementasi kami untuk beberapa algoritma poligon:
polygon.cpp | py | java | ml