在二维块网格中查找矩形

发布于 2024-11-04 01:42:00 字数 935 浏览 3 评论 0原文

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

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

我想在这个网格中找到特定最小尺寸的矩形，以及我能找到的最大矩形，然后再缩小，直到找不到大于或等于最小尺寸的矩形。

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

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

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

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

我想要的是以编程方式执行此操作。当你告诉某人在网格中寻找矩形时，他会立即找到它们，无需任何思考。问题是，我如何编写一个具有相同功能的算法？

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

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

原文

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.

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 at (4,8)
5x1 at (3,10)
2x3 at (1,3)
2x2 at (6,1)
2x2 at (1,11)
4x1 at (3,12)

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

随梦而飞# 2024-11-11 01:42:00

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

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

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

我提到的最大矩形算法是为单色矩形设计的，但如果您无法使其适应多色问题，您只需在开始步骤 2 之前为每种颜色运行一次即可。

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

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.
Loop through this matrix, adding each sufficiently-large rectangle in it to a max-heap ordered by area (width * height).
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.

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.

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.

回复收藏 0 原文

以歌曲疗慰 2024-11-11 01:42:00

我必须为我的第一人称射击游戏解决一个非常相似的问题。我在输入中使用它：
[  ][  ][  ][  ][  ][  ][  ][  ]
[  ][  ][  ][X][  ][  ][  ][  ]
[  ][X][X][X][X][X][X][X]
[  ][  ][X][X][X][X][  ][  ]
[  ][X][X][X][X][  ][  ][  ]
[  ][X][X][X][X][  ][  ][  ]
[  ][  ][X][  ][  ][  ][  ][  ]
[  ][  ][  ][  ][  ][  ][  ][  ]

我在输出中得到了这个：

[  ][  ][  ][  ][  ][  ][  ][  ]
[  ][  ][  ][A][  ][  ][  ][  ]
[  ][B][G][G][G][F][E][E]
[  ][  ][G][G][G][F][  ][  ]
[  ][D][G][G][G][  ][  ][  ]
[  ][D][G][G][G][  ][  ][  ]
[  ][  ][C][  ][  ][  ][  ][  ]
[  ][  ][  ][  ][  ][  ][  ][  ]

这个架构更好。源代码（根据 GNU 通用公共许可证版本 2）为这里，有很多评论。您可能需要对其进行一些调整以适应您的需求，就像 j_random_hacker 所建议的那样。

回复收藏 0 原文

血之狂魔 2024-11-11 01:42:00

注意：这是在您尝试找到最大的 k 矩形的假设下进行的。

我们知道，在最坏的情况下，我们必须至少查看网格中的每个节点一次。这意味着我们最好情况的最坏情况是O(len*wid)。

你的暴力破解将是O(len*len*wid*wid)，采用天真的方法“检查某个点的矩形是O(len*wid)” >，并且您执行了 O(len*wid) 次，

您可能会发现情况并非如此，因为每次找到矩形时，您都有可能减少问题空间。不过，我认为“检查每个矩形”的强力方法将是最好的方法。

基本算法：

for(x = 1 .. wid) {
    for(y = 1 .. len) {
        Rectangle rect = biggestRectOriginatingAt(x,y);
        // process this rectangle for being added
    }
}

跟踪最大的k<。 /code> 矩形。随着您的操作，您可以搜索符合条件的矩形可能所在的周长。

矩形MaximumRectOriginatingAt(x,y) {
    面积=面积（最小的合格矩形）； // 如果我们想要最大的 k 个矩形，这个
                                              // 返回第 k 大的面积
                                              // 到目前为止已知的矩形

    for(i = 1 .. 面积) {
        临时宽度=我
        坦普尔 = 面积 / i

        tempx = x + tempwid
        临时 = y + 坦普尔

        checkForRectangle(x,y,tempx,tempy); // x,y --> tempx,tempy 形成一个矩形？
    }

}

这使您可以在大型搜索结束时获得巨大的性能提升（如果是小型搜索，您不会获得太多性能提升，但您不在乎，因为这是小型搜索！）

这也不起作用以获得更多随机分布。

另一种优化是使用绘画填充算法来查找最大的连续区域。这是O(len*wid)，这是一个很小的成本。这将允许您搜索最有可能出现大矩形的区域。

请注意，这些方法都不能减少最坏的情况。但是，它们确实减少了现实世界的预期运行时间。

Note: this operates under the assumption that you're trying to find the biggest k rectangles.

We know we must, in the worst case, look at every node in the grid at least once. This means our best-case worst-cast is O(len*wid).

Your brute-force is going to be O(len*len*wid*wid) with the naive approach of "Checking for rectangles at a point is O(len*wid), and you do that O(len*wid) times.

It may be that you find this to not be the case, as each time you find a rectangle, you have potential to reduce the problem space. A brute force approach of "check each rectangle" I feel is going to be the best approach. There are things you can do to speed it up, though.

Basic algorithm:

for(x = 1 .. wid) {
    for(y = 1 .. len) {
        Rectangle rect = biggestRectOriginatingAt(x,y);
        // process this rectangle for being added
    }
}

Keep track of the largest k rectangles. As you go along, you can search the perimeter of where an eligible rectangle could possibly be.

Rectangle biggestRectOriginatingAt(x,y) {
    area = areaOf(smallestEligibleRectangle); // if we want the biggest k rect's, this
                                              // returns the area of the kth biggest
                                              // known rectangle thus far

    for(i = 1 .. area) {
        tempwid = i
        templen = area / i

        tempx = x + tempwid
        tempy = y + templen

        checkForRectangle(x,y,tempx,tempy); // does x,y --> tempx,tempy form a rectangle?
    }

}

This allows you to get big performance gains towards the end of your large searches (if it's a small search, you don't gain as much but you don't care because it's a small search!)

This also doesn't work as well for more random distrobutions.

Another optimization is to use a paint-fill algorithm to find the largest consecutive areas. This is O(len*wid), which is a small cost. This will allow you to search the most likely areas for a large rectangle to be.

Note that neither of these approaches reduce the worst case. But, they do reduce the real-world expected running time.

回复收藏 0 原文

时常饿 2024-11-11 01:42:00

我自己的解决方案是找到最大的矩形，使用与 @j_random_hacker 答案中相同的算法，然后将剩余区域分成4 个区域，并在每个区域中再次递归搜索最大的矩形。

链接到 C++ 源

它会发现比接受的答案更少的矩形，因为我发现它很困难在搜索最大的矩形时，采用该算法来保存每个中间矩形。
该算法会跳过所有较小的矩形，因此我们必须迭代网格中的每个点，以保存每个可能的矩形，然后丢弃较小的矩形，这会使算法的复杂度回到 O(M3 ⋅ N3) 。

我们可以用两种方式分割剩余区域，算法将检查两者，并使用覆盖最多区域的选项，因此它将执行两次递归调用 - 第一次计算面积，第二次填充输出数组。

    ****|***|***                ************
    ****|***|***                ************
    ****#####***                ----#####---
    ****#####***        vs      ****#####***
    ****#####***                ----#####---
    ****|***|***                ************

我们可以只留下一种区域分割的选择，以使算法运行得更快，因为说实话，这种区域比较并没有对检测到的矩形数量提供太大的改进。

编辑：我刚刚意识到，递归地检查两个分割变体会将算法提高到阶乘复杂度，达到 O(min(M,N)!) 之类的程度。因此，我禁用了第二个区域分割，这使得算法的复杂度约为 O(M⋅N⋅log(M⋅N))。

My own solution is to find the biggest rectangle, using the same algorithm as in @j_random_hacker answer, then split the remaining area into 4 regions, and recursively search for the biggest rectangle again in each of these regions.

Link to C++ sources

It will find less rectangles than the accepted answer, because I have found it difficult to adopt that algorithm to save each intermediary rectangle when searching for the biggest one.
The algorithm skips all smaller rectangles, so we have to iterate through every point in our grid, to save every rectangle possible, then discard smaller ones, and this bumps the algorithm back to O(M³ ⋅ N³) complexity.

We can split the remaining area in two ways, the algorithm will check both, and will use the option which covers the most area, so it will perform the recursive call twice - first time to calculate the area, second time to fill the output array.

    ****|***|***                ************
    ****|***|***                ************
    ****#####***                ----#####---
    ****#####***        vs      ****#####***
    ****#####***                ----#####---
    ****|***|***                ************

We can leave only one choice of area split to make the algorithm run faster, because this area comparison does not provide much improvement to the amount of detected rectangles, to be honest.

Edit: I just realized that recursively checking both splitting variants raises the algorithm to factorial complexity, to something like O(min(M,N)!). So I've disabled the second area split, which leaves the algorithm with complexity around O(M⋅N⋅log(M⋅N)).

回复收藏 0 原文

~没有更多了~