grouping array

Discussion in 'Python' started by pkilambi@gmail.com, Sep 29, 2005.

  1. Guest

    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
    , Sep 29, 2005
    #1
    1. Advertising

  2. Bill Mill Guest

    On 29 Sep 2005 10:01:40 -0700, <> 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.
    >


    I don't understand. Could you give some inputs with expected outputs
    and some explanation?

    Peace
    Bill Mill
    bill.mill at gmail.com
    Bill Mill, Sep 29, 2005
    #2
    1. Advertising

  3. Guest

    sure:
    basically I am looking for clustering of non zero groups in that 2D
    list...so in the above array the first non zero cluster is 2,2 in row
    0, 1,1 in row 1 and 1,1 in row 1 so if we think of this as one group we
    have the first element of the group is at (0,0) in the list and last is
    at (2,1) in the list so we have that group represented as (0,0,2,1)
    similarly the second non group...and finally we get the result list
    with the location of that group in the whole list as
    [(0,0,2,1),(0,4,2,5)...]

    hope I am clear.
    , Sep 29, 2005
    #3
  4. 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.


    given your definitions, neither (0, 0, 2, 1) nor (0, 4, 2, 5) are clusters
    in your data. assuming that your description is wrong but your data is
    correct, and your clusters are always this simple, here's a snippet that
    does what I think you want:

    x = [[2,2,0,0,1,1],
    [1,1,0,0,1,1],
    [1,1,0,0,1,1]]

    # http://www.pythonware.com/products/pil/
    import Image

    h = len(x)
    w = len(x[0])

    data = []
    for row in x:
    data.extend(row)

    im = Image.new("L", (w, h), None)
    im.putdata(data)

    def runlength(x):
    out = []
    u = 0
    for i, v in enumerate(x):
    if v:
    if not u:
    lo = i
    elif u:
    out.append((lo, i))
    u = v
    if u: out.append((lo, i+1))
    return out

    xx, yy = im.getprojection()

    for y in runlength(yy):
    y0, y1 = y
    for x in runlength(xx):
    x0, x1 = x
    print (y0, x0, y1-1, x1-1)

    </F>
    Fredrik Lundh, Sep 29, 2005
    #4
  5. Guest

    1. why are you creating an Image object here? cant this be done by
    handling lists?
    2. What exactly is getprojection doing?
    , Sep 29, 2005
    #5
  6. <> 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


    I guess you imply rectangular regions only ? If not, what's the output supposed to be for

    [[2,2,0,0,1,1],
    [1,1,3,0,0,1],
    [1,1,3,0,1,1]]

    or

    [[2,2,2,2],
    [1,0,3,3],
    [1,1,3,0]]

    George
    George Sakkis, Sep 29, 2005
    #6
  7. 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
    Michael Spencer, Sep 30, 2005
    #7
  8. Guest

    fredrick's solutions seems to be more closer to what I was looking
    for.But I am still not sure if that could be done without the use of
    Image module.
    Also in your solution I cannot follow this
    [[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)]
    This is kind of confusing...could you please correlate the grid to the
    result and explain
    , Sep 30, 2005
    #8
  9. wrote:
    > fredrick's solutions seems to be more closer to what I was looking
    > for.But I am still not sure if that could be done without the use of
    > Image module.


    What do you mean by "closer to what I was looking
    for"? For the single test case you provided:

    > 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.
    >



    my solution provides the correct output:

    >>> 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))]

    * except that the points aren't flattened. If that's important to you, rewrite
    getregioncoords as follows:

    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]

    >>> getregioncoords(x)

    [(0, 0, 2, 1), (0, 4, 2, 5)]
    >>>



    > Also in your solution I cannot follow this


    I broke the solution into two parts:

    1) the getregions generator yields a list of all the contiguous regions. The
    output below is the lists of coordinates that are contiguous non-zero cells in
    the grid.

    > [[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)]



    2) If the regions are rectangular, the getregioncoords functions returns the
    coordinates of the top-left and bottom-right points. You did not answer the
    previous post which asked what to do if the regions were not rectangular.



    HTH

    Michael
    Michael Spencer, Sep 30, 2005
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Brad Foster

    Grouping array data

    Brad Foster, Oct 24, 2003, in forum: Java
    Replies:
    9
    Views:
    2,583
  2. neda

    grouping data of array

    neda, Aug 1, 2011, in forum: Java
    Replies:
    2
    Views:
    468
    javabudy
    Aug 6, 2011
  3. Debbie Davis

    Grouping totalling maybe an array?

    Debbie Davis, Oct 19, 2004, in forum: ASP General
    Replies:
    6
    Views:
    136
    Debbie Davis
    Oct 20, 2004
  4. Sam Kong

    Grouping elements of an array?

    Sam Kong, Jan 8, 2007, in forum: Ruby
    Replies:
    6
    Views:
    115
    Sam Kong
    Jan 8, 2007
  5. Sam Kong
    Replies:
    5
    Views:
    316
    Peña, Botp
    Oct 22, 2007
Loading...

Share This Page