A semi-discrete geometric representation for nesting problems

This paper deals with the resolution of nesting algorithm, known as the irregular packing problem. It focuses on the geometric layer of the nesting algorithm, namely on the implementation of a semi-discrete representation of irregular geometric shapes and on the use of this representation in a nesting algorithm, proposed in previous publications. The proposed geometric scheme combines the features of discrete representation scheme and analytical concepts to quickly represent the geometry of part/sheet in digital form. The uniqueness of the proposed representation scheme lies in representing a part/sheet, of simple to complex geometry, with a series of equidistant vertical lines. These vertical lines not only aid in detecting collision among the parts easily but also assist in effective placement of parts on the sheet with bottom-left placement heuristic. With a view to enhance the speed of nesting, a scheme called Quick Void Skip is proposed to quickly identify the vacant regions on the sheet. For faster and effective nesting of a variety of parts on any geometry of sheet, the distance between the vertical lines, representing the part/sheet geometry, is adaptively chosen. Finally, the effectiveness of the proposed scheme is demonstrated by comparing its performance with that achieved by a semi-discrete approach, proposed in a previous study. © 2013 Copyright Taylor and Francis Group, LLC.