在矩阵中找到具有某些属性的所有矩形区域 [英] find all rectangular areas with certain properties in a matrix

问题描述

给出一个n * m矩阵，其可能值为1、2和null：

given an n*m matrix with the possible values of 1, 2 and null:

  . . . . . 1 . .
  . 1 . . . . . 1
  . . . 2 . . . .
  . . . . 2 . . .
  1 . . . . . 1 .
  . . . . . . . .
  . . 1 . . 2 . .
  2 . . . . . . 1

我正在寻找所有块B（包含（x0，y0）和（x1之间的所有值，y1））：

I am looking for all blocks B (containing all values between (x0,y0) and (x1,y1)) that:

• 包含至少一个'1'


• 不包含'2 '


• 不是具有上述属性的另一个块的子集

示例：

红色，绿色和蓝色区域均包含'1'，不包含'2'，并且不属于较大区域。
此图片中当然有3个以上这样的块。我想找到所有这些块。

The red, green and blue area all contain an '1', no '2', and are not part of a larger area. There are of course more than 3 such blocks in this picture. I want to find all these blocks.

什么是找到所有这些区域的快速方法？

what would be a fast way to find all these areas?

我有一个有效的蛮力解决方案，遍历所有可能的矩形，检查它们是否满足前两个条件。然后遍历所有找到的矩形，删除另一个矩形中包含的所有矩形；并且我可以通过先删除连续的相同行和列来加快速度。但我可以肯定，有一种更快的方法。

I have a working brute-force solution, iterating over all possible rectangles, checking if they fulfill the first two criteria; then iterating over all found rectangles, removing all rectangles that are contained in another rectangle; and I can speed that up by first removing consecutive identical rows and columns. But I am fairly certain that there is a much faster way.

推荐答案

我终于找到了一种几乎可以线性运行的解决方案（有一个小因素取决于找到的区域数）。我认为这是最快的解决方案。

I finally found a solution that works almost in linear time (there is a small factor depending on the number of found areas). I think this is the fastest possible solution.

受到此答案的启发： https ：//stackoverflow.com/a/7353193/145999 （也从那里拍摄）

Inspired by this answer: https://stackoverflow.com/a/7353193/145999 (pictures also taken from there)

首先，我逐列处理矩阵，创建了一个新矩阵M1测量到最后一个'1'的步数，矩阵M2测量到最后一个'2'的步数

First, I go trought the matrix by column, creating a new matrix M1 measuring the number of steps to the last '1' and a matrix M2 measuring the number of steps to the last '2'

在上图中的任何灰色块中想象一个 1或 2

imagine a '1' or '2' in any of the grey blocks in the above picture

最后，我的M1和M2看起来像这样：

in the end I have M1 and M2 looking like this:

不能按行反向通过M1和M2：

No go through M1 and M2 in reverse, by row:

我执行以下算法：

 foundAreas = new list()

 For each row y backwards:
     potentialAreas = new List()
     for each column x:
        if M2[x,y]>M2[x-1,y]:
            add to potentialAreas: 
                new Area(left=x,height=M2[x,y],hasOne=M1[x,y],hasTop=false)
        if M2[x,y]<M2[x-1,y]:
            for each area in potentialAreas:
                 if area.hasTop and area.hasOne<area.height:
                        add to foundAreas:
                             new Box(Area.left,y-area.height,x,y)
            if M2[x,y]==0: delete all potentialAreas
            else:
                 find the area in potentialAreas with height=M2[x,y] 
                 or the one with the closest bigger height: set its height to M2[x,y]
                 delete all potentialAreas with a bigger height

            for each area in potentialAreas:
                 if area.hasOne>M1[x,y]: area.hasOne=M1[x,y]
                 if M2[x,y+1]==0: area.hasTop=true

现在找到了具有所需属性的所有矩形。

now foundAreas contains all rectangles with the desired properties.

这篇关于在矩阵中找到具有某些属性的所有矩形区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！