Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes. (arXiv:2104.04525v1 [cs.CG])

We consider the irregular strip packing problem of rasterized shapes, where a
given set of pieces of irregular shapes represented in pixels should be placed
into a rectangular container without overlap. The rasterized shapes enable us
to check overlap without any exceptional handling due to geometric issues,
while they often require much memory and computational effort in
high-resolution. We develop an efficient algorithm to check overlap using a
pair of scanlines that reduces the complexity of rasterized shapes by merging
consecutive pixels in each row and column into strips with unit width,
respectively. Based on this, we develop coordinate descent heuristics that
repeat a line search in the horizontal and vertical directions alternately.
Computational results for test instances show that the proposed algorithm
obtains sufficiently dense layouts of rasterized shapes in high-resolution
within a reasonable computation time.



Related post