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.
翻译:我们考虑了光化形状的不规则条形包装问题,在这个问题上,以像素为代表的一组非常规形状应该放在一个长方形容器中,不出现重叠。光化形状使我们能够检查重叠,而不必因几何问题而有任何特殊处理,而往往需要大量高分辨率的内存和计算工作。我们开发了一种有效的算法,用一对扫描线来检查重叠,通过将每行连续的像素和柱体分别合并成具有单位宽度的条形来降低光化形状的复杂性。基于这一点,我们开发了协调的底部螺旋,在水平和垂直方向重复线搜索。测试实例的计算结果显示,拟议的算法在合理的计算时间内获得了足够密集的光化形状。