an algorithm for fitting a rectangle inside a polygon

Question

I have a kind of cutting problem. There is an irregular polygon that doesn't have any holes and a list of standard sized of rectangular tiles and their values.

I want an efficient algorithm to find the single best valued tile that fit in this polygon; or an algorithm that just says if a single tile can fit inside the polygon. And it should run in deterministic time for irregular polygons with less than 100 vertices.

Please consider that you can rotate the polygon and tiles. Answers/hints for both convex and non-convex polygons are appreciated.

Answer 1

Disclaimer: I've never read any literature on this, so there might be a better way of doing this. This solution is just what I've thought about after having read your question.

A rectangle has two important measurements - it's height and it's width

now if we start with a polygon and a rectangle:

1: go around the perimeter of the polygon and take note of all the places the height of the rectangle will fit in the polygon (you can store this as a polygon*):

2: go around the perimeter of the new polygon you just made and take note of all the places the width of the rectangle will fit in the polygon (again, you can store this as a polygon):

3: the rectangle should fit within this new polygon (just be careful that you position the rectangle inside the polygon correctly, as this is a polygon - not a rectangle. If you align the top left node of the rectangle with the top left node of this new polygon, you should be ok)

4: if no area can be found that the rectangle will fit in, rotate the polygon by a couple of degrees, and try again.

*Note: in some polygons, you will get more than one place a rectangle can be fitted: