找到面积最大的矩形，包含占用网格中的特定点

Question

例如，给定一个占用网格:

...................*
*...............*...
*..*.............*..
...........*........
....................
..*.......X.........
............*.*.*...
....*..........*....
...*........*.......
..............*.....

其中，* 表示一个被占用的块，.表示一个自由块，X 表示一个感兴趣的点（或块），那么找到包含 X 但不包含任何障碍物（即任何 *）的最大矩形的最省时的算法是什么？

例如，所提供网格的解决方案将是:

.....######........*
*....######.....*...
*..*.######......*..
.....######*........
.....######.........
..*..#####X.........
.....######.*.*.*...
....*######....*....
...*.######.*.......
.....######...*.....

鉴于我们有一个已知的起点X，我不禁认为必须有一个简单的解决方案来将线条“捕捉”到外部边界以创建最大的矩形。

我目前的想法是以循环的方式将线捕捉到最大位置偏移（即转到下一行或下一列，直到遇到障碍物）。E、 g.从点X向下传播一条水平线，直到沿着该线有障碍物，然后向左传播一条垂直线，直到遇到障碍物，再向上传播一条横线，向右传播一条竖线。从四条移动线中的一条开始重复此操作，得到四个矩形，然后选择面积最大的矩形。然而，我不知道这是否是最佳的，也不知道这是最快的方法。

Answer 1

一种可能的方法是以某种方式(隐含地)排除不相关的被占据的单元:那些相对于起始点在其他单元的“阴影”中的单元:

 0         1          X
 01234567890123456789 →
0....................
1....................
2...*................
3...........*........
4....................
5..*.......X.........
6............*.......
7....*...............
8....................
9....................

↓ Y

看着这张照片，你可以说

• 矩形只有 3 个相关的 xmin 值：[3，4，5]，每个值分别具有关联的 ymin 和 ymax [（3，6），（0，6），（0，9）]
• 矩形只有 3 个相关的 xmax 值：[10，11，19]，每个值分别具有关联的 ymin 和 ymax [（0，9），（4，9），（4，5）]

因此，问题可以简化为从xmin和xmax值的唯一组合的3x3集合中找出面积最大的矩形

如果考虑到选择相关占用单元的准备部分，则其复杂性为O（occ_count），如果仍需要，则不考虑排序，occ_ count是占用单元的数量。

找到最佳解决方案（在本例中为 3x3 组合）将是 O（min（C，R，occ_count）²）。min（C，R）包括您可以在R的情况下选择“转置”方法

Answer 2

这个问题是计算几何中一个众所周知的问题。这里简要描述了这个问题的简化版本（没有查询点）。查询点的问题可以用以下方式表示：

设P是平面上固定轴平行矩形B中的n个点的集合。P-空矩形（或简称空矩形）是B中包含的任何轴平行矩形，其内部不包含任何点。我们考虑将P预处理成数据结构的问题，以便在给定一个查询点q的情况下，我们可以有效地找到包含q的最大面积P-空矩形。

上面的段落是从这篇论文中复制的，其中作者描述了平面上具有< code>N个点的集合的算法和数据结构，它允许在O(log^4(N))时间内为任何查询点找到最大的空矩形。不好意思说，这是一篇理论论文，不包含任何算法实现细节。