相关疑难解决方法(0)

什么是最有效的算法找到适合空白区域的最大面积的矩形？

假设屏幕看起来像这样('#'代表填充区域):

....................
..............######
##..................
.................###
.................###
#####...............
#####...............
#####...............

一个可能的解决方案是:

....................
..............######
##...++++++++++++...
.....++++++++++++###
.....++++++++++++###
#####++++++++++++...
#####++++++++++++...
#####++++++++++++...

通常我会喜欢找出解决方案.虽然这次我想避免浪费时间自己摸索,因为这对我正在研究的项目有实际用途.有一个众所周知的解决方案吗？

Shog9写道:

您的输入是一个数组(如其他响应所暗示的那样),还是一个以任意大小的定位矩形形式的遮挡列表(在处理窗口位置时窗口系统中可能就是这种情况)？

是的,我有一个跟踪屏幕上放置的一组窗口的结构.我还有一个网格,可以跟踪每条边之间的所有区域,无论它们是空的还是填充的,以及它们左边或顶边的像素位置.我认为有一些修改后的形式可以利用这个属性.你知道吗？

我将去哪里寻找算法,这些算法将2d网格的值为0或1作为输入,然后识别其中所有可能的非重叠矩形？

在一个更实际的解释中:我正在绘制一个由多个正方形表示的网格,我希望找到一种方法将尽可能多的相邻正方形组合成矩形,以减少在循环中花费的时间.每个方块并绘制它.

不需要最高效率,速度更重要.

附录:显然我正在寻找的似乎是一种称为Tesselation的技术.现在我只需要为这个具体案例找到一个很好的描述.

附录2:"1"方块的边界将是不规则的,在某些情况下甚至不连接,因为"1"方格的分布将是完全随机的.我需要识别这些不规则的形状并将其拆分成规则的矩形.

正确答案:为了在速度和效率之间取得最佳平衡,最好使用网格数据填充四叉树,每个节点的状态值为空/部分填充/填充.

我需要通过获取其中的"元素"数量来优化网格,并尽可能地将其最小化.当我说元素时,我指的是该网格中的一个部分.这里基本上是"输入"在视觉上看起来像什么:

想到的第一个解决方案是泛洪填充算法,但是,我有一个限制:所有元素必须有4个边,因此,所有元素必须是矩形.

我的第一个有限的方法简单包括逐个元素地循环输入网格,并检查最后一个新创建的元素是否是相同的颜色,并且具有与应该创建的元素相同的alpha - 如果是,则改为创建新元素时,它只会调整最后一个元素以进一步向下延伸1个块.

这是我正在做的一个伪代码示例:

element output_array();
element last_element = null;

for (int x = 0; x < grid_width; x++) {
    for (int y = 0; y < grid_height; y++) {
        color current_input_color = input_grid(x, y);

        if (last_element && last_element.x === x && last_element.color === current_input_color) {
            last_element.span_y++;
        } else {
            last_element = create_element(
                x,                   // element.x      (the x coordinate of the elements top left most grid space)
                y,                   // element.y      (the y coordinate of the elements …