Re: grouping array

pkilambi@gmail.com 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
Received on Sat Oct 15 03:58:36 2005