ESICUP meeting edition:13 location:Ibiza, Spain date:18-20 May 2016
Nesting problems are one of the toughest cutting and packing problems. These problems, which are highly relevant for industry, concern the cutting or packing of irregular shapes from a larger one. However, there are two main difficulties hindering the research on these problems. The first difficulty arises from the combinatorial aspect. The problem is NP-complete, which results mainly in the usage of heuristic techniques. The second difficulty, and a large struggle point for researchers developing methods for nesting problems, are the geometrical complications arising from the irregular shapes. An established technique for dealing with these geometrical concerns is the nofit polygon. The nofit polygon defines the overlapping area between two given polygons with fixed orientations. Several methods to obtain these nofit polygons, such as those based on Minkowski sums and the orbiting method, are available in the literature.
Unfortunately, implementing an efficient and robust nofit polygon generator remains a daunting task, especially for researchers lacking the necessary programming skills. Furthermore, no tool or nofit polygon library is publicly available. Therefore, this research proposes a Java NoFit Polygon (JNFP) library. The library provides multiple methods for generating nofit polygons, based on different implementations. Initially, existing methods from the literature are implemented. New methods or method variants can be subsequently added. Basic geometric techniques are shared between the different methods. For example the intersection of two lines. Implemented methods are thoroughly tested on a large set of test cases and compared in terms of both robustness and performance. Note, however, that not all implemented methods will provide the same capabilities, such as dealing with holes, exact-fit, or other such intricacies. Additional tests are added which check these special conditions. An automated selection algorithm is added to the library. This selection algorithm chooses the most appropriate method of generating nofit polygons for any given instance, based on the properties of the input polygons (such as the existence of holes).
JNFP is made public, but also open-source at: [https://github.com/TonyWauters/JNFP].
Other researchers have the ability to contribute by improving existing implementations or by adding new test cases. Such contributions assist in further developing this library, thereby benefiting every researcher within the cutting and packing field.