Multi tool use

Clash Royale CLAN TAG

How to algorithmically find the biggest rectangle that can fit in a space with other rectangles?

So I have a rectangle that is 6m x 2.25m and I have 4 other rectangles with static dimensions but are randomly placed inside the global rectangle.

6m x 2.25m

I need to have a function that will calculate the area of the largest rectangle that can fit in the outer rectangle that also won't overlap with the other rectangles.

I thought about finding the maximum x distance between the small rects but depending if they're oriented landscape or portrait, x might not do the job. At this point I'm rather stuck and I can't find much online about doing this, but I'm sure this is quite an ordinary task for experienced coders.

Update:
Here an example image to show what I'm trying to describe. The colored rectangles are randomly placed with static dimensions, and I want to find the largest rectangle that can fit.

Thanks for your time!

1 Answer
1

As a starting point. Quadratic in the number of smaller rectangles in time and space complexity.

High-level approach

1) Divide the large rectangle into subrectangles based on the dimensions of the smaller subrectangles (purple lines in the figure). The optimal rectangle will always have its border made up of these subrectangles.

2) Mark off filled subrectangles that cannot be part of the end result (the red and yellow rectangles in the figure)

3) Now we have a search problem. We can use any search algorithm (I'm using a DFS). There are optimizations you can do on this (e.g. caching), but for simplicity:

Pseudocode

frontier = queue(all subrectangles)
largest_area = None

while frontier is not empty:
rectangle = pop a rectangle off frontier

if all subrectangles to the right of rectangle are unoccupied:
add (rectangle + extra subrectangles to the right) to frontier
largest_area = max(area of new rectangle, largest_area)
else if all subrectangles below rectangle are unoccupied:
add (rectangle + extra subrectangles below) to the frontier
largest_area = max(area of new rectangle, largest_area)

print largest_area


Explanation

Say rectangle is the green rectangle. The possible successor states are adding the subrectangles with blue stars or adding the subrectangles with pink stars. However the pink stars overlap with the yellow rectangle, so we cannot add that.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.