Sample program that does a simple flood fill using recursion
program testit
integer :: array(20,50)
! Fill array with rectangles of values
array(:,:)=61 ! fill array
do i= 5 , 15; do j= 4 , 45; array(i , j)= 43; enddo; enddo
do i= 10 , 12; do j= 3 , 35; array(i , j)= 45; enddo; enddo
do i= 13 , 18; do j= 2 , 45; array(i , j)= 45; enddo; enddo
do i= 2 , 10; do j= 26 , 49; array(i , j)= 45; enddo; enddo
do i= 3 , 8; do j= 30 , 44; array(i , j)= 42; enddo; enddo
do i= 2 , 2; do j= 2 , 14; array(i , j)= 45; enddo; enddo
! print the array assuming the values can be printed as characters
WRITE (*, FMT = ’(50a1)’) ((char(array(i,j)),j=1,50,1),i=1,20,1)
! pick a point and flood fill value 45 with value 35
call flood_fill(array,10,17,45,35)
write(*,’(a)’)
WRITE (*, FMT = ’(50a1)’) ((char(array(i,j)),j=1,50,1),i=1,20,1)
contains
recursive subroutine flood_fill(array,y,x,old_attribute,new_attribute)
! Stack-based recursive flood-fill (Four-way)
!
! Flood fill, also called seed fill, is an algorithm that determines the
! area connected to a given node in a multi-dimensional array. It is used
! in pixel-based graphics to "bucket" fill connected, similarly-colored
! areas with a different color,
!
! The flood fill algorithm takes three parameters: a start node, a target
! color, and a replacement color. The algorithm looks for all nodes in the
! array which are connected to the start node by a path of the target color,
! and changes them to the replacement color.
!
! Depending on whether we consider nodes touching at the corners connected
! or not, we have two variations, Eight-way and Four-way, respectively.
!
! One implicitly stack-based (recursive) flood-fill implementation (for
! a two-dimensional array) goes as follows:
!
! Flood-fill (node, target-color, replacement-color):
! 1. If target-color is equal to replacement-color, return.
! 2. If the color of node is not equal to target-color, return.
! 3. Set the color of node to replacement-color.
! 4. Perform Flood-fill (one step to the west of node, target-color, replacement-color).
! Perform Flood-fill (one step to the east of node, target-color, replacement-color).
! Perform Flood-fill (one step to the north of node, target-color, replacement-color).
! Perform Flood-fill (one step to the south of node, target-color, replacement-color).
! 5. Return.
!
! Though easy to understand, the implementation of the algorithm above
! is impractical in languages and environments where stack space is
! severely constrained. Many other algorithms are available if this is an issue.
integer :: array(:,:)
integer :: y, x, old_attribute, new_attribute
integer :: test_attribute
test_attribute=array(y,x)
if(test_attribute.eq.new_attribute) return
if(test_attribute.ne.old_attribute) return
array(y,x)=new_attribute
if(x.gt.1) call flood_fill(array,y,x-1,old_attribute,new_attribute)
if(x.lt.size(array,dim=2))call flood_fill(array,y,x+1,old_attribute,new_attribute)
if(y.gt.1) call flood_fill(array,y-1,x,old_attribute,new_attribute)
if(y.lt.size(array,dim=1))call flood_fill(array,y+1,x,old_attribute,new_attribute)
end subroutine flood_fill
end program testit
