获取最大矩形的位置

Question

我正在尝试按照此处的答案中的代码进行操作：在 N×N 二进制矩阵中查找仅包含零的最大矩形

我很难理解如何找到(x,y)算法找到的最大矩形的原点。

来自收藏

import namedtuple
from operator import mul
import numpy as np
import functools

x = np.zeros(shape=(4,5))
x[0][0] = 1
x[0][1] = 1
x[0][2] = 1
x[0][3] = 1
x[1][0] = 1
x[1][1] = 1
x[1][2] = 1
x[1][3] = 1
print(x)
print(max_size(x))

Info = namedtuple('Info', 'start height')

def find_maximum_frame(mat, value=1):
    """Find height, width of the largest rectangle containing all `value`'s."""
    it = iter(mat)
    hist = [(el==value) for el in next(it, [])]
    max_size, _ = max_rectangle_size(hist)
    old_size = (0,0)
    coordinates = None
    for y,row in enumerate(it):
        hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
        new_rect, c = max_rectangle_size(hist)
        max_size = max(max_size, new_rect, key=area)
        if max_size[0]*max_size[1] > old_size[0]*old_size[1]:
            coordinates = [c[0], (y+2)-max_size[0]]
        old_size = max_size
    return [max_size, coordinates]

def max_rectangle_size(histogram):
    """Find height, width of the largest rectangle that fits entirely under
    the histogram.
    """
    stack = []
    top = lambda: stack[-1]
    max_size = (0, 0) # height, width of the largest rectangle
    pos = 0 # current position in the histogram
    for pos, height in enumerate(histogram):
        start = pos # position where rectangle starts
        while True:
            if not stack or height > top().height:
                stack.append(Info(start, height)) # push
                print(stack)
            elif stack and height < top().height:
                max_size = max(max_size, (top().height, (pos - top().start)),
                               key=area)
                start, _ = stack.pop()
                continue
            break # height == top().height goes here

    pos += 1
    coordinates = [0,0]
    old_size = (0,0)
    for start, height in stack:
        max_size = max(max_size, (height, (pos - start)), key=area)
        if max_size[0]*max_size[1] > old_size[0]*old_size[1]:
            coordinates = [start,height]
        old_size = max_size
    return [max_size, coordinates]

def area(size):
    return functools.reduce(mul, size)

上面的代码在我的示例中似乎可以找到矩形的左上角，但是当我在更大的图像上尝试它时，它会崩溃并且我无法调试原因。

Answer 1

这是修改JF Sebastian答案的Gist 版本的解决方案：

from collections import namedtuple

Info = namedtuple('Info', 'start height')

# returns height, width, and position of the top left corner of the largest
#  rectangle with the given value in mat
def max_size(mat, value=0):
    it = iter(mat)
    hist = [(el==value) for el in next(it, [])]
    max_size_start, start_row = max_rectangle_size(hist), 0
    for i, row in enumerate(it):
        hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
        mss = max_rectangle_size(hist)
        if area(mss) > area(max_size_start):
            max_size_start, start_row = mss, i+2-mss[0]
    return max_size_start[:2], (start_row, max_size_start[2])

# returns height, width, and start column of the largest rectangle that
#  fits entirely under the histogram
def max_rectangle_size(histogram):
    stack = []
    top = lambda: stack[-1]
    max_size_start = (0, 0, 0) # height, width, start of the largest rectangle
    pos = 0 # current position in the histogram
    for pos, height in enumerate(histogram):
        start = pos # position where rectangle starts
        while True:
            if not stack or height > top().height:
                stack.append(Info(start, height)) # push
            elif stack and height < top().height:
                max_size_start = max(
                    max_size_start,
                    (top().height, pos - top().start, top().start),
                    key=area)
                start, _ = stack.pop()
                continue
            break # height == top().height goes here

    pos += 1
    for start, height in stack:
        max_size_start = max(max_size_start, (height, pos - start, start),
            key=area)

    return max_size_start

def area(size): return size[0]*size[1]

一旦将位置添加到测试中，代码就会通过Gist 版本的所有测试。在这里，例如，第一个测试：

    self.assertEqual(max_size(self.__s2m("""
    0 0 0 0 1 0
    0 0 1 0 0 1
    0 0 0 0 0 0
    1 0 0 0 0 0
    0 0 0 0 0 1
    0 0 1 0 0 0""")), ((3, 4), (2, 1)))

大小为 (3, 4) 的矩形位于位置 (2, 1)。