0

I have a 3D array. In this array I want to find elements that can be combined in bigger elements. Rectangles cannot overlay each other. Preferably I would like to find the biggest rectangle first, but a first come first serve wouldn't be wrong either, especially if that increases performance.

E.g.

1 0 0 0 1
0 0 0 0 0
0 0 0 0 1
1 1 0 0 1

will yield (as 3x3 is the biggest rectangle that can be found; position 1, 0 to 3, 2 - zerobased):

0 0 0
0 0 0
0 0 0

and (as 1x2 is the next biggest rectangle that can be found; position 0, 1 to 0, 2):

0
0

and (as 2x1 is the next biggest rectangle that can be found; position 2, 3 to 3, 3):

0 0

and of course (left is position 4, 1; which is not bigger but still needs to be used)

0

as bigger elements (I only need to know about the zeros OR ones). The purpose is to lessen the amount of colliders for a voxelgrid.

I don't know the name for such an algorithm, possibly I could find out myself how to do this then.

If someone could provide me some viable information for this, that would be great!

RobotRock
  • 4,211
  • 6
  • 46
  • 86
  • You may be looking for a "region growing algorithm". – Floris Jun 03 '13 at 18:20
  • Could You be a little more specific? –  Jun 03 '13 at 18:22
  • Okay, I'll try to add some additional information. – RobotRock Jun 03 '13 at 18:23
  • 1
    yeah, I think you need to provide more information, for example, in your case, why it doesn't yield the 2*4 '0' (row 1-2, col 0-3)? – cxyzs7 Jun 03 '13 at 18:27
  • I've added extra information; if it's not clear please tell. – RobotRock Jun 03 '13 at 18:30
  • One more question: What to do with disjunct parts? For example the rectangles by size: 9,8,6. The rectangle with 9 zeros is separated by a layer of ones from the two joint rectangles with size 8 and 6. What is the good answer here? –  Jun 03 '13 at 19:18
  • That is not really an issue to me. Either would be fine (although rectangles cannot overlay); selecting biggest would be best, but might take more time. – RobotRock Jun 03 '13 at 19:27

1 Answers1

1

For the 2D case, the algorithm used to find the biggest rectangle is the "Largest Rectangle Area under a Histogram". It is a pretty simple, O(n) algorithm, which is also discussed here.

The trick is to visualize that your matrix may actually be processed as n histograms of length m - at each line, from top to bottom, you have either a column of height 0 (which in your example would be represented by the number 1's), or a column of height height[i-1][j] + 1 when the current character is a 0. Thus each line is processed in O(m) and the total complexity becomes O(n*m). Now, since you want all the rectangles, not just THE biggest one, you'll just adapt the algorithm to "consume" any rectangle you're satisfied with, that is, whenever you find a stray 1 interrupting your rectangle formation, you can just "consume" the rectangle above that would be discontinued, and ensure the other positions below it will be restarting at height 0 or 1, effectively setting height[i-1][jbegin~jend] = 0. (Where jbegin and jend are the beginning and end of the rectangle that ends at line i-1 and which you've just chosen to "use", because it becomes blocked at line i)

For the 3D case, you'll have to understand how the Histogram algorithm works, so that you can develop your adaptation, but it should basically become a more complex version of the above, keeping track of an extra coordinate. This may not be the easiest approach to implement, but will yield optimal performance if that is what you need.

Community
  • 1
  • 1
i Code 4 Food
  • 2,144
  • 1
  • 15
  • 21
  • I agree that you can visualize it as 1 histogram per row. So there are `n` histograms of size `m`. (if the array is `n*m`) However, **to produce that histogram at each row, you need to traverse the area of the histogram** which is bounded by `n*m`. So the algorithm is at least `O(n*n*m)`. – Apiwat Chantawibul Jun 03 '13 at 21:15
  • @Billiska nope, that is why you'll keep a matrix `height[n][m]`. You process one line at a time, updating its height with the information you've already obtained from the previous line. So at line 3 you're processing your matrix as if your histogram had at most height 3, and then you move on to line 4. If you find a number `1` blocking a column, that means your column now effectively represents a height of 0, and you know there was a rectangle that ended just above it (unless it also had height 0). In fact, you also only need O(m) memory, but you don't need to worry about that at first. – i Code 4 Food Jun 03 '13 at 21:39
  • This is actually **the** most used and best algorithm to solve the problem of biggest rectangle in 2D space, and if you didn't understand why it's complexity is O(n*m), then it was my fault for not explaining it clearly enough. I, however, have not seen it being applied to the 3D case, but then again, this is the first time I see someone interested in the 3D version of the problem, whereas the 2D is rather common and well-known. (Not your specific variation of wanting *all* the rectangles, though) – i Code 4 Food Jun 03 '13 at 21:49
  • I understand yours now. Thank you. It's just that when you own algorithm result in `O(n^3)`, you kind of get the bias that other's algorithm shouldn't be faster. Anyway, now that I see you mention **variation of wanting all the rectangles**, I just realized how I don't really understand the OP. Will delete my answer for now. – Apiwat Chantawibul Jun 03 '13 at 22:17