Maximum Rectangle algorithms

maximum_rectangle.py

"""Maximum rectangle algorithm

Main source: [1]

[1] http://stackoverflow.com/questions/8663079/maximum-rectangle-algorithm-implementation

"""
from collections import namedtuple
import numpy as np

Point = namedtuple('Point', ('X', 'Y'))

def _area(ll, ur):
    if (ll.X < 0) or (ll.Y < 0) or (ur.X < 0) or (ur.Y < 0):
        return 0
    else:
        return ((ur.X - ll.X) + 1) * ((ur.Y - ll.Y) + 1)

def _update_cache(a, c, x):
    N,M = a.shape
    for y in xrange(M):
        if a[x,y] == 0:
            c[y] += 1
        else:
            c[y] = 0

def mrp(a):
    """Find the largest rectangle within `a` containing only zeros"""
    best_ll = Point(-1, -1)
    best_ur = Point(-1, -1)
    N,M = a.shape
    c = np.zeros(M+1,int)
    stack = []
    for x in xrange(N-1,-1,-1):
        _update_cache(a, c, x)        
        width = 0
        for y in xrange(M + 1):
            if c[y] > width:
                stack.append((y, width))                
                width = c[y]
            if c[y] < width:
                while stack:
                    y0, w0 = stack.pop()
                    if (width * (y - y0)) > _area(best_ll, best_ur):
                        best_ll = Point(x, y0)
                        best_ur = Point(x + width - 1, y - 1)
                    width = w0
                    if (c[y] >= width):
                        break
                width = c[y] 
                if width == 0:
                    stack.append((y0, w0))
    return best_ll, best_ur


def smallest_container(a):
    """Find the smallest rectangle within `a` containing all the zeros"""
    jj = np.where(np.diff(a,axis=0)!=0)[0]
    ja,jo = np.min(jj),np.max(jj)
    ii = np.where(np.diff(a,axis=1)!=0)[1]
    ia,io = np.min(ii),np.max(ii)
    return (ja,ia),(jo,io)


def demo():
    #Y               0  1  2      X
    arr = np.array([[0, 0, 0, ], #0
                    [1, 0, 0, ], #1
                    [0, 0, 1, ], #2
                    ])
    print(arr)
    print(mrp(arr))    

if __name__ == "__main__":
    
    demo()