Algoritma Pemisahan Orthogonal Polygon dengan sebuah Polyline

Abstract

Pemisahan adalah sebuah operasi dasar pada orthgonal polyogon. Tulisan ini mengusulkan sebuah algoritma untuk memisahkan orthogonal polygon dengan sebuah polyline. Terdapat tiga langkah untuk melakukan pemisahan yaitu: 1) sortir simpul secara AB-sorted; 2) gabungkan simpul polygon orthogonal dan polyline; 3) kelompokan simpul yang telah digabungkan menjadi dua kolompok simpul yang mewakili polygon orthogonal yang lebih kecil. Algoritma ini ekfektif dan mempunyai kompleksitas waktu yang linear.

Keywords--orthogonal polygon, polyline, penyortiran