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
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
Finally algorithm sorts the found rectangles in descending surface area order and removes overlap. The resulting rectangles are returned as output.