Hello all :)

I have a grid program that lets me define a grid and do some basic stuff with it. The next step I need to implement is that I need to add a floodFill like method (http://en.wikipedia.org/wiki/Flood_fill). What I wanna achieve with this is the functionality that I can define the clusters of cells with the same value. The floodFill method works almost fine but the problem is I need to somehow define if a cell is visited by the floodFill or not. If it was visited before it should return and stop the method for that cell.

Here is my code so far:

``````# Create a Python spatial grid.

from math import sqrt
import csv

class Grid(object):
"""Grid class with a width, height, length"""
def __init__(self, width, height):
self.grid = []
self.width = width
self.height = height
self.length = width * height
for x in range(self.width):
col = []
for y in range(self.height):
col.append(Cell(x, y, self.grid))
self.grid.append(col)

def getWidth(self):
return self.width

def getHeight(self):
return self.height

def getLength(self):
return self.length

def __len__(self):
return self.length

def setCellValue(self, x, y, i):
self.grid[x][y].value = i

def getCellValue(self, x, y):
return self.grid[x][y].value

def getCell(self, x, y):
return self.grid[x][y]

def __getitem__(self, (x, y)):
return self.grid[x][y]

def index(self, value):
return self.grid.index(value)

def fillBlock(self, left, right, top, bottom, value):
# You can choose if you want to iterate over a range of left - exclusive right
# or over a range of left - inclusive right. Same goes for top - exclusive bottom
# or top - inclusive bottom
# For now it's exclusive
for x in range(left, right):
for y in range(top, bottom):
self[x, y].value = value

def floodFill(self, x, y, landUse):
if (x < 0 or y < 0 or x >= self.width or y >= self.height):
return

cell = self.grid[x][y]
# Add something that checks if a cell is visited yet by floodFill. Else this
# algorithm gets into an infinite loop untill maximum recursion depth is exceeded.
# Make something like cell.visited = True then return...
if (cell.value != landUse):
return

self.floodFill(x-1, y, landUse)
self.floodFill(x+1, y, landUse)
self.floodFill(x, y-1, landUse)
self.floodFill(x, y+1, landUse)

def printGrid(self):
for y in range(self.height):
for x in range(self.width):
print self[x, y].value,
print

grid = Grid(width, height)
for x in range(width):
for y in range(height):
return grid

class Cell(object):
def __init__(self, x, y, grid):
self.x = x
self.y = y
self.grid = grid
self.value = 0

def inspect(self):
"#<Cell: value = #(value), x = #(x), y = #(y)>"

my_grid = Grid(5, 5)
my_grid.printGrid()
print '-'*40

my_grid[2, 0].value = 1
my_grid[1, 1].value = 1
my_grid[2, 1].value = 1
my_grid[2, 2].value = 1
my_grid.printGrid()

#my_grid.floodFill(0, 0, 0)``````

If I run floodFill now I get into an recursion because it does not know when to stop. I need to add something that defines if a cell is visited by the floodFill or not. This way I want to be able to go over the cells and make in this example 2 clusters: 1 cluster of cells with value 0 and one cluster with value 1.

0 0 1 0 0
0 1 1 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

If anyone can help me with this I would be very glad to hear some ideas / solutions. Thanks in advance!

I'd suggest a non recursive method using 2 sets like this one, which generates the cluster

``````class Grid(object):
def floodFill(self, x, y, landUse):
visited = set()
todo = set([(x, y)])
while todo:
x, y = todo.pop()
if (x, y) in visited:
continue
if (x < 0 or y < 0 or x >= self.width or y >= self.height):
continue
cell = self.grid[x][y]
if (cell.value != landUse):
continue
todo.update([(x-1,y),(x+1,y),(x,y-1),(x,y+1)])
yield cell

def exampleUsage(self, x, y, landUse):
for cell in self.floodFill(x, y, landUse):
doSomething(cell) # do anything you want``````

Hi,

thanks for your reply. Since i'm just a beginner with Python coding I have the feeling I cannot fully understand your way in doing this. You can't point out a way that my old floodFill method marks the cells that are visited by the method and if a cell is visited he skips it? I'm trying to find a way to do this but I don't seem to be able to come up with something. The way you work with the two sets I could imagine using something like that in my method but I'm not sure.

I will try and look deeper in your code to see if I can get a better understanding of it (as easy as it may seem to the most of you here...) but if you could point out if I can implement something like this in my old floodFill method I would be very grateful.

Thanks!

Well, basically, you have 2 solutions: either you make a collection of all visited cells (using a `set` object), or you "mark" the cells as you said, which is the technique used in mark and sweep garbage collection algorithms, which are just a particular type of floodfill. If you want to mark the cells, a good way to do this is to add a member in cell objects, like `Cell.mark` .
In the set solution, you would obtain a (partial) code structure like this one

``````class Grid(object):
def floodFill(self, x, y, landUse):
visited = set()
self.rec_floodFill(x, y, landUse, visited)

def rec_foodFill(self, x, y, landUse, visited):
if (x,y) in visited:
return
...
self.rec_floodFill(x-1, y, landUse, visited)
self.rec_floodFill(x+1, y, landUse, visited)
self.rec_floodFill(x, y-1, landUse, visited)
self.rec_floodFill(x, y+1, landUse, visited)``````

and in the "mark" solution, it would be a code like this

``````class Cell(object):
def __init__(self):
...
self.mark = None

class Grid(object):
markcnt = 0

def floodFill(self, x, y, landUse):
Grid.markcnt += 1
self.rec_floodFill(x, y, landUse)

def rec_foodFill(self, x, y, landUse):
...
if cell.mark == Grid.markcnt:
return
cell.mark = Grid.markcnt
...
self.rec_floodFill(x-1, y, landUse)
self.rec_floodFill(x+1, y, landUse)
self.rec_floodFill(x, y-1, landUse)
self.rec_floodFill(x, y+1, landUse)``````

I would rather prefer the "set" solution, because the "mark" solution wouldn't work if 2 different threads called `floddFill` :)

Hello, i did some adjustments to my old program and it's starting to get more and more functionality.

The floodFill operation works and I also added a clusterId which sets a new clusterId to each new cluster defined by the floodFill algorithm. This is my code now:

``````import csv

class Grid(object):
"""Grid class with a width, height and length."""
def __init__(self, width, height):
self.grid = []
self.width = width
self.height = height
self.length = width * height
for x in range(self.width):
col = []
for y in range(self.height):
col.append(Cell(x, y, self.grid))
self.grid.append(col)

def getWidth(self):
return self.width

def getHeight(self):
return self.height

def getLength(self):
return self.length

def getCell(self, x, y):
return self.grid[x][y]

def __getitem__(self, (x, y)):
return self.grid[x][y]

def fillBlock(self, left, right, top, bottom, value):
for x in range(left, right):
for y in range(top, bottom):
self[x, y].value = value

def firstFreeCell(self):
for y in range(self.height):
for x in range(self.width):
if self.grid[x][y].clusterId == -1:
return self.grid[x][y]
return None

def reset(self):
for y in range(self.height):
for x in range(self.width):
self.grid[x][y].clusterId == -1

def floodFill(self, x, y, clusterId, landUse):
if (x < 0 or y < 0 or x >= self.width or y >= self.height):
return

cell = self.grid[x][y]
if (cell.clusterId != -1 or cell.value != landUse):
return

cell.setClusterId(clusterId)

self.floodFill(x-1, y, clusterId, landUse)
self.floodFill(x+1, y, clusterId, landUse)
self.floodFill(x, y-1, clusterId, landUse)
self.floodFill(x, y+1, clusterId, landUse)

def analyze(self):
freeCell = self.firstFreeCell()
clusterId = 0
while freeCell != None:
self.floodFill(freeCell.x, freeCell.y, clusterId, freeCell.value)

freeCell = self.firstFreeCell()
clusterId += 1

def printClusterId(self, clusterId):
for y in range(self.height):
for x in range(self.width):
if self.grid[x][y].clusterId == clusterId:
print 'ClusterId:', clusterId, '=>', 'Cell-coordinates:', '(', self.grid[x][y].x, ',', self.grid[x][y].y, ')', 'with a landUse value of:', self.grid[x][y].value
print "No cells with such clusterId left or the clusterId is not defined yet..."

def printGrid(self):
for y in range(self.height):
for x in range(self.width):
print self[x, y].value,
print

grid = Grid(width, height)
for x in range(width):
for y in range(height):
return grid

class Cell(object):
"""Cell class with x, y, grid."""
def __init__(self, x, y, grid):
self.x = x
self.y = y
self.grid = grid
self.value = 0
self.clusterId = -1

def setClusterId(self, clusterId):
self.clusterId = clusterId

def getClusterId(self):
return self.clusterId

my_grid = Grid(10, 10)
my_grid.fillBlock(2, 5, 1, 4, 1)
my_grid[5, 2].value = 1
my_grid[5, 3].value = 1
my_grid.fillBlock(2, 4, 7, 9, 2)
my_grid.fillBlock(4, 8, 5, 9, 2)
my_grid.printGrid()
print '-'*20

my_grid.analyze()
my_grid.printClusterId(1)
my_grid.printClusterId(2)``````

I need to add 2 more things to this program:

1. I want to keep track of the area of each cluster. So when the floodFill finds a new cluster the inital area has to be set to 0 and updated to 1 (the new cell that is added). Then it goes searching for the other cells that are part of this cluster. For each cell that it finds I want to add another value of 1 to the allready existing area. Where and how should I add this initial area and the updating of it (something like area += 1)? All works perfect now but im kinda lost to how to program this functionality.

2. I want to add a boundingBox property to a cluster. A boundingBox here means that it makes a rectangle around the cluster. That way I want to be able to get information about the left, right, top and bottom of the cluster. From this boundingBox I would like to be able to get the area of it and adding cells to the boundingBox:
Something like:

``````def getArea()
return ((right - left) + 1) * ((bottom - top) + 1)

pass``````

For a simple grid like:

0 0 1 0 0
0 1 1 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

Here the area of the cluster of cells with value = 1 has to be 4, and the boundingBox should have something like left = 1, right = 2, top = 0, bottom = 2 and an area of:

((2 - 1) + 1) * ((2 - 0) + 1) = 2 * 3 = 6

I hope anyone here can help me a bit further with these 2 questions / functionalities.

There is a very simple solution: you define Cluster objects like this

``````class Cluster(object):
def __init__(self):
self.right = self.left = self.bottom = self.top = None
def area(self):
return (self.right - self.left + 1) * (self.bottom - self.top + 1)
...``````

Then when you call floodfill, instead of passing a new integer clusterId, you pass a new Cluster object like this

``````class Grid...:
def analyse(self):
...
cluster = Cluster()
while freeCell != None:
self.floodFill(..., cluster,...)
....``````

Then your cell would point to the cluster instead of the clusterId, and the body of the method floodFill can use cluster.add. You can also store a list of all clusters in the Grid object, and you can later add methods and content to the Cluster class.

but i'm afraid that for tonight I lost it here...can't seem to get it to work and it even gets more messy now. According my teacher the program was fine as I had it...I only needed to figure out how I could add +1 to the area every time a cell has been added to the cluster and too find something for this boundingbox.

You tried it yourself and got it working? Guess im missing something again...

Do as your teacher tells you. There are many ways to program this.

Hey I fiddled around some more with my code. For the ease of use I made a new program to test the 3 classes: Grid, Cell and Cluster

I want to ask if my add method in the Cluster class and the initializing of the Cluster class are set up correctly like this:

``````class Grid(object):
def __init__(self, width, height):
self.grid = []
self.width = width
self.height = height
self.length = width * height
for x in range(self.height):
col = []
for y in range(self.width):
col.append(Cell(x, y, self.grid))
self.grid.append(col)

def __getitem__(self, (x, y)):
return self.grid[x][y]

def printGrid(self):
for y in range(self.height):
for x in range(self.width):
print self[x, y].value,
print

class Cell(object):
def __init__(self, x, y, grid):
self.x = x
self.y = y
self.grid = grid
self.value = 0
self.clusterId = -1

class Cluster(object):
def __init__(self, grid):
self.cells = []
self.grid = grid
self.right = self.left = self.bottom = self.top = None

self.cells.append(Cell(x, y, self.grid))``````

In the Python Shell I can now do something as the following:
>>> my_grid = Grid(5, 5)
>>> cluster = Cluster(my_grid)