Algorithm for finding the largest inscribed rectangle in polygon
نویسندگان
1 Department of computer science, Shahid Beheshti University, G.C., Tehran, Iran.
2 Department of computer science, Shahid Beheshti University, G.C., Tehran, Iran.
3 Department of computer science, Shahid Beheshti University, G.C., Tehran, Iran.
doi
10.22059/jac.2019.71280چکیده
In many industrial and non-industrial applications, it is necessary to identify the largest inscribed rectangle in a certain shape. The problem is studied for convex and non-convex polygons. Another criterion is the direction of the rectangle: axis aligned or general. In this paper a heuristic algorithm is presented for finding the largest axis aligned inscribed rectangle in a general polygon. Comparing with stare of the art, the rectangles resulted from our algorithm have bigger area. We also proposed an approach to use the algorithm for finding a rectangle with general direction.
