Source code for tryalgo.rectangles_from_grid
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Largest area rectangle in a binary matrix
plus grand rectangle monochromatique
jill-jenn vie et christoph durr - 2014-2018
"""
from tryalgo.rectangles_from_histogram import rectangles_from_histogram
# snip{
[docs]
def rectangles_from_grid(P, black=1):
"""Largest area rectangle in a binary matrix
:param P: matrix
:param black: search for rectangles filled with value black
:returns: area, left, top, right, bottom of optimal rectangle
consisting of all (i,j) with
left <= j < right and top <= i <= bottom
:complexity: linear
"""
rows = len(P)
cols = len(P[0])
t = [0] * cols
best = None
for i in range(rows):
for j in range(cols):
if P[i][j] == black:
t[j] += 1
else:
t[j] = 0
(area, left, height, right) = rectangles_from_histogram(t)
alt = (area, left, i, right, i-height)
if best is None or alt > best:
best = alt
return best
# snip}