如何将由小正方形组成的区域划分为更大的矩形? [英] How to divide an area composed of small squares into bigger rectangles?

问题描述

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

Where would i go to look for algorithms that take a 2d grid of values that are either 0 or 1 as input and then identifies all possible non-overlapping rectangles in it?

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

In a more practical explanation: I am drawing a grid that is represented by a number of squares, and i wish to find a way to combine as many adjacent squares into rectangles as possible, in order to cut down on the time spent on cycling through each square and drawing it.

不需要最大效率，速度更重要.

Maximum efficiency is not needed, speed is more important.

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

Addendum: Apparently what i am looking for seems to be a technique called Tesselation. Now i only need to find a good description for this specific case.

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

Addendum 2: The boundary of the "1" squares will be irregular and in some cases not even connected, as the distribution of "1" squares will be completely random. I need these irregular shapes to be identified and split up into regular rectangles.

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

Correct answer: To get the best balance between speed and efficiency it is optimal to use the grid data to fill a quad-tree with each node having a status value of either empty/partly filled/filled.

推荐答案

我已经使用 OpenGL 对 3d 框的快速和肮脏的体素可视化做了类似的事情.

I've done something similar for a quick-and-dirty voxel visualization of 3d boxes with OpenGL.

我从左上角的框开始并存储空/已填充标志.然后我尝试将矩形向右扩展，直到我碰到一个带有不同标志的框.我在向下的方向上做了同样的事情.

I started from the top left box and stored the empty/filled flag. Then I tried to expand the rectangle to the right until I hit a box with a different flag. I did the same in the down direction.

绘制矩形，如果它被填充了.

Draw the rectangle, if it is filled.

如果还有剩余的框，则递归地对由最后一个矩形引出的所有三个剩余矩形重复该过程，分别是右、下和右下:

If there are boxes remaing, recursivly repeat the procedure for all three remaing rectangles induced by the last rectangle, which are right, bottom and bottom right:

xxxx   1111
xxxx   1111
xxxx   1111

2222   3333
2222   3333
2222   3333

这篇关于如何将由小正方形组成的区域划分为更大的矩形?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！