代码之家 › 专栏 › 技术社区 › Mithaldu

如何将一个由小方块组成的区域划分为更大的矩形?

rectangles area 2d geometry

11

Mithaldu · 技术社区 · 16 年前

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

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

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

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

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

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

5 回复 | 直到 16 年前

1

3

Joel in Gö 16 年前

我也做了类似的事情,用OpenGL对3d框进行快速而肮脏的体素可视化。

我从左上角的盒子开始,储存了空/满的标志。然后我试图向右扩展矩形,直到碰到一个带有不同标志的框。我在向下的方向上做了同样的事情。

绘制矩形(如果已填充)。

如果存在重造框,则对最后一个矩形(右、下和右下)诱导的所有三个重造矩形重复该过程:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

2

Daniel Rikowski 16 年前

看一看 this article from Dr Dobb's Portal 在你的情况下找到一个最大的矩形。这是对一种极其高效的算法的非常详细的讨论,我认为迭代地重复它可能会解决你的问题。

3

1

Peter Olsson 16 年前

由于你不是在寻找最小的平方数,我建议使用一种折衷方案,仍然保持算法的简单性。

最佳解决方案取决于您的数据,但一个简单的替代方案是只收集一行中的方框。即:

0 0 1 1 1 0 0 0 1 1 1 1 0

将导致:

skip 2
draw 3
skip 3
draw 4
skip 1

这将减少对绘制框的调用次数,而不需要任何缓存(即您可以动态构建框)。

如果你想创建更大的盒子,我建议你使用回溯算法,找到第一个1,并尝试向各个方向展开盒子。建立一个方框列表,并清除使用过的1:。

4

0

Martin Beckett 16 年前

所以你在寻找“ON”方块的矩形边界?
你想要内层还是外层?
即,边界必须只有“ON”方格,还是希望矩形包含一组中的所有“ON”正方形?

5

0

Community CDub 8 年前

我必须解决一个类似的问题,我的算法支持锯齿状数组,我对它进行了大量测试和评论,但它比joel-in的建议慢: https://stackoverflow.com/a/13802336