CN112488429B - 一种基于扫描线法的二维不规则排样下料方法 - Google Patents
一种基于扫描线法的二维不规则排样下料方法 Download PDFInfo
- Publication number
- CN112488429B CN112488429B CN202011518760.3A CN202011518760A CN112488429B CN 112488429 B CN112488429 B CN 112488429B CN 202011518760 A CN202011518760 A CN 202011518760A CN 112488429 B CN112488429 B CN 112488429B
- Authority
- CN
- China
- Prior art keywords
- irregular
- scanning line
- reward
- penalty
- parts
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
- G06Q10/043—Optimisation of two dimensional placement, e.g. cutting of clothes or wood
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q50/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
- G06Q50/04—Manufacturing
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02P—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS
- Y02P90/00—Enabling technologies with a potential contribution to greenhouse gas [GHG] emissions mitigation
- Y02P90/30—Computing systems specially adapted for manufacturing
Landscapes
- Business, Economics & Management (AREA)
- Engineering & Computer Science (AREA)
- Human Resources & Organizations (AREA)
- Economics (AREA)
- Strategic Management (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Marketing (AREA)
- General Business, Economics & Management (AREA)
- Tourism & Hospitality (AREA)
- General Health & Medical Sciences (AREA)
- Primary Health Care (AREA)
- Health & Medical Sciences (AREA)
- Manufacturing & Machinery (AREA)
- Development Economics (AREA)
- Game Theory and Decision Science (AREA)
- Entrepreneurship & Innovation (AREA)
- Operations Research (AREA)
- Quality & Reliability (AREA)
- Image Analysis (AREA)
- Editing Of Facsimile Originals (AREA)
Abstract
本发明公开了一种基于扫描线法的二维不规则排样下料方法，包括以下步骤：步骤A：将目标面板容器和不规则零件进行扫描线化；步骤B：对每个所述不规则零件的零件扫描线随机排序，生成零件扫描线序列；步骤C：按照所述零件扫描线序列的顺序对所述不规则零件的零件扫描线进行重叠检测，所述不规则零件的零件扫描线按照所述零件扫描线序列遍历所述目标面板容器的每条面板扫描线上对应的位置。步骤D：对每个位置评价每个所述不规则零件的放置可行性；步骤E：选择可行性最高的所述不规则零件放置于对应的位置。所述基于扫描线法的二维不规则排样下料方法，解决了现有的不规则排样下料方法消耗时间长、内存占用大的问题。
Description
技术领域
本发明涉及工业排样下料技术领域，特别是一种基于扫描线法的二维不规则排样下料方法。
背景技术
二维不规则排样下料问题在工业制造中随处可见，如布料加工、钢板加工、皮革加工、板材加工、钣金加工等行业。在制造业中，原料费用一直是必须面对的难题之一，排样下料问题则应运而生，为提高原料利用率，缩小原料费用提供渠道。
由于在实际生产中，面对的零件经常是不规则的形状，则由排样下料问题衍生出二维不规则排样下料问题。采取哪种几何工具表述零件、零件的放置顺序、零件放置采用的策略以及可用布局的搜索策略，都很大程度地影响了排样结果和排样速率。
目前求解不规则排样下料问题的几何工具有临界多边形、像素点法等。临界零件的方法缺点在于，在初始化临界零件，及后续进行重叠检测时耗时非常长；像素点法的缺点在于，虽然初始化和重叠检测耗时没有临界零件漫长，但内存消耗明显，且精度较低，在同时对两个维度进行像素点填充下，若要保证精度，则填充密度必须高，但同时性能变得越低，内存占用越大。
发明内容
针对上述缺陷，本发明的目的在于提出一种基于扫描线法的二维不规则排样下料方法，解决了现有的不规则排样下料方法消耗时间长、内存占用大的问题。
为达此目的，本发明采用以下技术方案：一种基于扫描线法的二维不规则排样下料方法，包括以下步骤：
步骤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，直到所有所述不规则零件都放置完毕为止。
经过上述步骤，最终将所有所述不规则零件放置于所述目标面板容器。
在本说明书的描述中，参考术语“一个实施方式”、“一些实施方式”、“示意性实施方式”、“示例”、“具体示例”或“一些示例”等的描述意指结合所述实施方式或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施方式或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施方式或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施方式或示例中以合适的方式结合。
流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本发明的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本发明的实施例所属技术领域的技术人员所理解。
尽管上面已经示出和描述了本发明的实施方式，可以理解的是，上述实施方式是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施实施进行变化、修改、替换和变型。
Claims (6)
1.一种基于扫描线法的二维不规则排样下料方法，其特征在于：包括以下步骤：
步骤A：将目标面板容器和不规则零件进行扫描线化得到面板扫描线和零件扫描线；
所述步骤A具体为：
步骤A1：选取一个精度k；
步骤A2：根据所述目标面板容器在垂直方向的尺寸，将所述目标面板容器填充进精度k下的多条所述面板扫描线；
所述步骤A2中，在对所述目标面板容器进行扫描线化时设置步长，所述步长为所述目标面板容器的宽度乘以精度k后的千分之一；
步骤A3：根据不规则零件在垂直方向的尺寸，将不规则零件填充进精度k下的多层零件扫描线层，每层零件扫描线层包含一条或一条以上零件扫描线；
步骤A4：根据不规则零件在垂直方向的每条零件扫描线的y值，得到每条对应的零件扫描线的x值，其中y值通过不规则零件的包络矩形的y方向的尺寸得到，x值通过所述不规则零件的每条y方向的零件扫描线的两端的端点得到；
步骤A5：根据每层所述零件扫描线层的零件扫描线的x值进行排列，并储存到零件扫描线表中；
步骤B：对每个所述不规则零件的零件扫描线随机排序，生成零件扫描线序列；
步骤C：按照所述零件扫描线序列的顺序对所述不规则零件的零件扫描线进行重叠检测，所述不规则零件的零件扫描线按照所述零件扫描线序列遍历所述目标面板容器的每条面板扫描线上对应的位置；
所述步骤C具体为：按照左下原则，依次将所述不规则零件移动至所述目标面板容器的每条面板扫描线上对应的位置，通过所述步长动态调整搜索到每条面板扫描线可放置的最小x值；
所述步骤C中，所述步长动态调整为：在对所述目标面板容器的位置进行重叠检测时，当已放置的不规则零件的零件扫描线与当前放置的不规则零件的零件扫描线发生重叠时，已放置的不规则零件的零件扫描线与当前放置的不规则零件的零件扫描线形成重叠差值，将所述重叠差值与当前放置的不规则零件放置于该位置时的最大差值作比较，当所述重叠差值大于所述最大差值时，将更新所述重叠差值作为步长；
步骤D：对每个位置评价每个所述不规则零件的放置可行性；
步骤E：选择可行性最高的所述不规则零件放置于对应的位置。
2.根据权利要求1所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于，所述步骤D具体为：对每个位置评价每个所述不规则零件的放置可行性的评价函数包括多个惩罚函数和奖励函数，通过计算所有所述惩罚函数和奖励函数的分数，然后将所述分数相加得出每个位置中各个所述不规则零件的得分。
3.根据权利要求2所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于：所述步骤D中，所述惩罚函数包括：第一惩罚函数和第二惩罚函数；
所述第一惩罚函数为：所述不规则零件的零件扫描线与目标面板容器的边界的距离值和还未放置的不规则零件的包络矩形的边长最小值的比值乘以第一惩罚比重，其中所述第一惩罚比重为-10；
所述第二惩罚函数为：所述不规则零件的零件扫描线的最小x值与所述不规则零件目前布局的横向长度的比值乘以第二惩罚比重，其中所述第二惩罚比重为-30。
4.根据权利要求3所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于：所述步骤D中，所述奖励函数包括：第一奖励函数、第二奖励函数、第三奖励函数和第四奖励函数；
所述第一奖励函数为：所述不规则零件的面积与面积最小的不规则零件的面积的比值乘以第一奖励比重，其中第一奖励比重为10；
所述第二奖励函数为：所述不规则零件的面积与所述不规则零件的包络矩形面积的比值乘以第二奖励比重，其中第二奖励比重为50；
所述第三奖励函数为：所述目标面板容器放置所述不规则零件前后的包络矩形的形心的比值乘以第三奖励比重，其中第三奖励比重为30；
所述第四奖励函数为：所述目标面板容器放置所述不规则零件前后的布局的利用率乘以第四奖励比重，其中第四奖励比重为4。
5.根据权利要求4所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于：所述步骤D中，所述惩罚函数还包括第三惩罚函数，在进行步骤C的所述不规则零件的零件扫描线的重叠检测时，通过计算所述第三惩罚函数而得到对应的分数；
所述第三惩罚函数为：所述不规则零件的零件扫描线与其左边最靠近的所述目标面板容器的面板扫描线的距离值与所述不规则零件目前布局的横向长度的比值乘以第三惩罚比重，其中第三惩罚比重为-40。
6.根据权利要求5所述的一种基于扫描线法的二维不规则排样下料方法，其特征在于，所述步骤E具体为：
步骤E1：选择所述步骤D中得分最高的所述不规则零件和对应的位置进行放置；
步骤E2：将所述不规则零件放置于所述目标面板容器对应的位置；
步骤E3：重复步骤E1和步骤E2，直到所有所述不规则零件都放置完毕为止。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011518760.3A CN112488429B (zh) | 2020-12-21 | 2020-12-21 | 一种基于扫描线法的二维不规则排样下料方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202011518760.3A CN112488429B (zh) | 2020-12-21 | 2020-12-21 | 一种基于扫描线法的二维不规则排样下料方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN112488429A CN112488429A (zh) | 2021-03-12 |
| CN112488429B true CN112488429B (zh) | 2021-07-23 |
Family
ID=74915227
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202011518760.3A Active CN112488429B (zh) | 2020-12-21 | 2020-12-21 | 一种基于扫描线法的二维不规则排样下料方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN112488429B (zh) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115048691B (zh) * | 2022-05-11 | 2024-08-09 | 浙江大学高端装备研究院 | 一种基于扫描线的室内设计自动辅助布局系统及布局方法 |
| CN116663483B (zh) * | 2023-07-31 | 2023-10-20 | 全芯智造技术有限公司 | 用于芯片排版的方法、设备和介质 |
| CN117556955A (zh) * | 2023-11-24 | 2024-02-13 | 南京工业大学 | 一种基于变异驱动遗传算法的不规则零件二维排布方法 |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101533418A (zh) * | 2008-03-14 | 2009-09-16 | 上海卡休智能科技有限公司 | 玩具版片下料方法 |
| CN106426188A (zh) * | 2016-12-24 | 2017-02-22 | 宁波亿诺维信息技术有限公司 | 一种程控工业机器人 |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR3061669B1 (fr) * | 2017-01-09 | 2019-05-31 | Lectra | Procede de modification de la trajectoire de coupe de pieces destinees a etre decoupees dans un materiau souple |
| CN109063917A (zh) * | 2018-08-14 | 2018-12-21 | 苏州瑞思智造信息科技有限公司 | 基于遗传优化算法的分阶布料排样方法 |
-
2020
- 2020-12-21 CN CN202011518760.3A patent/CN112488429B/zh active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101533418A (zh) * | 2008-03-14 | 2009-09-16 | 上海卡休智能科技有限公司 | 玩具版片下料方法 |
| CN106426188A (zh) * | 2016-12-24 | 2017-02-22 | 宁波亿诺维信息技术有限公司 | 一种程控工业机器人 |
Also Published As
| Publication number | Publication date |
|---|---|
| CN112488429A (zh) | 2021-03-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN112488429B (zh) | 一种基于扫描线法的二维不规则排样下料方法 | |
| CN105590339B (zh) | 三维模型的碰撞检测方法及系统 | |
| CN101930594A (zh) | 一种扫描文档图像的快速纠偏方法 | |
| CN113942230B (zh) | 针对双激光分割的3d打印控制系统及其分割方法 | |
| CN1010512B (zh) | 字符的识别方法 | |
| CN116758084B (zh) | 基于图像数据的钣金件焊接缺陷智能检测方法 | |
| CN106296773B (zh) | 一种生成多层次矢量图的方法与装置 | |
| CN103823649A (zh) | 一种基于切片文件的三维打印均匀壁厚抽壳方法 | |
| CN105957113B (zh) | 基于曼哈顿网络的任意连通域的水平内接矩形算法及装置 | |
| CN111222235B (zh) | 一种随机生成多结构层沥青路面离散元模型的方法 | |
| CN110046462B (zh) | 一种集装箱型材自动排样方法 | |
| CN1088869C (zh) | 一种信息处理装置和一种信息处理方法 | |
| CN110298838A (zh) | 一种确定样本图像的方法、装置、设备和存储介质 | |
| CN109359381B (zh) | 一种基于体素的激光路径规划方法 | |
| CN1497695A (zh) | 图形计测方法、使用其的半导体器件制造方法和图形计测装置 | |
| CN108021900B (zh) | 版面分栏方法及装置 | |
| CN110807113B (zh) | 可视化布局中的矩形图元重叠的非迭代消除方法 | |
| CN114742851B (zh) | 基于轮廓特征的多激光粉末床融合负载均衡方法和装置 | |
| CN101620737B (zh) | 一种基于纹理块间隔分布的纹理合成方法 | |
| CN114663416A (zh) | 基于计算机视觉的铜排冷隔缺陷检测方法及系统 | |
| CN109685792B (zh) | 一种基于图像差分空间频率特性的瓦楞纸智能识别算法 | |
| TWI407365B (zh) | 資料分群方法 | |
| CN113487666B (zh) | 一种多边形链的求交方法及装置 | |
| CN113052460B (zh) | 一种板材垛位确定方法及装置 | |
| CN118504927B (zh) | 基于多边形相交检测的滚装船配载方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |