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.

A Google search on [rectangle inside polygon] returns some interesting results, including this research paper: mpi-inf.mpg.de/~jeschmid/public/Knauer2012.pdf, and a few SO questions: stackoverflow.com/q/610462/56778, and stackoverflow.com/q/10214829/56778 — Jim Mischel
Of course I had Googled it before. But thanks for your guidance. And I edited the problem. — Zhr Saghaie
Here's a simple approximation idea that I would try for a convex polygon. First rotate it until it's as horizontal as possible (look for a diameter and make it horizontal). Given a tile, rotate that too, if necessary, to make it horizontal. Then place it in the center of the polygon's bounding rectangle, and see which vertices are inside the polygon. If only one or two adjacent vertices are outside, move the tile in the obvious direction and see if you can get them all inside. — Hew Wolff

stormCloud stormCloud · Accepted Answer · 2013-04-09T20:18:15

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:

polygon and 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*):

where will the hight fit?

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):

where will the width fit?

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:

more than one rectangle can be fitted here

an algorithm for fitting a rectangle inside a polygon

3 Answers