欢迎访问《图学学报》
分享到：
摘 要：不规则多边形定位算法是排料算法的重要组成部分，其效率对排料算法的性能有重要影响。基于扫描区间表示的不规则多边形定位算法因能适应任意复杂多边形而被广泛采用，但它存在计算量大的不足。通过深入研究基于扫描区间表示的多边形定位算法，该文从两个方面对其方法进行改进：首先提出候选平移位置矩阵的概念，进而实现定位扫描算法；然后通过最大跨度比较法快速排除一些不可能的行，从而通过减少定位扫描算法的调用次数进一步加速。该算法已应用于自主开发服装排料软件，多个实际衣片数据的测试结果证明了该文算法的有效性和高效性。#br# 关 键 词：排料；扫描区间表示法；不规则多边形；定位算法
Abstract: Irregular polygon position algorithm is an important part of nesting algorithm, and it has great influence on nesting algorithm?s performance. Scan region representation based fast irregular polygon position algorithm is widely applied for it can process complex polygon, but it has shortcoming of huge computation. By intensively analyzing the algorithm, the paper improves it in two ways: the paper firstly presents the concept of candidate position matrix to realize fast position scan algorithm; and impossible rows are fast picked out through maximum span cooperation, so that the algorithm is further accelerated by avoid calling position scan algorithm for impossible rows. The algorithm has been applied in self-developed cloth nesting software, several real cloth designs are used to test the algorithm, and the result demonstrates the algorithm?s effectiveness and efficiency.#br# Key words: nesting; scan region representation; irregular polygon; position algorithm
