Shapes/Flood Fill
From GameDevID
Flood Fill merupakan salah satu teknik untuk mengarsir poligon.
Prinsip dari Flood Fill adalah mewarnai seluruh piksel yang berwarna sama dan terhubung dengan piksel pada posisi awal. Titik (piksel) awal ini dinamakan titik bakar karena seluruh piksel tetangganya yang berwarna sama akan diganti dengan warna baru secara merambat seperti dibakar.
Penentuan tetangga dari tiap piksel mengikuti pada umumnya mengikuti dua kaidah yaitu :
- ketetanggaan 4, tetangga yang diperiksa adalah atas, kanan, bawah, dan kiri
- ketetanggaan 8, tetangga yang diperiksa adalah sama dengan ketetanggaan 4 dengan tambahan tetangga yang terhubung secara diagonal
Algoritma dasarnya adalah:
- Simpan warna piksel di posisi titik bakar (w0)
- Ganti warna pada titik bakar dengan warna yang ditentukan (w')
- periksa seluruh tetangga piksel tersebut, jika warnanya sama dengan w0 maka ulangi langkah 1 untuk piksel tersebut
Algoritma Flood Fill dapat diimplementasi dengan dua cara yaitu cara rekursif dan cara iteratif. Algoritma yang diimplementasi secara rekursif lebih sederhana dibandingkan dengan algoritma yang diimplementasi secara iteratif. Walaupun demikian algoritma yang diimplementasi secara rekursif lebih beresiko terhadap Stack Overflow dibandingkan algoritma yang diimplementasi secara iteratif. Hal ini disebabkan implementasi iteratif menggunakan struktur data tumpukan (stack) yang terpisah dengan stack untuk pemanggilan prosedur. Oleh sebab itu implementasi secara iteratif lebih tahan untuk resolusi yang besar (misal 1000x1000).
Algoritma Flood Fill Rekursif
procedure floodfill (x,y:integer; w:twarna);
var
warna_asal : twarna;
begin
warna_asal := getpixel(x,y);
putpixel(x,y,w);
(* foreach tetangga di titik (x,y) *)
if is_warna_sama(getpixel(x-1, y), warna_asal) then
floodfill(x-1, y, w);
if is_warna_sama(getpixel(x+1, y), warna_asal) then
floodfill(x+1, y, w);
if is_warna_sama(getpixel(x, y-1), warna_asal) then
floodfill(x, y-1, w);
if is_warna_sama(getpixel(x, y+1), warna_asal) then
floodfill(x, y+1, w);
end;
Algoritma Flood Fill Iteratif
procedure floodfill (x,y:integer; w:twarna);
var
warna_asal : twarna;
ymin, ymax, yy : integer;
kiri_ok, kanan_ok : boolean;
kandidat : stack of titik;
cur_titik : titik;
begin
warna_asal := getpixel(x,y);
kandidat.push(titik(x,y));
while not kandidat.kosong() do begin
cur_titik := kandidat.pop();
ymin := cur_titik.Y;
while (is_titik_valid(cur_titik.X, ymin-1)) and (is_warna_sama(getpixel(cur_titik.X, ymin-1), warna_asal)) do
ymin := ymin - 1;
ymax := cur_titik.Y;
while (is_titik_valid(cur_titik.X, ymax+1)) and (is_warna_sama(getpixel(cur_titik.X, ymin+1), warna_asal)) do
ymax := ymax + 1;
kiri_ok := false;
kanan_ok := false;
for yy := ymin to ymax do begin
if is_titik_valid(cur_titik.X-1, yy) then begin
if not kiri_ok and (is_warna_sama(getpixel(cur_titik.X-1, yy), warna_asal)) then begin
kiri_ok := true;
kandidat.push(titik(cur_titik.X-1, yy));
end;
if kiri_ok and not (is_warna_sama(getpixel(cur_titik.X-1, yy), warna_asal)) then
kiri_ok := false;
end;
if is_titik_valid(cur_titik.X+1, yy) then begin
if not kanan_ok and (is_warna_sama(getpixel(cur_titik.X+1, yy), warna_asal)) then begin
kanan_ok := true;
kandidat.push(titik(cur_titik.X+1, yy));
end;
if kanan_ok and not (is_warna_sama(getpixel(cur_titik.X+1, yy), warna_asal)) then
kanan_ok := false;
end;
putpixel(cur_titik.X, yy, w);
end;
end;
end;
