2D Irregular Bin Packing With Application In Digital Design

In rapid prototyping, a set of 2D irregular shapes are generated from a given 3D digital module. These 2D irregular shaped items are cut from a set of rectangular materials. When being assembled, these items form a hollow structure which resembles the original module. The target is to design a system to pack a given set of irregular shapes into a minimum number of rectangular bins with fixed size.This paper describes a best-fit heuristic algorithm based on a simple policy:make full use of the current packing pattern and maximize the residual space (RS), i.e. the unused irregular region, so that the subsequent shapes can fit with maximum likelihood. To implement this policy, an efficient searching strategy to find all the feasible positions is proposed based on a semi-discrete representation method.The proposed best-fit strategy packs the larger items into the smallest suitable RS firstly. All the feasible positions for the current item in this RS are found, and then the final position is chosen by considering the placement policy.The irregular shape of items involves a lot of computation, which is time consuming and is also the bottleneck of the traditional heuristic algorithms in the literature. The proposed algorithm can handle the irregular shaped items and find their good feasible positions quickly.With the application of rapid prototyping, results of different modules are given. Analyses based on the given experiment results shows that the propose algorithm can get a good packing pattern with high quality in a short time.