CODEWITHSUNDEEP
performancematrixluagridrectangles
S. Nichols
S. Nichols

Reputation: 21

Looking for an approach to finding the minimum number of rectangles necessary in order to fill the occupied area of a 2D matrix?

I'm trying to reduce the number of objects that need to be rendered in order to fill only the occupied cells of a 2D matrix. Each cell's occupancy is binary, and the matrix extents can reach up to 512 by 512 cells. Rendering each cell independently is untenable.

Grouping occupied cells into more manageable regions is my main goal. Finding the absolute minimum number of rectangular groupings isn't necessary, but the fewer the better.

I originally thought that iterating over the grid and then grouping adjacent cells based on the occupancy of their neighbors would be the best way to approach this, but I've struggled to find performant solutions. I'm trying to avoid an O(n^2) type of situation (maybe this is unreasonable, I don't know).

I've also considered iterating over the matrix and "growing" a rectangle from every occupied cell to the nearest unoccupied cell on both axes. While this works fairly well, it clearly generates more rectangles than necessary.

I hypothesize that picking a coordinate at random and then "growing" a rectangle outward in all directions would further reduce the number of rectangles needed, but I don't know if that's true, and I haven't come up with a good test for it.

I've been working on this problem in Lua, but feel free to respond with solutions in any language.

Thank you, -SN

EDIT: For context, the matrix is a table, and each cell within the matrix has its own table, such that matrix[x][y] = {occupied = true/false}. Every coordinate in the matrix has cell data, so there aren't any nil gaps in the matrix.

Upvotes: 2

Views: 44

Answers (1)

darkfrei
darkfrei

Reputation: 521

It looks like that you search the algorithm to convert tiles (tile size is always 1×1) to rectangles as {x=x, y=y, w=w, h=h}.

Please try this solution:

https://love2d.org/wiki/TileMerging

Matrix example:

local grid = {
    {1,1,1,1,1,1,1,1,1},
    {1,0,0,1,1,1,0,0,1},
    {1,0,1,1,1,1,1,0,1},
    {1,1,1,0,1,0,1,1,1},
    {1,1,1,1,0,1,1,1,1},
    {1,1,1,0,1,0,1,1,1},
    {1,0,1,1,1,1,1,0,1},
    {1,0,0,1,1,1,0,0,1},
    {1,1,1,1,1,1,1,1,1},
}

Result:

rectangles

Upvotes: 0

Related Questions