在二维块网格中查找矩形 [英] Finding rectangles in a 2d block grid

问题描述

假设我有一个 7x12 的方块网格.我们使用颜色 '*'、'%'、'@' 和空单元格 '-'.

Let's say I have a grid of blocks, 7x12. We use the colors '*','%','@' and an empty cell '-'.

1 2 3 4 5 6 7
- - - - - - -  1
- - - - - - -  2
% % - - - - -  3
% % - - - - *  4 
% % - - - @ %  5
@ @ @ - - @ %  6
@ @ * * * - *  7
* * * % % % %  8 
% @ @ % * * %  9
% @ % % % % %  10
* * * % % @ @  11
* * @ @ @ @ *  12

我想在这个网格中找到某个最小尺寸的矩形，我能找到最大的，然后再变小，直到找不到大于或等于最小尺寸的矩形.

I want to find rectangles in this grid of a certain minimum size, and the biggest I can find and then smaller until no rectangles greater or equal to the minimum size can be found.

在此示例中，考虑最小尺寸 1x4、4x1、2x2，因此 1x3 无效，但 2x3 有效.如果我们想要最大的矩形，我们会找到以下内容:

In this example, consider the minimum size 1x4, 4x1, 2x2 so a 1x3 is not valid but a 2x3 is. If we want the biggest rectangles we find the following:

• 在 (4,8) 处 4x1
• 5x1 在 (3,10)
• 在 (1,3) 处 2x3
• 在 (6,1) 处 2x2
• 2x2 在 (1,11)
• 4x1 在 (3,12)

请注意，矩形不能在彼此的空间中，它们不能重叠.例如，没有提到 (4,10) 处的 2x2 矩形，因为它会与 (3,10) 处的 5x1 矩形重叠.

Note that rectangles cannot be in each others space, they cannot overlap. For example the 2x2 rectangle at (4,10) is not mentioned because it would overlap the 5x1 rectangle at (3,10).

所有都是完全有效的矩形:它们等于或大于最小尺寸，并且每个矩形的所有块都具有相同的颜色.

All are perfectly valid rectangles: they are equal or greater that the minimum size and all the blocks per rectangle are of the same color.

我想要以编程方式执行此操作.当您告诉某人在网格中查找矩形时，他会立即找到它们，而无需考虑.问题是，我怎样才能写出同样的算法?

What I want is to do this programmatically. When you tell someone to find rectangles in a grid, he finds them immediatly, without any thinking about it. The question is, how can I write an algoritm that does the same?

我考虑过暴力破解，但我需要算法尽可能快地执行，因为它需要在有限的(移动)设备上在非常短的时间内执行很多次.

I considered bruteforcing but I need the algorithm to execute as fast as possible as it will need to be executed a lot in a very small time frame on a limited (mobile) device.

我在互联网上看到很多关于矩形的问题，但我很惊讶这个问题还没有被问到任何地方.是我想得太难了，还是从来没有人想做这样的事情?

I see a lot of questions on the internet about rectangles, but I'm suprised this one hasn't been asked anywhere yet. Am I thinking too difficult or has no one ever wanted to do something like this?

推荐答案

分别调用输入数组W和H的宽高.

Call the width and height of the input array W and H respectively.

1. 运行 这种巧妙的 O(WH) 算法 用于确定最大矩形，但不是只跟踪单个最大矩形，而是为 W*H 矩阵中的每个 (x, y) 位置记录，其宽度和高度为 (一个或全部)左上角为 (x, y) 的最大矩形，并随时更新这些值.
2. 遍历这个矩阵，将其中的每个足够大的矩形添加到 max-堆按面积(宽*高)排序.
3. 从这个堆中读取条目；它们将按面积递减顺序生产.读取左上角为 (x, y) 且宽度为 w 和高度为 h 的每个条目，将矩形中包含的每个 wh 位置标记为 WH 中的已使用"位数组.从堆中读取矩形时，我们必须丢弃任何包含已使用"正方形的矩形，以避免产生重叠的矩形.仅检查每个候选矩形的 四个边 与已使用"数组就足够了，因为候选矩形可以与另一个矩形重叠的唯一另一种方法是，如果后一个矩形完全被它包含，这是不可能的，因为我们正在按面积递减顺序读取矩形.

1. Run this clever O(WH) algorithm for determining the largest rectangle, but instead of tracking just the single largest rectangle, for each (x, y) location record in a W*H matrix the width and height of (one or all of) the largest rectangles whose top-left corner is (x, y), updating these values as you go.
2. Loop through this matrix, adding each sufficiently-large rectangle in it to a max-heap ordered by area (width * height).
3. Read entries out of this heap; they will be produced in decreasing area order. With every entry read whose top-left corner is (x, y) and which has width w and height h, mark each of the wh locations included in the rectangle as "used" in a WH bit array. When reading rectangles from the heap, we must discard any rectangles that contain "used" squares to avoid producing overlapping rectangles. It's sufficient to check just the four edges of each candidate rectangle against the "used" array, since the only other way that the candidate rectangle could overlap another rectangle would be if the latter rectangle was completely contained by it, which is impossible due to the fact that we are reading rectangles in decreasing area order.

这种方法是贪婪的"，因为如果有多种方法可以将纯色区域雕刻成最大的矩形，则它不能保证选择整体上最大的矩形序列.(例如，可能有几个矩形的左上角位于 (10, 10) 并且面积为 16:16x1、8x2、4x4、2x8、1x16.在这种情况下，一种选择可能会产生更大的矩形下游"，但我的算法不能保证做出这样的选择.)如有必要，您可以使用回溯找到这个整体最优的矩形系列，但我怀疑在最坏的情况下这可能会非常慢.

This approach is "greedy" insofar as it won't guarantee to choose the largest sequence of rectangles overall if there are multiple ways to carve a solid coloured region into maximal rectangles. (E.g. it might be that there are several rectangles whose top-left corner is at (10, 10) and which have an area of 16: 16x1, 8x2, 4x4, 2x8, 1x16. In this case one choice might produce bigger rectangles "downstream" but my algorithm doesn't guarantee to make that choice.) If necessary you could find this overall optimal series of rectangles using backtracking, though I suspect this could be very slow in the worst case.

我提到的最大矩形算法是为单色矩形设计的，但如果你不能让它适应你的多色问题，你可以在开始第 2 步之前对每种颜色运行一次.

The maximum-rectangle algorithm I mention is designed for single-colour rectangles, but if you can't adapt it to your multi-colour problem you can simply run it once for each colour before starting step 2.

这篇关于在二维块网格中查找矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！