CODEWITHSUNDEEP
pythonrecursionflood-fill
Juan Gallostra
Juan Gallostra

Reputation: 301

Using flood fill algorithm to determine map area with equal height

I have a list of lists where each element represents the average height in integers of a all square metres contained in the map (one number= one square metre). For example:

map=[
  [1,1,1,1],     
  [1,1,2,2],
  [1,2,2,2]
           ] # where 1 and 2 are the average heights of those coordenates.

I'm trying to implement a method that, given a position looks for the area around him that has the same height. let's call them 'Flat areas'. I found a solution in the flood-fill algorithm. However, i'm having some problems when it comes to writing the code. I get a 

 RuntimeError: maximum recursion depth exceeded

I've no idea of where my problem is. Here it is the code of the function:

def zona_igual_alcada(self,pos,zones=[],h=None):
    x,y=pos
    if h==None:
        h=base_terreny.base_terreny.__getitem__(self,(x,y))
    if base_terreny.base_terreny.__getitem__(self,(x,y))!=h:
            return
    if x in range(0,self.files) and y in range(0,self.columnes):
        if base_terreny.base_terreny.__getitem__(self,(x,y))==h:
            zones.append((x,y))
            terreny.zona_igual_alcada(self,(x-1,y),zones,h)
            terreny.zona_igual_alcada(self,(x+1,y),zones,h)
            terreny.zona_igual_alcada(self,(x,y-1),zones,h)
            terreny.zona_igual_alcada(self,(x,y+1),zones,h)
    return set(zones)

Upvotes: 2

Views: 503

Answers (1)

John La Rooy
John La Rooy

Reputation: 304355

You're not doing anything to "mark" the zones you have already visited, so you are doing the same zones over and over until the stack fills up.

This isn't a particularly efficient way to do a flood fill, so if you have a large number of zones you will be better off looking for a more efficient algorithm to do the flood fill (eg. scanline fill).

Upvotes: 3

Related Questions