Algoritma Flood Fill

Metode ini dimulai pada titik (x,y) dan mendefinisikan seluruh pixel pada bidang tersebut dengan warna yang sama. Bila bidang yang akan diisi warna mempunyai beberapa warna, pertama-tama yang dilakukan adalah membuat nilai pixel yang baru, sehingga semua pixel mempunyai warna yang sama.. titik awal warna dituang dinamakan dengan titik bakar.
Pada kuliah grafika komputer, dan buku teksnya. Algoritma Floodfill dideskripsikan secara rekursif sbb

{menggunakan predikat warna sama dengan warna titik bakar}
procedure floodfill(p:point, i:image; newcolor:color);
var
   oldcolor : color;
begin
   oldcolor := i.pixel[p.x][p.y];
   i.pixel[p.x][p.y] := newcolor;
   {i.pixel[neighbor.x][neighbor.y]=oldcolor merupakan predikat sebagai syarat rekurens}
   {tetangga kiri}
   if (p.x > i.left_bound) and (i.pixel[p.x-1][p.y]=oldcolor) then floodfill(point(p.x-1, p.y), i, newcolor);
  {tetangga kanan}
  if (p.x < i.right_bound) and (i.pixel[p.x+1][p.y]=oldcolor) then floodfill(point(p.x+1, p.y), i, newcolor);
  {tetangga atas}
  if (p.y > i.top_bound) and (i.pixel[p.x][p.y-1]=oldcolor) then floodfill(point(p.x, p.y-1), i, newcolor);
  {tetangga bawah}
  if (p.y < i.bottom_bound) and (i.pixel[p.x][p.y+1]=oldcolor) then floodfill(point(p.x, p.y+1), i, newcolor);
end;

Algoritma di atas merupakan contoh generik untuk citra 2D. Untuk citra 3D algoritma di atas dapat diperluas dengan ekspresi yang sama, yang berbeda hanyalah rekursif tetangganya yang bertambah yaitu tetangga depan dan tetangga belakang.

{menggunakan predikat warna sama dengan warna titik bakar}
procedure floodfill(p:point3d, i:image; newcolor:color);
var
   oldcolor : color;
begin
   oldcolor := i.pixel[p.x][p.y][p.z];
   i.pixel[p.x][p.y][p.z] := newcolor;
   {i.pixel[neighbor.x][neighbor.y][neighbor.z]=oldcolor merupakan predikat sebagai syarat rekurens}
   {tetangga kiri}
   if (p.x > i.left_bound) and (i.pixel[p.x-1][p.y][p.z]=oldcolor) then floodfill(point(p.x-1, p.y,p.z), i, newcolor);
  {tetangga kanan}
  if (p.x < i.right_bound) and (i.pixel[p.x+1][p.y][p.z]=oldcolor) then floodfill(point(p.x+1, p.y,p.z), i, newcolor);
  {tetangga atas}
  if (p.y > i.top_bound) and (i.pixel[p.x][p.y-1][p.z]=oldcolor) then floodfill(point(p.x, p.y-1,p.z), i, newcolor);
  {tetangga bawah}
  if (p.y < i.bottom_bound) and (i.pixel[p.x][p.y+1][p.z]=oldcolor) then floodfill(point(p.x, p.y+1,p.z), i, newcolor);
  {tetangga depan}
  if (p.z > i.front_bound) and (i.pixel[p.x][p.y][p.z-1]=oldcolor) then floodfill(point(p.x, p.y,p.z-1), i, newcolor);
  {tetangga belakang}
  if (p.z < i.rear_bound) and (i.pixel[p.x][p.y][p.z+1]=oldcolor) then floodfill(point(p.x, p.y,p.z+1), i, newcolor);
end;

algoritma rekursif memang memiliki ekspresi yang sederhana namun seringkali implementasinya terganggu dengan pesan stack overflow yang diakibatkan ukuran stack di heap untuk procedure call yang terbatas. Hal ini dapat diatasi dengan mengubah algoritma di atas menjadi iteratif dan mensimulasikan stack sebagai struktur data eksternal. Apakah kedua hal tersebut sudah cukup? tentu belum, jika mekanisme mencari tetangganya sama persis dengan algoritma rekursif di atas maka justru algoritma versi iteratif lebih buruk performanya. Kita perlu mengoptimasi pencarian tetangga sehingga ukuran untuk stack dapat dikurangi.

Untuk mengurangi pengisian stack tersebut kita dapat mengubah ide dari algoritma di atas dengan cara memusatkan perhatian pada tetangga yang berada di satu sumbu. Misalkan kita perhatikan di sumbu vertikal (sumbu Y), maka kita akan mendapatkan sebuah rentang minimum-maksimum yang memiliki predikat sama. Rentang ini kemudian ditelusuri. Selama menelusuri rentang tersebut, barulah kita memperhatikan tetangga di sumbu lainnya (sumbu X). Karena kita secara konstan menelusuri rentang vertikal maka kita cukup memperhatikan perubahan di tetangga. Kita hanya perlu menyimpan ke stack, tetangga yang baru kita temukan pertama. Tetangga yang letaknya di bawah tetangga tersebut jika memiliki predikat yang sama tidak perlu disimpan karena pasti dikunjungi ketika titik tersebut diproses pertama kali secara vertikal.
Algoritma tersebut diekspresikan dalam kode berikut:

{menggunakan predikat warna sama dengan warna titik bakar}
procedure floodfill(p:point3d, i:image; newcolor:color);
var
   oldcolor : color;
   stpt : stack;// stack of point3d;
   pt : point3d;
   y1, y2, yy : integer;
   span_left, span_right, span_front, span_rear: boolean;
begin
   oldcolor := i.pixel[p.x][p.y];
   stpt.push(p.x,p.y,p.z);
   while not stpt.is_empty() do begin
      pt := stpt.pop();
      y1 := pt.y;
      while (y1 > i.top_bound) and (i.pixel[pt.x][y1-1][pt.z]=oldcolor) do dec(y1);
      y2 := pt.y;
      while (y2 < i.bottom_bound) and (i.pixel[pt.x][y1+1][pt.z]=oldcolor) do inc(y2);
      span_left := false;
      span_right := false;
      span_front := false;
      span_rear := false;
      for yy := y1 to y2 do begin
         if (pt.x > i.left_bound) then begin
            if not span_left and (i.pixel[pt.x-1][yy][pt.z]=oldcolor) then begin
               span_left := true;
               stpt.push(pt.x-1, yy, pt.z);
            end else if span_left and not (i.pixel[pt.x-1][yy][pt.z]=oldcolor) then span_left := false;
         end;
         if (pt.x < i.right_bound) then begin
            if not span_right and (i.pixel[pt.x+1][yy][pt.z]=oldcolor) then begin
               span_right := true;
               stpt.push(pt.x+1, yy, pt.z);
            end else if span_right and not (i.pixel[pt.x+1][yy][pt.z]=oldcolor) then span_right := false;
         end;
         if (pt.z > i.front_bound) then begin
            if not span_front and (i.pixel[pt.x][yy][pt.z-1]=oldcolor) then begin
               span_front := true;
               stpt.push(pt.x, yy, pt.z-1);
            end else if span_front and not (i.pixel[pt.x][yy][pt.z-1]=oldcolor) then span_front := false;
         end;
         if (pt.z < i.rear_bound) then begin
            if not span_rear and (i.pixel[pt.x][yy][pt.z+1]=oldcolor) then begin
               span_rear := true;
               stpt.push(pt.x, yy, pt.z+1);
            end else if span_rear and not (i.pixel[pt.x][yy][pt.z+1]=oldcolor) then span_rear := false;
         end;
         i.pixel[pt.x][yy][pt.z] := newcolor;
      end;
   end;
end;

• Twitter
• Facebook
• Google
• Tumblr
• Pinterest

About AdaNamanya