Finding maximal rectangles in a grid

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.