Algorithm for fitting a rectangle inside a polygon

Question

I have a cutting problem. There is an irregular polygon that does not have holes and a list of standard sizes of rectangular tiles and their values.

I want an efficient algorithm to find the single best valuable tile that fits into this polygon; or an algorithm that simply says that one tile can fit into a polygon. And it should work in deterministic time for irregular polygons with less than 100 vertices.

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

Answer 1

After many hopeless searches, I think there is no specific algorithm for this problem. Until then, I found this old document on the problem of polygon containment.
This mentioned article presents a real good algorithm to consider if a polygon with n points can correspond to a polygon with m points or not.
The algorithm has O (n ^ 3 m ^ 3 (n + m) log (n + m)) in the general case for two portable and rotating two-dimensional polygons.

Hope this helps you if you are looking for such an irregular algorithm in computational geometry.

Answer 2

Disclaimer: I have never read any literature on this subject, so there may be a better way to do this. This solution is what I was thinking about after reading your question.

A rectangle has two important dimensions: height and width

now if we start with a polygon and a rectangle:

1: go around the perimeter of the polygon and pay attention to all the places where the height of the rectangle will fit in the polygon (you can save this as a polygon *):

2: go around the perimeter of the new polygon that you just made and pay attention to all the places where the width of the rectangle will fit in the polygon (again, you can save this as a polygon):

3: the rectangle should fit into this new polygon (just be careful to correctly place the rectangle inside the polygon, as it is a polygon, not a rectangle. If you align the upper left node of the rectangle with the upper left node of this new polygon, you should be fine )

4: if no area is found that the rectangle will fit into, rotate the polygon a couple of degrees and try again.

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

Answer 3

This can help. It comes with source code written in Java

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/