获取最大矩形的位置 [英] Obtain location of largest rectangle

问题描述

我正在尝试遵循此处答案中的代码：找到在N×N个二进制矩阵中仅包含零的最大矩形

I'm trying to follow the code in the answer here: Find largest rectangle containing only zeros in an N×N binary matrix

我很难理解如何找出算法找到的最大矩形的原点（x，y）。

I'm having difficulty understanding how to find the origin (x,y) of the largest rectangle found by the algorithm.

来自集合

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)

上面的代码似乎有效在我的示例中找到矩形的左上角，但是当我在较大的图像上尝试它时，它就崩溃了，我无法调试原因。

The above code seems to work to in my example to find the upper left-hand corner of the rectangle, but when I try it on a larger image it's breaking down and I can't debug why.

推荐答案

这里有一个解决方案，修改了 Gist版本肯尼迪·塞巴斯蒂安（JF Sebastian）的答案：

Here a solution that modifies the Gist version of J.F. Sebastian's answer:

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版本通过所有测试。在这里，例如第一个测试：

The code passes all tests from the Gist version once the positions are added to the tests. Here, e.g., the first test:

    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）。

The rectangle of size (3, 4) is at position (2, 1).

这篇关于获取最大矩形的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！