如何划分一个由小方块成更大的矩形区域？ [英] How to divide an area composed of small squares into bigger rectangles?

问题描述

我会在哪里去寻找那些需要是0或1的输入值的2D网格算法，然后确定其中的所有可能的非重叠的矩形？

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?

在一个更实际的解释：我画一个网格再由多个平方psented $ P $，我希望找到一种方法，尽可能多的相邻的方块组合成长方形越好，以减少花费在通过每平方循环并绘制它的时间。

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.

推荐答案

我已经做了相似的3D盒，OpenGL的一个快速和肮脏的体素的可视化的东西。

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.

如果有纸盒remaing，recursivly重复此过程诱导最后的矩形三个remaing长方形，这是正确的，底部和右下：

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屋！