Warm tip: This article is reproduced from serverfault.com, please click

algorithm-查找具有最大面积的矩形,该矩形在占用栅格中包含特定点

(algorithm - Find the rectangle with the maximum area, containing a specific point in an occupancy grid)

发布于 2020-11-24 07:26:33

问题

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

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

其中,*代表占用的方块,.代表一个自由的方块并X代表一个兴趣点,寻找包含(但不包括)障碍物(即任何障碍物)最大矩形的最省时的算法是X什么*

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

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

我的想法

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

我当前的想法是以周期性的方式将线对齐到最大位置偏移(即,转到下一行或下一列,直到遇到障碍物为止)。例如,你从点X向下传播一条水平线,直到沿着该线有障碍物,然后向左传播一条垂直线,直到遇到障碍物,然后再传播一条水平线,向右传播一条垂直线。从四条移动线之一开始重复此操作,以得到四个矩形,然后选择面积最大的矩形。但是,我不知道这是否是最佳方法,也不是最快的方法。

Questioner
Athena
Viewed
11
HEKTO 2020-12-01 01:18:14

这个问题是计算几何学中的一个众所周知的问题这里简要描述了此问题的简化版本(没有查询点)这个问题查询点可以通过以下方式配制:

令P为平面中固定轴平行矩形B中的n个点的集合。P空矩形(或简称为空矩形)是B中包含的任何与轴平行的矩形,并且其内部不包含P的任何点。我们考虑将P预处理为数据结构的问题,因此,给定一个查询点q,我们可以有效地找到包含q的最大面积的P空矩形。

上述段落中已经从复制纸,其中作者描述的算法和数据结构的集合与N在平面上的点,其允许找到在任何查询点的最大空矩形O(log^4(N))时间。抱歉地说,这是一篇理论论文,其中不包含任何算法实现细节。