在2D块网格发现矩形 [英] Finding rectangles in a 2d block grid

问题描述

让我们说我有块网格，7×12。我们使用的颜色'*'，'％'，'@'和空单元格 -

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.

在本例中，考虑的最小尺寸1×4，4×，2×2所以一个1×3是无效的，但一个2×3是。如果我们希望最大的矩形，我们发现如下：

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:

• 在4X1在（4,8）
• 在5X1（3,10）
• 的2x3在（1,3）
• 在2×2的（6,1）
• 2×2时（1,11）
• 在4X1在（3,12）

注意，矩形不能在彼此的空间，它们不能重叠。例如2×2矩形的（4,10）未提及，因为它会重叠在5X1矩形（3,10）。

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.

我要的是编程做到这一点。当你告诉别人发现矩形网格中，他发现他们立刻，没有任何关于它的想法。现在的问题是，我该怎么写，做同样的algoritm？

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）算法确定最大的矩形，但不是只跟踪最大的单一的矩形，对于每个（X，Y）的位置在W * H矩阵记录的宽度和高度（一个或全部），其左上角为（x，y）的最大的矩形，当您去更新这些值。
2. 循环遍历这个矩阵，将在它的每个足够-大矩形到最大堆的有序由区（宽*高）。
3. 阅读条目出这堆;它们将在减少面积顺序来制造。与每一个条目读取其左上角为（x，y）和具有宽度w和高度h，标记每个的瓦特*包括在矩形ħ位置为用于在W * H位阵列的。当从堆中阅读矩形，我们必须抛弃包含拿来主义的广场，以避免产生重叠的矩形任何矩形。它足以以检查在四个边缘反对使用的阵列，每个候选矩形的的，因为唯一的其他方式，候选矩形可以重叠另一个矩形是，如果后者矩形被它完全包含，这是不可能的，因为我们正在阅读的矩形面积递减顺序的事实。

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 w*h locations included in the rectangle as "used" in a W*H 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的，2×8，×16在这种情况下，一个选择可能会产生较大的矩形下游但我的算法并不能保证做出这样的选择。）如果有必要，你可以找到这个全局最优系列采用回溯矩形的，虽然我怀疑这可能是在最坏的情况下很慢。

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.

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