کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4630283 | 1340597 | 2012 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Finding the largest area rectangle of arbitrary orientation in a closed contour Finding the largest area rectangle of arbitrary orientation in a closed contour](/preview/png/4630283.png)
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)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.
Journal: Applied Mathematics and Computation - Volume 218, Issue 19, 1 June 2012, Pages 9866–9874