an algorithm for fitting a rectangle inside a polygon
algorithm, computational-geometry, polygon, rectangles
Solution
After many hopeless searches, I think there isn't any specific algorithm for this problem. Until, I found this old paper about polygon containment problem. That mentioned article, present a really good algorithm to consider if a polygon with n points can fit a polygon with m points or not. The algorithm is of O(n^3 m^3(n+m)log(n+m)) in general for two transportable and rotatable 2D polygon.
I hope it can help you, if you are searching for such an irregular algorithm in computational geometry.
Problem
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.