任意多边形中最大的内接矩形

Question

我曾与OpenCV Stitching合作过一段时间.现在我想做拼接的最后一步:裁剪图像.这导致在一般多边形中找到最大的内接轴平行矩形.

我已经用Google搜索并找到了一些答案(如何裁剪到OpenCV中最大的内部边界框？).尽管程序运行缓慢,但输出图像的质量仍然很好(裁剪图像需要15秒才能将36个1600x1200图像拼接成1个全景图,因为使用的算法时间复杂度很低(对于轮廓中的每个点,它扫描同一行/列中的所有点).

有什么方法可以改善吗？谢谢.

P/S:我也找到了这本书:

在多边形中找到最大面积轴平行矩形

Karen Daniels和Victor Milenkovicz Dan Rothx哈佛大学,

应用科学系,

计算技术研究中心,

剑桥,MA 02138.

1995年6月

但是我没有任何想法将这个理论应用到代码中:v

Answer 1

您可能不想实现该算法; 这需要一段时间,而且我怀疑尽管有大O界,你会对表现感到失望.

听起来好像你正在使用栅格,所以你可以使用线性时间算法来找到二进制矩阵中最大的零矩形.