Geometric Problem , Baca judul pun sudah tau pasti ini
berhubungan dengan matematika dan dalam materi Analisis Algoritma geometry
problem tersebut akan di implementasikan dalam bentuk komputasi..
Oke ini adalah Pengertian Singkat dari Geometry Problem :
Berkaitan dengan objek geometrik : 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 .
Setelah Tau nih geometry problem berbentuk apa ,,
disini
langsung aja contoh algoritma salah satu geometry problem,
disini saya akan
memberi satu persoalaan dari Convex Hull ..
Sebelum masuk ke ngoding – ngoding nihh .. harus tau juga
convex hull itu apa ..
Ya.. seperi dalam pengertian singkat di atas 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).
contoh
geometry
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)).
Nah dari Pengertian
sampe salah satu contoh sudah saya muat diblog ini..
Tujuan dari disiplin ilmu ini adalah untuk mempelajari dan mengembangkan algoritma-algoritma yang efisien untuk menyelesaikan masalah geometri dengan menggunakan komputer.
Jika ada yang harus
ditanyakn .. siahkan beri komentar ..
Sumber :
EmoticonEmoticon