在多边形内找到最大的矩形。

Question

我需要找到能够适应任何多边形的最大矩形。

我尝试的方法是将SVG划分为二维网格，并循环遍历二维数组，以查看当前网格单元格是否与多边形相交，从而创建一个新的二进制二维数组，其中交叉点为1，否则为0。

现在我需要从该二维数组中找到最大的矩形，更重要的是它的位置。

例如：

如果给定一个二维数组，我需要找到其中最大的矩形以及它的起始坐标x1,y1（即开始的行和列）和结束坐标x2,y2（即结束的行和列）。

- Sherif Salah

---

轴对齐或者任意方向的内接矩形？如果要寻找任意方向的内接矩形，可以参考 2D OBB，它可以找到最小的外接矩形，但是我认为只需要修改搜索条件就可以得到最大的内接矩形了... SQUARE_MAP（3D CUBE_MAP 的 2D 版本）是你的好朋友... - Spektre

@Spektre 谢谢您的回复。是的，轴已经对齐而不是定向。 - Sherif Salah

你的意思是最大矩形指的是单边长度还是面积？ - Spektre

@Spektre，我现在几乎可以得到最大面积的矩形了，但是难点在于找到它的位置，我无法获取其x和y坐标，我正在使用直方图算法中的最大面积，它只返回面积（大多数情况下正确）...我需要坐标并且需要知道是否有更好的解决方案。 - Sherif Salah

Answer 1

你可以通过暴力搜索位置并扫描大小来解决问题，如果n是地图边缘的平均像素大小，则时间复杂度为O(n^6)...

可以通过搜索来加速定位（接受非严格排序数据），例如：

• 近似搜索如何工作

这将导致~O(n^4.log^2(n))。但要注意，必须正确配置搜索以避免跳过解决方案...大小搜索也可以通过使用类似于此处所做的技术进行改进：

• 2D OBB

只需使用不同的度量标准，我会为每个x和y创建起始和结束位置的LUT表（4个LUT表），这将加速搜索，从而导致~O(n^2.log^2(n))，而LUT的创建是O(n^2)。顺便说一下，我有时在OCR中使用相同的LUT，例如这里（最后两张图片）：

• OCR和字符相似度

现在这种方法的问题是它无法正确处理凹多边形，因为可能会有比2个更多的边缘每x,y。因此，为了解决这个问题，您需要拥有更多的LUT并根据多边形中的位置使用它们（将多边形分成“凸”区域）。

因此，将所有这些放在一起看起来像这样：

approx loop (center x) // ~O(log(n))
 approx loop (center y) // ~O(log(n))
  grow loop (square size to max using) LUT // O(n)
    {
    grow loop (x size to max while decreasing original square y size) // O(n)
    grow loop (y size to max while decreasing original square x size) // O(n)
    use bigger from the above 2 rectangles
    }

只需不要忘记使用 多边形区域/矩形区域 作为近似误差值。此算法的结果为 〜O(n^2.log^2(n))，虽然不是很好但仍可行。

另一个选项是将多边形转换为正方形，并使用装箱和/或图形和/或回溯技术来扩展到最大的矩形...但这些不是我的强项，所以我不太自信能给出关于它们的答案。

- Spektre