1,105,363 Community Members

floodFill on a Grid

Member Avatar
tillaart36
Light Poster
41 posts since Jul 2008
Reputation Points: 2 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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!

Member Avatar
Gribouillis
Posting Maven
3,456 posts since Jul 2008
Reputation Points: 1,140 [?]
Q&As Helped to Solve: 884 [?]
Skill Endorsements: 18 [?]
Moderator
 
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
Member Avatar
tillaart36
Light Poster
41 posts since Jul 2008
Reputation Points: 2 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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!

Member Avatar
Gribouillis
Posting Maven
3,456 posts since Jul 2008
Reputation Points: 1,140 [?]
Q&As Helped to Solve: 884 [?]
Skill Endorsements: 18 [?]
Moderator
 
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 :)

Member Avatar
tillaart36
Light Poster
41 posts since Jul 2008
Reputation Points: 2 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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.

Member Avatar
Gribouillis
Posting Maven
3,456 posts since Jul 2008
Reputation Points: 1,140 [?]
Q&As Helped to Solve: 884 [?]
Skill Endorsements: 18 [?]
Moderator
 
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.

Member Avatar
tillaart36
Light Poster
41 posts since Jul 2008
Reputation Points: 2 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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...

Member Avatar
Gribouillis
Posting Maven
3,456 posts since Jul 2008
Reputation Points: 1,140 [?]
Q&As Helped to Solve: 884 [?]
Skill Endorsements: 18 [?]
Moderator
 
0
 

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

Member Avatar
tillaart36
Light Poster
41 posts since Jul 2008
Reputation Points: 2 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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 three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article