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
def load(cls, filename):
print "Loaded csv file"
loadGrid = []
reader = csv.reader(open(filename), delimiter=';')
for line in reader:
loadGrid.append(line)
width = len(loadGrid[0])
height = len(loadGrid)
grid = Grid(width, height)
for x in range(width):
for y in range(height):
grid.getCell(x, y).value = loadGrid[x][y]
return grid
load = classmethod(load)
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
visited.add((x, y))
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
visited.add((x,y))
...
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
def load(cls, filename):
print "Loaded csv file"
loadGrid = []
reader = csv.reader(open(filename), delimiter=';')
for line in reader:
loadGrid.append(line)
width = len(loadGrid[0])
height = len(loadGrid)
grid = Grid(width, height)
for x in range(width):
for y in range(height):
grid[x, y].value = loadGrid[y][x]
return grid
load = classmethod(load)
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)
def add(x, y):
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)
def add(self, x, y):
...
```

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.

Thanks for your reply...

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...

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
def add(self, (x, y)):
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)

>>> cluster.add((1, 1))

>>> cluster.add((3, 3))

>>> print cluster.cells

[<__main__.Cell object at 0x01412CF0>, <__main__.Cell object at 0x01412C50>]

Is this adding method set up correcly and can I now use this kind of Cluster class in my old program?