lir

在二进制网格中快速计算最大内部矩形。

:rocket: 通过Numba，Python代码被编译成机器码，以原生机器码速度执行！

安装

使用pip从PyPI安装largestinteriorrectangle。

pip install largestinteriorrectangle

:snail: 编译代码需要一些时间（在我的电脑上大约1分钟）。这只需在安装后执行一次，编译后的代码会被缓存。如果你想在应用程序外进行此操作，打开Python控制台并输入import largestinteriorrectangle。你会看到控制台暂时阻塞。完成后，第二次导入只需几毫秒。

使用方法

import largestinteriorrectangle as lir
import numpy as np

grid = np.array([[0, 0, 1, 0, 0, 0, 0, 0, 0],
                 [0, 0, 1, 0, 1, 1, 0, 0, 0],
                 [0, 0, 1, 1, 1, 1, 1, 0, 0],
                 [0, 0, 1, 1, 1, 1, 1, 1, 0],
                 [0, 0, 1, 1, 1, 1, 1, 1, 0],
                 [0, 1, 1, 1, 1, 1, 1, 0, 0],
                 [0, 0, 1, 1, 1, 1, 0, 0, 0],
                 [0, 0, 1, 1, 1, 1, 0, 0, 0],
                 [1, 1, 1, 1, 1, 1, 0, 0, 0],
                 [1, 1, 0, 0, 0, 1, 1, 1, 1],
                 [0, 0, 0, 0, 0, 0, 0, 0, 0]],
                "bool")

lir.lir(grid) # array([2, 2, 4, 7])

对于较大的网格，指定要考虑的多边形轮廓可以显著提高性能。如果网格只有一个多边形，如示例所示，可以这样获取轮廓（使用opencv）：

import cv2 as cv
cv_grid = grid.astype("uint8") * 255
contours, _ = \
    cv.findContours(cv_grid, cv.RETR_TREE, cv.CHAIN_APPROX_NONE)
contour = contours[0][:, 0, :]

然后计算矩形：

lir.lir(grid, contour) # array([2, 2, 4, 7])

你也可以从多边形坐标列表计算lir：

import numpy as np
import cv2 as cv
import largestinteriorrectangle as lir

polygon = np.array([[[20, 15], [210, 10], [220, 100], [100, 150], [20, 100]]], np.int32)
rectangle = lir.lir(polygon)

img = np.zeros((160, 240, 3), dtype="uint8")

cv.polylines(img, [polygon], True, (0, 0, 255), 1)
cv.rectangle(img, lir.pt1(rectangle), lir.pt2(rectangle), (255, 0, 0), 1)

cv.imshow('lir', img)
cv.waitKey(0)
cv.destroyAllWindows()

在后台，使用cv.fillPoly创建网格（需要OpenCV作为可选依赖），然后计算轮廓并使用基于轮廓的lir。

另请参阅我在这个Stack Overflow问题中的回答。

贡献

欢迎提交拉取请求。对于重大更改，请先开issue讨论你想要改变的内容。

请确保适当更新测试。

使用以下命令运行测试：

python -m unittest

许可证

Apache License 2.0

致谢

感谢Tim Swan将他的C#版最大内部矩形实现开源，并写了一篇很棒的博客文章。第一部分主要是用Python重新实现他的解决方案。

使用的算法在2019年的论文Algorithm for finding the largest inscribed rectangle in polygon中由Zahraa Marzeh, Maryam Tahmasbi和Narges Mireh描述。

还要感谢Mark Setchell和joni，他们在这个Stack Overflow问题中极大地帮助优化了使用cpython/numba的性能。

工作原理

对于二进制网格：

我们可以为每个单元格指定向右和向下可以走多远：

水平邻接	垂直邻接

现在目标是为每个单元格找到可能的矩形。为此，我们可以基于水平邻接指定水平向量，基于垂直邻接指定垂直向量：

水平向量 (2,2)	垂直向量 (2,2)

所以在给定的单元格(2,2)处，水平向量是(5,4)，垂直向量是(7,4)。

反转任一向量可以通过堆叠向量创建跨度，例如，将垂直向量反转为(4,7)会得到一组(5 x 4)和(4 x 7)的跨度。 由于47=28 > 54=20，宽度为4、高度为7的矩形是单元格(2,2)可能的最大矩形。宽度和高度存储在跨度图中，其中所有单元格的最大矩形的宽度和高度都被记录。通过面积，我们可以确定(2,2)处最大的矩形，其宽度为4，高度为7。

宽度	高度	面积

---

基于轮廓的LIR

特别是对于更大的网格，通过仅分析多边形的轮廓可以进一步优化功能。以下是通过计算不同分辨率掩码的lir所得到的时间：

时间	时间（对数转换）

通过仅分析轮廓像素而不是所有单元格，节省了计算成本。我们利用了LIR总是接触多边形轮廓的事实。以下是其工作原理：

轮廓单元格可以向一个（蓝色）、两个（绿色）或三个（红色）方向（上、下、左、右）延伸：

通过计算所有可能方向的跨度，我们可以得到一个跨度图：

宽度	高度	面积

为了分析这里发生的情况，我们将仔细查看单元格(4,2)。

它可以向3个方向延伸：左、下和右。向左和下延伸，最大跨度为(3 x 7)。最终跨度以从左到右和从上到下的表示法记录。然而，在这种情况下，宽度是从右到左计算的。我们可以用简单的公式x = 单元格_x - 跨度宽度 + 1转换它，在这种情况下是4 - 3 + 1 = 2。由于高度已经从上到下计算，y不变，跨度(3 x 7)被分配到单元格(2,2)（黑色虚线）。

(2,2)是跨度图中面积最大的单元格（除了(1,6)）。然而，矩形可以向右扩展（青色虚线）的信息丢失了。

因此，对于像(2,2)这样不在轮廓上且来自可向3个方向延伸的轮廓单元格的"候选单元格"，我们创建一个新的跨度图（使用从左到右和从上到下的邻接关系）：

宽度	高度	面积

比较两个跨度图的最大跨度，返回较大的一个作为lir，在这种情况下是单元格(2,2)，跨度为(4 x 7)。