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!
