Convex Hull 2D

Convex Hull merupakan persoalan klasik dalam geometri komputasional. Persoalan ini saya ketahui pertama kali ketika lomba pemrograman waktu SMA. 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.

1. memilih titik pertama
2. 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(n²). 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(n²)) untuk mempermudah pemahaman, jika dibutuhkan algoritma pengurutan dapat menggunakan algoritma yang memiliki kompleksitas lebih rendah/linearitmik (O(n.log n)).