找到面积最大的矩形，包含占用网格中的特定点
Find the rectangle with the maximum area, containing a specific point in an occupancy grid
问题
给定一个占用网格，例如：
...................*
*...............*...
*..*.............*..
...........*........
....................
..*.......X.........
............*.*.*...
....*..........*....
...*........*.......
..............*.....
其中，*代表占用块，.代表空闲块，X代表兴趣点（或块），什么是最省时的算法找到包含 X 但不包含任何障碍物的 最大 矩形，即任何 *?
例如，提供的网格的解决方案是：
.....######........*
*....######.....*...
*..*.######......*..
.....######*........
.....######.........
..*..#####X.........
.....######.*.*.*...
....*######....*....
...*.######.*.......
.....######...*.....
我的想法
鉴于我们有一个已知的起点 X，我不禁认为必须有一个直接的解决方案来将线“捕捉”到外边界以创建最大的矩形。
我目前的想法是以循环的方式将线捕捉到最大位置偏移（即转到下一行或下一列，直到遇到障碍物）。例如。您从 X 点向下传播一条水平线，直到沿该线存在障碍物，然后向左传播一条垂直线，直到遇到障碍物，然后向上传播一条水平线，向右传播一条垂直线。从四条移动线之一开始重复此操作以获得四个矩形，然后 select 面积最大的矩形。但是，我不知道这是否是最优的，也不是最快的方法。
一种可能的方法是以某种方式（隐含地）排除不相关的占用单元格：那些相对于起点处于其他单元格“阴影”中的单元格：
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 和的 3x3 组唯一组合 中找到面积最大的矩形xmax 值
如果考虑到选择相关占用单元格的准备部分，这具有 O(occ_count) 的复杂性，如果仍然需要并且 occ_count，则不考虑排序是占用的单元格数。
找到最佳解决方案（在本例中为 3x3 组合）将是 O(min(C,R,occ_count)²)。 min(C,R) 包括您可以在 R
这个问题在 Computational Geometry. A simplified version of this problem (without a query point) is briefly described here 中是一个众所周知的问题。 with查询点的问题可以表述为：
Let P be a set of n points in a fixed axis-parallel rectangle B in the plane. A P-empty rectangle (or just an empty rectangle for short) is any axis-parallel rectangle that is contained in
B and its interior does not contain any point of P. We consider the problem of preprocessing
P into a data structure so that, given a query point q, we can efficiently find the largest-area
P-empty rectangle containing q.
上面的段落是从 this 论文中复制的，作者在论文中描述了平面上具有 N 个点的集合的算法和数据结构，它允许找到一个最大的空矩形O(log^4(N)) 时间内的任何查询点。不好意思，这是一篇理论论文，不包含任何算法实现细节。
问题
给定一个占用网格，例如：
...................*
*...............*...
*..*.............*..
...........*........
....................
..*.......X.........
............*.*.*...
....*..........*....
...*........*.......
..............*.....
其中，*代表占用块，.代表空闲块，X代表兴趣点（或块），什么是最省时的算法找到包含 X 但不包含任何障碍物的 最大 矩形，即任何 *?
例如，提供的网格的解决方案是：
.....######........*
*....######.....*...
*..*.######......*..
.....######*........
.....######.........
..*..#####X.........
.....######.*.*.*...
....*######....*....
...*.######.*.......
.....######...*.....
我的想法
鉴于我们有一个已知的起点 X，我不禁认为必须有一个直接的解决方案来将线“捕捉”到外边界以创建最大的矩形。
我目前的想法是以循环的方式将线捕捉到最大位置偏移（即转到下一行或下一列，直到遇到障碍物）。例如。您从 X 点向下传播一条水平线，直到沿该线存在障碍物，然后向左传播一条垂直线，直到遇到障碍物，然后向上传播一条水平线，向右传播一条垂直线。从四条移动线之一开始重复此操作以获得四个矩形，然后 select 面积最大的矩形。但是，我不知道这是否是最优的，也不是最快的方法。
一种可能的方法是以某种方式（隐含地）排除不相关的占用单元格：那些相对于起点处于其他单元格“阴影”中的单元格：
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 和的 3x3 组唯一组合 中找到面积最大的矩形xmax 值
如果考虑到选择相关占用单元格的准备部分，这具有 O(occ_count) 的复杂性，如果仍然需要并且 occ_count，则不考虑排序是占用的单元格数。
找到最佳解决方案（在本例中为 3x3 组合）将是 O(min(C,R,occ_count)²)。 min(C,R) 包括您可以在 R
这个问题在 Computational Geometry. A simplified version of this problem (without a query point) is briefly described here 中是一个众所周知的问题。 with查询点的问题可以表述为：
Let P be a set of n points in a fixed axis-parallel rectangle B in the plane. A P-empty rectangle (or just an empty rectangle for short) is any axis-parallel rectangle that is contained in B and its interior does not contain any point of P. We consider the problem of preprocessing P into a data structure so that, given a query point q, we can efficiently find the largest-area P-empty rectangle containing q.
上面的段落是从 this 论文中复制的，作者在论文中描述了平面上具有 N 个点的集合的算法和数据结构，它允许找到一个最大的空矩形O(log^4(N)) 时间内的任何查询点。不好意思，这是一篇理论论文，不包含任何算法实现细节。