Algoritmus vypĺňania do hraničných bodov (Bound fill Algorithm)

Princíp algoritmu

Na vstupe je 4-súvislá hranica farby $hranicna-farba$. Na výstupe má byť oblasť ohraničená touto hranicou a zafarbená farbou nova_farba. V tomto algoritme potrebujeme hranicu, ktorá je 4-súvislá v silnejšom zmysle ako sme definovali v úvode. Hranica nesmie mať 8-dieru (Obr. 1)

Ako vidno, myšlienka tohto algoritmu sa podobá na Flood_fill_4. Nestačí však testovať, či bod $(x,y)$ patrí oblasti. Potrebné sú dva testy, či je vo vnútri oblasti a či mu už skôr nebola pridelená nová farba. Aj modifikácia tohto algoritmu na 8-súvislé oblasti je pomerne jednoduchá.

Obr. 1 - 4-súvislá hranica

Pseudokód

Implementácia rekurzívneho Bound_fill_4 algoritmu je zhrnutá v nasledovnom zápise.

Na vstupe nech je 4-súvislá hranica farby hranicna_farba. Na výstupe má byť oblasť ohraničená touto hranicou a zafarbená farbou nova_farba. Algoritmus opäť obsahuje funkciu zapis_pixel(x, y, color) a funkciu nacitaj_pixel(x,y), ktorá vráti farbu zadaného pixlu $(x,y)$. Opäť potrebujeme poznať ešte súradnice jedného vnútorného bodu oblasti $(x, y)$.

Bound_fill_4(int $x$, int $y$, color hranicna_farba, color nova_color) $\lbrace$

  zapis_pixel(x,y,nova_farba);

  Bound_fill_4(x,y-1,hranicna_farba, nova_farba);

  Bound_fill_4(x,y+1,hranicna_farba, nova_farba);

  Bound_fill_4(x-1,y,hranicna_farba, nova_farba);

  Bound_fill_4(x+1,y,hranicna_farba, nova_farba);

  $\rbrace$

Túto procedúru vieme rozšíriť aj na osem susedných bodov:.

Bound_fill_8(int $x$, int $y$, color hranicna_farba, color nova_color) $\lbrace$

  zapis_pixel(x,y,nova_farba);

  Bound_fill_8(x,y-1,hranicna_farba, nova_farba);

  Bound_fill_8(x,y+1,hranicna_farba, nova_farba);

  Bound_fill_8(x-1,y,hranicna_farba, nova_farba);

  Bound_fill_8(x+1,y,hranicna_farba, nova_farba);

  Bound_fill_8(x-1,y-1,hranicna_farba, nova_farba);

  Bound_fill_8(x+1,y-1,hranicna_farba, nova_farba);

  Bound_fill_8(x-1,y+1,hranicna_farba, nova_farba);

  Bound_fill_8(x+1,y+1,hranicna_farba, nova_farba);

  $\rbrace$

Literatúra

Algoritmus Bound fill vieme nájsť podrobne spracovaný v literatúre [3] na strane 130 ako aj v literatúre [1] na strane 66 a [2].