Two-dimensional residual-space-maximized packing

Many approaches exist for solving two dimensional rectangle-packing problems. Some rely on multiple heuristic policies to detect suitable packing positions. Others resort to searching for a sound packing sequence from a great number of variations. This paper describes a heuristic algorithm with only a single policy: maximize the residual space during packing, which ensures that rectangles to be packed will fit into the space with maximum likelihood. An efficient implementation is proposed to realize the policy. Experimental results based on openly available datasets demonstrate that the proposed algorithm is comparable to most state-of-the-art algorithms in space efficiency while is significantly faster in data processing. In the case of large-scale problems tested, it is the best by both evaluation metrics.