## Finding maximal rectangles in a grid

January 18, 2015 Leave a comment

Maximal rectangles problem is to find rectangles inside an area that have maximum possible surface area. This is often needed in games to show the player where in area a certain item can fit etc.. There are many ways to approach the problem, and for some cases (such as areas defined by polygon) they can get complex to implement. Here is one relatively simple method for looking up those maximum rectangles inside an area in a common grid. It’s pretty efficient and does support following restrictions

- Rectangles can have minimum size (e.g. larger than 2×2).
- There can be more than one maximum rectangle in the area. (in case two large areas are joined with narrow path)

First part is defining function that looks up rectangle dimensions. This function starts from a tile that will be left top corner of rectangle and returns its width and height. The listings here are in pseudocode.

**Listing 1. Get rectangle size**

FUNC get_rectangle_size( tile, tiles ) BEGIN # find rectangle width width = 1 WHILE contains( (tile.x + width, c.y, tiles ) width = width + 1 # find rectangle height height = 0 stop = false REPEAT height = height + 1 LOOP FROM x = tile.x TO tile.x + width IF NOT contains( (x, tile.y + height), tiles ) THEN stop = true BREAK ELSE x = x + 1 UNTIL stop RETURN (width, height) END

Function finds the maximum width of the rectangle starting from the left corner and working right (lines 5-6), then it finds rectangle height by looking up rows of same width (lines 11-20).

The actual algorithm that finds the rectangles accepts list of grid tiles as input and outputs the found rectangles that are maximally sized. The pseudocode listing here assumes some helper functions for simplicity.

`sort ( list, compare )`

– Sorts list in place by compare function`add( item, list )`

– Adds item to a list`remove (item, list)`

– Removes item from list`contains( item, list )`

– Returns true if item is found from list`length( list )`

– Returns lists length`overlap (rect1, rect2)`

– Returns true if two rectangles overlap

**Listing 2. Find maximal rectangles. Unoptimized for readability!**

FUNC find_tiles( tiles ) # the list of tiles as (x,y) tuples BEGIN rectangles = [] # list of found rectangles # sort with compare order by y and x. sort(tiles, (a, b) => a.y == b.y ? a.x - b.x : a.y - b.y) WHILE length(tiles) > 0 c = head(tiles) # take first item from the sorted list # get rectangle size (width, height) = get_rectangle_size( c, tiles ) # remove tiles that can not be part of any larger rectangle LOOP FROM x = c.x TO c.x + width LOOP FROM y = c.y TO c.y + height IF NOT contains( (c.x - 1, y, tiles) AND NOT contains( (c.x + width, y), tiles) AND NOT contains( (x, c.y - 1), tiles) AND NOT contains( (x, c.y + height), tiles) THEN remove( (x, y), tiles ) # if big enough rectangle add it to list IF width > 1 AND height > 1 THEN add ( (c.x, c.y, width, height), rectangles ) # sort rectangles by area size sort( rectangles, (r1, r2) => r2.width * r2.height - r1.width * r1.height ) # remove overlapping rectangles i = 0 WHILE i < length(rectangles) - 1 LOOP FROM j = length(rectangles) - 1 TO i + 1 # descending order IF overlaps(rectangles[i], rectangles[j]) THEN remove(rectangles[j], rectangles) i = i + 1 RETURN rectangles END

Here is example how the algorithm works, here white area presents the working set of tiles that algorithm works on, white presents the tiles that are in list `tiles`

.

Algorithm sorts first the tiles in top-to-bottom and left-to-right order so it starts from top left tile. The pink denotes the current working tile `c`

. The green represents the tiles that belong to rectangle as determined by call to `get_rectangle_size`

.

Next step is to remove tiles from working set that can not be part of any other rectangle. This is determined by checking if the row and column of tile are bounded inside the current rectangle. The purple presents tiles that were removed from the working set `tiles`

. Found rectangle is added in the list `rectangles`

if it’s large enough (in this case larger than 2×2).

Then loop is executed again with next corner tile `c`

.

Next iteration of the main loop returns another rectangle and closed tiles are removed and rectangle added to list.

Final loop of the rectangle. There are no more tiles to work so main loop stops.

Finally algorithm sorts the found rectangles in descending surface area order and removes overlap. The resulting rectangles are returned as output.