相关疑难解决方法(0)

我有一组矩形,我想"减少"这个集合,所以我有最少的矩形来描述与原始集合相同的区域.如果可能的话,我希望它也快,但我更关心的是尽可能减少矩形的数量.我现在有一种方法,大部分时间都可以使用.

目前,我从最左上角的矩形开始,看看我是否可以在保持矩形的同时向右和向下展开它.我这样做,直到它不能再展开,删除并拆分所有相交的矩形,并在列表中添加展开的矩形.然后我再次使用下一个左上角的矩形开始该过程,依此类推.但在某些情况下,它不起作用.例如:

使用这组三个矩形,正确的解决方案最终会有两个矩形,如下所示:

但是,在这种情况下,我的算法从处理蓝色矩形开始.这会向下扩展并分割黄色矩形(正确).但是当处理黄色矩形的剩余部分时,它不是向下扩展,而是首先向右扩展并收回先前分离的部分.然后处理最后一个矩形,它不能向右或向下扩展,因此保留原始的矩形集.我可以调整算法,先向下扩展然后向右扩展.这将解决这种情况,但它会在翻转的类似场景中导致同样的问题.

编辑:只是为了澄清,原始的矩形集不重叠,不必连接.如果连接了矩形的子集,则完全覆盖它们的多边形可以在其中具有孔.

简化后,我要解决以下问题:

你有一个填充0和1的二维数组.找到最小数量的矩形,使它们覆盖所有1.矩形不应重叠.

函数签名可能如下所示: List<Rectangle> FindCoveringRectangles(bool[,] array)

我已经有一个"足够好"的解决方案,但并不总能找到最小数量的矩形.我想知道是否有一些众所周知且有效的算法可用于解决这个问题？

例:

输入数组:

..........
.1.....11.
.......11.
...111....
...111....
...111....
....1111..
....1111..
......11..
..........

(为了便于阅读,将0替换为点)

可能导致以下矩形:

(2,2,2,2),
(2,8,3,9),
(4,4,6,6),
(7,5,8,8),
(9,7,9,8)

(上,左,下,右),基于1

可以有多个解决方案,但其中一个就足够了.