本发明涉及工业排样下料技术领域，特别是一种基于扫描线法的二维不规则排样下料方法。
背景技术：
二维不规则排样下料问题在工业制造中随处可见，如布料加工、钢板加工、皮革加工、板材加工、钣金加工等行业。在制造业中，原料费用一直是必须面对的难题之一，排样下料问题则应运而生，为提高原料利用率，缩小原料费用提供渠道。
由于在实际生产中，面对的零件经常是不规则的形状，则由排样下料问题衍生出二维不规则排样下料问题。采取哪种几何工具表述零件、零件的放置顺序、零件放置采用的策略以及可用布局的搜索策略，都很大程度地影响了排样结果和排样速率。
目前求解不规则排样下料问题的几何工具有临界多边形、像素点法等。临界零件的方法缺点在于，在初始化临界零件，及后续进行重叠检测时耗时非常长；像素点法的缺点在于，虽然初始化和重叠检测耗时没有临界零件漫长，但内存消耗明显，且精度较低，在同时对两个维度进行像素点填充下，若要保证精度，则填充密度必须高，但同时性能变得越低，内存占用越大。
技术实现要素：
针对上述缺陷，本发明的目的在于提出一种基于扫描线法的二维不规则排样下料方法，解决了现有的不规则排样下料方法消耗时间长、内存占用大的问题。
为达此目的，本发明采用以下技术方案：一种基于扫描线法的二维不规则排样下料方法，包括以下步骤：
步骤a：将目标面板容器和不规则零件进行扫描线化得到面板扫描线和零件扫描线；
步骤b：对每个所述不规则零件的零件扫描线随机排序，生成零件扫描线序列；
步骤c：按照所述零件扫描线序列的顺序对所述不规则零件的零件扫描线进行重叠检测，所述不规则零件的零件扫描线按照所述零件扫描线序列遍历所述目标面板容器的每条面板扫描线上对应的位置；
步骤d：对每个位置评价每个所述不规则零件的放置可行性；
步骤e：选择可行性最高的所述不规则零件放置于对应的位置。
例如，所述步骤a具体为：
步骤a1：选取一个精度k；
步骤a2：根据所述目标面板容器在垂直方向的尺寸，将所述目标面板容器填充进精度k下的多条所述面板扫描线；
步骤a3：根据不规则零件在垂直方向的尺寸，将不规则零件填充进精度k下的多层零件扫描线层，每层零件扫描线层包含一条或一条以上零件扫描线；
步骤a4：根据不规则零件在垂直方向的每条零件扫描线的y值，得到每条对应的零件扫描线的x值，其中y值通过不规则零件的包络矩形的y方向的尺寸得到，x值通过所述不规则零件的每条y方向的零件扫描线的两端的端点得到；
步骤a5：根据每层所述零件扫描线层的零件扫描线的x值进行排列，并储存到零件扫描线表中。
值得说明的是，所述步骤a2中，在对所述目标面板容器进行扫描线化时设置步长，所述步长为所述目标面板容器的宽度乘以精度k后的千分之一。
可选地，所述步骤c具体为：按照左下原则，依次将所述不规则零件移动至所述目标面板容器的每条面板扫描线上对应的位置，通过所述步长动态调整搜索到每条面板扫描线可放置的最小x值。
具体地，所述步骤c中，所述步长动态调整为：在对所述目标面板容器的位置进行重叠检测时，当已放置的不规则零件的零件扫描线与当前放置的不规则零件的零件扫描线发生重叠时，已放置的不规则零件的零件扫描线与当前放置的不规则零件的零件扫描线形成重叠差值，将所述重叠差值与当前放置的不规则零件放置于该位置时的最大差值作比较，当所述重叠差值大于所述最大差值时，将更新所述重叠差值作为步长。
优选的，所述步骤d具体为：对每个位置评价每个所述不规则零件的放置可行性的评价函数包括多个惩罚函数和奖励函数，通过计算所有所述惩罚函数和奖励函数的分数，然后将所述分数相加得出每个位置中各个所述不规则零件的得分。
例如，所述步骤d中，所述惩罚函数包括：第一惩罚函数和第二惩罚函数；
所述第一惩罚函数为：所述不规则零件的零件扫描线与目标面板容器的边界的距离值和还未放置的不规则零件的包络矩形的边长最小值的比值乘以第一惩罚比重；
所述第二惩罚函数为：所述不规则零件的零件扫描线的最小x值与所述不规则零件目前布局的横向长度的比值乘以第二惩罚比重。
值得说明的是，所述步骤d中，所述奖励函数包括：第一奖励函数、第二奖励函数、第三奖励函数和第四奖励函数；
所述第一奖励函数为：所述不规则零件的面积与面积最小的不规则零件的面积的比值乘以第一奖励比重；
所述第二奖励函数为：所述不规则零件的面积与所述不规则零件的包络矩形面积的比值乘以第二奖励比重；
所述第三奖励函数为：所述目标面板容器放置所述不规则零件前后的包络矩形的形心的比值乘以第三奖励比重；
所述第四奖励函数为：所述目标面板容器放置所述不规则零件前后的布局的利用率乘以第四奖励比重。
可选地，所述步骤d中，所述惩罚函数还包括第三惩罚函数，在进行步骤c的所述不规则零件的零件扫描线的重叠检测时，通过计算所述第三惩罚函数而得到对应的分数；
所述第三惩罚函数为：所述不规则零件的零件扫描线与其左边最靠近的所述目标面板容器的面板扫描线的距离值与所述不规则零件目前布局的横向长度的比值乘以第三惩罚比重，其中第三惩罚比重为-40。
具体地，所述步骤e具体为：
步骤e1：选择所述步骤d中得分最高的所述不规则零件和对应的位置进行放置；
步骤e2：将所述不规则零件放置于所述目标面板容器对应的位置；
步骤e3：重复步骤e1和步骤e2，直到所有所述不规则零件都放置完毕为止。
本发明的有益效果：所述基于扫描线法的二维不规则排样下料方法采用扫描线法表述不规则零件，即采用线段的方式填充不规则零件，该方法只在一个维度进行填充，保证了另外一个维度的精度；同时由于仅需要储存一个维度的数据，相较于临界零件的方法，在初始化不规则零件时节省了时间，相较于像素点法，从量级上大幅度地降低了内存占用；在进行重叠检测的同时，不仅检测的数量仅需要一个维度的数量级，同时检测所需要的计算也并不复杂。所述重叠检测是将不规则零件的零件扫描线对应于希望放置在目标面板容器上的位置的面板扫描线，通过判断每条零件扫描线和储存于面板扫描线上的零件扫描线是否会发生重叠进行检测。相邻几条零件扫描线和储存于面板扫描线上的零件扫描线在大多数情况下是相同的，若按照顺序遍历则相当耗费时间，则采用随机生成的零件扫描线的序列选取扫描线进行检测，相较于临界多边形的方法，采用上述方法能节省时间。
附图说明
图1是本发明的一个实施例的结构示意图。
具体实施方式
下面详细描述本发明的实施方式，实施方式的示例在附图中示出，其中，相同或类似的标号自始至终表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。
在本发明的实施方式的描述中，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个所述特征。在本发明的实施方式的描述中，“多个”的含义是两个或两个以上，除非另有明确具体的限定。
下文的公开提供了许多不同的实施方式或例子用来实现本发明的实施方式的不同结构。为了简化本发明的实施方式的公开，下文中对特定例子的部件和设置进行描述。当然，它们仅仅为示例，并且目的不在于限制本发明。此外，本发明的实施方式可以在不同例子中重复参考数字和/或参考字母，这种重复是为了简化和清楚的目的，其本身不指示所讨论各种实施方式和/或设置之间的关系。此外，本发明的实施方式提供了的各种特定的工艺和材料的例子，但是本领域普通技术人员可以意识到其他工艺的应用和/或其他材料的使用。
如图1所示，一种基于扫描线法的二维不规则排样下料方法，包括以下步骤：
步骤a：将目标面板容器和不规则零件进行扫描线化得到面板扫描线和零件扫描线；
步骤b：对每个所述不规则零件的零件扫描线随机排序，生成零件扫描线序列；
步骤c：按照所述零件扫描线序列的顺序对所述不规则零件的零件扫描线进行重叠检测，所述不规则零件的零件扫描线按照所述零件扫描线序列遍历所述目标面板容器的每条面板扫描线上对应的位置；
步骤d：对每个位置评价每个所述不规则零件的放置可行性；
步骤e：选择可行性最高的所述不规则零件放置于对应的位置。
所述基于扫描线法的二维不规则排样下料方法采用扫描线法表述不规则零件，即采用线段的方式填充不规则零件，该方法只在一个维度进行填充，保证了另外一个维度的精度；同时由于仅需要储存一个维度的数据，相较于临界零件的方法，在初始化不规则零件时节省了时间，相较于像素点法，从量级上大幅度地降低了内存占用；在进行重叠检测的同时，不仅检测的数量仅需要一个维度的数量级，同时检测所需要的计算也并不复杂。所述重叠检测是将不规则零件的零件扫描线对应于希望放置在目标面板容器上的位置的面板扫描线，通过判断每条零件扫描线和储存于面板扫描线上的零件扫描线是否会发生重叠进行检测。相邻几条零件扫描线和储存于面板扫描线上的零件扫描线在大多数情况下是相同的，若按照顺序遍历则相当耗费时间，则采用随机生成的零件扫描线的序列选取扫描线进行检测，相较于临界多边形的方法，采用上述方法能节省时间。
一些实施例中，所述步骤a具体为：
步骤a1：选取一个精度k；
步骤a2：根据所述目标面板容器在垂直方向的尺寸，将所述目标面板容器填充进精度k下的多条所述面板扫描线；
步骤a3：根据不规则零件在垂直方向的尺寸，将不规则零件填充进精度k下的多层零件扫描线层，每层零件扫描线层包含一条或一条以上零件扫描线；
步骤a4：根据不规则零件在垂直方向的每条零件扫描线的y值，得到每条对应的零件扫描线的x值，其中y值通过不规则零件的包络矩形的y方向的尺寸得到，x值通过所述不规则零件的每条y方向的零件扫描线的两端的端点得到；
步骤a5：根据每层所述零件扫描线层的零件扫描线的x值进行排列，并储存到零件扫描线表中。
所述精度k相当于将给定尺寸扩充k倍，将垂直方向的每1mm填充k条面板扫描线或零件扫描线。所述不规则零件在垂直方向的尺寸在原有数据中给定。
例如，所述步骤a2中，在对所述目标面板容器进行扫描线化时设置步长，所述步长为所述目标面板容器的宽度乘以精度k后的千分之一。
目标面板容器在扫描线化时形成多层面板扫描线层，每层扫描线层包含多条面板扫描线，面板扫描线层的层数等于所述精度k下的面板扫描线的数量除以步长。所述步长指的是每层扫描线的数量。分层后，对每层的面板扫描线同步进行扫描，分层能减少检索所述目标面板容器的面板扫描线的时间。当所述目标面板容器的尺寸过大时，所述不规则零件的零件扫描线放置时得到的评判分数通常是相近的，但所述目标面板容器的尺寸较小时设置步长会忽略掉很多解，因此所述步长为所述目标面板容器的宽度乘以精度k后的千分之一能针对面板容器尺寸较大的情况的同时在针对较小尺寸的所述目标面板容器也不会忽略掉太多的解。
值得说明的是，所述步骤c具体为：按照左下原则，依次将所述不规则零件移动至所述目标面板容器的每条面板扫描线上对应的位置，通过所述步长动态调整搜索到每条面板扫描线可放置的最小x值。
上述步骤通过判断线段与线段之间是否发生重叠进行判断不规则零件是否发生重叠，并根据左下原则，按照步长动态调整的搜索步长选取坐标，通过评判零件的放置可行性，从而能选择合适的不规则零件进行放置。
可选地，所述步骤c中，所述步长动态调整为：在对所述目标面板容器的位置进行重叠检测时，当已放置的不规则零件的零件扫描线与当前放置的不规则零件的零件扫描线发生重叠时，已放置的不规则零件的零件扫描线与当前放置的不规则零件的零件扫描线形成重叠差值，将所述重叠差值与当前放置的不规则零件放置于该位置时的最大差值作比较，当所述重叠差值大于所述最大差值时，将更新所述重叠差值作为步长。
本发明采用了动态调整的搜索步长搜索可行的布局，相较于固定的搜索步长，不仅有利于增加排样速率，同时有利于搜索到更加紧凑的布局。当所述步长不为整数时则向上取整，避免了在遍历所述目标面板容器时无法将不规则零件的零件扫描线与所述目标面板容器上的面板扫描线进行一一对应进行重叠检测。由于所述目标面板容器上的面板扫描线储存有已放置后的不规则零件在相对应位置上的零件扫描线，在进行重叠检测时，若发生重叠，可在两条零件扫描线之间形成一个重叠差值，并与目前该不规则零件放置于该位置时的最大差值作比较，若大于该差值，则更新此差值作为步长，进行步长动态调整。
具体地，所述步骤d具体为：对每个位置评价每个所述不规则零件的放置可行性的评价函数包括多个惩罚函数和奖励函数，通过计算所有所述惩罚函数和奖励函数的分数，然后将所述分数相加得出每个位置中各个所述不规则零件的得分。
本方法采用了评价函数，用于评判每个零件的放置可行性，相较于传统左下原则按照一定的排列顺序进行放置，更能考虑到零件放置后对最后布局的影响，通过每次放置时的实时调整，避免了考虑单一因素的排列顺序对最后结果的影响。所述惩罚函数的分数为负值，所述奖励函数的分数为正值，每次进行评价时均全部走一遍，通过评价函数内的所有内容的正值分值和负值分值分别乘以对应的比值后再相加，最终得到得分。
优选的，所述步骤d中，所述惩罚函数包括：第一惩罚函数和第二惩罚函数；
所述第一惩罚函数为：所述不规则零件的零件扫描线与目标面板容器的边界的距离值和还未放置的不规则零件的包络矩形的边长最小值的比值乘以第一惩罚比重，其中所述第一惩罚比重为-10；
所述第二惩罚函数为：所述不规则零件的零件扫描线的最小x值与所述不规则零件目前布局的横向长度的比值乘以第二惩罚比重，其中所述第二惩罚比重为-30。
所述第一惩罚函数的原理为：不规则零件在放置后会对目标面板容器边界产生一个距离值，所述距离值若比还未放置的不规则零件的包络矩形的垂直或者水平方向的长度更短，则会造成一定的浪费，对于这个现象，需要进行一定的惩罚。
所述第二惩罚函数的原理为：在选择所述不规则零件的每条零件扫描线不发生重叠的最小x值进行放置的时候，在不同零件扫描线的最小x值的比较下，所述最小x值越小，则代表布局可以更为紧凑。
一些实施例中，所述步骤d中，所述奖励函数包括：第一奖励函数、第二奖励函数、第三奖励函数和第四奖励函数；
所述第一奖励函数为：所述不规则零件的面积与面积最小的不规则零件的面积的比值乘以第一奖励比重，其中第一奖励比重为10；
所述第二奖励函数为：所述不规则零件的面积与所述不规则零件的包络矩形面积的比值乘以第二奖励比重，其中第二奖励比重为50；
所述第三奖励函数为：所述目标面板容器放置所述不规则零件前后的包络矩形的形心的比值乘以第三奖励比重，其中第三奖励比重为30；
所述第四奖励函数为：所述目标面板容器放置所述不规则零件前后的布局的利用率乘以第四奖励比重，其中第四奖励比重为4。
所述第一奖励函数的原理为：不规则零件的几何形状决定了，将面积越大的不规则零件率先放置更有利于整体布局的利用率，因此对于面积越大的不规则零件进行奖励。
所述第二奖励函数的原理为：不规则零件的几何不规则性质决定了，不规则零件的面积和不规则零件的包络矩形面积的比值越小，则率先放置，更有利于整体布局的利用率。
所述第三奖励函数的原理为：在每放置一个不规则零件前后，分别会对所述目标面板容器的整个布局产生一个包络矩形，针对放置前后的包络矩形的形心，当形心差距越小时，代表布局更加紧凑。
所述第四奖励函数的原理为：放置前后产生的利用率，对最后整体布局的利用率也有一定的参考意义。
例如，所述步骤d中，所述惩罚函数还包括第三惩罚函数，在进行步骤c的所述不规则零件的零件扫描线的重叠检测时，通过计算所述第三惩罚函数而得到对应的分数；
所述第三惩罚函数为：所述不规则零件的零件扫描线与其左边最靠近的所述目标面板容器的面板扫描线的距离值与所述不规则零件目前布局的横向长度的比值乘以第三惩罚比重，其中第三惩罚比重为-40。
所述第三惩罚函数的原理为：在进行不规则零件的每条零件扫描线检测是否重叠时，如果在不重叠的情况下，与该不规则零件左边最靠近所述目标面板容器的面板扫描线的距离值越小，则代表着该零件的放置更为紧凑。
值得说明的是，所述步骤e具体为：
步骤e1：选择所述步骤d中得分最高的所述不规则零件和对应的位置进行放置；
步骤e2：将所述不规则零件放置于所述目标面板容器对应的位置；
步骤e3：重复步骤e1和步骤e2，直到所有所述不规则零件都放置完毕为止。
经过上述步骤，最终将所有所述不规则零件放置于所述目标面板容器。
在本说明书的描述中，参考术语“一个实施方式”、“一些实施方式”、“示意性实施方式”、“示例”、“具体示例”或“一些示例”等的描述意指结合所述实施方式或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施方式或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施方式或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施方式或示例中以合适的方式结合。
流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本发明的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本发明的实施例所属技术领域的技术人员所理解。
尽管上面已经示出和描述了本发明的实施方式，可以理解的是，上述实施方式是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施实施进行变化、修改、替换和变型。
1.一种基于扫描线法的二维不规则排样下料方法，其特征在于：包括以下步骤：
步骤a：将目标面板容器和不规则零件进行扫描线化得到面板扫描线和零件扫描线；
步骤b：对每个所述不规则零件的零件扫描线随机排序，生成零件扫描线序列；
步骤c：按照所述零件扫描线序列的顺序对所述不规则零件的零件扫描线进行重叠检测，所述不规则零件的零件扫描线按照所述零件扫描线序列遍历所述目标面板容器的每条面板扫描线上对应的位置；
步骤d：对每个位置评价每个所述不规则零件的放置可行性；
步骤e：选择可行性最高的所述不规则零件放置于对应的位置。
2.根据权利要求1所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于，所述步骤a具体为：
步骤a1：选取一个精度k；
步骤a2：根据所述目标面板容器在垂直方向的尺寸，将所述目标面板容器填充进精度k下的多条所述面板扫描线；
步骤a3：根据不规则零件在垂直方向的尺寸，将不规则零件填充进精度k下的多层零件扫描线层，每层零件扫描线层包含一条或一条以上零件扫描线；
步骤a4：根据不规则零件在垂直方向的每条零件扫描线的y值，得到每条对应的零件扫描线的x值，其中y值通过不规则零件的包络矩形的y方向的尺寸得到，x值通过所述不规则零件的每条y方向的零件扫描线的两端的端点得到；
步骤a5：根据每层所述零件扫描线层的零件扫描线的x值进行排列，并储存到零件扫描线表中。
3.根据权利要求2所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于：所述步骤a2中，在对所述目标面板容器进行扫描线化时设置步长，所述步长为所述目标面板容器的宽度乘以精度k后的千分之一。
4.根据权利要求3所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于，所述步骤c具体为：按照左下原则，依次将所述不规则零件移动至所述目标面板容器的每条面板扫描线上对应的位置，通过所述步长动态调整搜索到每条面板扫描线可放置的最小x值。
5.根据权利要求4所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于：所述步骤c中，所述步长动态调整为：在对所述目标面板容器的位置进行重叠检测时，当已放置的不规则零件的零件扫描线与当前放置的不规则零件的零件扫描线发生重叠时，已放置的不规则零件的零件扫描线与当前放置的不规则零件的零件扫描线形成重叠差值，将所述重叠差值与当前放置的不规则零件放置于该位置时的最大差值作比较，当所述重叠差值大于所述最大差值时，将更新所述重叠差值作为步长。
6.根据权利要求5所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于，所述步骤d具体为：对每个位置评价每个所述不规则零件的放置可行性的评价函数包括多个惩罚函数和奖励函数，通过计算所有所述惩罚函数和奖励函数的分数，然后将所述分数相加得出每个位置中各个所述不规则零件的得分。
7.根据权利要求6所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于：所述步骤d中，所述惩罚函数包括：第一惩罚函数和第二惩罚函数；
所述第一惩罚函数为：所述不规则零件的零件扫描线与目标面板容器的边界的距离值和还未放置的不规则零件的包络矩形的边长最小值的比值乘以第一惩罚比重，其中所述第一惩罚比重为-10；
所述第二惩罚函数为：所述不规则零件的零件扫描线的最小x值与所述不规则零件目前布局的横向长度的比值乘以第二惩罚比重，其中所述第二惩罚比重为-30。
8.根据权利要求7所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于：所述步骤d中，所述奖励函数包括：第一奖励函数、第二奖励函数、第三奖励函数和第四奖励函数；
所述第一奖励函数为：所述不规则零件的面积与面积最小的不规则零件的面积的比值乘以第一奖励比重，其中第一奖励比重为10；
所述第二奖励函数为：所述不规则零件的面积与所述不规则零件的包络矩形面积的比值乘以第二奖励比重，其中第二奖励比重为50；
所述第三奖励函数为：所述目标面板容器放置所述不规则零件前后的包络矩形的形心的比值乘以第三奖励比重，其中第三奖励比重为30；
所述第四奖励函数为：所述目标面板容器放置所述不规则零件前后的布局的利用率乘以第四奖励比重，其中第四奖励比重为4。
9.根据权利要求8所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于：所述步骤d中，所述惩罚函数还包括第三惩罚函数，在进行步骤c的所述不规则零件的零件扫描线的重叠检测时，通过计算所述第三惩罚函数而得到对应的分数；
所述第三惩罚函数为：所述不规则零件的零件扫描线与其左边最靠近的所述目标面板容器的面板扫描线的距离值与所述不规则零件目前布局的横向长度的比值乘以第三惩罚比重，其中第三惩罚比重为-40。
10.根据权利要求9所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于，所述步骤e具体为：
步骤e1：选择所述步骤d中得分最高的所述不规则零件和对应的位置进行放置；
步骤e2：将所述不规则零件放置于所述目标面板容器对应的位置；
步骤e3：重复步骤e1和步骤e2，直到所有所述不规则零件都放置完毕为止。
技术总结