A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums

The nofit polygon is a powerful and effective tool for handling the geometric requirements of solution approaches to irregular cutting and packing problems. Although the concept was first described in 1966, it was not until the early 90s that the general trend of research moved away from direct trigonometry to favour the nofit polygon. Since then, the ability to calculate the nofit polygon has practically become a pre-requisite for researching irregular packing problems. However, realization of this concept in the form of a robust algorithm is a highly challenging task with few instructive approaches published. In this paper, a procedure using the mathematical concept of Minkowski sums for the calculation of the nofit polygon is presented. The described procedure is more robust than other approaches using Minkowski sum knowledge and includes details of the removal of internal edges to find holes, slits and lock and key positions. The procedure is tested on benchmark data sets and gives examples of complicated cases.Scope and purposeCutting and packing problems involving irregular shapes feature in a wide variety of manufacturing processes. Automated solution techniques that can generate packing arrangements more efficiently than current technology that employs user intervention, must be able to handle the complex geometry that arises from these problems. The nofit polygon has been demonstrated to be an effective tool in providing efficient handling of the geometric characteristics of these problems. The paper presents a new algorithmic procedure for deriving this tool.