[發(fā)明專利]基于二元組塊樹的矩形優(yōu)化排樣方法及裝置

在審

• 申請?zhí)枺?/td>: 202010796212.0
• 申請日: 2020-08-10
• 公開（公告）號: CN111932011A
• 公開（公告）日: 2020-11-13
• 發(fā)明（設(shè)計）人: 陸宇升;廖淑珍;黃晴
• 申請（專利權(quán)）人: 南寧市永恒影像有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 北京細(xì)軟智谷知識產(chǎn)權(quán)代理有限責(zé)任公司 11471
• 代理人: 岳鳳羽

1.一種基于二元組塊樹的矩形件優(yōu)化排樣方法，其特征在于，包括：

基于預(yù)設(shè)映射關(guān)系，將目標(biāo)板材坐標(biāo)映射為預(yù)設(shè)分辨率位圖坐標(biāo)；

根據(jù)矩形件集合和預(yù)設(shè)組合規(guī)則，在所述預(yù)設(shè)分辨率位圖坐標(biāo)上構(gòu)造二元組塊樹；

基于所述目標(biāo)板材坐標(biāo)，獲取所述二元組塊樹的根節(jié)點的實例，確定所述矩形件集合的排樣結(jié)果。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，還包括：

基于預(yù)設(shè)處理方法，對殘留矩形件進(jìn)行處理。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)矩形件集合和預(yù)設(shè)組合規(guī)則，在所述預(yù)設(shè)分辨率位圖坐標(biāo)上構(gòu)造二元組塊樹，包括：

確定矩形節(jié)點R_i＝(w_i,h_i,PS_i,GS_i)，其中w_i為矩形件寬度，h_i為矩形件高度；PS_i為矩形件集合的子集，包含所有寬度高度為(w_i,h_i)的所有矩形件；GS_i為二元組塊的子集，包含所有寬度高度等于(w_i,h_i)的所有二元組塊集合；

利用xreduce函數(shù)或yreduce函數(shù)計算每個矩形件Pi在所述預(yù)設(shè)分辨率位圖坐標(biāo)上的寬度w’和高度h’；

對于矩形件集合P中的矩形件P_i，遍歷矩形節(jié)點集合R中是否存在矩形節(jié)點R_i，滿足R_i的寬度和高度分別等于P_i的寬度w’和高度h’，若不存在，則創(chuàng)建寬度和高度分別等于P_i的寬度w’和高度h’的矩形節(jié)點R_i，并將R_i加入集合R；將P_i加入R_i的PS_i子集；遍歷矩形節(jié)點集合R中是否存在矩形節(jié)點R_i，滿足R_i的寬度和高度分別等于P_i的高度h’和寬度w’，如果不存在，則創(chuàng)建寬度和高度分別等于P_i的高度h’和寬度w’的矩形節(jié)點R_i，并將R_i加入集合R；將P_i加入R_i的PS_i子集；

計算矩形節(jié)點集合R與自身的笛卡爾積，獲取二元組塊集合GCR＝R*R*{0,1}；

計算所述二元組塊集合GCR的子集GC，遍歷每個GCR中的二元組塊GCR_i，如果滿足預(yù)設(shè)條件，且GCR_i的寬度和高度均分別小于w’_max和h’_max，則將GCR_i加入子集GC；

對每個GC中的二元組塊GC_j，查找矩形節(jié)點集合R中是否存在矩形節(jié)點R_i，滿足R_i的寬度和高度分別等于GC_i的寬度和高度，如果不存在，則創(chuàng)建寬度和高度分別等于GC_i的寬度和高度的矩形節(jié)點R_i，加入集合R；把GC_j加入R_i的GS_i子集；查找矩形節(jié)點集合R中是否存在一個矩形節(jié)點R_i，滿足R_i寬度和高度分別等于GC_i的寬度和高度，如果不存在，則創(chuàng)建寬度和高度分別等于GC_i的寬度和高度的矩形節(jié)點R_i，加入集合R；把GC_j加入R_i的GS_i子集；

計算R集合的二元組塊森林根節(jié)點子集RR，如果矩形節(jié)點R_i高度h’_i等于h’_max或者h(yuǎn)’_max-h’_i小于某個閾值，不存在于任何其他矩形節(jié)點R_j的GS_j子集中，則把R_i加入RR子集；

在R集合中添加虛根節(jié)點R_vr＝(w’_max,h’_max,{},RR)，虛根節(jié)點的矩形件子集為空集，寬和高設(shè)置為極限值；GS子集為RR集合；獲取二元組樹塊。