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 )
# find rectangle width
width = 1
WHILE contains( (tile.x + width, c.y, tiles )
width = width + 1
# find rectangle height
height = 0
stop = false
height = height + 1
LOOP FROM x = tile.x TO tile.x + width
IF NOT contains( (x, tile.y + height), tiles )
stop = true
x = x + 1
RETURN (width, height)
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
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)
remove( (x, y), tiles )
# if big enough rectangle add it to list
IF width > 1 AND height > 1
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])
i = i + 1
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
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
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
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.