[EMAIL PROTECTED] wrote:
> hi if I have an array
>
> say x = [[2,2,0,0,1,1],
> [1,1,0,0,1,1],
> [1,1,0,0,1,1]]
> I basically want to group regions that are non zero like I want to get
> the coordinates of non zero regions..as (x1,y1,x2,y2)
> [(0,0,2,1),(0,4,2,5)] which show the top left(x1,y1) and bottom
> right(x2,y2) corners of each group.hope i am clear.
>
> Thanks
>
How about this:
def getregions(grid):
"""Yield lists of adjancent points, not necessarily rectangular"""
adj = [(-1,0),(+1,0),(0,-1),(0,+1)] # horizontal and vertical adjacencies
# could add diagonals
points = set((y,x) for y, row in enumerate(grid)
for x, cell in enumerate(row)
if cell)
while points: # set of (y,x) non-zero points
region = [points.pop()] # start a new region with any remaining point
ptr = 0
while ptr < len(region):
y, x = region[ptr]
adjpoints = set((y + j, x + i) for j, i in adj)
adjpoints &= points # keep only the non-zero, unseen points
points -= adjpoints # remove these adjancencies from points
region.extend(adjpoints) # add them to the region
ptr += 1
yield region
def getregioncoords(grid):
"""Get top left and bottom right of *rectangular* regions"""
regions = getregions(grid)
return [(reg[0], reg[-1]) for reg in regions if reg.sort() or True]
>>> x = [[2,2,0,0,1,1],
... [1,1,0,0,1,1],
... [1,1,0,0,1,1]]
...
...
>>> getregioncoords(x)
[((0, 0), (2, 1)), ((0, 4), (2, 5))]
>>> x = [[1,0,1,0,1]]
>>> getregioncoords(x)
[((0, 0), (0, 0)), ((0, 2), (0, 2)), ((0, 4), (0, 4))]
>>> x = [[random.choice([0,1,2]) for x in range(6)] for y in range(6)]
>>> pprint.pprint(x)
[[1, 1, 2, 1, 2, 0],
[2, 0, 0, 2, 0, 1],
[1, 2, 2, 0, 2, 0],
[0, 1, 0, 0, 0, 0],
[2, 0, 0, 1, 1, 0],
[2, 2, 2, 0, 1, 0]]
>>> print "\n".join(str(reg) for reg in getregions(x))
[(0, 1), (0, 0), (0, 2), (1, 0), (0, 3), (2, 0), (1, 3), (0, 4), (2, 1), (3,
1), (2, 2)]
[(5, 4), (4, 4), (4, 3)]
[(5, 0), (5, 1), (4, 0), (5, 2)]
[(1, 5)]
[(2, 4)]
>>>
Unfortunately, it's rather slow. This one is much faster, using just one data
structure
def getregions2(grid):
"""Yield lists of adjancent points, not necessarily rectangular"""
adj = [(-1,0),(+1,0),(0,-1),(0,+1)] # horizontal and vertical adjacencies
# could add diagonals
rows = len(grid)
cols = len(grid[0])
griddata = []
for row in grid:
griddata.extend(row)
for y in xrange(rows):
ybase = y * cols
for x in xrange(cols):
if griddata[ybase + x]:
griddata[ybase + x] = 0
region = [(y, x)]
append = region.append
ptr = 0
while ptr < len(region):
y1, x1 = region[ptr]
for j, i in adj:
y2, x2 = y1 + j, x1 + i
if y2 < 0 or y2 == rows: continue
if x2 < 0 or x2 == cols: continue
if griddata[y2 * cols + x2]:
append((y2, x2))
griddata[y2 * cols + x2] = 0
ptr += 1
yield region
Michael
--
http://mail.python.org/mailman/listinfo/python-list
