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) 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!