Poligon dan Algoritma-Algoritma pada Poligon

1. Introduction

Poligon adalah sebuah figur bidang yang dibatasi oleh sirkuit tertutup yang terdiri dari urutan terbatas segmen garis lurus.

Visualisasi ini memiliki beberapa algoritma yang dapat dilakukan pada poligon simpel dengan lebih dari 3 titik non-kolinear, seperti menentukan apakah sebuah poligon termasuk konveks atau konkaf, apakah suatu titik terdapat di dalam atau di luar poligon, serta menentukan apakah sebuah garis memotong poligon tersebut.

2. Visualisasi

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.

3. Operasi-Operasi yang Tersedia

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.

3-1. Edit Polygon

In this visualization, you can edit the currently displayed simple polygon (at least 3 points) into any other valid simple polygon, without any collinear points (actually, it is possible to modify our implementation to allow collinear points, just that it will complicate a few operations). The smallest such polygon is a triangle.


The polygon that you draw can be either convex (line connecting any two points inside the polygon will remain inside the polygon) or concave.


If you do not close the loop (draw an edge from last vertex back to vertex 0), we will do that automatically for you.

3-2. Contoh Poligon-Poligon

We provide a few example polygons as a starting point.


Upon loading this visualization page, we will randomize the chosen example polygon.


Note that some of these example polygons indeed already have a few collinear points to showcase some edge cases, making some of these example polygons a bit hard to edit.

3-3. Keliling dari sebuah Poligon

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 Perimeter dari poligon yang sedang digambar saat ini.

3-4. Luas dari sebuah Poligon

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 Area dari poligon yang saat ini digambar.

3-5. Mengecek jika Poligonnya Konveks

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 IsConvex.

3-6. Cek Bila sebuah TItik berada didalam Poligon

There are a few algorithms for checking if a point (pt1) is inside a polygon or not. We reckon the most robust algorithm is the Winding Number algorithm that computes the sum of angles subtended by each edge/side of the polygon with pt1 as the origin. As there are only n such angles, this check also runs in O(n).


The input simple polygon can be as complicated as the currently displayed "MAZE" test case. Try InsidePolygon, OutsidePolygon, or OnPolygon test cases.


In Exploration Mode, you will be asked to provide the tested point (pt1) as additional input of this operation.

3-7. Cutting a Convex Polygon with a Vector

We can cut a convex polygon with a straight line defined by two points (pt1, pt2). The result of the cut are two smaller but also convex polygons. This algorithm currently returns the smaller polygon on 'the left side' of the cutting vector (pt1 → pt2).


Note that although possible, cutting a Concave polygon is more complicated as it may result in more than two (and possibly degenerate) polygons. We allow such operation in this visualization but extra care must be exercised in the actual implementations.


Try Left Side to see the default version of this routine and Right Side where we swap pt1 and pt2 to get the other side of the cut.


In Exploration Mode, you will be asked to provide two points to define the cut line (pt1 and pt2) as additional input of this operation (to avoid degenerate case, these two points should be placed at different locations).


This routine also runs in O(n).

4. Tambahan-Tambahan

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