Search

The two-dimensional graphical nesting problem is widespread in industrial production and is an NP-complete problem. The core technology of various nesting methods is the graphical collision algorithm. In this paper, a general algorithm for geometric graphics is proposed. According to the geometrical characteristics of the packed parts, the idea of divide and conquer is adopted, and the corresponding collision strategies are designed, respectively. Two-point bidirectional collision calculation, aligned bidirectional collision and slipping calculation are proposed to determine the collision relationship between graphics. The interpolation strategy is used to reduce the computation of NFP (No-Fit-Polygon). The precise interpolation between graphics is achieved by first marking and positioning, and then sliding interpolation in both directions, which improves the interpolation efficiency. Finally, the results of the comparison test by several cases of different types show that the algorithm is effective, stable, reliable and adaptable. [ABSTRACT FROM AUTHOR]

The packing for two-dimensional irregular graphics is one of the NP-complete problems and widely used in industrial applications. In this paper, a descending nesting algorithm for a two-dimensional irregular graph based on geometric feature points is proposed. Before the packing, the parts to be packed are sorted, matched, and spliced, and the matching of the rectangular pieces and the rectangular-like pieces is carried out according to the plate size. On this basis, the geometric feature points of the parts are used to construct the packing baseline, and the packing is accurately carried out according to the principles of the bottom left, the principle of the lowest center of gravity, and combination with virtual moving, rotating collision calculation. The computation of the moving collision distance between the graphics is replaced by the projecting computation of the geometric feature points of the graphic parts, so the computation amount can be reduced. Also, this method is used to test a number of benchmarks examples which are provided by ESICUP (EURO Special Interest Group on Cutting and Packing), which show that the proposed algorithm not only can improve packing but also has better stability and reliability. [ABSTRACT FROM AUTHOR]