如何将由小正方形组成的区域分成更大的矩形？
我该去哪里寻找采用 0 或 1 值的二维网格作为输入，然后识别其中所有可能的不重叠矩形的算法？
更实际的解释是：我正在绘制一个由多个正方形表示的网格，我希望找到一种方法将尽可能多的相邻正方形组合成矩形，以减少循环遍历所花费的时间每个正方形并绘制它。
不需要最高效率，速度更重要。
附录：显然我正在寻找一种称为曲面细分的技术。 现在我只需要为这个具体案例找到一个好的描述。
附录2：“1”方格的边界将是不规则的，在某些情况下甚至不相连，因为“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.
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.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我已经用 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:
请参阅这篇来自 Dr Dobb's Portal 的文章，了解如何在您的情况下找到最大矩形。 这是对极其有效的算法的非常详细的讨论，我认为迭代地重复它可能会解决您的问题。
Have a look at this article from Dr Dobb's Portal on finding a maximal rectangle in your situation. It is a very detailed discussion of an extremely efficient algorithm, and I think that repeating it iteratively would possibly solve your problem.
由于您不是在寻找最小的平方数，因此我建议使用一种折衷方案来保持算法的简单性。
最佳解决方案是什么取决于您的数据，但一个简单的替代方案是仅沿一排收集盒子。 即：
将导致：
这将减少对绘图框的调用次数，而无需任何缓存（即您可以即时构建您的框）。
如果你想创建更大的盒子，我建议你使用回溯算法，找到第一个 1 并尝试向各个方向扩展盒子。 建立一个方框列表并清除您使用过的 1:s。
As you are not looking for the minimum number of squares I would suggest using a compromise that still keeps your algorithm simple.
What the best solution is depends on your data, but one simple alternative is to just collect boxes along one row. I.e:
Will result in:
This will reduce the number of calls to draw box without any need of caching (i.e you can build your boxes on the fly).
If you want to create bigger boxes I would suggest a backtracking algorithm there you find the first 1 and try to expand the box in all directions. Build a list of boxes and clear the 1:s as you have used them.
那么您正在寻找“ON”方块的矩形边界？
您想要内界还是外界？
IE。 边界必须只有“ON”方块，还是希望矩形包含一组中的所有“ON”方块？
So you are looking for the rectangular boundary of the 'ON' squares?
Do you want the inner or outer bound?
ie. Must the boundary only have 'ON' squares or do you want the rectangle to contain all the 'ON' squares in a group?
我必须解决类似的问题，我的算法支持锯齿状数组，我已经对其进行了大量测试和评论，但它比 joel-in-gö 的建议慢：
https://stackoverflow.com/a/13802336
I had to solve a similar problem, my algorithm supports jagged arrays, I have heavily tested and commented it but it's slower than joel-in-gö's suggestion :
https://stackoverflow.com/a/13802336