0-tree, which has been proposed to represent rectangle packing, has some outstanding properties. One of them is that the packing which keeps all the constraints imposed by a given 0-tree can be obtained in 0(n) time, where n is the number of rectangles. Recently, methods to extend 0-tree to represent L-shaped block packing were proposed. In this paper, a method to extend 0-tree to represent rectilinear block packing is proposed. Also, a novel algorithm to obtain the packing which keeps all the constraints imposed by any feasible 0-tree in 0(nm) time is proposed, where in is the number of rectilinear blocks. The proposed algorithm can obtain the packing in 0(n) time if all the blocks are convex.
展开▼
