No Fit Polygon problem : Developing a complete solution to the No Fit Polygon problem

Abstract: This thesis evaluates some of the most recent and promising approaches for deriving the No Fit Polygon for two simple polygons, possibly with holes, and verify that the approach works in practice. We have chosen three different approaches based on the complexity of the input. These approaches were implemented and benchmarked against CGAL [1], a third party library which provides solvers for many computational geometry problems. Our solution solves problems of a higher degree of complexity than that of the library we benchmarked against and for input of lower complexity we solve the problem in a more efficient manner.