相关疑难解决方法(0)

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

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

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

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

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

我不确定是否有一种算法可以解决这个问题.

给定数量的矩形从左到右水平并排放置以形成形状.给出每个的宽度和高度.

您如何确定覆盖整个形状所需的最小矩形数？即如何使用尽可能少的矩形重绘这个形状？

我只能考虑尽可能地挤压尽可能多的大矩形,但这似乎效率低下.有任何想法吗？

编辑:给你一个数字n,然后n个大小:2 1 3 2 5

上面将有两个尺寸为1x3和2x5的矩形彼此相邻.我想知道在矩形不能重叠的情况下,最不需要重建多少个矩形.