用于不规则钣金件排样干涉检测的扫描线NFP生成方法

用于不规则钣金件排样干涉检测的扫描线nfp生成方法
技术领域
1.本发明属于机械加工生产过程中不规则钣金件优化下料领域，更具体地，涉及一种用于不规则钣金件排样干涉检测的扫描线nfp生成方法。


背景技术：

2.由于钣金件重量轻、强度高、成本低、大规模量产性能好等优点，致使钣金件的市场使用率不断提高，继而企业间竞争加剧，企业迫切希望通过降低生产成本、提高生产效率来提高其市场竞争力。对于不规则钣金件，传统的手工排样方式已经难以满足企业的生产需求，企业迫切需要一种更加高效的排样方法，不规则钣金件排样是指按照最优的排样方案在给定的母板上排放给定数量和种类的不规则轮廓的钣金件，不规则钣金件排样问题最显著的特征是所排放的钣金件属于不规则轮廓，在求解不规则钣金件排样问题时，判断不同钣金件的轮廓之间是否发生干涉的这一过程涉及到复杂的几何运算，不同的钣金件轮廓表达方式所采用的干涉判断方法不同，所需要的计算时间不同，方法的健壮性也不同。
3.在现有的针对不规则钣金件排样问题的研究中，扫描线是一种常用的不规则钣金件轮廓表达方式，在现有技术中，采用扫描线表达不规则钣金件轮廓时，排样过程中的轮廓干涉检测是通过逐个判断不同轮廓间的每条扫描线是否发生重叠来实现，该方法健壮性高，但检测效率低，且检测需要在排样过程中实时进行，严重降低了排样算法的运算效率。


技术实现要素：

4.针对现有技术的改进需求，本发明提供了一种用于不规则钣金件排样干涉检测的扫描线nfp生成方法，用于计算出两个轮廓之间完整的干涉区域。其目的在于当采用扫描线表达不规则钣金件轮廓时，通过离线计算得到两个轮廓之间完整的干涉区域，能够高效地实现排样过程中的轮廓干涉检测。
5.为实现上述目的，本发明公开了如下技术方案：
6.步骤1：输入不规则钣金件a的扫描线信息和不规则钣金件b的扫描线信息；所述扫描线信息是指在y轴方向上，以给定的扫描精度填充位于不规则钣金件内部的所有扫描线；
7.步骤2：生成外围nfp；首先选定不规则钣金件b的参考点，保持不规则钣金件a的扫描线的位置一定，将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点位于外围nfp起始高度的位置；而后使不规则钣金件b的扫描线所在高度保持固定，将不规则钣金件b的扫描线从x轴负方向无穷远处沿x轴正方向进行平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置，标记对应的不规则钣金件b的参考点为所述高度的水平左端点；使不规则钣金件b的扫描线所在高度固定，将不规则钣金件b的扫描线从x轴正方向无穷远处向x轴负方向平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置，标记对应的不规则钣金件b的参考点为所述高度的水平右端点；之后依次增加不规则钣金件b的扫描线所在高度并重复循环上述步骤，即依次将不规则钣金件b的扫描线所在高度增加一个扫描单位，并按上述过程
计算出对应高度处的左端点和右端点并标记，直至完成外围nfp终止高度对应的左端点和右端点的计算与标记；将循环过程中标记的每一高度处的左端点与对应的右端点连线，形成外围nfp在对应高度处的扫描线；所有高度对应的扫描线共同组成外围nfp；
8.步骤3：生成位于外围nfp内部的可行区域；所述可行区域指当不规则钣金件b的参考点位于该区域时不规则钣金件b的扫描线与不规则钣金件a的扫描线不存在干涉的区域；遍历外围nfp的每个扫描高度，计算出每个扫描高度的所有可行位置；判断可行位置是否为单点可行位置，若可行位置为单点可行位置，向容器中添加两次所述可行位置，若可行位置为连续可行位置，向容器中添加一次所述可行位置的x坐标和y坐标并标记为容器的一个元素，所述容器为代表可行位置的元素或元素组的集合；将容器中的所有元素按其对应的x坐标由小到大进行升序排列；排列后依序不重复地将每两个元素构成一个新元素组；容器中的每个新元素组表示对应扫描高度中的一个可行区域；遍历外围nfp的所有扫描高度后，得到位于外围nfp内部的所有可行区域；
9.步骤4：将步骤3得到的位于外围nfp内部的可行区域从外围nfp中去除；遍历外围nfp的所有扫描高度，判断所述扫描高度中是否存在可行区域，若存在，则去除所述扫描高度中的可行区域，否则直接进行下一个扫描高度的判断，直至遍历外围nfp的所有扫描高度，得到去除外围nfp内部的可行区域后的外围nfp；
10.步骤5：将步骤4得到的去除外围nfp内部的可行区域后的外围nfp作为最终nfp结果并输出。
11.可优选的，所述步骤2中外围nfp起始高度与外围nfp终止高度的定义如下：外围nfp起始高度指使不规则钣金件b的最大扫描高度与不规则钣金件a的最小扫描高度重合时，不规则钣金件b的参考点所在的高度；外围nfp终止高度是指使不规则钣金件b的最小扫描高度与不规则钣金件a的最大扫描高度重合时，不规则钣金件b的参考点所在的高度。
12.可优选的，所述步骤3中计算外围nfp某扫描高度中的所有可行位置的具体过程如下：对于给定的外围nfp的扫描高度h，将位于给定的外围nfp的扫描高度h上的扫描线记作scanh；沿y轴方向平移不规则钣金件b的扫描线至使不规则钣金件b的参考点位于高度h的位置；使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线从x轴负方向无穷远处向x轴正方向平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置；而后使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线向x正方向平移ε个单位，其中ε是大于0远小于1的正数；平移后，检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉；若不存在干涉，进一步判断该位置对应的不规则钣金件b的参考点是否位于scanh的右端点处；若该位置对应的不规则钣金件b的参考点位于scanh的右端点处，结束扫描高度h中可行位置的计算，否则标记该位置对应的不规则钣金件b的参考点为一个可行位置，而后将不规则钣金件b的扫描线向x正方向平移α个单位，其中，α取值如公式(1)所示，平移后，再次检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉，直至不规则钣金件a的扫描线与不规则钣金件b的扫描线彼此相离，且该位置对应的不规则钣金件b的参考点位于scanh的右端点处时，结束所述扫描高度中可行位置的计算；若存在干涉，将不规则钣金件b的扫描线向x轴正方向平移β个单位，其中，β指为使不规则钣金件a的扫描线与不规则钣金件b的扫描线彼此相离时不规则钣金件b的扫描线需要向x正方向平移的最小距离，平移后，再次检测不规则钣金件a
的扫描线与不规则钣金件b的扫描线是否存在干涉，直至不规则钣金件a的扫描线与不规则钣金件b的扫描线彼此相离，且该位置对应的不规则钣金件b的参考点位于scanh的右端点处时，结束该扫描高度中可行位置的计算；遍历外围nfp每个扫描高度后，得到位于外围nfp内部的所有可行位置；
[0013][0014]
公式(1)中，ha为不规则钣金件a的实扫描高度总数，hb为不规则钣金件b的实扫描高度总数，sj为不规则钣金件a的第j个实扫描高度中包含的扫描线总数，sk为不规则钣金件b的第k个实扫描高度中包含的扫描线总数，x
0ju
为不规则钣金件a的第j个实扫描高度中第u个扫描线左端点的x坐标，x
1kv
为不规则钣金件b的第k个实扫描高度中第v个扫描线右端点的x坐标，x
1ju
为不规则钣金件a的第j个实扫描高度中第u个扫描线右端点的x坐标，x
0kv
为不规则钣金件b的第k个实扫描高度中第v个扫描线左端点的x坐标，y
0j0
不规则钣金件a的第j个实扫描高度中第1个扫描线左端点的y坐标，y
0k0
为不规则钣金件b的第k个实扫描高度中第1个扫描线左端点的y坐标；所述不规则钣金件的实扫描高度是指至少存在一条扫描线的扫描高度。
[0015]
可优选的，所述步骤3中判断可行位置是否为单点可行位置的具体过程如下：对于给定的可行位置，首先将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点与所述可行位置重合的位置；而后使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线向x轴正方向平移ε个单位；其中，ε是大于0远小于1的正数；平移后，检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉；若存在干涉，标记所述可行位置为右侧干涉，否则标记所述可行位置为右侧可行；而后将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点与该可行位置重合的位置；使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线向x轴负方向平移ε个单位；其中，ε是大于0远小于1的正数；平移后，检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉；若存在干涉，标记所述可行位置为左侧干涉，否则标记所述可行位置为左侧可行；若所述可行位置既是左侧干涉又是右侧干涉，则标记所述可行位置为单点可行位置。
[0016]
可优选的，所述步骤4中去除某扫描高度中的可行区域的具体过程如下：对于外围nfp中某个存在可行区域的扫描高度h，首先将所述高度h中对应的外围nfp的扫描线的左端点存入容器ch；而后遍历所述高度h中对应的各可行区域，根据可行区域左端点x坐标由小到大排列，依次将各可行区域的左端点和右端点存入容器ch；而后将所述高度h中对应的外围nfp的扫描线的右端点存入容器ch；将容器ch中的所有元素依序不重复地两两组合，构成新元素组并按顺序存入容器ch；所述容器ch中每一个新元素组表示去除可行区域后的一个nfp扫描线片段。
[0017]
与现有技术相比，本发明具有以下有益效果：
[0018]
1.本发明用于不规则钣金件排样干涉检测的扫描线nfp生成方法，采用扫描线表达不规则钣金件轮廓时，通过离线计算得到两个轮廓之间完整的干涉区域，能够高效地实
现排样过程中的轮廓干涉检测，具有运算效率高的特点。
[0019]
2.本发明用于不规则钣金件排样干涉检测的扫描线nfp生成方法，在排样过程的干涉检测过程中，在保持不规则钣金件a的扫描线位置的情况下，通过移动不规则钣金件b的扫描线，根据不规则钣金件b的参考点与不规则钣金件a的扫描线之间的位置关系得到不规则钣金件b与不规则钣金件a之间的可行区域，从而能够针对复杂不规则钣金件准确计算出不规则钣金件的nfp，具有良好的算法稳定性。
附图说明
[0020]
图1为本发明的不规则钣金件扫描线表达示意图；
[0021]
图2为本发明的外围nfp起始高度与终止高度示意图；
[0022]
图3为本发明的外围nfp第i个高度中左端点和右端点示意图；
[0023]
图4为本发明的位于外围nfp内部的可行位置示意图；
[0024]
图5为本发明不规则钣金件a的轮廓；
[0025]
图6为本发明不规则钣金件b的轮廓；
[0026]
图7为本发明不规则钣金件a的扫描线表达；
[0027]
图8为本发明不规则钣金件b的扫描线表达；
[0028]
图9为本发明生成的外围nfp结果图；
[0029]
图10为本发明生成的最终nfp结果图；
[0030]
图11为本发明采用现有技术得到的排样方案图；
[0031]
图12为本发明采用本发明提供技术得到的排样方案图；
[0032]
图13为本发明用于不规则钣金件排样干涉检测的扫描线nfp生成方法流程图。
具体实施方式
[0033]
为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。
[0034]
本发明用于不规则钣金件排样干涉检测的扫描线nfp生成方法，在扫描线表达不规则钣金件轮廓时，通过离线计算得到两个轮廓之间完整的干涉区域，能够高效地实现排样过程中的轮廓干涉检测，应用于计算两个复杂不规则钣金件轮廓间完整的干涉区域，具有运算效率高、算法稳定性好的特点。
[0035]
具体地，如图13所示，本发明提供一种用于不规则钣金件排样干涉检测的扫描线nfp(临界多边形法nofitpolygon)生成方法，其包括下列步骤：
[0036]
步骤1：输入不规则钣金件a的扫描线信息和不规则钣金件b的扫描线信息；如图1所示，扫描线信息是指在y轴方向上，以给定的扫描精度填充位于不规则钣金件内部的所有扫描线。
[0037]
步骤2：生成外围nfp；首先选定不规则钣金件b的参考点，保持不规则钣金件a的扫描线的位置一定，将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点位于外围nfp起始高度的位置；而后使不规则钣金件b的扫描线所在高度保持固定，将不规则钣金件b
的扫描线从x轴负方向无穷远处沿x轴正方向进行平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置，标记对应的不规则钣金件b的参考点为所述高度的水平左端点；使不规则钣金件b的扫描线所在高度固定，将不规则钣金件b的扫描线从x轴正方向无穷远处向x轴负方向平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置，标记对应的不规则钣金件b的参考点为所述高度的水平右端点；之后依次增加不规则钣金件b的扫描线所在高度并重复循环上述步骤，即依次将不规则钣金件b的扫描线所在高度增加一个扫描单位，并按上述过程计算出对应高度处的左端点和右端点并标记，直至完成外围nfp终止高度对应的左端点和右端点的计算与标记；将循环过程中标记的每一高度处的左端点与对应的右端点连线，形成外围nfp在对应高度处的扫描线；所有高度对应的扫描线共同组成外围nfp。
[0038]
步骤3：生成位于外围nfp内部的可行区域；可行区域指当不规则钣金件b的参考点位于该区域时不规则钣金件b的扫描线与不规则钣金件a的扫描线不存在干涉的区域；遍历外围nfp的每个扫描高度，计算出每个扫描高度的所有可行位置；判断可行位置是否为单点可行位置，若可行位置为单点可行位置，向容器中添加两次可行位置，若可行位置为连续可行位置，向容器中添加一次可行位置的x坐标和y坐标并标记为容器的一个元素，容器为代表可行位置的元素或元素组的集合；将容器中的所有元素按其对应的x坐标由小到大进行升序排列；排列后依序不重复地将每两个元素构成一个新元素组；容器中的每个新元素组表示对应扫描高度中的一个可行区域；遍历外围nfp的所有扫描高度后，得到位于外围nfp内部的所有可行区域。
[0039]
步骤4：将步骤3得到的位于外围nfp内部的可行区域从外围nfp中去除；遍历外围nfp的所有扫描高度，判断扫描高度中是否存在可行区域，若存在，则去除扫描高度中的可行区域，否则直接进行下一个扫描高度的判断，直至遍历外围nfp的所有扫描高度，得到去除外围nfp内部的可行区域后的外围nfp。
[0040]
步骤5：将步骤4得到的去除外围nfp内部的可行区域后的外围nfp作为最终nfp结果并输出。
[0041]
其中，图2示出了外围nfp起始高度和外围nfp终止高度示意图；图3示出了外围nfp第i个高度中的左端点和外围nfp第i个高度中的右端点的示意图；图4示出了位于外围nfp内部的可行位置的示意图。
[0042]
下面结合具体实施例对本发明的工作原理进行进一步叙述：本实施例以欧洲排样问题兴趣小组esicup提供的基准问题中的swims算例的两个不规则钣金件为例，两个不规则钣金件之间的扫描线nfp生成过程如下：
[0043]
首先给出本实施例中采用扫描线表达的不规则钣金件a和不规则钣金件b的顶点信息如表1和表2所示。平移不规则钣金件a和不规则钣金件b，使其最低点移至y坐标为0后，绘制的不规则钣金件a如图5所示，绘制的不规则钣金件b图6所示。在实施例中，不规则钣金件a为固定不规则钣金件，不规则钣金件b为可水平方向和垂直方向平移的不规则钣金件。图7和图8给出了本实施例中涉及的不规则钣金件a和不规则钣金件b的标准化扫描线表达。扫描线标准化，指的是将各扫描线的实际y坐标值变为对应的扫描高度的序号，例如位于第1个扫描高度中的所有扫描线的y坐标值全部变为0，位于第2个扫描高度中的所有扫描线的y坐标值全部变为1，其余扫描高度以此类推。其中，扫描线标准化前，相邻两条扫描线的y坐
标实际间隔设置为40.0。
[0044]
表1不规则钣金件a顶点坐标
[0045]
[0046][0047]
表2不规则钣金件b顶点坐标
[0048]
[0049][0050]
本发明优选实施例的一种用于不规则钣金件排样干涉检测的扫描线nfp生成方法，包括下列步骤：
[0051]
步骤1：输入不规则钣金件a的扫描线信息和不规则钣金件b的扫描线信息；扫描线信息是指在y轴方向上，以给定的扫描精度填充位于不规则钣金件内部的所有扫描线；本实施例中输入的不规则钣金件a的扫描线信息如图7所示；本实施例中输入的不规则钣金件b的扫描线信息如图8所示。
[0052]
步骤2：生成外围nfp；首先选定不规则钣金件b的参考点，保持不规则钣金件a的扫描线的位置一定，将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点位于外围nfp起始高度的位置；而后使不规则钣金件b的扫描线所在高度保持固定，将不规则钣金件b的扫描线从x轴负方向无穷远处沿x轴正方向进行平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置，标记对应的不规则钣金件b的参考点为所述高度的水平左端点；使不规则钣金件b的扫描线所在高度固定，将不规则钣金件b的扫描线从x轴正方向无穷远处向x轴负方向平移，直至到达第一个使不规则钣金件a的
扫描线与不规则钣金件b的扫描线有且仅有点接触的位置，标记对应的不规则钣金件b的参考点为所述高度的水平右端点；之后依次增加不规则钣金件b的扫描线所在高度并重复循环上述步骤，即依次将不规则钣金件b的扫描线所在高度增加一个扫描单位，并按上述过程计算出对应高度处的左端点和右端点并标记，直至完成外围nfp终止高度对应的左端点和右端点的计算与标记；将循环过程中标记的每一高度处的左端点与对应的右端点连线，形成外围nfp在对应高度处的扫描线；所有高度对应的扫描线共同组成外围nfp；本实施例中生成的外围nfp如图9所示。
[0053]
步骤3：生成位于外围nfp内部的可行区域；可行区域指当不规则钣金件b的参考点位于该区域时不规则钣金件b的扫描线与不规则钣金件a的扫描线不存在干涉的区域；遍历外围nfp的每个扫描高度，计算出每个扫描高度的所有可行位置；判断可行位置是否为单点可行位置，若可行位置为单点可行位置，向容器中添加两次可行位置，若可行位置为连续可行位置，向容器中添加一次可行位置的x坐标和y坐标并标记为容器的一个元素，容器为代表可行位置的元素或元素组的集合；将容器中的所有元素按其对应的x坐标由小到大进行升序排列；排列后依序不重复地将每两个元素构成一个新元素组；容器中的每个新元素组表示对应扫描高度中的一个可行区域；遍历外围nfp的所有扫描高度后，得到位于外围nfp内部的所有可行区域。
[0054]
步骤4：将步骤3得到的位于外围nfp内部的可行区域从外围nfp中去除；遍历外围nfp的所有扫描高度，判断扫描高度中是否存在可行区域，若存在，则去除扫描高度中的可行区域，否则直接进行下一个扫描高度的判断，直至遍历外围nfp的所有扫描高度，得到去除外围nfp内部的可行区域后的外围nfp。
[0055]
步骤5：将步骤4得到的去除外围nfp内部的可行区域后的外围nfp作为最终nfp结果并输出。本实施例中输出的最终nfp结果如图10所示。
[0056]
步骤2中外围nfp起始高度与外围nfp终止高度的定义如下：外围nfp起始高度指使不规则钣金件b的最大扫描高度与不规则钣金件a的最小扫描高度重合时，不规则钣金件b的参考点所在的高度；外围nfp终止高度是指使不规则钣金件b的最小扫描高度与不规则钣金件a的最大扫描高度重合时，不规则钣金件b的参考点所在的高度。
[0057]
步骤3中计算外围nfp某扫描高度中的所有可行位置的具体过程如下：对于给定的外围nfp的扫描高度h，将位于给定的外围nfp的扫描高度h上的扫描线记作scanh；沿y轴方向平移不规则钣金件b的扫描线至使不规则钣金件b的参考点位于高度h的位置；使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线从x轴负方向无穷远处向x轴正方向平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置；而后使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线向x正方向平移ε个单位，其中ε是大于0远小于1的正数；平移后，检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉；若不存在干涉，进一步判断该位置对应的不规则钣金件b的参考点是否位于scanh的右端点处；若该位置对应的不规则钣金件b的参考点位于scanh的右端点处，结束扫描高度h中可行位置的计算，否则标记该位置对应的不规则钣金件b的参考点为一个可行位置，而后将不规则钣金件b的扫描线向x正方向平移α个单位，其中，α取值如公式(1)所示，平移后，再次检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉，直至不规则钣金件a的扫描线与不规则钣金件b的扫描线彼此相
离，且该位置对应的不规则钣金件b的参考点位于scanh的右端点处时，结束扫描高度中可行位置的计算；若存在干涉，将不规则钣金件b的扫描线向x轴正方向平移β个单位，其中，β指为使不规则钣金件a的扫描线与不规则钣金件b的扫描线彼此相离时不规则钣金件b的扫描线需要向x正方向平移的最小距离，平移后，再次检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉，直至不规则钣金件a的扫描线与不规则钣金件b的扫描线彼此相离，且该位置对应的不规则钣金件b的参考点位于scanh的右端点处时，结束该扫描高度中可行位置的计算；遍历外围nfp每个扫描高度后，得到位于外围nfp内部的所有可行位置；
[0058][0059]
公式(1)中，ha为不规则钣金件a的实扫描高度总数，hb为不规则钣金件b的实扫描高度总数，sj为不规则钣金件a的第j个实扫描高度中包含的扫描线总数，sk为不规则钣金件b的第k个实扫描高度中包含的扫描线总数，x
0ju
为不规则钣金件a的第j个实扫描高度中第u个扫描线左端点的x坐标，x
1kv
为不规则钣金件b的第k个实扫描高度中第v个扫描线右端点的x坐标，x
1ju
为不规则钣金件a的第j个实扫描高度中第u个扫描线右端点的x坐标，x
0kv
为不规则钣金件b的第k个实扫描高度中第v个扫描线左端点的x坐标，y
0j0
不规则钣金件a的第j个实扫描高度中第1个扫描线左端点的y坐标，y
0k0
为不规则钣金件b的第k个实扫描高度中第1个扫描线左端点的y坐标；不规则钣金件的实扫描高度是指至少存在一条扫描线的扫描高度。
[0060]
步骤3中判断可行位置是否为单点可行位置的具体过程如下：对于给定的可行位置，首先将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点与可行位置重合的位置；而后使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线向x轴正方向平移ε个单位；其中，ε是大于0远小于1的正数；平移后，检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉；若存在干涉，标记可行位置为右侧干涉，否则标记可行位置为右侧可行；而后将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点与该可行位置重合的位置；使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线向x轴负方向平移ε个单位；其中，ε是大于0远小于1的正数；平移后，检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉；若存在干涉，标记可行位置为左侧干涉，否则标记可行位置为左侧可行；若可行位置既是左侧干涉又是右侧干涉，则标记可行位置为单点可行位置。
[0061]
步骤4中去除某扫描高度中的可行区域的具体过程如下：对于外围nfp中某个存在可行区域的扫描高度h，首先将高度h中对应的外围nfp的扫描线的左端点存入容器ch；而后遍历高度h中对应的各可行区域，根据可行区域左端点x坐标由小到大排列，依次将各可行区域的左端点和右端点存入容器ch；而后将高度h中对应的外围nfp的扫描线的右端点存入容器ch；将容器ch中的所有元素依序不重复地两两组合，构成新元素组并按顺序存入容器ch；容器ch中每一个新元素组表示去除可行区域后的一个nfp扫描线片段。
[0062]
为验证本发明所提供方法的高效性，采用esicup基准问题的shirts算例作为测试算例，将本发明提供方法得到的排样数据与现有技术得到的排样数据进行对比。算例包含的不规则钣金件信息如表2所示，不规则钣金件额扫描线表达的基本扫描精度rb取值为0.16，得到的排样结果如表3所示。采用现有技术得到的排样方案图如图11所示，采用本发明所提供技术得到的排样方案图如图12所示。
[0063]
由表3可知，与现有技术相比，本发明提供的方法在保证排样效果的前提下，计算效率得到大幅度提升，证明了本发明所提供方法的有效性。
[0064]
表2算例信息
[0065][0066]
表3排样结果
[0067][0068]
以上所述的实施例仅是对本发明的优选实施方式进行描述，并非对本发明的范围进行限定，在不脱离本发明设计精神的前提下，本领域普通技术人员对本发明的技术方案做出的各种变形和改进，均应落入本发明权利要求书确定的保护范围内。

技术特征：
1.一种用于不规则钣金件排样干涉检测的扫描线nfp生成方法，其特征在于，其包括下列步骤：步骤1：输入不规则钣金件a的扫描线信息和不规则钣金件b的扫描线信息；所述扫描线信息是指在y轴方向上，以给定的扫描精度填充位于不规则钣金件内部的所有扫描线；步骤2：生成外围nfp；首先选定不规则钣金件b的参考点，保持不规则钣金件a的扫描线的位置一定，将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点位于外围nfp起始高度的位置；而后使不规则钣金件b的扫描线所在高度保持固定，将不规则钣金件b的扫描线从x轴负方向无穷远处沿x轴正方向进行平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置，标记对应的不规则钣金件b的参考点为所述高度的水平左端点；使不规则钣金件b的扫描线所在高度固定，将不规则钣金件b的扫描线从x轴正方向无穷远处向x轴负方向平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置，标记对应的不规则钣金件b的参考点为所述高度的水平右端点；之后依次增加不规则钣金件b的扫描线所在高度并重复循环上述步骤，即依次将不规则钣金件b的扫描线所在高度增加一个扫描单位，并按上述过程计算出对应高度处的左端点和右端点并标记，直至完成外围nfp终止高度对应的左端点和右端点的计算与标记；将循环过程中标记的每一高度处的左端点与对应的右端点连线，形成外围nfp在对应高度处的扫描线；所有高度对应的扫描线共同组成外围nfp；步骤3：生成位于外围nfp内部的可行区域；所述可行区域指当不规则钣金件b的参考点位于该区域时不规则钣金件b的扫描线与不规则钣金件a的扫描线不存在干涉的区域；遍历外围nfp的每个扫描高度，计算出每个扫描高度的所有可行位置；判断可行位置是否为单点可行位置，若可行位置为单点可行位置，向容器中添加两次所述可行位置，若可行位置为连续可行位置，向容器中添加一次所述可行位置的x坐标和y坐标并标记为容器的一个元素，所述容器为代表可行位置的元素或元素组的集合；将容器中的所有元素按其对应的x坐标由小到大进行升序排列；排列后依序不重复地将每两个元素构成一个新元素组；容器中的每个新元素组表示对应扫描高度中的一个可行区域；遍历外围nfp的所有扫描高度后，得到位于外围nfp内部的所有可行区域；步骤4：将步骤3得到的位于外围nfp内部的可行区域从外围nfp中去除；遍历外围nfp的所有扫描高度，判断所述扫描高度中是否存在可行区域，若存在，则去除所述扫描高度中的可行区域，否则直接进行下一个扫描高度的判断，直至遍历外围nfp的所有扫描高度，得到去除外围nfp内部的可行区域后的外围nfp；步骤5：将步骤4得到的去除外围nfp内部的可行区域后的外围nfp作为最终nfp结果并输出。2.根据权利要求1所述的用于不规则钣金件排样干涉检测的扫描线nfp生成方法，其特征在于，所述步骤2中，外围nfp起始高度与外围nfp终止高度的定义如下：外围nfp起始高度指使不规则钣金件b的最大扫描高度与不规则钣金件a的最小扫描高度重合时，不规则钣金件b的参考点所在的高度；外围nfp终止高度是指使不规则钣金件b的最小扫描高度与不规则钣金件a的最大扫描高度重合时，不规则钣金件b的参考点所在的高度。3.根据权利要求1所述的用于不规则钣金件排样干涉检测的扫描线nfp生成方法，其特征在于，所述步骤3中，计算外围nfp给定扫描高度中的所有可行位置的具体过程如下：对于
给定的外围nfp的扫描高度h，将位于给定的外围nfp的扫描高度h上的扫描线记作scan
h
；沿y轴方向平移不规则钣金件b的扫描线至使不规则钣金件b的参考点位于高度h的位置；使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线从x轴负方向无穷远处向x轴正方向平移，直至到达第一个使不规则钣金件a的扫描线与不规则钣金件b的扫描线有且仅有点接触的位置；而后使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线向x正方向平移ε个单位，其中ε是大于0远小于1的正数；平移后，检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉；若不存在干涉，进一步判断该位置对应的不规则钣金件b的参考点是否位于scan
h
的右端点处；若该位置对应的不规则钣金件b的参考点位于scan
h
的右端点处，结束扫描高度h中可行位置的计算，否则标记该位置对应的不规则钣金件b的参考点为一个可行位置，而后将不规则钣金件b的扫描线向x正方向平移α个单位，其中，α取值如公式(1)所示，平移后，再次检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉，直至不规则钣金件a的扫描线与不规则钣金件b的扫描线彼此相离，且该位置对应的不规则钣金件b的参考点位于scan
h
的右端点处时，结束所述扫描高度中可行位置的计算；若存在干涉，将不规则钣金件b的扫描线向x轴正方向平移β个单位，其中，β指为使不规则钣金件a的扫描线与不规则钣金件b的扫描线彼此相离时不规则钣金件b的扫描线需要向x正方向平移的最小距离，平移后，再次检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉，直至不规则钣金件a的扫描线与不规则钣金件b的扫描线彼此相离，且该位置对应的不规则钣金件b的参考点位于scan
h
的右端点处时，结束该扫描高度中可行位置的计算；遍历外围nfp每个扫描高度后，得到位于外围nfp内部的所有可行位置；公式(1)中，h
a
为不规则钣金件a的实扫描高度总数，h
b
为不规则钣金件b的实扫描高度总数，s
j
为不规则钣金件a的第j个实扫描高度中包含的扫描线总数，s
k
为不规则钣金件b的第k个实扫描高度中包含的扫描线总数，x
0ju
为不规则钣金件a的第j个实扫描高度中第u个扫描线左端点的x坐标，x
1kv
为不规则钣金件b的第k个实扫描高度中第v个扫描线右端点的x坐标，x
1ju
为不规则钣金件a的第j个实扫描高度中第u个扫描线右端点的x坐标，x
0kv
为不规则钣金件b的第k个实扫描高度中第v个扫描线左端点的x坐标，y
0j0
不规则钣金件a的第j个实扫描高度中第1个扫描线左端点的y坐标，y
0k0
为不规则钣金件b的第k个实扫描高度中第1个扫描线左端点的y坐标；所述不规则钣金件的实扫描高度是指至少存在一条扫描线的扫描高度。4.根据权利要求1所述的用于不规则钣金件排样干涉检测的扫描线nfp生成方法，其特征在于，所述步骤3中，判断可行位置是否为单点可行位置的具体过程如下：对于给定的可行位置，首先将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点与所述可行位置重合的位置；而后使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线向x轴正方向平移ε个单位；其中，ε是大于0远小于1的正数；平移后，检测不
规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉；若存在干涉，标记所述可行位置为右侧干涉，否则标记所述可行位置为右侧可行；而后将不规则钣金件b的扫描线平移至使不规则钣金件b的参考点与该可行位置重合的位置；使不规则钣金件b的扫描线所在高度不变，将不规则钣金件b的扫描线向x轴负方向平移ε个单位；其中，ε是大于0远小于1的正数；平移后，检测不规则钣金件a的扫描线与不规则钣金件b的扫描线是否存在干涉；若存在干涉，标记所述可行位置为左侧干涉，否则标记所述可行位置为左侧可行；若所述可行位置既是左侧干涉又是右侧干涉，则标记所述可行位置为单点可行位置。5.根据权利要求1所述的用于不规则钣金件排样干涉检测的扫描线nfp生成方法，其特征在于，所述步骤4中，去除某扫描高度中的可行区域的具体过程如下：对于外围nfp中某个存在可行区域的扫描高度h，首先将所述高度h中对应的外围nfp的扫描线的左端点存入容器c
h
；而后遍历所述高度h中对应的各可行区域，根据可行区域左端点x坐标由小到大排列，依次将各可行区域的左端点和右端点存入容器c
h
；而后将所述高度h中对应的外围nfp的扫描线的右端点存入容器c
h
；将容器c
h
中的所有元素依序不重复地两两组合，构成新元素组并按顺序存入容器c
h
；所述容器c
h
中每一个新元素组表示去除可行区域后的一个nfp扫描线片段。

技术总结
本发明公开一种用于不规则钣金件排样干涉检测的扫描线NFP生成方法，属于机械加工生产过程中不规则钣金件优化下料领域。本发明方法具体步骤包括：步骤1：输入不规则钣金件的扫描线信息；步骤2：生成外围NFP；步骤3：生成位于外围NFP内部的可行区域；步骤4：将位于外围NFP内部的可行区域从外围NFP中去除；步骤五：输出NFP结果。本发明采用扫描线表达不规则钣金件轮廓时，通过离线计算得到两个轮廓之间完整的干涉区域，能够高效地实现排样过程中的轮廓干涉检测，具有运算效率高的特点，能够用于快速有效地检测排样过程中的不规则钣金件干涉，并能在多场景下应用。能在多场景下应用。能在多场景下应用。


技术研发人员：郭保苏 马健明 程丽丹
受保护的技术使用者：燕山大学
技术研发日：2023.05.11
技术公布日：2023/8/9