任意多边形中的最大内切矩形 [英] largest inscribed rectangle in arbitrary polygon

问题描述

我使用过OpenCV Stitching一段时间。现在我想做最后一步拼接：裁剪图像。这导致在一般多边形中找到最大的内切轴平行矩形。

I've worked with OpenCV Stitching for a while. Now I want to do the last step of stitching: crop image. This leads to find the largest inscribed axis-parallel rectangle in general polygon.

我已经google了，并找到一些答案（如何裁剪到OpenCV中最大的内部边界框？）。由于所使用的算法具有不好的时间复杂度（对于轮廓中的每个点），输出图像的质量是良好的，尽管程序运行缓慢（需要15秒修剪图像相当只需要47秒以将36个1600×1200图片拼接成1个全景图）它扫描同一行/列中的所有点）。

I've already googled it and found some answers (How do I crop to largest interior bounding box in OpenCV?). The quality of output image is good despite the program run slowly (it takes 15 sec to crop image quite takes only 47 sec to stitch 36 1600x1200 pictures into 1 panorama) since the used algorithm have bad time complexity (for each point in the contour, it scan all point in same row/column).

以任何方式改善这一点？非常感谢。

Any way to improve this? Thanks.

P / S：我也发现这本书：

P/S: I also found this book:

多边形中的最大面积轴平行矩形

Finding the Largest Area Axis-Parallel Rectangle in a Polygon

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

Karen Daniels y Victor Milenkovicz Dan Rothx Harvard University,

应用科学部

计算技术研究中心

Cambridge，MA 02138。

Cambridge, MA 02138.

1995年6月

但我没有任何想法代码：v

but I didn't have any idea to implement the theory into code :v

推荐答案

你可能不想实现那个算法;这将需要一段时间，我怀疑你会失望的性能尽管大O绑定。

You probably don't want to implement that algorithm; it would take quite a while, and I suspect that you would be disappointed with the performance in spite of the big-O bound.

这听起来像你正在工作仍然使用栅格，因此您可以使用线性时间算法，用于在二进制矩阵中找到零的最大矩形。

It sounds as though you're working with a raster anyway, so you could use a linear-time algorithm for finding the largest rectangle of zeros in a binary matrix.

这篇关于任意多边形中的最大内切矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！