问题描述
我正在尝试遵循此处答案中的代码：
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.
推荐答案
这里有一个解决方案，修改了肯尼迪·塞巴斯蒂安（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]
一旦将位置添加到测试中，代码就会通过通过所有测试。在这里，例如第一个测试：
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).
这篇关于获取最大矩形的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！