Geometric Problem , dengan membaca judul pun sudah tau pasti ini berhubungan dengan matematika dan dalam materi Analisis Algoritma geometry problem tersebut akan di implementasikan dalam bentuk komputasi.
Pengertian Geometric Problem Bekaitan dengan objek geometrik, yaitu titik, garis, poligon dan lain-lain.
Pada jaman Yunani Kuno : membangun geometrik sederhana contohnya segitiga, lingkaran dan lain-lain, dan pada Masa kini digunakan dalam aplikasi computer grafik atau robot. Masalah klasik :
1. Problem closest pair : diberikan titik pada suatubidang, dan temukan pasangan terdekatnya
2. Convex hull : temukan poligon cembung terkecilyang melibatkan smeua titik yang telah ditentukan.
Convex hull adalah masalah klasik , dan Persoalannya digambarkan secara sederhana dalam ruang dimensi dua (bidang) sebagai mencari subset dari himpunan titik pada bidang tersebut sedemikian rupa sehingga jika titik-titik tersebut dijadikan poligon maka akan membentuk poligon yang konveks. Suatu poligon dikatakan konveks jika digambarkan garis yang menghubungkan antar titik maka tidak ada garis yang memotong garis yang menjadi batas luar poligon. Definisi lain dari convex hull adalah poligon yang disusun dari subset titik sedemikian sehingga tidak ada titik dari himpunan awal yang berada di luar poligon tersebut (semua titik berada di batas luar atau di dalam area yang dilingkupi oleh poligon tersebut).
Pengertian Geometric Problem Bekaitan dengan objek geometrik, yaitu titik, garis, poligon dan lain-lain.
Pada jaman Yunani Kuno : membangun geometrik sederhana contohnya segitiga, lingkaran dan lain-lain, dan pada Masa kini digunakan dalam aplikasi computer grafik atau robot. Masalah klasik :
1. Problem closest pair : diberikan titik pada suatubidang, dan temukan pasangan terdekatnya
2. Convex hull : temukan poligon cembung terkecilyang melibatkan smeua titik yang telah ditentukan.
Convex hull adalah masalah klasik , dan Persoalannya digambarkan secara sederhana dalam ruang dimensi dua (bidang) sebagai mencari subset dari himpunan titik pada bidang tersebut sedemikian rupa sehingga jika titik-titik tersebut dijadikan poligon maka akan membentuk poligon yang konveks. Suatu poligon dikatakan konveks jika digambarkan garis yang menghubungkan antar titik maka tidak ada garis yang memotong garis yang menjadi batas luar poligon. Definisi lain dari convex hull adalah poligon yang disusun dari subset titik sedemikian sehingga tidak ada titik dari himpunan awal yang berada di luar poligon tersebut (semua titik berada di batas luar atau di dalam area yang dilingkupi oleh poligon tersebut).
 |
| Convex Hull |
Petunjuk untuk
menyelesaikan persoalan ini adalah persamaan garis pada bidang. Persamaan garis
pada bidang memisahkan bidang menjadi dua bagian yaitu area di sebelah kanan
bidang (relatif terhadap orientasi garis). Sebagai contoh garis berorientasi
adalah sumbu koordinat. Misalkan saja sumbu vertikal (ordinat, arah orientasi
ke atas), seluruh titik di sebelah kanan garis ini memiliki nilai komponen
koordinat horizontal (X) yang positif sedangkan seluruh titik di sebelah kiri
garis memiliki nilai komponen koordinat horizontal negatif.
Petunjuk di atas
dimanfaatkan dengan membuat definisi bahwa garis yang dibentuk oleh titik-titik
poligon jika diasumsikan memiliki orientasi yang sama, maka setiap titik berada
di sebelah kanan seluruh garis batas tersebut. Definisi ini kemudian
dimanfaatkan untuk menentukan aksi awal yaitu memilih titik yang berada paling
luar pertama. Mencari titik pertama cukup mudah yaitu cukup memilih titik yang
memiliki nilai komponen koordinat (horizontal atau vertikal) yang ekstrim
(minimum atau maksimum). Titik-titik convex hull lainnya ditentukan berdasarkan
titik pertama tadi.
Algoritma awal yang
intuitif dari deskripsi paragraf sebelumnya adalah.
· - memilih titik
pertama
· - memilih titik
berikutnya, berdasarkan definisi:
· - jika dibuat garis
dengan titik sebelumnya maka seluruh titik lainnya tidak ada yang berada di
sebelah kiri.
· - jika titik tersebut
sesuai maka dimasukkan dalam daftar titik luar.
Algoritma tersebut menggunakan pendekatan exhaustive (brute-force).
kompleksitas algoritma tersebut mendekati O(n2). Algoritma tersebut dapat
dioptimasi dengan membuat agar kumpulan titik-titik tersebut terurut secara
lexicografis (urutkan dulu berdasarkan koordinat sumbu-X lalu untuk koordinat
pada sumbu-X yang sama urutkan berdasarkan koordinat pada sumbu-Y). Sifat
keterurutan ini kemudian dimanfaatkan sehingga pada setiap fase tiap titik
hanya dikunjungi satu kali (kompleksitas linier). Adapun fase-fase yang perlu
dilalui terdiri dari dua fase yaitu batas bagian atas (upper boundary) dan
batas bagian bawah (lower boundary). Misal pada contoh algoritma berikut :
procedure TForm1.ConvexHull( ap: array of TPoint );
var
pi
: array of integer;
hull
: array of integer;
h, i, j,
k, l : integer;
dx, dy,
dx2, dy2 : integer;
found
: boolean;
begin
{
initialize index }
setlength(
pi, length( ap ) );
for i := 0 to high( pi ) do
pi[i]
:= i;
{ sort the
index lexicographically, shown here using simple quadratic complexity sort
algorithm }
for i := 0 to high( pi ) - 1 do begin
for j := i + 1 to high( pi ) do begin
if ( ap[pi[j]].X < ap[pi[i]].X ) or ( ( ap[pi[j]].X < ap[pi[i]].X ) and ( ap[pi[j]].Y > ap[pi[i]].Y ) ) then begin
k
:= pi[j];
pi[j]
:= pi[i];
pi[i]
:= k;
end;
end;
end;
{ build
upper boundary }
setlength(
hull, 2 );
hull[0] :=
pi[0];
hull[1] :=
pi[1];
h := 1;
for i := 2 to high( pi ) do begin
found
:= false;
for k := 1 to high( hull ) do begin
dx
:= ap[hull[k]].X - ap[hull[k - 1]].X;
dy
:= ap[hull[k]].Y - ap[hull[k - 1]].Y;
dx2
:= ap[pi[i]].X - ap[hull[k]].X;
dy2
:= ap[pi[i]].Y - ap[hull[k]].Y;
j
:= dy * dx2 - dx * dy2;
{
delete previous non-convex edge w.r.t current point }
if j > 0 then begin
hull[k]
:= pi[i];
setlength(
hull, k + 1 );
found
:= true;
break;
end;
end;
{
add if current point lies on the right side of previous upper edges }
if not found then begin
setlength(
hull, length( hull ) + 1 );
hull[high(
hull )] := pi[i];
end;
end;
{ build
lower boundary }
h := high(
hull ) - 1;
for i := high( pi ) downto 0 do begin
found
:= false;
for k := h to high( hull ) do begin
dx
:= ap[hull[k]].X - ap[hull[k - 1]].X;
dy
:= ap[hull[k]].Y - ap[hull[k - 1]].Y;
dx2
:= ap[pi[i]].X - ap[hull[k]].X;
dy2
:= ap[pi[i]].Y - ap[hull[k]].Y;
j
:= dy * dx2 - dx * dy2;
if j > 0 then begin
hull[k]
:= pi[i];
setlength(
hull, k + 1 );
found
:= true;
break;
end;
end;
if not found then begin
setlength(
hull, length( hull ) + 1 );
hull[high(
hull )] := pi[i];
end;
end;
{ display
result }
Image1.Canvas.Pen.Color
:= clLime;
Image1.Canvas.MoveTo(
ap[hull[0]].X, ap[hull[0]].Y );
for i := 1 to high( hull ) do
Image1.Canvas.LineTo(
ap[hull[i]].X, ap[hull[i]].Y );
for i := 0 to high( hull ) do
drawpt(
ap[hull[i]].X, ap[hull[i]].Y, clRed );
end;
Algoritma di atas terdiri dari tiga bagian yaitu pengurutan titik,
penyusunan batas bagian atas, dan penyusunan batas bagian bawah. Pada contoh di
atas kompleksitas ditentukan oleh algoritma pengurutan titik yang cenderung
kuadratik (O(n2)) untuk mempermudah pemahaman, jika dibutuhkan algoritma
pengurutan dapat menggunakan algoritma yang memiliki kompleksitas lebih
rendah/linearitmik (O(n.log n)).
REFERENSI
Posting Komentar