Geometry Problem

Geometri sederhana pada jaman yunani kuno biasa di gunakan untuk membangun segitiga, lingkaran dan lain-lain. Namun pada masa kini geometri digunakan dalam aplikasi computer atau robot.

Adapun masalah klasik geometry adalah :

1. Ø  Problem Closest Pair : Diberikan suatu titik pada suatu bidang, dan temukan pasangan terdekatnya.
2. Convex Hull                  :  Temukan poligon cembung terkecil yang melibatkan semua titik yang telah ditentukan.

Setelah mengetahui geometry problem berbentuk apa, selanjutnya lanjut ke contoh algoritma salah satu geometri problem. Disini di ambil contoh suatu persoalan dari Convex Hull.

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 : 

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 di buat garis dengan titik sebelumnya maka seluruh titik yang 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)).

Jadi kesimpulan dari seluruh pembahasan di atas ialah untuk mempelajari dan mmengembangkan algoritma-algoritma yang efisien untuk menyelesaikan masalah geometri / Geometry Problem dengan menggunakan computer.

SUMBER       :

link

link 2