1.11M Members

floodFill on a Grid

 
0
 

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!

 
0
 

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
 
0
 

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!

 
0
 

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

 
0
 

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.

 
0
 

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.

 
0
 

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

 
0
 

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

 
0
 

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?

You
This article has been dead for over six months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article