First read my post Isolating distinct, arbitrary shapes on a 2D grid.

In this post I’ll explain how to break up polygons on a 2D grid into distinct rectangles. This is useful, for example, if you’re aiming to add shapes to Box2D physics engine, as convex shapes cannot be used in Box2D. The easiest way to eliminate concavity is slicing your polygons into smaller rectangles.

Here’s the 2D grid from the previous post, with two polygonal shapes (n = 2) distinguished on the grid:

{0,0,0,0,0,0}
{0,1,1,0,0,0}
{0,1,1,0,0,2}
{1,1,0,2,0,2}
{0,0,0,2,0,2}
{0,0,2,2,2,2}

This algorithm requires you to iterate the grid left-to-right, top-to-bottom. You’ll need to know the how many distinct shapes are already present on the grid (i.e. n = 2, in this example).

The method is to find how long the first row of the shape r1 is, assign each cell in r1 with the value vx,y = n, and then copy down r1 to rows rj, 1 < j < h – j (h = height of grid) below, as many times as it will continue to fit within the shape.

For example:

{0,0,0,0}
{0,1,1,0} <-- r1
{0,1,1,0}
{1,1,0,0}

r1 of the shape currently with v = 1, contains cells (x2,y2) and (x3,y2) and it’s width is 2. Give those cells the value n++ (in this case, 2). r1 can be copied down to r2 successfully, but not r3. This is because r3 has the same width as r1, but it’s left-most cell is obviously not in the same column as r1’s left-most cell.

So the algorithm would identify the first two rows as part of one rectangle, and further on would distinguish the third row as another rectangle, assigning it’s cells the value n++:

{0,0,0,0}
{0,2,2,0}
{0,2,2,0}
{3,3,0,0}

To return to the original example, for each cell (xi, yj) with a value vi where i > 0, and v < n, find out how long it’s row is by checking each tile to it’s right i.e. xi+k where k is iterated between k = 1 and k = w – x (the width of the grid – x). Stop when you reach a cell where vi+k != vi. The length of the row ri will then be l = j-i. Now, iterate yi+k, where 1 < k < h – y (where h is the height of the grid). Continue until you can no longer fit l tiles into the row ri+k. The number of rows you can copy down will be m = k – i.

Your identified rectangle will be of size l x m, starting at point (xi, yj). Each cell in that rectangle is now assigned the value vx,y = n. Once you’ve done that, increment n and continue running the algorithm.

Once you’ve finished you’ll end up with this:

{0,0,0,0,0,0}
{0,3,3,0,0,0}
{0,3,3,0,0,4}
{5,5,0,6,0,4}
{0,0,0,6,0,4}
{0,0,7,6,8,4}

You can then “normalise” the grid the so the lowest shape number is 1:

{0,0,0,0,0,0}
{0,1,1,0,0,0}
{0,1,1,0,0,2}
{3,3,0,4,0,2}
{0,0,0,4,0,2}
{0,0,5,4,6,2}

The algorithm has divided the original 2 polygonal shapes into 6 rectangles.

Here’s a Lua implementation of the algorithm:

-- grid is the 2D grid to input
-- n is the number of distinct polygons on the grid
local function createRectObjects (grid, n)
    local max = n
    local objNum = max

    -- Iterate grid
    for y = 1, #grid, 1 do
        for x = 1, #grid[y], 1 do

            --Subject tile
            local subject = {}
            subject.val = grid[y][x]
            subject.x = x
            subject.y = y

            if subject.val > 0 and subject.val <= max then
                objNum = objNum + 1
                --grid[y][x] = objNum

                --Determine width
                local blockWidth = 1
                for i = 1, #grid[y] - x, 1 do
                    if grid[y][x+i] == subject.val then
                        blockWidth = blockWidth + 1
                    else
                        break
                    end
                end

                --Determine height
                local blockHeight = 1
                for i = 1, #grid - y, 1 do
                    local invalidRow = false
                    for j = 1, blockWidth, 1 do
                        if grid[y+i][x+j-1] ~= subject.val then
                            invalidRow = true
                            break
                        end
                    end
                    if invalidRow then
                        blockHeight = i
                        break
                    elseif i == (#grid - y) then
                        blockHeight = i
                        break
                    end
                end

                --Stamp the new objNum onto the tiles in the block
                for i = subject.y, subject.y + blockHeight - 1, 1 do
                    for j = subject.x, subject.x + blockWidth -1, 1 do
                        grid[i][j] = objNum
                    end
                end
            end
        end
    end

    --Normalise numbers
    for y = 1, #grid, 1 do
        for x = 1, #grid[y], 1 do
            if grid[y][x] ~= 0 then
                grid[y][x] = grid[y][x] - max
            end
        end
    end

    obj.max = objNum - max
    return grid
end

This code is part of my Lua Grid Tools repo on Bitbucket: https://bitbucket.org/anthonygore/luagridtools

Next I’ll explain how to trace these shapes and return a table of points which outline each rectangle. Tools like Box2D take an array of vertices.