Finding the largest area rectangle of arbitrary orientation in a closed contour

摘要

For many software applications, it is sometimes necessary to find the rectangle of largest area inscribed in a polygon, in any possible direction. Thus, given a closed contour C, we consider approximation algorithms for the problem of finding the largest area rectangle of arbitrary orientation that is fully contained in C. Furthermore, we compute the largest area rectangle of arbitrary orientation in a quasi-lattice polygon, which models the C contour. In this paper, we propose an approximation algorithm that solves this problem with an O(n3) computational cost, where n is the number of vertices of the polygon. There is no other algorithm having lower computational complexity regardless of any constraints. In addition, we have developed a web application that uses the proposed algorithm.