(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111394202.5 (22)申请日 2021.11.23 (71)申请人 江苏科技大学 地址 212008 江苏省镇江市丹徒区长晖路 666号 (72)发明人 张永林　刘想　潘薇　吴梦宇　 刘妮　戴磊　 (74)专利代理 机构 南京苏高专利商标事务所 (普通合伙) 32204 代理人 柏尚春 (51)Int.Cl. G06F 30/20(2020.01) G06Q 10/04(2012.01) (54)发明名称 一种基于临界多边形的二维平面排样优化 方法 (57)摘要 本发明公开了一种基于临界多边形的二维 平面排样 优化方法， 包括以下步骤： (1)基于明可 夫斯基法计算图形与图形间的NFP； (2)计算各图 形与母版之间的IFP； (3)基于遗传算法确定图形 之间的放置顺序； (4)基于放置顺序计算C FR； (5) 确定每个图形的放置策略； 本方案中采用明可夫 斯基法计算NFP可实现两个多 边形之间的位置关 系相互接触且不重叠， 处理大规模复杂图形的速 度更快， 其次， 对IFP的计算可保证零件放置于板 材内部， 同时舍弃CF R凹点、 选择简化点简化边的 放置策略， 提高了材 料利用率。 权利要求书1页 说明书3页 附图3页 CN 114021381 A 2022.02.08 CN 114021381 A 1.一种基于临界多边形的二维平面 排样优化方法， 其特 征在于， 包括以下步骤： (1)基于明可 夫斯基法计算图形与图形间的NFP； (2)计算各图形与母版之间的IFP； (3)基于遗传算法确定图形之间的放置顺序； (4)基于放置顺序计算CFR； (5)确定每个图形的放置策略， 其中， CFR作为表示图形的所有可放置位置， 对于CFR所 有可行解， 在CFR的凹点位置， 图形与图形只有一个交点， 将该点舍弃； 随后将图形依次放置 在CFR的简化 点、 简化边， 若CFR不存在简化 点和简化 边， 则将图形放置在CFR的左下点。 2.根据权利要求1所述的基于临界多边形的二维平面排样优化方法， 其特征在于， 在步 骤(1)中， 计算 NFP的具体步骤为， 将 样片A固定， 样片B绕其旋转 一周， 通过计算公式： 得到NFP。 3.根据权利要求1所述的基于临界多边形的二维平面排样优化方法， 其特征在于， 在步 骤(2)中， 计算IFP的具备步骤为， 在母版BIN是矩形的前提下， IFP表示样片A完全放置在母 版内的位置集 合， 通过计算公式： 得到IFP。 4.根据权利要求1所述的基于临界多边形的二维平面排样优化方法， 其特征在于， 在步 骤(3)中， 确定放置顺序的具体步骤为， 基于遗传算法， 包括个体的编码， 定义利用率适应度 函数， 设计交叉变异过程。 5.根据权利要求1所述的基于临界多边形的二维平面排样优化方法， 其特征在于， 在步 骤(4)中， 计算CFR的具体步骤为， 在母版BIN内， 已放置n个样片， 第n +1个样片可放置的位置 集合即为可放置区CFR， 通过计算公式： CFR(BIN， P， Pn+1)＝IFP(BIN， Pn+1)‑∪NFP(Pi， Pn+1) 得到CFR。 6.根据权利要求1所述的基于临界多边形的二维平面排样优化方法， 其特征在于， 在步 骤(5)中， CFR由多边形、 简化边和简化点组成， CFR的简化点和简化边来自于计算NFP时产生 的简化点和简化边， 也就是采用明可夫斯基法计算NFP过程中产生的简化点和简化边， 这个 点和边合并时被保留。 7.根据权利要求1所述的基于临界多边形的二维平面排样优化方法， 其特征在于， 在步 骤(5)中， CFR由多边形、 简化边和简化点组成， CFR的简化点和简化边来自于计算NFP时产生 的简化点和简化边， 也就是合并NFP布尔运算时产生的简化点和简化边， 这个点和边合并时 被保留。权　利　要　求　书 1/1 页 2 CN 114021381 A 2一种基于临界多边形的二维平面 排样优化方 法 技术领域 [0001]本发明涉及数控激光切割机技术， 具体涉及一种基于临界多边形的二维平面排样 优化方法。 背景技术 [0002]平面排样问题， 也就是套料问题， 是指在平面内将不规则图形进行合理布局， 并保 持互相不重 叠， 以提高材 料利用率， 节约资源， 降低生产成本 。 [0003]目前， 排样技术被广泛应用于激光切割、 服装皮革、 石材加工等领域。 按照空间划 分， 排样问题可分为一维线材排样， 二维平面排样和三维填充问题。 在二维平面排样 中， 不 同的放置顺序和放置策略对提升板材利用率有极其重要的作用， 但目前基于面积大小确定 放置顺序和基于最左最下的放置策略， 无法大幅提高利用率。 发明内容 [0004]发明目的： 本发明的目的是提供一种精度 高、 速度快且能够提高材料利用率的基 于临界多边形的二维平面 排样优化方法。 [0005]技术方案： 本发明所述的一种基于临界多边形的二维平面排样优化方法， 包括以 下步骤： [0006](1)基于明可 夫斯基法计算图形与图形间的NFP； [0007](2)计算各图形与母版之间的IFP； [0008](3)基于遗传算法确定图形之间的放置顺序； [0009](4)基于放置顺序计算CFR； [0010](5)确定每个图形的放置策略， 其中， CFR作为表示图形的所有可放置位置， 对于 CFR所有可行解， 在CFR的凹点位置， 图形与图形只有一个交点， 将该点舍弃； 随后将图形依 次放置在CFR的简化点、 简化边， 若CFR不存在简化点和简化边， 则将图形放置在CFR的左下 点。 [0011]在上述技术方案中， 采用明可夫斯基法计算图形 间NFP， 可以实现两个多边形之间 的位置关系相互接触但不重叠的效果， 且其计算方式简单， 耗时少； 全新设计的放置策略有 效提高了材 料利用率， 且该算法速度快， 处 理大规模复杂图形的效率更高。 [0012]优选的， 在步骤(1)中， 计算NFP的具体步骤为， 将样片A固定， 样片B绕其旋转一周， 通过计算公式： [0013] [0014]得到NFP， 该 方式计算过程简单， 耗时少。 [0015]优选的， 在步骤(2)中， 计算IFP的具备步骤为， 在母版BIN是矩形 的前提下， IFP表 示样片A完全放置在母版内的位置集 合， 通过计算公式： [0016] 说　明　书 1/3 页 3 CN 114021381 A 3