find all rectangular areas with certain properties in a matrix
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
I am looking for all blocks B (containing all values between (x0,y0) and (x1,y1)) that:
Example:
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.
You can get somewhere between considering every rectangle, and a properly clever solution.
For example, starting at each 1 you could create a rectangle and gradually expand its edges outwards in 4 directions. Stop when you hit a 2, record this rectangle if (a) you've had to stop in all 4 directions, and (b) you haven't seen this rectangle before.
Then backtrack: you need to be able to generate both the red rectangle and the green rectangle starting from the 1 near the top left.
This algorithm has some pretty bad worst cases, though. An input consisting of all 1 s springs to mind. So it does need to be combined with some other cleverness, or some constraints on the input.
Consider the simpler one dimension problem:
Find all the substrings of .2.1.1...12....2..1.1..2.1..2 which contains at least one 1 and no 2 and are not substring of such string. This can be solved in linear time, you just have to check if there is a 1 between two 2 .
Now you can easily adapt this algorithm to the two dimension problem:
For 1≤i≤j≤n sum all lines from i to j using the following law: .+.=. , .+1=1 , .+2=2 , 1+1=1 , 1+2=2 , 2+2=2 and apply the one dimension algorithm to the resulting line.
Complexity: O(n²m).
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.
Inspired by this answer: https://stackoverflow.com/a/7353193/145999 (pictures also taken from there)
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'
imagine a '1' or '2' in any of the grey blocks in the above picture
in the end I have M1 and M2 looking like this:
No go through M1 and M2 in reverse, by row:
I execute the following algorithm:
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.
链接地址: http://www.djcxy.com/p/10836.html上一篇: 如何让密码回显为星号
下一篇: 找到矩阵中具有某些属性的所有矩形区域