给定一个占用网格,例如:
...................*
*...............*...
*..*.............*..
...........*........
....................
..*.......X.........
............*.*.*...
....*..........*....
...*........*.......
..............*.....
其中,*
代表占用的方块,.
代表一个自由的方块并X
代表一个兴趣点,寻找包含(但不包括)障碍物(即任何障碍物)的最大矩形的最省时的算法是X
什么*
?
例如,提供的网格的解决方案将是:
.....######........*
*....######.....*...
*..*.######......*..
.....######*........
.....######.........
..*..#####X.........
.....######.*.*.*...
....*######....*....
...*.######.*.......
.....######...*.....
鉴于我们有一个已知的起点X
,我不禁要想到必须有一个简单的解决方案,以将线“捕捉”到外部边界以创建最大的矩形。
我当前的想法是以周期性的方式将线对齐到最大位置偏移(即,转到下一行或下一列,直到遇到障碍物为止)。例如,你从点X
向下传播一条水平线,直到沿着该线有障碍物,然后向左传播一条垂直线,直到遇到障碍物,然后再传播一条水平线,向右传播一条垂直线。从四条移动线之一开始重复此操作,以得到四个矩形,然后选择面积最大的矩形。但是,我不知道这是否是最佳方法,也不是最快的方法。