Detecting Rectangles (sub-arrays Of Same Element Value) In 2-d List

A rectangle is defined as any rectangular-shaped section of zeros within a 2-d array of 1s and 0s. Typical example: [ [1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 0],

Solution 1:

I don't know numpy, so here's a plain Python solution:

from collections import namedtuple

Rectangle = namedtuple("Rectangle", "top bottom left right")

deffind_rectangles(arr):

    # Deeply copy the array so that it can be modified safely
    arr = [row[:] for row in arr]

    rectangles = []

    for top, row inenumerate(arr):
        start = 0# Look for rectangles whose top row is herewhileTrue:
            try:
                left = row.index(0, start)
            except ValueError:
                break# Set start to one past the last 0 in the contiguous line of 0stry:
                start = row.index(1, left)
            except ValueError:
                start = len(row)

            right = start - 1if (  # Width == 1
                  left == right or# There are 0s above
                  top > 0andnotall(arr[top-1][left:right + 1])):
                continue

            bottom = top + 1while (bottom < len(arr) and# No extra zeroes on the sides
                   (left == 0or arr[bottom][left-1]) and
                   (right == len(row) - 1or arr[bottom][right + 1]) and# All zeroes in the rownotany(arr[bottom][left:right + 1])):
                bottom += 1# The loop ends when bottom has gone too far, so backtrack
            bottom -= 1if (  # Height == 1
                  bottom == top or# There are 0s beneath
                  (bottom < len(arr) - 1andnotall(arr[bottom + 1][left:right+1]))):
                continue

            rectangles.append(Rectangle(top, bottom, left, right))

            # Remove the rectangle so that it doesn't affect future searchesfor i inrange(top, bottom+1):
                arr[i][left:right+1] = [1] * (right + 1 - left)

    return rectangles

For the given input, the output is:

[Rectangle(top=2, bottom=3, left=3, right=5),
 Rectangle(top=5, bottom=6, left=3, right=4)]

This is correct because the comments indicate that the 'rectangle' on the right is not to be counted since there is an extra 0 sticking out. I suggest you add more test cases though.

I expect it to be reasonably fast since much of the low-level iteration is done with calls to index and any, so there's decent usage of C code even without the help of numpy.

Solution 2:

I have written a simple algorithms using the Sweep line method. The idea is that You go through the columns of You array column by column, and detect the series of zeros as potentially new rectangles. In each column You have to check if the rectangles detected earlier have ended, and if yes add them to the results.

import numpy as np
from sets importSetfrom collections import namedtuple

example = np.array([
    [1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 0],
    [1, 1, 1, 0, 0, 0, 1, 0, 0],
    [1, 0, 1, 0, 0, 0, 1, 0, 0],
    [1, 0, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 1, 0, 0, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 1, 1, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1],
])

Rectangle = namedtuple("Rectangle", "left top bottom right")

defsweep(A):
    height = A.shape[0]
    length = A.shape[1]
    rectangles = dict()  # detected rectangles {(rowstart, rowend): col}
    result = []

    # sweep the matrix column by columnfor i in xrange(length):
        column = A[:, i]

        # for currently detected rectangles check if we should extend them or endfor r in rectangles.keys():
            # detect non rectangles shapes like requesten in question edit and del those rectanglesifall([x == 0for x in column[r[0]:r[1]+1]]) and ((r[0]-1>0and column[r[0]-1]==0) or (r[1]+1<height and column[r[1]+1]==0)):
                del rectangles[r]
            elifany([x == 0for x in column[r[0]:r[1]+1]]) andnotall([x == 0for x in column[r[0]:r[1]+1]]):
                del rectangles[r]
            # special case in the last column - add detected rectangleselif i == length - 1andall([x == 0for x in column[r[0]:r[1]+1]]):
               result.append(Rectangle(rectangles[r], r[0], r[1], i))
            # if detected rectangle is not extended - add to result and del from listelifall([x == 1for x in column[r[0]:r[1]+1]]):
                result.append(Rectangle(rectangles[r], r[0], r[1], i-1))
                del rectangles[r]

        newRectangle = False
        start = 0# go through the column and check if any new rectangles appearfor j in xrange(height):
            # new rectangle in column detectedif column[j] == 0andnot newRectangle and j+1 < height and column[j+1] == 0:
                start = j
                newRectangle = True# new rectangle in column endselif column[j] == 1and newRectangle:
                # check if new detected rectangle is already on the listifnot (start, j-1) in rectangles:
                    rectangles[(start, j-1)] = i
                newRectangle = False# delete single column rectangles
    resultWithout1ColumnRectangles = []
    for r in result:
        if r[0] != r[3]:
            resultWithout1ColumnRectangles.append(r)
    return resultWithout1ColumnRectangles

print example
print sweep(example)

returns:

[[1 1 1 1 1 1 1 1 1][1 1 1 1 1 1 1 1 0][1 1 1 0 0 0 1 0 0][1 0 1 0 0 0 1 0 0][1 0 1 1 1 1 1 1 1][1 0 1 0 0 1 1 1 1][1 1 1 0 0 1 1 1 1][1 1 1 1 1 1 1 1 1]][Rectangle(left=3, top=5, bottom=6, right=4), 
 Rectangle(left=3, top=2, bottom=3, right=5)]