矩形的最小矩形数量？

Question

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

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

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

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

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

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

Answer 1

由于矩形排列良好,因此问题更容易解决.您可以从下往上创建矩形.每次执行此操作时,都会创建要检查的新形状.好处是,所有新形状也将基本对齐,您可以根据需要重复.

首先,您要查找最小高度矩形.制作一个高度为矩形的矩形,宽度为形状的总宽度.从形状的底部切下那么多.

你将留下多种形状.对于每一个,做同样的事情.

找到最小高度矩形应为O(n).因为你为每个组都这样做,最坏的情况是不同的高度.总计为O(n ²).

例如:

在图像中,每个形状的最小值以绿色突出显示.生成的矩形在右侧是蓝色.所需的矩形总数是图像中蓝色矩形的总数,7.

请注意,我正在解释这就好像这些是物理矩形.在代码中,您可以完全取消宽度,因为除非您想要输出矩形而不是仅计算所需的数量,否则它至少无关紧要.

您还可以减少"制作矩形并将其从形状中剪切",以简单地从构成该形状/子形状的每个矩形中减去高度.在这样做之后,每个连续的形状具有+ ve高度将构成一个新的子形状.

Answer 2

如果你看对算法的概述的一般问题,二值图像的矩形分解(文章作者:托马斯·苏克,西里尔·霍舍尔,和Jan Flusser)可能会有所帮助.它比较了不同的方法:行方法,四叉树,最大内切块,基于变换和图形的方法.

一个多汁的人物(来自第11页)作为开胃菜:

图5:(a)实验中使用的二进制卷积内核.(b)其10个GBD分解块.