Bounding box on clusters in a 2D list

[bearophileHUGS at lycos.com]

Then you can probably use something like this:

. def boxesArea(m, foreground=1, background=0):
.     maxr = len(m)
.     maxc = len(m[0])
.     newCol = 2
.     oldCol = foreground
.     for r,row in enumerate(m):
.         for c,e in enumerate(row):
.             if e == oldCol:
.                 # Flood fill by Lonnie Princehouse
.                 stack = [ (r, c) ]
.                 while stack:
.                     r, c = stack.pop()
.                     if c>=0 and c<maxc and r>=0 and r<maxr and
m[r][c]==oldCol:
.                         m[r][c] = newCol
.                         stack += [ (r+1, c), (r-1, c), (r, c+1), (r,
c-1) ]
.                 newCol += 1
.     box = {}
.     for r,row in enumerate(m):
.         for c,e in enumerate(row):
.             if e in box:
.                 box[e] = ( min(c, box[e][0]), min(r, box[e][1]),
.                            max(c, box[e][2]), max(r, box[e][3] ) )
.             else:
.                 box[e] = (c, r, c, r)
.     del box[background]
.     return [(b[2]-b[0]+1)*(b[3]-b[1]+1) for b in box.values()]
.
. try: import psyco
. except ImportError: pass
. else: psyco.bind(boxesArea)

Note that this version modifies the given m still.

Hugs,
Bearophile